Difference between revisions of "MD5"

From The ECRYPT Hash Function Website
(Best Known Results)
(Collision Attacks)
 
(2 intermediate revisions by the same user not shown)
Line 11: Line 11:
 
=== Best Known Results ===
 
=== Best Known Results ===
  
The best known collision attack is due to Klima with a complexity of 2<sup>29</sup> effort. No preimage or 2nd preimgae attacks are known.
+
The best known collision attack is due to Klima with a complexity of 2<sup>29</sup> effort.  
  
 
----
 
----
Line 102: 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 113: 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

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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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
Bibtex
Author : 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

FSE 4047:262-277,2006
http://dx.doi.org/10.1007/11799313_17
Bibtex
Author : John Black, Martin Cochran, Trevor Highland
Title : A Study of the MD5 Attacks: Insights and Improvements
In : FSE -
Address :
Date : 2006