Difference between revisions of "SHA-1"
From The ECRYPT Hash Function Website
Npramstaller (talk | contribs) (→Collision Attacks) |
Npramstaller (talk | contribs) (→Collision Attacks) |
||
| Line 29: | Line 29: | ||
isbn = {3-540-49475-8}, | isbn = {3-540-49475-8}, | ||
abstract = {The most efficient collision attacks on members of the SHA family presented so far all use complex characteristics which were manually constructed by Wang et al. In this report, we describe a method to search for characteristics in an automatic way. This is particularly useful for multi-block attacks, and as a proof of concept, we give a two-block collision for 64-step SHA-1 based on a new characteristic. The highest number of steps for which a SHA-1 collision was published so far was 58. We also give a unified view on the expected work factor of a collision search and the needed degrees of freedom for the search, which facilitates optimization.}, | abstract = {The most efficient collision attacks on members of the SHA family presented so far all use complex characteristics which were manually constructed by Wang et al. In this report, we describe a method to search for characteristics in an automatic way. This is particularly useful for multi-block attacks, and as a proof of concept, we give a two-block collision for 64-step SHA-1 based on a new characteristic. The highest number of steps for which a SHA-1 collision was published so far was 58. We also give a unified view on the expected work factor of a collision search and the needed degrees of freedom for the search, which facilitates optimization.}, | ||
| + | } | ||
| + | </bibtex> | ||
| + | |||
| + | <bibtex> | ||
| + | @inproceedings{sacryptJutlaP06, | ||
| + | author = {Charanjit S. Jutla and Anindya C. Patthak}, | ||
| + | title = {Provably Good Codes for Hash Function Design}, | ||
| + | booktitle = {Selected Areas in Cryptography}, | ||
| + | year = {2006}, | ||
| + | pages = {376-393}, | ||
| + | url = {http://dx.doi.org/10.1007/978-3-540-74462-7_26}, | ||
| + | editor = {Eli Biham and Amr M. Youssef}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {4356}, | ||
| + | isbn = {978-3-540-74461-0}, | ||
| + | abstract = {We develop a new technique to lower bound the minimum distance of quasi-cyclic codes with large dimension by reducing the problem to lower bounding the minimum distance of a few significantly smaller dimensional codes. Using this technique, we prove that a code which is similar to the SHA-1 message expansion 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 expect our technique to be helpful in designing future practical collision-resistant hash functions. We also use the technique to find the minimum weight of the SHA-1 code (25 in the last 60 words), which was an open problem.}, | ||
} | } | ||
</bibtex> | </bibtex> | ||
Revision as of 07:35, 11 March 2008
Contents
1 Specification
- digest size: 160 bits
- max. message length: < 264 bits
- compression function: 512-bit message block, 160-bit chaining variable
- Specification: FIPS 180-2 Secure Hash Standard
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 published by DeCanniere, Mendel and Rechberger.
2.2 Collision Attacks
Christophe De Canni\`ere, Christian Rechberger - Finding SHA-1 Characteristics: General Results and Applications
- ASIACRYPT 4284:1-20,2006
- http://dx.doi.org/10.1007/11935230_1
BibtexAuthor : Christophe De Canni\`ere, Christian Rechberger
Title : Finding SHA-1 Characteristics: General Results and Applications
In : ASIACRYPT -
Address :
Date : 2006
Charanjit S. Jutla, Anindya C. Patthak - Provably Good Codes for Hash Function Design
- Selected Areas in Cryptography 4356:376-393,2006
- http://dx.doi.org/10.1007/978-3-540-74462-7_26
BibtexAuthor : Charanjit S. Jutla, Anindya C. Patthak
Title : Provably Good Codes for Hash Function Design
In : Selected Areas in Cryptography -
Address :
Date : 2006
Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - Impact of Rotations in SHA-1 and Related Hash Functions
- Selected Areas in Cryptography 3897:261-275,2005
- http://dx.doi.org/10.1007/11693383_18
BibtexAuthor : Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : Impact of Rotations in SHA-1 and Related Hash Functions
In : Selected Areas in Cryptography -
Address :
Date : 2005
Vincent Rijmen, Elisabeth Oswald - Update on SHA-1
- CT-RSA pp. 58-71,2005
- http://dx.doi.org/10.1007/b105222
BibtexAuthor : Vincent Rijmen, Elisabeth Oswald
Title : Update on SHA-1
In : CT-RSA -
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
Akashi Satoh - Hardware Architecture and Cost Estimates for Breaking SHA-1
- ISC 3650:259-273,2005
- http://dx.doi.org/10.1007/11556992_19
BibtexAuthor : Akashi Satoh
Title : Hardware Architecture and Cost Estimates for Breaking SHA-1
In : ISC -
Address :
Date : 2005
3 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.
