Difference between revisions of "SHA-0"
From The ECRYPT Hash Function Website
(→Collision Attacks) |
Mlamberger (talk | contribs) (→Collision Attacks) |
||
| Line 34: | Line 34: | ||
isbn = {3-540-49475-8}, | isbn = {3-540-49475-8}, | ||
abstract = {At CRYPTO 2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed a collision attack on SHA-0 that could generate a collision with complexity $2^39$ SHA-0 hash operations. Although the method of Wang et al. can find messages that satisfy the sufficient conditions in steps 1 to 20 by using message modification, it makes no mention of the message modifications needed to yield satisfaction of the sufficient conditions in steps 21 and onwards. In this paper, first, we give sufficient conditions for the steps from step 21, and propose submarine modification as the message modification technique that will ensure satisfaction of the sufficient conditions from steps 21 to 24. Submarine modification is an extension of the multi-message modification used in collision attacks on the MD-family. Next, we point out that the sufficient conditions given by Wang et al. are not enough to generate a collision with high probability; we rectify this shortfall by introducing two new sufficient conditions. The combination of our newly found sufficient conditions and submarine modification allows us to generate a collision with complexity $2^36$ SHA-0 hash operations. At the end of this paper, we show the example of a collision generated by applying our proposals.}, | abstract = {At CRYPTO 2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed a collision attack on SHA-0 that could generate a collision with complexity $2^39$ SHA-0 hash operations. Although the method of Wang et al. can find messages that satisfy the sufficient conditions in steps 1 to 20 by using message modification, it makes no mention of the message modifications needed to yield satisfaction of the sufficient conditions in steps 21 and onwards. In this paper, first, we give sufficient conditions for the steps from step 21, and propose submarine modification as the message modification technique that will ensure satisfaction of the sufficient conditions from steps 21 to 24. Submarine modification is an extension of the multi-message modification used in collision attacks on the MD-family. Next, we point out that the sufficient conditions given by Wang et al. are not enough to generate a collision with high probability; we rectify this shortfall by introducing two new sufficient conditions. The combination of our newly found sufficient conditions and submarine modification allows us to generate a collision with complexity $2^36$ SHA-0 hash operations. At the end of this paper, we show the example of a collision generated by applying our proposals.}, | ||
| + | } | ||
| + | </bibtex> | ||
| + | |||
| + | <bibtex> | ||
| + | @inproceedings{eurocryptBihamCJCLJ05, | ||
| + | author = {Eli Biham and Rafi Chen and Antoine Joux and Patrick Carribault and Christophe Lemuet and William Jalby}, | ||
| + | title = {Collisions of SHA-0 and Reduced SHA-1}, | ||
| + | booktitle = {EUROCRYPT}, | ||
| + | year = {2005}, | ||
| + | pages = {36-57}, | ||
| + | abstract = {In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 251. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53–58 rounds can still be found faster than by birthday attacks. Part of the results of this paper were given by the first author in an invited talk in SAC 2004, Waterloo, Canada.}, | ||
| + | editor = {Ronald Cramer}, | ||
| + | volume = {3494}, | ||
| + | series = {LNCS}, | ||
| + | publisher = {Springer}, | ||
| + | isbn = {3-540-25910-4}, | ||
| + | url = {http://dx.doi.org/10.1007/11426639_3}, | ||
} | } | ||
</bibtex> | </bibtex> | ||
Revision as of 12:18, 11 March 2008
Contents
1 Specification
- digest size: 160 bits
- max. message length: < 264 bits
- compression function: 512-bit message block, 160-bit chaining variable
- Specification:
2 Cryptanalysis
2.1 Best Known Results
2.2 Generic Attacks
2.3 Collision Attacks
Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, Noboru Kunihiro, Kazuo Ohta - Improved Collision Search for SHA-0
- ASIACRYPT 4284:21-36,2006
- http://dx.doi.org/10.1007/11935230_2
BibtexAuthor : Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, Noboru Kunihiro, Kazuo Ohta
Title : Improved Collision Search for SHA-0
In : ASIACRYPT -
Address :
Date : 2006
Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, William Jalby - Collisions of SHA-0 and Reduced SHA-1
- EUROCRYPT 3494:36-57,2005
- http://dx.doi.org/10.1007/11426639_3
BibtexAuthor : Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, William Jalby
Title : Collisions of SHA-0 and Reduced SHA-1
In : EUROCRYPT -
Address :
Date : 2005
