Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Collision Attacks)
Line 56: Line 56:
 
     url = {http://eprint.iacr.org/2005/266},
 
     url = {http://eprint.iacr.org/2005/266},
 
     abstract= {Recently, Wang, Yin, and Yu have used a low weight codeword in the SHA-1 message expansion to show a better than brute force method to find collisions in SHA-1. The codeword they used has a (bit) weight of 25 in the last 60 of the 80 expanded words. In this paper we show, using a computer assisted method, that this is indeed the smallest weight codeword. In particular, we show that the minimum weight over GF2 of any non-zero codeword in the SHA-1 (linear) message expansion code, projected on the last 60 words, is at least 25.},
 
     abstract= {Recently, Wang, Yin, and Yu have used a low weight codeword in the SHA-1 message expansion to show a better than brute force method to find collisions in SHA-1. The codeword they used has a (bit) weight of 25 in the last 60 of the 80 expanded words. In this paper we show, using a computer assisted method, that this is indeed the smallest weight codeword. In particular, we show that the minimum weight over GF2 of any non-zero codeword in the SHA-1 (linear) message expansion code, projected on the last 60 words, is at least 25.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2005:247,
 +
    author = {Charanjit S. Jutla  and Anindya C. Patthak},
 +
    title = {A Simple and Provably Good Code for SHA Message Expansion},
 +
    howpublished = {Cryptology ePrint Archive, Report 2005/247},
 +
    year = {2005},
 +
    url = {http://eprint.iacr.org/2005/247},
 +
    abstract = {We develop a new computer assisted technique for lower bounding the minimum distance of linear codes similar to those used in SHA-1 message expansion. Using this technique, we prove that a modified SHA-1 like 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 propose a new compression function which is identical to SHA-1 except for the modified message expansion code. We argue that the high minimum weight of the message expansion code makes the new compression function resistant to recent differential attacks.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Revision as of 15:02, 24 October 2006

1 General

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
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 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
Bibtex
Author : 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
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=1577"