Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Preimage Attacks)
(→‎Performance Evaluation / Implementation (HW and SW))
Line 209: Line 209:
  
 
<bibtex>
 
<bibtex>
−
@inproceedings{DBLP:conf/asap/LeeCV06,
+
@inproceedings{Lee2006,
 
   author    = {Yong Ki Lee and Herwin Chan and Ingrid Verbauwhede},
 
   author    = {Yong Ki Lee and Herwin Chan and Ingrid Verbauwhede},
 
   title    = {Throughput Optimized SHA-1 Architecture Using Unfolding Transformation.},
 
   title    = {Throughput Optimized SHA-1 Architecture Using Unfolding Transformation.},
Line 215: Line 215:
 
   year      = {2006},
 
   year      = {2006},
 
   pages    = {354-359},
 
   pages    = {354-359},
−
   url      = {http://doi.ieeecomputersociety.org/10.1109/ASAP.2006.68},
+
   url      = {http://doi.ieeecomputersociety.org/10.1109/ASAP.2006.68
−
   series    = {IEEE Computer Society},
+
   publisher = {IEEE Computer Society},
 
   year      = {2006},
 
   year      = {2006},
−
  isbn      = {0-7695-2682-9},
+
   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.},
−
   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>
 +
 
 +
<bibtex>
 +
@inproceedings{Chaves2006,
 +
  author    = {Ricardo Chaves and Georgi Kuzmanov and Leonel Sousa and Stamatis Vassiliadis},
 +
  title    = {Rescheduling for Optimized SHA-1 Calculation.},
 +
  booktitle = {SAMOS 2006},
 +
  year      = {2006},
 +
  pages    = {425-434},
 +
  url      = {http://dx.doi.org/10.1007/11796435_43},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4017},
 +
  abstract  = {This paper proposes the rescheduling of the SHA-1 hash function operations on hardware implementations. The proposal is mapped on the Xilinx Virtex II Pro technology. The proposed rescheduling allows for a manipulation of the critical path in the SHA-1 function computation, facilitating the implementation of a more parallelized structure without an increase on the required hardware resources. Two cores have been developed, one that uses a constant initialization vector and a second one that allows for different Initialization Vectors (IV), in order to be used in HMAC and in the processing of fragmented messages. A hybrid software/hardware implementation is also proposed. Experimental results indicate a throughput of 1.4 Gbits/s requiring only 533 slices for a constant IV and 596 for an imputable IV. Comparisons to SHA-1 related art suggest improvements of the throughput/slice metric of 29% against the most recent commercial cores and 59% to the current academia proposals.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{Michail2005OptimizingSHA-1Hash,
 +
  author    = {H. E. Michail and A. P. Kakarountas and George N. Selimis and Costas E. Goutis},
 +
  title    = {Optimizing SHA-1 Hash Function for High Throughput with a Partial Unrolling Study.},
 +
  booktitle = {PATMOS 2005},
 +
  year      = {2005},
 +
  pages    = {591-600},
 +
  url      = {http://dx.doi.org/10.1007/11556930_60},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {3728},
 +
  abstract = {Hash functions are widely used in applications that call for data integrity and signature authentication at electronic transactions. A hash function is utilized in the security layer of every communication protocol. As time passes more sophisticated applications arise that address to more users-clients and thus demand for higher throughput. Furthermore, due to the tendency of the market to minimize devices’ size and increase their autonomy to make them portable, power issues have also to be considered. The existing SHA-1 Hash Function implementations (SHA-1 is common in many protocols e.g. IPSec) limit throughput to a maximum of 2 Gbps. In this paper, a new implementation comes to exceed this limit improving the throughput by 53%. Furthermore,power dissipation is kept low compared to previous works, in such way that the proposed implementation can be characterized as low-power.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{Toma2005FormalVerificationOf,
 +
  author    = {Diana Toma and Dominique Borrione},
 +
  title    = {Formal Verification of a SHA-1 Circuit Core Using ACL2.},
 +
  booktitle = {TPHOLs 2005},
 +
  year      = {2005},
 +
  pages    = {326-341},
 +
  url      = {http://dx.doi.org/10.1007/11541868_21},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {3603},
 +
  abstract ={Our study was part of a project aiming at the design and verification of a circuit for secure communications between a computer and a terminal smart card reader. A SHA-1 component is included in the circuit. SHA-1 is a cryptographic primive that produces, for any message, a 160 bit message digest. We formalize the standard specification in ACL2, then automatically produce the ACL2 model for the VHDL RTL design; finally, we prove the implementation compliant with the specification. We apply a stepwise approach that proves theorems about each computation step of the RTL design, using intermediate digest functions.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{Jarvinen2005ACompactMD5,
 +
  author    = {Kimmo U. J{\"a}rvinen and Matti Tommiska and Jorma Skytt{\"a}},
 +
  title    = {A Compact MD5 and SHA-1 Co-Implementation Utilizing Algorithm Similarities.},
 +
  booktitle = {ERSA},
 +
  year      = {2005},
 +
  pages    = {48-54},
 +
  publisher = {CSREA Press},
 +
  year      = {2005},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{Lien2004A1Gbit/s,
 +
  author    = {Roar Lien and Tim Grembowski and Kris Gaj},
 +
  title    = {A 1 Gbit/s Partially Unrolled Architecture of Hash Functions SHA-1 and SHA-512.},
 +
  booktitle = {CT-RSA},
 +
  year      = {2004},
 +
  pages    = {324-338},
 +
  url      = {http://dx.doi.org/10.1007/b95630},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {2964},
 +
  abstract  = {Hash functions are among the most widespread cryptographic primitives, and are currently used in multiple cryptographic schemes and security protocols, such as IPSec and SSL. In this paper, we investigate a new hardware architecture for a family of dedicated hash functions, including American standards SHA-1 and SHA-512. Our architecture is based on unrolling several message digest steps and executing them in one clock cycle. This modification permits implementing majority of dedicated hash functions with the throughput exceeding 1 Gbit/s using medium-size Xilinx Virtex FPGAs. In particular, our new architecture has enabled us to speed up the implementation of SHA-1 compared to the basic iterative architecture from 544 Mbit/s to 1 Gbit/s using Xilinx XCV1000. The implementation of SHA-512 has been sped up from 717 to 929 Mbit/s for Virtex FPGAs, and exceeded 1 Gbit/s for Virtex-E Xilinx FPGAs.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{Wang2004AnHMACProcessor,
 +
  author    = {Mao-Yin Wang and Chih-Pin Su and Chih-Tsun Huang and Cheng-Wen Wu},
 +
  title    = {An HMAC processor with integrated SHA-1 and MD5 algorithms.},
 +
  booktitle = {ASP-DAC},
 +
  year      = {2004},
 +
  pages    = {456-458},
 +
  url      = {http://doi.acm.org/10.1145/1015090.1015204},
 +
  publisher = {IEEE},
 +
  abstract  = {Cryptographic algorithms are prevalent and important in digital communications and storage, e.g., both SHA-1 and MD5 algorithms are widely used hash functions in IPSec and SSL for checking the data integrity. In this paper, we propose a hardware architecture for the standard HMAC function that supports both. Our HMAC design automatically generates the padding words and reuses the key for consecutive HMAC jobs that use the same key. We have also implemented the HMAC design in silicon. Compared with existing designs, our HMAC processor has lower hardware cost---12.5% by sharing of the SHA-1 and MD5 circuitry and a little performance penalty.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{Grembowski2002ComparativeAnalysisOf,
 +
  author    = {Tim Grembowski and Roar Lien and Kris Gaj and Nghi Nguyen and Peter Bellows and Jaroslav Flidr and Tom Lehman and Brian Schott},
 +
  title    = {Comparative Analysis of the Hardware Implementations of Hash Functions SHA-1 and SHA-512.},
 +
  booktitle = {ISC},
 +
  year      = {2002},
 +
  pages    = {75-89},
 +
  url      = {http://link.springer.de/link/service/series/0558/bibs/2433/24330075.htm},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {2433},
 +
  abstract  = {Hash functions are among the most widespread cryptographic primitives, and are currently used in multiple cryptographic schemes and security protocols such as IPSec and SSL. In this paper, we compare and contrast hardware implementations of the newly proposed draft hash standard SHA-512, and the old standard, SHA-1. In our implementation based on Xilinx Virtex FPGAs, the throughput of SHA-512 is equal to 670 Mbit/s, compared to 530 Mbit/s for SHA-1. Our analysis shows that the newly proposed hash standard is not only orders of magnitude more secure, but also significantly faster than the old standard. The basic iterative architectures of both hash functions are faster than the basic iterative architectures of symmetric-key ciphers with equivalent security.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Revision as of 15:12, 23 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

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"