Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
Line 3: Line 3:
 
* 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]
 
* [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf  Specification: FIPS 180-2 Secure Hash Standard]
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 publshed by DeCanniere, Mendel and Rechberger.
 
----
 
----
  
Line 203: Line 202:
 
----
 
----
  
−
=== 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^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 huge amount of data is required.
 
−
----
 
  
 
=== Preimage Attacks ===
 
=== Preimage Attacks ===

Revision as of 18:22, 6 March 2008

1 General

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 publshed by DeCanniere, Mendel 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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : Charanjit S. Jutla, Anindya C. Patthak
Title : A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code
In : -
Address :
Date : 2005

Charanjit S. Jutla, Anindya C. Patthak - A Simple and Provably Good Code for SHA Message Expansion

,2005
http://eprint.iacr.org/2005/247
Bibtex
Author : Charanjit S. Jutla, Anindya C. Patthak
Title : A Simple and Provably Good Code for SHA Message Expansion
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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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

, August 2005
Bibtex
Author : Xiaoyun Wang, Andrew Yao, Frances Yao
Title : New Collision Search for SHA-1
In : -
Address :
Date : August 2005

Xiaoyun Wang, Andrew Yao, Frances Yao - Cryptanalysis of SHA-1

, October 2005
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : Akashi Satoh
Title : Hardware Architecture and Cost Estimates for Breaking SHA-1.
In : ISC 2005 -
Address :
Date : 2005


2.3 Preimage Attacks

  • We are not aware of any articles w.r.t. preimage attacks on SHA-1.

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

ERSA pp. 48-54,2005
Bibtex
Author : Kimmo U. J\"arvinen, Matti Tommiska, Jorma Skytt\"a
Title : A Compact MD5 and SHA-1 Co-Implementation Utilizing Algorithm Similarities.
In : ERSA -
Address :
Date : 2005

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

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