Difference between revisions of "SHA-1"
(→Best Known Results) |
(→Second Preimage Attacks) |
||
| Line 150: | Line 150: | ||
=== Second Preimage Attacks === | === Second Preimage Attacks === | ||
| − | + | ||
| + | <bibtex> | ||
| + | @inproceedings{Kelsey2005SecondPreimageOn, | ||
| + | author = {John Kelsey and Bruce Schneier}, | ||
| + | title = {Second Preimages on n-Bit Hash Functions for Much Less than 2$^{\mbox{n}}$ Work.}, | ||
| + | booktitle = {EUROCRYPT}, | ||
| + | year = {2005}, | ||
| + | pages = {474-490}, | ||
| + | url = {http://dx.doi.org/10.1007/11426639_28}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {3494}, | ||
| + | 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.}, | ||
| + | } | ||
| + | </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 inpractical amount of data is required. | ||
---- | ---- | ||
Revision as of 14:43, 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
Michael Szydlo, Yiqun Lisa Yin - Collision-Resistant Usage of MD5 and SHA-1 Via Message Preprocessing.
- CT-RSA 2006 3860:99-114,2006
- http://dx.doi.org/10.1007/11605805_7
BibtexAuthor : Michael Szydlo, Yiqun Lisa Yin
Title : Collision-Resistant Usage of MD5 and SHA-1 Via Message Preprocessing.
In : CT-RSA 2006 -
Address :
Date : 2006
Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - Exploiting Coding Theory for Collision Attacks on SHA-1
- 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 : 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
John Kelsey, Bruce Schneier - Second Preimages on n-Bit Hash Functions for Much Less than 2$^{\mbox{n}}$ Work.
- EUROCRYPT 3494:474-490,2005
- http://dx.doi.org/10.1007/11426639_28
BibtexAuthor : John Kelsey, Bruce Schneier
Title : Second Preimages on n-Bit Hash Functions for Much Less than 2$^{\mbox{n}}$ Work.
In : EUROCRYPT -
Address :
Date : 2005
Note: This artcle shows that second preimages can be found in much less than 2n work. This approach works for all iterated hash functions. Nevertheless, this attack is not practical since a inpractical amount of data is required.
2.4 Preimage Attacks
- We are not aware of any article regarding preimage attacks on SHA-1.
2.5 Others
Markku-Juhani Olavi Saarinen - Cryptanalysis of Block Ciphers Based on SHA-1 and MD5.
- FSE 2003 2887:36-44,2003
- http://springerlink.metapress.com/content/xu0qg98tg38gl7nf/?p=2664f1c23d3f433f9d3fd6a9a1350eda&pi=3
BibtexAuthor : Markku-Juhani Olavi Saarinen
Title : Cryptanalysis of Block Ciphers Based on SHA-1 and MD5.
In : FSE 2003 -
Address :
Date : 2003
Helena Handschuh, Lars R. Knudsen, Matthew J. B. Robshaw - Analysis of SHA-1 in Encryption Mode.
- CT-RSA 2001 2020:70-83,2001
- http://link.springer.de/link/service/series/0558/bibs/2020/20200070.htm
BibtexAuthor : Helena Handschuh, Lars R. Knudsen, Matthew J. B. Robshaw
Title : Analysis of SHA-1 in Encryption Mode.
In : CT-RSA 2001 -
Address :
Date : 2001
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.
