SHA-1

From The ECRYPT Hash Function Website
Revision as of 15:12, 23 October 2006 by Nobbi (talk | contribs) (→‎Performance Evaluation / Implementation (HW and SW))

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

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 2n 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 2n 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 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 publisher = {IEEE Computer Society}, year = {2006}, abstract = {In this paper, we analyze the theoretical delay bound of the SHA-1 algorithm and propose architectures to achieve high throughput hardware implementations which approach this bound. According to the results of FPGA implementations, 3,541 Mbps with a pipeline and 893 Mbps without a pipeline were achieved. Moreover, synthesis results using 0.18..m CMOS technology showed that 10.4 Gbps with a pipeline and 3.1 Gbps without a pipeline can be achieved. These results are much faster than previously published results. The high throughputs are due to the unfolding transformation, which reduces the number of required cycles for one block hash. We reduced the required number of cycles to 12 cycles for a 512 bit block and showed that 12 cycles is the optimal in our design.},
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=1563"