Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Preimage Attacks)
 
(29 intermediate revisions by 6 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>
 
−
@misc{cryptoeprint:2006:098,
 
−
    author = {Makoto Sugita, Mitsuru Kawazoe, Hideki Imai},
 
−
    title = {Gr\"obner Basis Based Cryptanalysis of SHA-1},
 
−
    howpublished = {Cryptology ePrint Archive, Report 2006/098},
 
−
    year = {2006},
 
−
    url = {http://eprint.iacr.org/2006/098},
 
−
    abstract = {Recently, Wang proposed a new method to cryptanalyze SHA-1 and found collisions of $58$-round SHA-1. However many details of Wang's attack are still unpublished, especially, 1) How to find differential paths? 2) How to modify messages properly? For the first issue, some results have already been reported. In our article, we clarify the second issue and give a sophisticated method based on Gr\"obner basis techniques. We propose two algorithm based on the basic and an improved message modification techniques respectively. The complexity of our algorithm to find a collision for 58-round SHA-1 based on the basic message modification is $2^{29}$ message modifications and its implementation is equivalent to $2^{31}$ SHA-1 computation experimentally, whereas Wang's method needs $2^{34}$ SHA-1 computation. We propose an improved message modification and apply it to construct a more sophisticated algorithm to find a collision. The complexity to find a collision for 58-round SHA-1 based on this improved message modification technique is $2^8$ message modifications, but our latest implementation is very slow, equivalent to $2^{31}$ SHA-1 computation experimentally. However we conjecture that our algorithm can be improved by techniques of error correcting code and Gr\"obner basis. By using our methods, we have found many collisions for $58$-round SHA-1.},
 
−
}
 
−
</bibtex>
 
  
 
<bibtex>
 
<bibtex>
−
@misc{cryptoeprint:2005:350,
+
@inproceedings{sacryptCanniereMR07,
−
    author = {Charanjit S. Jutla  and Anindya C. Patthak},
+
  author   = {Christophe De Canni{\`e}re and Florian Mendel and Christian Rechberger},
−
    title = {Is SHA-1 conceptually sound?},
+
   title    = {Collisions for 70-Step SHA-1: On the Full Cost of Collision Search},
−
    howpublished = {Cryptology ePrint Archive, Report 2005/350},
+
   booktitle = {Selected Areas in Cryptography},
−
    year = {2005},
+
   year      = {2007},
−
    url = {http://eprint.iacr.org/2005/350},
+
   pages    = {56-73},
−
    abstract= {We argue that if the message expansion code of SHA-1 is replaced by a linear code with a better minimum distance, then the resulting hash function is collision resistant. To support this argument, we characterize the disturbance vectors which are used to build local collision attacks as a linear code. This linear code is the xor-sum of two codes, the message expansion code and a linear code representing the underlying block cipher in SHA-1. We also show that the following constraint satisfaction problem is $\np$-hard. The constraints are restricted to being XOR constraints, or Majority constraints on at most three variables each. The instances are further restricted by requiring that the constraints can be listed in a sequence C_1, C_2,...,C_m, such that for every constraint C_i, two of the variables in it occur only in constraints C_j, with |j-i|< 48. This problem is similar to the problem modeling the one-way function property of SHA-1. },
+
   url        = {http://dx.doi.org/10.1007/978-3-540-77360-3_4},
−
}
+
  editor    = {Carlisle M. Adams and Ali Miri and Michael J. Wiener},
−
</bibtex>
 
−
 
 
−
 
 
−
 
 
−
<bibtex>
 
−
@inproceedings{Yin2006Collision-ResistantUsageOf,
 
−
  author    = {Michael Szydlo and Yiqun Lisa Yin},
 
−
   title    = {Collision-Resistant Usage of MD5 and SHA-1 Via Message Preprocessing.},
 
−
   booktitle = {CT-RSA 2006},
 
−
   year      = {2006},
 
−
   pages    = {99-114},
 
−
   url        = {http://dx.doi.org/10.1007/11605805_7},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {3860},
+
   volume    = {4876},
−
   abstract = {A series of recent papers have demonstrated collision attacks on popularly used hash functions, including the widely deployed MD5 and SHA-1 algorithm. To assess this threat, the natural response has been to evaluate the extent to which various protocols actually depend on collision resistance for their security, and potentially schedule an upgrade to a stronger hash function. Other options involve altering the protocol in some way. This work suggests a different option. We present several simple message pre-processing techniques and show how the techniques can be combined with MD5 or SHA-1 so that applications are no longer vulnerable to the known collision attacks. For some applications, this may a viable alternative to upgrading the hash function.}
+
  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>
−
 
 
<bibtex>
 
<bibtex>
−
@INPROCEEDINGS{Pramstaller2005ExploitingCodingTheory,
+
@inproceedings{fseSugitaKPI07,  
−
   author = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
+
   author   = {Makoto Sugita and Mitsuru Kawazoe and Ludovic Perret and Hideki Imai},
−
   title = {Exploiting Coding Theory for Collision Attacks on SHA-1},
+
   title     = {Algebraic Cryptanalysis of 58-Round SHA-1},
−
   booktitle = {Cryptography and Coding 2005},
+
   pages    = {349-365},
−
   year = {2005},
+
   url        = {http://dx.doi.org/10.1007/978-3-540-74619-5_22},
−
   editor = {Nigel P. Smart},
+
   editor   = {Alex Biryukov},
−
   volume = {3796},
+
   booktitle = {FSE},
−
  series = {LNCS},
 
−
  pages = {78-95},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
−
   url      = {http://dx.doi.org/10.1007/11586821_7},
+
   series    = {LNCS},
−
   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.}
+
  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>
−
 
 
<bibtex>
 
<bibtex>
−
@inproceedings{Pramstaller2005ImpactOfRotations,
+
@inproceedings{asiacryptCanniereR06,
−
   author    = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
+
   author    = {Christophe De Canni{\`e}re and Christian Rechberger},
−
   title    = {Impact of Rotations in SHA-1 and Related Hash Functions.},
+
   title    = {Finding SHA-1 Characteristics: General Results and Applications},
−
   booktitle = {SAC 2005},
+
  pages    = {1-20},
−
   year      = {2006},
+
   url        = {http://dx.doi.org/10.1007/11935230_1},
−
   pages    = {261-275},
+
   editor    = {Xuejia Lai and Kefei Chen},
 +
   booktitle = {ASIACRYPT},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {3897},
+
   volume    = {4284},
−
   url        = {http://dx.doi.org/10.1007/11693383_18},
+
   year      = {2006},
−
   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.},
+
  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>
−
 
 
<bibtex>
 
<bibtex>
−
@MISC{Wang2005NewCollisionSearch,
+
@inproceedings{cryptoWangYY05a,
−
  author = {Xiaoyun Wang and Andrew Yao and Frances Yao},
+
   author   = {Xiaoyun Wang and Yiqun Lisa Yin and Hongbo Yu},
−
  title = {New Collision Search for SHA-1},
+
   title     = {Finding Collisions in the Full SHA-1},
−
  month = {August},
+
   booktitle = {CRYPTO},
−
  year = {2005},
+
   year     = {2005},
−
  howpublished = {Presented at rump session of CRYPTO 2005},
+
   pages     = {17-36},
−
  note = {Presented at rump session of CRYPTO 2005},
+
   url       = {http://dx.doi.org/10.1007/11535218_2},
−
  owner = {npramstaller},
+
  editor    = {Victor Shoup},
−
}
 
−
</bibtex>
 
−
 
 
−
<bibtex>
 
−
@MISC{Wang2005CryptanalysisOfSHA1,
 
−
  author = {Xiaoyun Wang and Andrew Yao and Frances Yao},
 
−
  title = {Cryptanalysis of SHA-1},
 
−
  howpublished = {Presented at the Cryptographic Hash Workshop hosted by NIST},
 
−
  month = {October},
 
−
  year = {2005},
 
−
}
 
−
</bibtex>
 
−
 
 
−
<bibtex>
 
−
@INPROCEEDINGS{Wang2005FindingCollisionsin,
 
−
   author = {Xiaoyun Wang and Yiqun Lisa Yin and Hongbo Yu},
 
−
   title = {Finding Collisions in the Full SHA-1},
 
−
   booktitle = {Advances in Cryptology - CRYPTO 2005},
 
−
   year = {2005},
 
−
  editor = {Victor Shoup},
 
−
  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    = {3621},
 +
  isbn      = {3-540-28114-2},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@INPROCEEDINGS{Rijmen2005UpdateonSHA-1,
+
@inproceedings{eurocryptBihamCJCLJ05,
−
  author = {Vincent Rijmen and Elisabeth Oswald},
+
   author = {Eli Biham and Rafi Chen and Antoine Joux and Patrick Carribault and Christophe Lemuet and William Jalby},
−
  title = {Update on SHA-1},
 
−
  booktitle = {CT-RSA 2005},
 
−
  year = {2005},
 
−
  editor = {Alfred Menezes},
 
−
  volume = {3376},
 
−
  series = {LNCS},
 
−
  pages = {58-71},
 
−
  publisher = {Springer},
 
−
  url      = {http://dx.doi.org/10.1007/b105222},
 
−
  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.},
 
−
}
 
−
</bibtex>
 
−
 
 
−
<bibtex>
 
−
@INPROCEEDINGS{Biham2005CollisionsofSHA-0,
 
−
   author = {Eli Biham and Rafi Chen and Antoine hirose and Patrick Carribault and Christophe Lemuet and William Jalby},
 
 
   title = {Collisions of SHA-0 and Reduced SHA-1},
 
   title = {Collisions of SHA-0 and Reduced SHA-1},
−
   booktitle = {Advances in Cryptology - EUROCRYPT 2005},
+
   booktitle = {EUROCRYPT},
 
   year = {2005},
 
   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},
 
   editor = {Ronald Cramer},
 
   volume = {3494},
 
   volume = {3494},
 
   series = {LNCS},
 
   series = {LNCS},
−
  pages = {36-57},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
−
   url       = {http://dx.doi.org/10.1007/11426639_3},
+
  isbn = {3-540-25910-4},
−
  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.},
+
   url = {http://dx.doi.org/10.1007/11426639_3},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@inproceedings{Satoh2005HardwareArchitectureAnd,
+
@inproceedings{ctrsaRijmenO05,
−
   author    = {Akashi Satoh},
+
   author    = {Vincent Rijmen and Elisabeth Oswald},
−
   title    = {Hardware Architecture and Cost Estimates for Breaking SHA-1.},
+
   title    = {Update on SHA-1},
−
   booktitle = {ISC 2005},
+
   booktitle = {CT-RSA},
 
   year      = {2005},
 
   year      = {2005},
−
   pages    = {259-273},
+
   pages    = {58-71},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {3650},
+
   volume    = {3376},
−
  url      = {http://dx.doi.org/10.1007/11556992_19},
+
   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  = {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.}
+
  url = {http://dx.doi.org/10.1007/b105222}}
−
}
 
 
</bibtex>
 
</bibtex>
−
 
 
----
 
----
  
−
=== Second Preimage Attacks ===
+
=== Preimage Attacks ===
  
 
<bibtex>
 
<bibtex>
−
@inproceedings{Kelsey2005SecondPreimageOn,
+
@inproceedings{cryptoCanniereR08,
−
   author    = {John Kelsey and Bruce Schneier},
+
   author    = {Christophe De Canni{\`e}re and Christian Rechberger},
−
   title    = {Second Preimages on n-Bit Hash Functions for Much Less than $2^n$ Work.},
+
   title    = {Preimages for Reduced SHA-0 and SHA-1},
−
   booktitle = {EUROCRYPT},
+
   booktitle = {CRYPTO},
−
   year      = {2005},
+
   year      = {2008},
−
   pages    = {474-490},
+
   pages    = {179-202},
−
   url       = {http://dx.doi.org/10.1007/11426639_28},
+
  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},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {3494},
+
   volume    = {5157},
−
   abstract  = {We expand a previous result of Dean [Dea99] to provide a second preimage attack on all n-bit iterated hash functions with Damgård-Merkle strengthening and n-bit intermediate states, allowing a second preimage to be found for a 2<sup>k</sup>-message-block message with about k × 2<sup>n/2+1</sup> + 2<sup>n - k + 1</sup> work. Using RIPEMD-160 as an example, our attack can find a second preimage for a 2<sup>60</sup> byte message in about 2<sup>106</sup> work, rather than the previously expected 2<sup>160</sup> work. We also provide slightly cheaper ways to find multicollisions than the method of Joux [Jou04]. Both of these results are based on expandable messages-patterns for producing messages of varying length, which all collide on the intermediate hash result immediately after processing the message. We provide an algorithm for finding expandable messages for any n-bit hash function built using the Damgård-Merkle construction, which requires only a small multiple of the work done to find a single collision in the hash function.},
+
   isbn      = {978-3-540-85173-8},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
−
'''Note:''' This artcle shows that second preimages can be found in much less than 2<sup>n</sup> work. This approach works for all iterated hash functions. Nevertheless, this attack is not practical since a huge amount of data is required.
 
−
----
 
−
 
−
=== Preimage Attacks ===
 
−
* We are not aware of any articles w.r.t. preimage attacks on SHA-1.
 
 
----
 
----
  
 
=== Others ===
 
=== Others ===
−
 
 
<bibtex>
 
<bibtex>
−
@inproceedings{Saarinen2003CryptanalysisOfBlock,
+
@inproceedings{cryptoJouxP07,
−
   author    = {Markku-Juhani Olavi Saarinen},
+
   author    = {Antoine Joux and Thomas Peyrin},
−
   title    = {Cryptanalysis of Block Ciphers Based on SHA-1 and MD5.},
+
   title    = {Hash Functions and the (Amplified) Boomerang Attack},
−
   booktitle = {FSE 2003},
+
   booktitle = {CRYPTO},
−
   year      = {2003},
+
   year      = {2007},
−
   pages    = {36-44},
+
   pages    = {244--263},
−
   url        = {http://springerlink.metapress.com/content/xu0qg98tg38gl7nf/?p=2664f1c23d3f433f9d3fd6a9a1350eda&pi=3},
+
   url        = {http://dx.doi.org/10.1007/978-3-540-74143-5_14},
 +
  editor    = {Alfred Menezes},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {2887},
+
   volume    = {4622},
−
   abstract  = {We cryptanalyse some block cipher proposals that are based on dedicated hash functions SHA-1 and MD5. We discuss a related-key attack against SHACAL-1 and present a method for finding rdquoslid pairsrdquo for it. We also present simple attacks against MDC-MD5 and the Kaliski-Robshaw block cipher.},
+
   isbn      = {978-3-540-74142-8},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@inproceedings{Handschuh2001AnalysisOfSHA-1,
+
@inproceedings{fseMendelPRR06a,  
−
   author    = {Helena Handschuh and Lars R. Knudsen and Matthew J. B. Robshaw},
+
   author    = {Florian Mendel and Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
−
   title    = {Analysis of SHA-1 in Encryption Mode.},
+
   title    = {The Impact of Carries on the Complexity of Collision Attacks on SHA-1},
−
  booktitle = {CT-RSA 2001},
+
   pages    = {278-292},
−
  year      = {2001},
+
   url        = {http://dx.doi.org/10.1007/11799313_18},
−
   pages    = {70-83},
+
  booktitle = {FSE},
−
   url        = {http://link.springer.de/link/service/series/0558/bibs/2020/20200070.htm},
 
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {2020},
+
   volume    = {4047},
−
  abstract  = {This paper analyses the cryptographic hash function SHA-1 in encryption mode. A detailed analysis is given of the resistance of SHA-1 against the most powerful known attacks today. It is concluded that none of these attacks can be applied successfully in practice to SHA-1. Breaking SHA-1 in encryption mode requires either an unrealistic amount of computation time and known/chosen texts, or a major breakthrough in cryptanalysis. The original motivation for this analysis is to investigate a block cipher named SHACAL based on these principles. SHACAL has been submitted to the NESSIE call for cryptographic primitives.},
 
−
}
 
−
</bibtex>
 
−
----
 
−
 
 
−
== Performance Evaluation / Implementation (HW and SW) ==
 
−
 
 
−
<bibtex>
 
−
@inproceedings{Lee2006,
 
−
  author    = {Yong Ki Lee and Herwin Chan and Ingrid Verbauwhede},
 
−
  title    = {Throughput Optimized SHA-1 Architecture Using Unfolding Transformation.},
 
−
  booktitle = {ASAP 2006},
 
 
   year      = {2006},
 
   year      = {2006},
−
   pages    = {354-359},
+
   isbn      = {3-540-36597-4},
−
  url      = {http://doi.ieeecomputersociety.org/10.1109/ASAP.2006.68},
+
   abstract  = {In this article we present a detailed analysis of
−
  publisher = {IEEE Computer Society},
+
the impact of carries on the estimation of the attack complexity
−
  year      = {2006},
+
for SHA-1. We build up on existing estimates and refine them. We
−
   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.},
+
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{Chaves2006,
+
@inproceedings{sacryptJutlaP06,
−
   author    = {Ricardo Chaves and Georgi Kuzmanov and Leonel Sousa and Stamatis Vassiliadis},
+
   author    = {Charanjit S. Jutla and Anindya C. Patthak},
−
   title    = {Rescheduling for Optimized SHA-1 Calculation.},
+
   title    = {Provably Good Codes for Hash Function Design},
−
   booktitle = {SAMOS 2006},
+
   booktitle = {Selected Areas in Cryptography},
 
   year      = {2006},
 
   year      = {2006},
−
   pages    = {425-434},
+
   pages    = {376-393},
−
   url       = {http://dx.doi.org/10.1007/11796435_43},
+
   url       = {http://dx.doi.org/10.1007/978-3-540-74462-7_26},
 +
  editor    = {Eli Biham and Amr M. Youssef},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {4017},
+
   volume    = {4356},
−
   abstract  = {This paper proposes the rescheduling of the SHA-1 hash function operations on hardware implementations. The proposal is mapped on the Xilinx Virtex II Pro technology. The proposed rescheduling allows for a manipulation of the critical path in the SHA-1 function computation, facilitating the implementation of a more parallelized structure without an increase on the required hardware resources. Two cores have been developed, one that uses a constant initialization vector and a second one that allows for different Initialization Vectors (IV), in order to be used in HMAC and in the processing of fragmented messages. A hybrid software/hardware implementation is also proposed. Experimental results indicate a throughput of 1.4 Gbits/s requiring only 533 slices for a constant IV and 596 for an imputable IV. Comparisons to SHA-1 related art suggest improvements of the throughput/slice metric of 29% against the most recent commercial cores and 59% to the current academia proposals.},
+
  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{Michail2005OptimizingSHA-1Hash,
+
@inproceedings{sacryptPramstallerRR05a,
−
   author    = {H. E. Michail and A. P. Kakarountas and George N. Selimis and Costas E. Goutis},
+
   author    = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
−
   title    = {Optimizing SHA-1 Hash Function for High Throughput with a Partial Unrolling Study.},
+
   title    = {Impact of Rotations in SHA-1 and Related Hash Functions},
−
   booktitle = {PATMOS 2005},
+
   booktitle = {Selected Areas in Cryptography},
 
   year      = {2005},
 
   year      = {2005},
−
   pages    = {591-600},
+
   pages    = {261-275},
−
   url       = {http://dx.doi.org/10.1007/11556930_60},
+
   url       = {http://dx.doi.org/10.1007/11693383_18},
 +
  editor    = {Bart Preneel and Stafford E. Tavares},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {3728},
+
   volume    = {3897},
−
   abstract = {Hash functions are widely used in applications that call for data integrity and signature authentication at electronic transactions. A hash function is utilized in the security layer of every communication protocol. As time passes more sophisticated applications arise that address to more users-clients and thus demand for higher throughput. Furthermore, due to the tendency of the market to minimize devices’ size and increase their autonomy to make them portable, power issues have also to be considered. The existing SHA-1 Hash Function implementations (SHA-1 is common in many protocols e.g. IPSec) limit throughput to a maximum of 2 Gbps. In this paper, a new implementation comes to exceed this limit improving the throughput by 53%. Furthermore,power dissipation is kept low compared to previous works, in such way that the proposed implementation can be characterized as low-power.},
+
  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{Toma2005FormalVerificationOf,
+
@inproceedings{iswSatoh05,
−
   author    = {Diana Toma and Dominique Borrione},
+
   author    = {Akashi Satoh},
−
   title    = {Formal Verification of a SHA-1 Circuit Core Using ACL2.},
+
   title    = {Hardware Architecture and Cost Estimates for Breaking SHA-1},
−
   booktitle = {TPHOLs 2005},
+
   booktitle = {ISC},
 
   year      = {2005},
 
   year      = {2005},
−
   pages    = {326-341},
+
   pages    = {259-273},
−
   url       = {http://dx.doi.org/10.1007/11541868_21},
+
   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    = {3603},
+
   volume    = {3650},
−
   abstract ={Our study was part of a project aiming at the design and verification of a circuit for secure communications between a computer and a terminal smart card reader. A SHA-1 component is included in the circuit. SHA-1 is a cryptographic primive that produces, for any message, a 160 bit message digest. We formalize the standard specification in ACL2, then automatically produce the ACL2 model for the VHDL RTL design; finally, we prove the implementation compliant with the specification. We apply a stepwise approach that proves theorems about each computation step of the RTL design, using intermediate digest functions.},
+
  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^{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>
  
−
<bibtex>
 
−
@inproceedings{Jarvinen2005ACompactMD5,
 
−
  author    = {Kimmo U. J{\"a}rvinen and Matti Tommiska and Jorma Skytt{\"a}},
 
−
  title    = {A Compact MD5 and SHA-1 Co-Implementation Utilizing Algorithm Similarities.},
 
−
  booktitle = {ERSA},
 
−
  year      = {2005},
 
−
  pages    = {48-54},
 
−
  publisher = {CSREA Press},
 
−
  year      = {2005},
 
−
}
 
−
</bibtex>
 
  
−
<bibtex>
+
----
−
@inproceedings{Lien2004A1Gbit/s,
 
−
  author    = {Roar Lien and Tim Grembowski and Kris Gaj},
 
−
  title    = {A 1 Gbit/s Partially Unrolled Architecture of Hash Functions SHA-1 and SHA-512.},
 
−
  booktitle = {CT-RSA},
 
−
  year      = {2004},
 
−
  pages    = {324-338},
 
−
  url      = {http://dx.doi.org/10.1007/b95630},
 
−
  publisher = {Springer},
 
−
  series    = {LNCS},
 
−
  volume    = {2964},
 
−
  abstract  = {Hash functions are among the most widespread cryptographic primitives, and are currently used in multiple cryptographic schemes and security protocols, such as IPSec and SSL. In this paper, we investigate a new hardware architecture for a family of dedicated hash functions, including American standards SHA-1 and SHA-512. Our architecture is based on unrolling several message digest steps and executing them in one clock cycle. This modification permits implementing majority of dedicated hash functions with the throughput exceeding 1 Gbit/s using medium-size Xilinx Virtex FPGAs. In particular, our new architecture has enabled us to speed up the implementation of SHA-1 compared to the basic iterative architecture from 544 Mbit/s to 1 Gbit/s using Xilinx XCV1000. The implementation of SHA-512 has been sped up from 717 to 929 Mbit/s for Virtex FPGAs, and exceeded 1 Gbit/s for Virtex-E Xilinx FPGAs.},
 
−
}
 
−
</bibtex>
 
−
 
 
−
<bibtex>
 
−
@inproceedings{Wang2004AnHMACProcessor,
 
−
  author    = {Mao-Yin Wang and Chih-Pin Su and Chih-Tsun Huang and Cheng-Wen Wu},
 
−
  title    = {An HMAC processor with integrated SHA-1 and MD5 algorithms.},
 
−
  booktitle = {ASP-DAC},
 
−
  year      = {2004},
 
−
  pages    = {456-458},
 
−
  url      = {http://doi.acm.org/10.1145/1015090.1015204},
 
−
  publisher = {IEEE},
 
−
  abstract  = {Cryptographic algorithms are prevalent and important in digital communications and storage, e.g., both SHA-1 and MD5 algorithms are widely used hash functions in IPSec and SSL for checking the data integrity. In this paper, we propose a hardware architecture for the standard HMAC function that supports both. Our HMAC design automatically generates the padding words and reuses the key for consecutive HMAC jobs that use the same key. We have also implemented the HMAC design in silicon. Compared with existing designs, our HMAC processor has lower hardware cost---12.5% by sharing of the SHA-1 and MD5 circuitry and a little performance penalty.},
 
−
}
 
−
</bibtex>
 
−
 
 
−
<bibtex>
 
−
@inproceedings{Grembowski2002ComparativeAnalysisOf,
 
−
  author    = {Tim Grembowski and Roar Lien and Kris Gaj and Nghi Nguyen and Peter Bellows and Jaroslav Flidr and Tom Lehman and Brian Schott},
 
−
  title    = {Comparative Analysis of the Hardware Implementations of Hash Functions SHA-1 and SHA-512.},
 
−
  booktitle = {ISC},
 
−
  year      = {2002},
 
−
  pages    = {75-89},
 
−
  url      = {http://link.springer.de/link/service/series/0558/bibs/2433/24330075.htm},
 
−
  publisher = {Springer},
 
−
  series    = {LNCS},
 
−
  volume    = {2433},
 
−
  abstract  = {Hash functions are among the most widespread cryptographic primitives, and are currently used in multiple cryptographic schemes and security protocols such as IPSec and SSL. In this paper, we compare and contrast hardware implementations of the newly proposed draft hash standard SHA-512, and the old standard, SHA-1. In our implementation based on Xilinx Virtex FPGAs, the throughput of SHA-512 is equal to 670 Mbit/s, compared to 530 Mbit/s for SHA-1. Our analysis shows that the newly proposed hash standard is not only orders of magnitude more secure, but also significantly faster than the old standard. The basic iterative architectures of both hash functions are faster than the basic iterative architectures of symmetric-key ciphers with equivalent security.},
 
−
}
 
−
</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"