Difference between revisions of "SHA-1"
(→Collision Attacks) |
(→Collision Attacks) |
||
| Line 23: | Line 23: | ||
url = {http://eprint.iacr.org/2006/098}, | 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.}, | 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> | ||
| + | @misc{cryptoeprint:2004:364, | ||
| + | author = {Krystian Matusiewicz and Josef Pieprzyk}, | ||
| + | title = {Finding good differential patterns for attacks on SHA-1}, | ||
| + | howpublished = {Cryptology ePrint Archive, Report 2004/364}, | ||
| + | year = {2004}, | ||
| + | url = {http://eprint.iacr.org/2004/364}, | ||
| + | abstract= {In this paper we describe a method of finding differential patterns that may be used to attack reduced versions of SHA-1. We show that the problem of finding optimal differential patterns for SHA-1 is equivalent to the problem of finding minimal weight codeword in a linear code. Finally, we present a number of patterns of different lengths suitable for finding collisions and near-collisions and discuss some bounds on minimal weights of them.}, | ||
} | } | ||
</bibtex> | </bibtex> | ||
Revision as of 14:31, 24 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
Makoto Sugita, Mitsuru Kawazoe, Hideki Imai - Gr\"obner Basis Based Cryptanalysis of SHA-1
- ,2006
- http://eprint.iacr.org/2006/098
BibtexAuthor : Makoto Sugita, Mitsuru Kawazoe, Hideki Imai
Title : Gr\"obner Basis Based Cryptanalysis of SHA-1
In : -
Address :
Date : 2006
Krystian Matusiewicz, Josef Pieprzyk - Finding good differential patterns for attacks on SHA-1
- ,2004
- http://eprint.iacr.org/2004/364
BibtexAuthor : Krystian Matusiewicz, Josef Pieprzyk
Title : Finding good differential patterns for attacks on SHA-1
In : -
Address :
Date : 2004
Charanjit S. Jutla, Anindya C. Patthak - Is SHA-1 conceptually sound?
- ,2005
- http://eprint.iacr.org/2005/350
BibtexAuthor : Charanjit S. Jutla, Anindya C. Patthak
Title : Is SHA-1 conceptually sound?
In : -
Address :
Date : 2005
Charanjit S. Jutla, Anindya C. Patthak - A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code
- ,2005
- http://eprint.iacr.org/2005/266
BibtexAuthor : Charanjit S. Jutla, Anindya C. Patthak
Title : A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code
In : -
Address :
Date : 2005
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^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^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 huge amount of data is required.
2.4 Preimage Attacks
- We are not aware of any articles w.r.t. 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
Ricardo Chaves, Georgi Kuzmanov, Leonel Sousa, Stamatis Vassiliadis - Rescheduling for Optimized SHA-1 Calculation.
- SAMOS 2006 4017:425-434,2006
- http://dx.doi.org/10.1007/11796435_43
BibtexAuthor : Ricardo Chaves, Georgi Kuzmanov, Leonel Sousa, Stamatis Vassiliadis
Title : Rescheduling for Optimized SHA-1 Calculation.
In : SAMOS 2006 -
Address :
Date : 2006
H. E. Michail, A. P. Kakarountas, George N. Selimis, Costas E. Goutis - Optimizing SHA-1 Hash Function for High Throughput with a Partial Unrolling Study.
- PATMOS 2005 3728:591-600,2005
- http://dx.doi.org/10.1007/11556930_60
BibtexAuthor : H. E. Michail, A. P. Kakarountas, George N. Selimis, Costas E. Goutis
Title : Optimizing SHA-1 Hash Function for High Throughput with a Partial Unrolling Study.
In : PATMOS 2005 -
Address :
Date : 2005
Diana Toma, Dominique Borrione - Formal Verification of a SHA-1 Circuit Core Using ACL2.
- TPHOLs 2005 3603:326-341,2005
- http://dx.doi.org/10.1007/11541868_21
BibtexAuthor : Diana Toma, Dominique Borrione
Title : Formal Verification of a SHA-1 Circuit Core Using ACL2.
In : TPHOLs 2005 -
Address :
Date : 2005
Kimmo U. J\"arvinen, Matti Tommiska, Jorma Skytt\"a - A Compact MD5 and SHA-1 Co-Implementation Utilizing Algorithm Similarities.
Roar Lien, Tim Grembowski, Kris Gaj - A 1 Gbit/s Partially Unrolled Architecture of Hash Functions SHA-1 and SHA-512.
- CT-RSA 2964:324-338,2004
- http://dx.doi.org/10.1007/b95630
BibtexAuthor : Roar Lien, Tim Grembowski, Kris Gaj
Title : A 1 Gbit/s Partially Unrolled Architecture of Hash Functions SHA-1 and SHA-512.
In : CT-RSA -
Address :
Date : 2004
Mao-Yin Wang, Chih-Pin Su, Chih-Tsun Huang, Cheng-Wen Wu - An HMAC processor with integrated SHA-1 and MD5 algorithms.
- ASP-DAC pp. 456-458,2004
- http://doi.acm.org/10.1145/1015090.1015204
BibtexAuthor : Mao-Yin Wang, Chih-Pin Su, Chih-Tsun Huang, Cheng-Wen Wu
Title : An HMAC processor with integrated SHA-1 and MD5 algorithms.
In : ASP-DAC -
Address :
Date : 2004
Tim Grembowski, Roar Lien, Kris Gaj, Nghi Nguyen, Peter Bellows, Jaroslav Flidr, Tom Lehman, Brian Schott - Comparative Analysis of the Hardware Implementations of Hash Functions SHA-1 and SHA-512.
- ISC 2433:75-89,2002
- http://link.springer.de/link/service/series/0558/bibs/2433/24330075.htm
BibtexAuthor : Tim Grembowski, Roar Lien, Kris Gaj, Nghi Nguyen, Peter Bellows, Jaroslav Flidr, Tom Lehman, Brian Schott
Title : Comparative Analysis of the Hardware Implementations of Hash Functions SHA-1 and SHA-512.
In : ISC -
Address :
Date : 2002
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.
