Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Collision Attacks)
Line 34: Line 34:
 
     url = {http://eprint.iacr.org/2005/350},
 
     url = {http://eprint.iacr.org/2005/350},
 
     abstract= {We argue that if the message expansion code of SHA-1 is replaced by a linear code with a better minimum distance, then the resulting hash function is collision resistant. To support this argument, we characterize the disturbance vectors which are used to build local collision attacks as a linear code. This linear code is the xor-sum of two codes, the message expansion code and a linear code representing the underlying block cipher in SHA-1. We also show that the following constraint satisfaction problem is $\np$-hard. The constraints are restricted to being XOR constraints, or Majority constraints on at most three variables each. The instances are further restricted by requiring that the constraints can be listed in a sequence C_1, C_2,...,C_m, such that for every constraint C_i, two of the variables in it occur only in constraints C_j, with |j-i|< 48. This problem is similar to the problem modeling the one-way function property of SHA-1. },
 
     abstract= {We argue that if the message expansion code of SHA-1 is replaced by a linear code with a better minimum distance, then the resulting hash function is collision resistant. To support this argument, we characterize the disturbance vectors which are used to build local collision attacks as a linear code. This linear code is the xor-sum of two codes, the message expansion code and a linear code representing the underlying block cipher in SHA-1. We also show that the following constraint satisfaction problem is $\np$-hard. The constraints are restricted to being XOR constraints, or Majority constraints on at most three variables each. The instances are further restricted by requiring that the constraints can be listed in a sequence C_1, C_2,...,C_m, such that for every constraint C_i, two of the variables in it occur only in constraints C_j, with |j-i|< 48. This problem is similar to the problem modeling the one-way function property of SHA-1. },
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2005:266,
 +
    author = {Charanjit S. Jutla and  Anindya C. Patthak},
 +
    title = {A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code},
 +
    howpublished = {Cryptology ePrint Archive, Report 2005/266},
 +
    year = {2005},
 +
    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.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Revision as of 14:29, 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

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

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=1575"