Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Preimage Attacks)
 
(44 intermediate revisions by 7 users not shown)
Line 1: Line 1:
−
== General ==
+
== Specification ==
  
 
* digest size: 160 bits
 
* digest size: 160 bits
 
* max. message length: < 2<sup>64</sup> bits
 
* max. message length: < 2<sup>64</sup> bits
−
* type: iterative hash function
 
 
* compression function: 512-bit message block, 160-bit chaining variable
 
* compression function: 512-bit message block, 160-bit chaining variable
−
* [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf Specification: FIPS 180-2 Secure Hash Standard]
+
* Specification: [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS 180-2 Secure Hash Standard]
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
Line 11: Line 10:
 
=== Best Known Results ===
 
=== Best Known Results ===
  
−
The best collision attack on full SHA-1 was published by Wang etal. It has complexity of 2<sup>69</sup> hash evaluations. The best collision example, a 64-step collision for SHA-1, was publshed by DeCanniere and Rechberger.
+
The best collision attack on full SHA-1 was published by Wang et al. It has complexity of 2<sup>69</sup> hash evaluations. The best collision example, a 70-step collision for SHA-1, was published by DeCanniere, Mendel and Rechberger.
 +
----
  
 
=== Collision Attacks ===
 
=== Collision Attacks ===
  
 
<bibtex>
 
<bibtex>
−
@INPROCEEDINGS{Pramstaller2005ExploitingCodingTheory,
+
@inproceedings{sacryptCanniereMR07,
−
   author = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
+
   author   = {Christophe De Canni{\`e}re and Florian Mendel and Christian Rechberger},
−
   title = {Exploiting Coding Theory for Collision Attacks on SHA-1},
+
   title     = {Collisions for 70-Step SHA-1: On the Full Cost of Collision Search},
−
   booktitle = {Cryptography and Coding 2005},
+
  booktitle = {Selected Areas in Cryptography},
 +
  year      = {2007},
 +
  pages    = {56-73},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-77360-3_4},
 +
  editor    = {Carlisle M. Adams and Ali Miri and Michael J. Wiener},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4876},
 +
  isbn      = {978-3-540-77359-7},
 +
  abstract  = {The diversity of methods for fast collision search in SHA-1 and similar hash functions makes a comparison of them difficult. The literature is at times very vague on this issue, which makes comparison even harder. In situations where differences in estimates of attack complexity of a small factor might influence short-term recommendations of standardization bodies, uncertainties and ambiguities in the literature amounting to a similar order of magnitude are unhelpful. We survey different techniques and propose a simple but effective method to facilitate comparison. In a case study, we consider a newly developed attack on 70-step SHA-1, and give complexity estimates and performance measurements of this new and improved collision search method.},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{fseSugitaKPI07,
 +
  author    = {Makoto Sugita and Mitsuru Kawazoe and Ludovic Perret and Hideki Imai},
 +
  title    = {Algebraic Cryptanalysis of 58-Round SHA-1},
 +
  pages    = {349-365},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-74619-5_22},
 +
  editor    = {Alex Biryukov},
 +
   booktitle = {FSE},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4593},
 +
  year      = {2007},
 +
  isbn      = {978-3-540-74617-1},
 +
  abstract  = {In 2004, a new attack against SHA-1 has been proposed
 +
by a team leaded by Wang [15]. The aim of this article is to sophisticate
 +
and improve Wang’s attack by using algebraic techniques. We introduce
 +
new notions, namely semi-neutral bit and adjuster and propose then an
 +
improved message modification technique based on algebraic techniques.
 +
In the case of the 58-round SHA-1, the experimental complexity of our
 +
improved attack is 2<sup>31</sup> SHA-1 computations, whereas Wang’s method needs
 +
2<sup>34</sup> SHA-1 computations. We have found many new collisions for the 58-round SHA-1.
 +
We also study the complexity of our attack for the full SHA-1.}
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{asiacryptCanniereR06,
 +
  author    = {Christophe De Canni{\`e}re and Christian Rechberger},
 +
  title    = {Finding SHA-1 Characteristics: General Results and Applications},
 +
  pages    = {1-20},
 +
  url        = {http://dx.doi.org/10.1007/11935230_1},
 +
  editor    = {Xuejia Lai and Kefei Chen},
 +
  booktitle = {ASIACRYPT},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4284},
 +
  year      = {2006},
 +
  isbn      = {3-540-49475-8},
 +
  abstract  = {The most efficient collision attacks on members of the SHA family presented so far all use complex characteristics which were manually constructed by Wang et al. In this report, we describe a method to search for characteristics in an automatic way. This is particularly useful for multi-block attacks, and as a proof of concept, we give a two-block collision for 64-step SHA-1 based on a new characteristic. The highest number of steps for which a SHA-1 collision was published so far was 58. We also give a unified view on the expected work factor of a collision search and the needed degrees of freedom for the search, which facilitates optimization.},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{cryptoWangYY05a,
 +
  author    = {Xiaoyun Wang and Yiqun Lisa Yin and Hongbo Yu},
 +
  title    = {Finding Collisions in the Full SHA-1},
 +
  booktitle = {CRYPTO},
 +
  year      = {2005},
 +
  pages    = {17-36},
 +
  url        = {http://dx.doi.org/10.1007/11535218_2},
 +
  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},
 
   year = {2005},
−
   editor = {Nigel P. Smart},
+
  pages = {36-57},
−
   volume = {3796},
+
  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},
 
   series = {LNCS},
−
  pages = {78-95},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
−
   url       = {http://dx.doi.org/10.1007/11586821_7},
+
  isbn = {3-540-25910-4},
−
  abstract  = {In this article we show that coding theory can be exploited efficiently for the cryptanalysis of hash functions. We will mainly focus on SHA-1. We present different linear codes that are used to find low-weight differences that lead to a collision. We extend existing approaches and include recent results in the cryptanalysis of hash functions. With our approach we are able to find differences with very low weight. Based on the weight of these differences we conjecture the complexity for a collision attack on the full SHA-1.}
+
   url = {http://dx.doi.org/10.1007/11426639_3},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@inproceedings{Pramstaller2005ImpactOfRotations,
+
@inproceedings{ctrsaRijmenO05,
−
   author    = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
+
   author    = {Vincent Rijmen and Elisabeth Oswald},
−
   title    = {Impact of Rotations in SHA-1 and Related Hash Functions.},
+
   title    = {Update on SHA-1},
−
   booktitle = {SAC 2005},
+
   booktitle = {CT-RSA},
−
   year      = {2006},
+
   year      = {2005},
−
   pages    = {261-275},
+
   pages    = {58-71},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {3897},
+
   volume    = {3376},
−
  url        = {http://dx.doi.org/10.1007/11693383_18},
+
   abstract  = {We report on the experiments we performed in order to assess the security of SHA-1 against the attack by Chabaud and Joux [5]. We present some ideas for optimizations of the attack and some properties of the message expansion routine. Finally, we show that for a reduced version of SHA-1, with 53 rounds instead of 80, it is possible to find collisions in less than 2^80 operations.},
−
   abstract  = {SHA-1 uses a single set of rotation constants within the compression function. However, most other members of the MD4 family of hash functions use multiple sets of rotation constants, MediaObjects/InlineFigure1.pngthe rotation amounts change with the step being processed. To our knowledge, no design rationales on the choice of rotation constants are given on any of these hash functions. This is the first paper that analyzes rotations in iterated hash functions. We focus on SHA-1-like hash functions and use recent developments in the analysis of these hash functions to evaluate the security implications of using multiple sets of rotation constants in the compression function instead of a single set. Additionally, we give some observations on the set of constants used in SHA-0 and SHA-1.},
+
  url = {http://dx.doi.org/10.1007/b105222}}
−
}
 
 
</bibtex>
 
</bibtex>
 +
----
 +
 +
=== Preimage Attacks ===
  
 
<bibtex>
 
<bibtex>
−
@MISC{Wang2005NewCollisionSearch,
+
@inproceedings{cryptoCanniereR08,
−
   author = {Xiaoyun Wang and Andrew Yao and Frances Yao},
+
   author   = {Christophe De Canni{\`e}re and Christian Rechberger},
−
   title = {New Collision Search for SHA-1},
+
   title     = {Preimages for Reduced SHA-0 and SHA-1},
−
   month = {August},
+
   booktitle = {CRYPTO},
−
   year = {2005},
+
   year     = {2008},
−
   howpublished = {Presented at rump session of CRYPTO 2005},
+
  pages    = {179-202},
−
   note = {Presented at rump session of CRYPTO 2005},
+
   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). },
−
   owner = {npramstaller},
+
  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>
 
</bibtex>
  
 +
----
 +
 +
=== Others ===
 
<bibtex>
 
<bibtex>
−
@MISC{Wang2005CryptanalysisOfSHA1,
+
@inproceedings{cryptoJouxP07,
−
   author = {Xiaoyun Wang and Andrew Yao and Frances Yao},
+
   author   = {Antoine Joux and Thomas Peyrin},
−
   title = {Cryptanalysis of SHA-1},
+
  title    = {Hash Functions and the (Amplified) Boomerang Attack},
−
   howpublished = {Presented at the Cryptographic Hash Workshop hosted by NIST},
+
   booktitle = {CRYPTO},
−
   month = {October},
+
  year      = {2007},
−
   year = {2005},
+
  pages    = {244--263},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-74143-5_14},
 +
  editor    = {Alfred Menezes},
 +
   publisher = {Springer},
 +
  series    = {LNCS},
 +
   volume    = {4622},
 +
   isbn      = {978-3-540-74142-8},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@INPROCEEDINGS{Wang2005FindingCollisionsin,
+
@inproceedings{fseMendelPRR06a,  
−
   author = {Xiaoyun Wang and Yiqun Lisa Yin and Hongbo Yu},
+
   author   = {Florian Mendel and Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
−
   title = {Finding Collisions in the Full SHA-1},
+
   title     = {The Impact of Carries on the Complexity of Collision Attacks on SHA-1},
−
  booktitle = {Advances in Cryptology - CRYPTO 2005},
+
   pages     = {278-292},
−
  year = {2005},
+
   url       = {http://dx.doi.org/10.1007/11799313_18},
−
  editor = {Victor Shoup},
+
  booktitle = {FSE},
−
  volume = {3621},
 
−
  series = {LNCS},
 
−
   pages = {17--36},
 
−
   url   = {http://dx.doi.org/10.1007/11535218_2},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
−
   abstract  = {In this paper, we present new collision search attacks on the hash function SHA-1. We show that collisions of SHA-1 can be found with complexity less than 2<sup>69</sup> hash operations. This is the first attack on the full 80-step SHA-1 with complexity less than the 2<sup>80</sup> theoretical bound.},
+
  series    = {LNCS},
 +
  volume    = {4047},
 +
  year      = {2006},
 +
  isbn      = {3-540-36597-4},
 +
   abstract  = {In this article we present a detailed analysis of
 +
the impact of carries on the estimation of the attack complexity
 +
for SHA-1. We build up on existing estimates and refine them. We
 +
show that the attack complexity is slightly lower than estimated
 +
in all published work to date. We point out that it is more accurate
 +
to consider probabilities instead of conditions.},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@INPROCEEDINGS{Rijmen2005UpdateonSHA-1,
+
@inproceedings{sacryptJutlaP06,
−
   author = {Vincent Rijmen and Elisabeth Oswald},
+
   author   = {Charanjit S. Jutla and Anindya C. Patthak},
−
   title = {Update on SHA-1},
+
   title     = {Provably Good Codes for Hash Function Design},
−
   booktitle = {CT-RSA 2005},
+
   booktitle = {Selected Areas in Cryptography},
−
   year = {2005},
+
   year     = {2006},
−
   editor = {Alfred Menezes},
+
   pages    = {376-393},
−
   volume = {3376},
+
   url        = {http://dx.doi.org/10.1007/978-3-540-74462-7_26},
−
   series = {LNCS},
+
   editor    = {Eli Biham and Amr M. Youssef},
−
  pages = {58--71},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
−
   url      = {http://dx.doi.org/10.1007/b105222},
+
   series    = {LNCS},
−
   abstract  = {We report on the experiments we performed in order to assess the security of SHA-1 against the attack by Chabaud and Joux [5]. We present some ideas for optimizations of the attack and some properties of the message expansion routine. Finally, we show that for a reduced version of SHA-1, with 53 rounds instead of 80, it is possible to find collisions in less than 2<sup>80</sup> operations.},
+
  volume    = {4356},
 +
  isbn      = {978-3-540-74461-0},
 +
   abstract  = {We develop a new technique to lower bound the minimum distance of quasi-cyclic codes with large dimension by reducing the problem to lower bounding the minimum distance of a few significantly smaller dimensional codes. Using this technique, we prove that a code which is similar to the SHA-1 message expansion code has minimum distance at least 82, and that too in just the last 64 of the 80 expanded words. Further the minimum weight in the last 60 words (last 48 words) is at least 75 (52 respectively). We expect our technique to be helpful in designing future practical collision-resistant hash functions. We also use the technique to find the minimum weight of the SHA-1 code (25 in the last 60 words), which was an open problem.},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@INPROCEEDINGS{Biham2005CollisionsofSHA-0,
+
@inproceedings{sacryptPramstallerRR05a,
−
   author = {Eli Biham and Rafi Chen and Antoine hirose and Patrick Carribault and Christophe Lemuet and William Jalby},
+
   author   = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
−
   title = {Collisions of SHA-0 and Reduced SHA-1},
+
   title     = {Impact of Rotations in SHA-1 and Related Hash Functions},
−
   booktitle = {Advances in Cryptology - EUROCRYPT 2005},
+
   booktitle = {Selected Areas in Cryptography},
−
   year = {2005},
+
   year     = {2005},
−
   editor = {Ronald Cramer},
+
   pages    = {261-275},
−
   volume = {3494},
+
   url        = {http://dx.doi.org/10.1007/11693383_18},
−
   series = {LNCS},
+
   editor    = {Bart Preneel and Stafford E. Tavares},
−
  pages = {36--57},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
−
   url      = {http://dx.doi.org/10.1007/11426639_3},
+
   series    = {LNCS},
−
   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 2<sup>51</sup>. 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.},
+
   volume   = {3897},
 +
  isbn      = {3-540-33108-5},
 +
  abstract  = {SHA-1 uses a single set of rotation constants within the compression function. However, most other members of the MD4 family of hash functions use multiple sets of rotation constants, i.e. the rotation amounts change with the step being processed. To our knowledge, no design rationales on the choice of rotation constants are given on any of these hash functions. This is the first paper that analyzes rotations in iterated hash functions. We focus on SHA-1-like hash functions and use recent developments in the analysis of these hash functions to evaluate the security implications of using multiple sets of rotation constants in the compression function instead of a single set. Additionally, we give some observations on the set of constants used in SHA-0 and SHA-1.},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@inproceedings{Satoh2005HardwareArchitectureAnd,
+
@inproceedings{iswSatoh05,
 
   author    = {Akashi Satoh},
 
   author    = {Akashi Satoh},
−
   title    = {Hardware Architecture and Cost Estimates for Breaking SHA-1.},
+
   title    = {Hardware Architecture and Cost Estimates for Breaking SHA-1},
−
   booktitle = {ISC 2005},
+
   booktitle = {ISC},
 
   year      = {2005},
 
   year      = {2005},
 
   pages    = {259-273},
 
   pages    = {259-273},
 +
  url        = {http://dx.doi.org/10.1007/11556992_19},
 +
  editor    = {Jianying Zhou and Javier Lopez and Robert H. Deng and Feng Bao},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
 
   volume    = {3650},
 
   volume    = {3650},
−
   url      = {http://dx.doi.org/10.1007/11556992_19},
+
   isbn      = {3-540-29001-X},
−
   abstract  = {The cryptanalysis of hash functions has advanced rapidly, and many hash functions have been broken one after another. The most popular hash function SHA-1 has not been broken yet, but the new collision search techniques proposed by Wang et al. reduced the computational complexity down to 2<sup>69</sup>, which is only 1/2,000 of the 2<sup>80</sup> operations needed for a birthday attack. The complexity is still too large even for today’s supercomputers, but no feasibility study of breaking SHA-1 using specialized hardware has been reported. The well known brute force attack on DES simply repeats the DES operation 2<sup>56</sup> times at a maximum, but the complexity of 2<sup>69</sup> hash operations to break SHA-1 does not mean 2<sup>69</sup> SHA-1 operations. Complex procedures using SHA-1 functions are required, and the total number of operations based on the probability of a collision occurrence is almost equivalent to the 2<sup>69</sup> SHA-1 operations. Therefore, we describe a procedure and propose an LSI architecture to find real collisions for SHA-1 in this paper. The hardware core was synthesized by using a 0.13-µm CMOS standard cell library, and its performances in speed, size, and power consumption were evaluated. A $10 million budget can build a custom hardware system that would consist of 303 personal computers with 16 circuit boards each, in which 32 SHA-1-breaking LSIs are mounted. Each LSI has 64 SHA-1 cores that can run in parallel. This system would find a real collision in 127 days.}
+
   abstract  = {The cryptanalysis of hash functions has advanced rapidly, and many hash functions have been broken one after another. The most popular hash function SHA-1 has not been broken yet, but the new collision search techniques proposed by Wang et al. reduced the computational complexity down to $2^{69}$, which is only 1/2,000 of the $2^{80}$ operations needed for a birthday attack. The complexity is still too large even for today's supercomputers, but no feasibility study of breaking SHA-1 using specialized hardware has been reported. The well known brute force attack on DES simply repeats the DES operation $2^{56}$ times at a maximum, but the complexity of $2^{69}$ hash operations to break SHA-1 does not mean $2^{69}$ SHA-1 operations. Complex procedures using SHA-1 functions are required, and the total number of operations based on the probability of a collision occurrence is almost equivalent to the $2^{69}$ SHA-1 operations. Therefore, we describe a procedure and propose an LSI architecture to find real collisions for SHA-1 in this paper. The hardware core was synthesized by using a 0.13-$\micro m$ CMOS standard cell library, and its performances in speed, size, and power consumption were evaluated. A \$10 million budget can build a custom hardware system that would consist of 303 personal computers with 16 circuit boards each, in which 32 SHA-1-breaking LSIs are mounted. Each LSI has 64 SHA-1 cores that can run in parallel. This system would find a real collision in 127 days.},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
−
=== Second Preimage Attacks ===
 
−
* There exists a generic attack (works for all iterated hash functions). See ....
 
−
----
 
−
 
−
=== Preimage Attacks ===
 
−
* We are not aware of any article regarding preimage attacks on SHA-1.
 
−
----
 
  
−
=== Others ===
 
−
everything that does not fit into coll/(2nd)preimage and implementation
 
 
----
 
----
−
 
−
== Performance Evaluation / Implementation (HW and SW) ==
 
−
 
−
<bibtex>
 
−
@inproceedings{DBLP:conf/asap/LeeCV06,
 
−
  author    = {Yong Ki Lee and Herwin Chan and Ingrid Verbauwhede},
 
−
  title    = {Throughput Optimized SHA-1 Architecture Using Unfolding Transformation.},
 
−
  booktitle = {ASAP 2006},
 
−
  year      = {2006},
 
−
  pages    = {354-359},
 
−
  url      = {http://doi.ieeecomputersociety.org/10.1109/ASAP.2006.68},
 
−
  series    = {IEEE Computer Society},
 
−
  year      = {2006},
 
−
  isbn      = {0-7695-2682-9},
 
−
  abstract  = {In this paper, we analyze the theoretical delay bound of the SHA-1 algorithm and propose architectures to achieve high throughput hardware implementations which approach this bound. According to the results of FPGA implementations, 3,541 Mbps with a pipeline and 893 Mbps without a pipeline were achieved. Moreover, synthesis results using 0.18..m CMOS technology showed that 10.4 Gbps with a pipeline and 3.1 Gbps without a pipeline can be achieved. These results are much faster than previously published results. The high throughputs are due to the unfolding transformation, which reduces the number of required cycles for one block hash. We reduced the required number of cycles to 12 cycles for a 512 bit block and showed that 12 cycles is the optimal in our design.}
 
−
}
 
−
</bibtex>
 
−
 
−
== eHash Recommendation (optional) or eHash Opinion ==
 
−
Something like: SHA-1 is considered to be broken. Please do not incorporate SHA-1 in new application any longer. Try to migrate to another hash function.
 

Latest revision as of 11:34, 10 November 2008

1 Specification

  • digest size: 160 bits
  • max. message length: < 264 bits
  • compression function: 512-bit message block, 160-bit chaining variable
  • Specification: FIPS 180-2 Secure Hash Standard

2 Cryptanalysis

2.1 Best Known Results

The best collision attack on full SHA-1 was published by Wang et al. It has complexity of 269 hash evaluations. The best collision example, a 70-step collision for SHA-1, was published by DeCanniere, Mendel and Rechberger.

2.2 Collision Attacks

Christophe De Canni\`ere, Florian Mendel, Christian Rechberger - Collisions for 70-Step SHA-1: On the Full Cost of Collision Search

Selected Areas in Cryptography 4876:56-73,2007
http://dx.doi.org/10.1007/978-3-540-77360-3_4
Bibtex
Author : Christophe De Canni\`ere, Florian Mendel, Christian Rechberger
Title : Collisions for 70-Step SHA-1: On the Full Cost of Collision Search
In : Selected Areas in Cryptography -
Address :
Date : 2007

Makoto Sugita, Mitsuru Kawazoe, Ludovic Perret, Hideki Imai - Algebraic Cryptanalysis of 58-Round SHA-1

FSE 4593:349-365,2007
http://dx.doi.org/10.1007/978-3-540-74619-5_22
Bibtex
Author : Makoto Sugita, Mitsuru Kawazoe, Ludovic Perret, Hideki Imai
Title : Algebraic Cryptanalysis of 58-Round SHA-1
In : FSE -
Address :
Date : 2007

Christophe De Canni\`ere, Christian Rechberger - Finding SHA-1 Characteristics: General Results and Applications

ASIACRYPT 4284:1-20,2006
http://dx.doi.org/10.1007/11935230_1
Bibtex
Author : Christophe De Canni\`ere, Christian Rechberger
Title : Finding SHA-1 Characteristics: General Results and Applications
In : ASIACRYPT -
Address :
Date : 2006

Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu - Finding Collisions in the Full SHA-1

CRYPTO 3621:17-36,2005
http://dx.doi.org/10.1007/11535218_2
Bibtex
Author : Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu
Title : Finding Collisions in the Full SHA-1
In : CRYPTO -
Address :
Date : 2005

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
Bibtex
Author : 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

Vincent Rijmen, Elisabeth Oswald - Update on SHA-1

CT-RSA 3376:58-71,2005
http://dx.doi.org/10.1007/b105222
Bibtex
Author : Vincent Rijmen, Elisabeth Oswald
Title : Update on SHA-1
In : CT-RSA -
Address :
Date : 2005

2.3 Preimage Attacks

Christophe De Canni\`ere, Christian Rechberger - Preimages for Reduced SHA-0 and SHA-1

CRYPTO 5157:179-202,2008
http://dx.doi.org/10.1007/978-3-540-85174-5_11
Bibtex
Author : Christophe De Canni\`ere, Christian Rechberger
Title : Preimages for Reduced SHA-0 and SHA-1
In : CRYPTO -
Address :
Date : 2008

2.4 Others

Antoine Joux, Thomas Peyrin - Hash Functions and the (Amplified) Boomerang Attack

CRYPTO 4622:244--263,2007
http://dx.doi.org/10.1007/978-3-540-74143-5_14
Bibtex
Author : Antoine Joux, Thomas Peyrin
Title : Hash Functions and the (Amplified) Boomerang Attack
In : CRYPTO -
Address :
Date : 2007

Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - The Impact of Carries on the Complexity of Collision Attacks on SHA-1

FSE 4047:278-292,2006
http://dx.doi.org/10.1007/11799313_18
Bibtex
Author : Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : The Impact of Carries on the Complexity of Collision Attacks on SHA-1
In : FSE -
Address :
Date : 2006

Charanjit S. Jutla, Anindya C. Patthak - Provably Good Codes for Hash Function Design

Selected Areas in Cryptography 4356:376-393,2006
http://dx.doi.org/10.1007/978-3-540-74462-7_26
Bibtex
Author : Charanjit S. Jutla, Anindya C. Patthak
Title : Provably Good Codes for Hash Function Design
In : Selected Areas in Cryptography -
Address :
Date : 2006

Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - Impact of Rotations in SHA-1 and Related Hash Functions

Selected Areas in Cryptography 3897:261-275,2005
http://dx.doi.org/10.1007/11693383_18
Bibtex
Author : Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : Impact of Rotations in SHA-1 and Related Hash Functions
In : Selected Areas in Cryptography -
Address :
Date : 2005

Akashi Satoh - Hardware Architecture and Cost Estimates for Breaking SHA-1

ISC 3650:259-273,2005
http://dx.doi.org/10.1007/11556992_19
Bibtex
Author : Akashi Satoh
Title : Hardware Architecture and Cost Estimates for Breaking SHA-1
In : ISC -
Address :
Date : 2005


Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=SHA-1&oldid=2249"