Difference between revisions of "SHA-1"
From The ECRYPT Hash Function Website
(→Cryptanalysis) |
(→Collision Attacks) |
||
| Line 16: | Line 16: | ||
<bibtex> | <bibtex> | ||
| − | @ | + | @INPROCEEDINGS{Pramstaller2005ExploitingCodingTheory, |
| − | author = { | + | author = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen}, |
| − | title = { | + | title = {Exploiting Coding Theory for Collision Attacks on SHA-1}, |
| − | + | booktitle = {10th Cryptography and Coding 2005}, | |
| − | + | year = {2005}, | |
| − | + | editor = {Nigel P. Smart}, | |
| − | url = {http:// | + | volume = {3796}, |
| + | series = {LNCS}, | ||
| + | pages = {78-95}, | ||
| + | publisher = {Springer}, | ||
| + | url = {http://dx.doi.org/10.1007/11586821_7}, | ||
| + | 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.} | ||
| + | } | ||
| + | </bibtex> | ||
| + | |||
| + | <bibtex> | ||
| + | @inproceedings{Pramstaller2005ImpactOfRotations, | ||
| + | author = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen}, | ||
| + | title = {Impact of Rotations in SHA-1 and Related Hash Functions.}, | ||
| + | booktitle = {SAC 2005}, | ||
| + | year = {2006}, | ||
| + | pages = {261-275}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {3897}, | ||
| + | url = {http://dx.doi.org/10.1007/11693383_18}, | ||
| + | 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.}, | ||
| + | } | ||
| + | </bibtex> | ||
| + | |||
| + | <bibtex> | ||
| + | @MISC{Wang2005NewCollisionSearch, | ||
| + | author = {Xiaoyun Wang and Andrew Yao and Frances Yao}, | ||
| + | title = {{New Collision Search for SHA-1}}, | ||
| + | month = {August}, | ||
| + | year = {2005}, | ||
| + | note = {Presented at rump session of CRYPTO 2005}, | ||
| + | owner = {npramstaller}, | ||
} | } | ||
</bibtex> | </bibtex> | ||
<bibtex> | <bibtex> | ||
| − | @ | + | @MISC{Wang2005CryptanalysisOfSHA1, |
| − | author = { | + | author = {Xiaoyun Wang and Andrew Yao and Frances Yao}, |
| − | title = {Cryptanalysis of the | + | title = {{Cryptanalysis of SHA-1}}, |
| − | booktitle = { | + | howpublished = {Presented at the Cryptographic Hash Workshop hosted by NIST}, |
| − | year = { | + | 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}, | series = {LNCS}, | ||
| − | pages = { | + | 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.}, | |
| − | |||
} | } | ||
</bibtex> | </bibtex> | ||
<bibtex> | <bibtex> | ||
| − | @ | + | @INPROCEEDINGS{Rijmen2005UpdateonSHA-1, |
| − | author = { | + | author = {Vincent Rijmen and Elisabeth Oswald}, |
| − | title = {{ | + | title = {Update on SHA-1}, |
| − | + | booktitle = {CT-RSA 2005}, | |
| − | + | year = {2005}, | |
| − | volume = { | + | editor = {Alfred Menezes}, |
| − | + | volume = {3376}, | |
| − | pages = { | + | 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> | ||
<bibtex> | <bibtex> | ||
| − | @ | + | @INPROCEEDINGS{Biham2005CollisionsofSHA-0, |
| − | title = { | + | 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}, | |
| − | year = { | + | booktitle = {Advances in Cryptology - EUROCRYPT 2005}, |
| − | + | year = {2005}, | |
| − | + | editor = {Ronald Cramer}, | |
| + | volume = {3494}, | ||
| + | series = {LNCS}, | ||
| + | pages = {36--57}, | ||
| + | publisher = {Springer}, | ||
| + | url = {http://dx.doi.org/10.1007/11426639_3}, | ||
| + | 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.}, | ||
} | } | ||
</bibtex> | </bibtex> | ||
| − | + | <bibtex> | |
| − | ---- | + | @inproceedings{Satoh2005HardwareArchitectureAnd, |
| + | author = {Akashi Satoh}, | ||
| + | title = {Hardware Architecture and Cost Estimates for Breaking SHA-1.}, | ||
| + | booktitle = {ISC 2005}, | ||
| + | year = {2005}, | ||
| + | pages = {259-273}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {3650}, | ||
| + | url = {http://dx.doi.org/10.1007/11556992_19}, | ||
| + | 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.} | ||
| + | } | ||
| + | </bibtex> | ||
=== Second Preimage Attacks === | === Second Preimage Attacks === | ||
Revision as of 14:23, 23 October 2006
Contents
1 General
- digest size: 160 bits
- max. message length: < 264 bits
- type: iterative hash function
- 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 etal. It has complexity of 269 hash evaluations. The best collision example, a 64-step collision for SHA-1, was publshed by DeCanniere and Rechberger.
2.2 Collision Attacks
Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - Exploiting Coding Theory for Collision Attacks on SHA-1
- 10th Cryptography and Coding 2005 3796:78-95,2005
- http://dx.doi.org/10.1007/11586821_7
BibtexAuthor : Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : Exploiting Coding Theory for Collision Attacks on SHA-1
In : 10th Cryptography and Coding 2005 -
Address :
Date : 2005
Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - Impact of Rotations in SHA-1 and Related Hash Functions.
- SAC 2005 3897:261-275,2006
- http://dx.doi.org/10.1007/11693383_18
BibtexAuthor : Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : Impact of Rotations in SHA-1 and Related Hash Functions.
In : SAC 2005 -
Address :
Date : 2006
Xiaoyun Wang, Andrew Yao, Frances Yao - {New Collision Search for SHA-1}
Xiaoyun Wang, Andrew Yao, Frances Yao - {Cryptanalysis of SHA-1}
- , October 2005
- BibtexAuthor : Xiaoyun Wang, Andrew Yao, Frances Yao
Title : {Cryptanalysis of SHA-1}
In : -
Address :
Date : October 2005
Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu - {Finding Collisions in the Full SHA-1}
- Advances in Cryptology - CRYPTO 2005 3621:17--36,2005
- http://dx.doi.org/10.1007/11535218_2
BibtexAuthor : Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu
Title : {Finding Collisions in the Full SHA-1}
In : Advances in Cryptology - CRYPTO 2005 -
Address :
Date : 2005
Vincent Rijmen, Elisabeth Oswald - Update on SHA-1
- CT-RSA 2005 3376:58--71,2005
- http://dx.doi.org/10.1007/b105222
BibtexAuthor : Vincent Rijmen, Elisabeth Oswald
Title : Update on SHA-1
In : CT-RSA 2005 -
Address :
Date : 2005
Eli Biham, Rafi Chen, Antoine hirose, Patrick Carribault, Christophe Lemuet, William Jalby - Collisions of SHA-0 and Reduced SHA-1
- Advances in Cryptology - EUROCRYPT 2005 3494:36--57,2005
- http://dx.doi.org/10.1007/11426639_3
BibtexAuthor : Eli Biham, Rafi Chen, Antoine hirose, Patrick Carribault, Christophe Lemuet, William Jalby
Title : Collisions of SHA-0 and Reduced SHA-1
In : Advances in Cryptology - EUROCRYPT 2005 -
Address :
Date : 2005
Akashi Satoh - Hardware Architecture and Cost Estimates for Breaking SHA-1.
- ISC 2005 3650:259-273,2005
- http://dx.doi.org/10.1007/11556992_19
BibtexAuthor : Akashi Satoh
Title : Hardware Architecture and Cost Estimates for Breaking SHA-1.
In : ISC 2005 -
Address :
Date : 2005
2.3 Second Preimage Attacks
- There exists a generic attack (works for all iterated hash functions). See ....
2.4 Preimage Attacks
- We are not aware of any article regarding preimage attacks on SHA-1.
2.5 Others
everything that does not fit into coll/(2nd)preimage and implementation
3 Performance Evaluation / Implementation (HW and SW)
Yong Ki Lee, Herwin Chan, Ingrid Verbauwhede - Throughput Optimized SHA-1 Architecture Using Unfolding Transformation.
- ASAP 2006 pp. 354-359,2006
- http://doi.ieeecomputersociety.org/10.1109/ASAP.2006.68
BibtexAuthor : Yong Ki Lee, Herwin Chan, Ingrid Verbauwhede
Title : Throughput Optimized SHA-1 Architecture Using Unfolding Transformation.
In : ASAP 2006 -
Address :
Date : 2006
4 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.
