Difference between revisions of "SHA-0"

@@ Line 4: / Line 4: @@
 * max. message length: < 2<sup>64</sup> bits
 * compression function: 512-bit message block, 160-bit chaining variable
-* Specification:
+* Specification: FIPS 180 Secure Hash Standard
 == Cryptanalysis ==
@@ Line 19: / Line 19: @@
 === Collision Attacks ===
+<bibtex>
+@inproceedings{fseManuelP08,
+  author    = {St{\'e}phane Manuel and Thomas Peyrin},
+  title     = {Collisions on SHA-0 in One Hour},
+  booktitle = {FSE},
+  year      = {2008},
+  pages     = {16-35},
+  abstract  = {At Crypto 2007, Joux and Peyrin showed that the boomerang attack, a classical tool in block cipher cryptanalysis, can also be very useful when analyzing hash functions. They applied their new theoretical results to SHA and provided new improvements for the cryptanalysis of this algorithm. In this paper, we concentrate on the case of SHA-0. First, we show that the previous perturbation vectors used in all known attacks are not optimal and we provide a new 2-block one. The problem of the possible existence of message modifications for this vector is tackled by the utilization of auxiliary differentials from the boomerang attack, relatively simple to use. Finally, we are able to produce the best collision attack against SHA-0 so far, with a measured complexity of 2^33,6 hash function calls. Finding one collision for SHA-0 takes us approximatively one hour of computation on an average PC.},
+  url        = {http://dx.doi.org/10.1007/978-3-540-71039-4_2},
+  editor    = {Kaisa Nyberg},
+  publisher = {Springer},
+  series    = {LNCS},
+  volume    = {5086},
+  isbn      = {978-3-540-71038-7},
+}
+</bibtex>
 <bibtex>
@@ Line 34: / Line 51: @@
    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.},
+}
+</bibtex>
+<bibtex>
+@inproceedings{cryptoWangYY05,
+  author    = {Xiaoyun Wang and Hongbo Yu and Yiqun Lisa Yin},
+  title     = {Efficient Collision Search Attacks on SHA-0},
+  booktitle = {CRYPTO},
+  year      = {2005},
+  pages     = {1-16},
+  url        = {http://dx.doi.org/10.1007/11535218_1},
+  editor    = {Victor Shoup},
+  publisher = {Springer},
+  series    = {LNCS},
+  volume    = {3621},
+  isbn      = {3-540-28114-2},
+}
+</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>
+@inproceedings{cryptoBihamC04,
+  author    = {Eli Biham and Rafi Chen},
+  title     = {Near-Collisions of SHA-0},
+  booktitle = {CRYPTO},
+  year      = {2004},
+  pages     = {290-305},
+  url        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3152{\&}spage=290},
+  editor    = {Matthew K. Franklin},
+  publisher = {Springer},
+  series    = {LNCS},
+  volume    = {3152},
+  isbn      = {3-540-22668-0},
+  editor    = {Matthew K. Franklin},
+  publisher = {Springer},
+  series    = {LNCS},
+  volume    = {3152},
+  isbn      = {3-540-22668-0},
+}
+</bibtex>
+<bibtex>
+@inproceedings{cryptoChabaudJ98,
+  author    = {Florent Chabaud and Antoine Joux},
+  title     = {Differential Collisions in SHA-0},
+  booktitle = {CRYPTO},
+  year      = {1998},
+  pages     = {56-71},
+  url        = {http://link.springer.de/link/service/series/0558/bibs/1462/14620056.htm},
+  editor    = {Hugo Krawczyk},
+  publisher = {Springer},
+  series    = {LNCS},
+  volume    = {1462},
+  isbn      = {3-540-64892-5},
 }
 </bibtex>
@@ Line 45: / Line 128: @@
 === Preimage Attacks ===
+<bibtex>
+@inproceedings{cryptoCanniereR08,
+  author    = {Christophe De Canni{\`e}re and Christian Rechberger},
+  title     = {Preimages for Reduced SHA-0 and SHA-1},
+  booktitle = {CRYPTO},
+  year      = {2008},
+  pages     = {179-202},
+  abstract  = {In this paper, we examine the resistance of the popular hash function SHA-1 and its predecessor SHA-0 against dedicated preimage attacks. In order to assess the security margin of these hash functions against these attacks, two new cryptanalytic techniques are developed: (1) Reversing the inversion problem: the idea is to start with an impossible expanded message that would lead to the required digest, and then to correct this message until it becomes valid without destroying the preimage property. (2) P^3 graphs: an algorithm based on the theory of random graphs that allows the conversion of preimage attacks on the compression function to attacks on the hash function with less effort than traditional meet-in-the-middle approaches. Combining these techniques, we obtain preimage-style shortcuts attacks for up to 45 steps of SHA-1, and up to 50 steps of SHA-0 (out of 80). },
+  url        = {http://dx.doi.org/10.1007/978-3-540-85174-5_11},
+  editor    = {David Wagner},
+  publisher = {Springer},
+  series    = {LNCS},
+  volume    = {5157},
+  isbn      = {978-3-540-85173-8},
+}
+</bibtex>
 ----
 === Others ===

Difference between revisions of "SHA-0"

Latest revision as of 11:35, 10 November 2008

Contents

1 Specification

2 Cryptanalysis

2.1 Best Known Results

2.2 Generic Attacks

2.3 Collision Attacks

2.4 Second Preimage Attacks

2.5 Preimage Attacks

2.6 Others

Navigation menu

Views

Personal tools

Navigation

Search

Tools