Difference between revisions of "MD5"
From The ECRYPT Hash Function Website
(→Specification) |
(→Collision Attacks) |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 4: | Line 4: | ||
* max. message length: < 2<sup>64</sup> bits | * max. message length: < 2<sup>64</sup> bits | ||
* compression function: 512-bit message block, 128-bit chaining variable | * compression function: 512-bit message block, 128-bit chaining variable | ||
| − | * Specification: [http://www.ietf.org/rfc/rfc1321.txt | + | * Specification: [http://www.ietf.org/rfc/rfc1321.txt RFC1321] |
== Cryptanalysis == | == Cryptanalysis == | ||
| Line 10: | Line 10: | ||
=== Best Known Results === | === Best Known Results === | ||
| + | |||
| + | The best known collision attack is due to Klima with a complexity of 2<sup>29</sup> effort. | ||
---- | ---- | ||
| Line 100: | Line 102: | ||
abstract = {We introduce the idea of differential cryptanalysis mod 2^32 and apply it to the MD5 message digest algorithm. We derive a theory for differential cryptanalysis of the circular shift function. We demonstrate a high-probability differentials which leave the message digest register unchanged for each of MD5’s four rounds, and explain how more such differentials may be calculated.}, | abstract = {We introduce the idea of differential cryptanalysis mod 2^32 and apply it to the MD5 message digest algorithm. We derive a theory for differential cryptanalysis of the circular shift function. We demonstrate a high-probability differentials which leave the message digest register unchanged for each of MD5’s four rounds, and explain how more such differentials may be calculated.}, | ||
url = {http://link.springer.de/link/service/series/0558/bibs/0658/06580071.htm}, | url = {http://link.springer.de/link/service/series/0558/bibs/0658/06580071.htm}, | ||
| + | editor = {Rainer A. Rueppel}, | ||
| + | series = {LNCS}, | ||
| + | volume = {658}, | ||
| + | year = {1993}, | ||
} | } | ||
</bibtex> | </bibtex> | ||
| Line 111: | Line 117: | ||
=== Preimage Attacks === | === Preimage Attacks === | ||
| + | <bibtex> | ||
| + | @inproceedings{acispSasakiA08, | ||
| + | author = {Yu Sasaki and Kazumaro Aoki}, | ||
| + | title = {Preimage Attacks on Step-Reduced MD5}, | ||
| + | booktitle = {ACISP}, | ||
| + | year = {2008}, | ||
| + | pages = {282-296}, | ||
| + | abstract = {In this paper, we propose preimage attacks on step-reduced MD5. We show that a preimage of a 44-step MD5 can be computed to a complexity of 2^96. We also consider a preimage attack against variants of MD5 where the round order is modified from the real MD5. In such a case, a preimage of a 51-step round-reordered MD5 can be computed to a complexity of 2^96. Our attack uses local collisions of MD5 to create a degree of message freedom. This freedom enables us to match the two 128-bit intermediate values efficiently.}, | ||
| + | url = {http://dx.doi.org/10.1007/978-3-540-70500-0_21}, | ||
| + | editor = {Yi Mu and Willy Susilo and Jennifer Seberry}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {5107}, | ||
| + | isbn = {978-3-540-69971-2}, | ||
| + | } | ||
| + | </bibtex> | ||
---- | ---- | ||
Latest revision as of 15:20, 10 November 2008
Contents
1 Specification
- digest size: 128 bits
- max. message length: < 264 bits
- compression function: 512-bit message block, 128-bit chaining variable
- Specification: RFC1321
2 Cryptanalysis
2.1 Best Known Results
The best known collision attack is due to Klima with a complexity of 229 effort.
2.2 Generic Attacks
2.3 Collision Attacks
Gaëtan Leurent - Message Freedom in MD4 and MD5 Collisions: Application to APOP
- FSE 4593:309-328,2007
- http://dx.doi.org/10.1007/978-3-540-74619-5_20
BibtexAuthor : Gaëtan Leurent
Title : Message Freedom in MD4 and MD5 Collisions: Application to APOP
In : FSE -
Address :
Date : 2007
Marc Stevens, Arjen K. Lenstra, Benne de Weger - Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities
- EUROCRYPT 4515:1-22,2007
- http://dx.doi.org/10.1007/978-3-540-72540-4_1
BibtexAuthor : Marc Stevens, Arjen K. Lenstra, Benne de Weger
Title : Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities
In : EUROCRYPT -
Address :
Date : 2007
Xiaoyun Wang, Hongbo Yu - How to Break MD5 and Other Hash Functions
- EUROCRYPT 3494:19-35,2005
- http://dx.doi.org/10.1007/11426639_2
BibtexAuthor : Xiaoyun Wang, Hongbo Yu
Title : How to Break MD5 and Other Hash Functions
In : EUROCRYPT -
Address :
Date : 2005
Bert den Boer, Antoon Bosselaers - Collisions for the Compression Function of MD5
- EUROCRYPT pp. 293-304,1993
- http://link.springer.de/link/service/series/0558/bibs/0765/07650293.htm
BibtexAuthor : Bert den Boer, Antoon Bosselaers
Title : Collisions for the Compression Function of MD5
In : EUROCRYPT -
Address :
Date : 1993
Thomas A. Berson - Differential Cryptanalysis Mod 2^32 with Applications to MD5
- EUROCRYPT 658:71-80,1993
- http://link.springer.de/link/service/series/0558/bibs/0658/06580071.htm
BibtexAuthor : Thomas A. Berson
Title : Differential Cryptanalysis Mod 2^32 with Applications to MD5
In : EUROCRYPT -
Address :
Date : 1993
2.4 Second Preimage Attacks
2.5 Preimage Attacks
Yu Sasaki, Kazumaro Aoki - Preimage Attacks on Step-Reduced MD5
- ACISP 5107:282-296,2008
- http://dx.doi.org/10.1007/978-3-540-70500-0_21
BibtexAuthor : Yu Sasaki, Kazumaro Aoki
Title : Preimage Attacks on Step-Reduced MD5
In : ACISP -
Address :
Date : 2008
2.6 Others
John Black, Martin Cochran, Trevor Highland - A Study of the MD5 Attacks: Insights and Improvements
