Paper 2005/075

Finding MD5 Collisions – a Toy For a Notebook

Vlastimil Klima

Abstract

One of the major cryptographic "break-through" of the recent years was a discovery of collisions for a set of hash functions (MD4, MD5, HAVAL-128, RIPEMD) by the Chinese cryptographers in August 2004 [1]. Their authors (Wang et al.) kept the algorithm secret, however. We have found a way to generate the first message block of the collision about 1000 - 2000 times faster than the Chinese team - that corresponds to reaching the first colliding block in 2 minutes using a common notebook. The same computation phase took the Chinese team about an hour using an IBM P690 supercomputer. On the other hand, the Chinese team was 2 - 80 times faster when computing the second message block of their collisions. Therefore, our and the Chinese methods probably differs in both parts of the computation. Overall, our method is about 3 - 6 times faster. More specifically, finding the first (complete) collision took 8 hours using a notebook PC (Intel Pentium 1.6 GHz). That should be a warning towards persisting usage of MD5. Note that our method works for any initialization vector. In the appendix, we show new examples of collisions for a standard and chosen initialization vectors.

Note: Common hash value in the second example corrected.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. will be published in a forthcoming conference
Keywords
MD5 collisionscryptanalysis
Contact author(s)
v klima @ volny cz
History
2005-03-08: revised
2005-03-08: received
See all versions
Short URL
https://ia.cr/2005/075
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/075,
      author = {Vlastimil Klima},
      title = {Finding {MD5} Collisions – a Toy For a Notebook},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/075},
      year = {2005},
      url = {https://eprint.iacr.org/2005/075}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.