Paper 2006/105

Tunnels in Hash Functions: MD5 Collisions Within a Minute

Vlastimil Klima

Abstract

In this paper we introduce a new idea of tunneling of hash functions. In some sense tunnels replace multi-message modification methods and exponentially accelerate collision search. We describe several tunnels in hash function MD5. Using it we find a MD5 collision roughly in one minute on a standard notebook PC (Intel Pentium, 1.6 GHz). The method works for any initializing value. Tunneling is a general idea, which can be used for finding collisions of other hash functions, such as SHA-1, 2. We show several capabilities of tunnels. A program, which source code is available on a project homepage, experimentally verified the method. Revised version of this paper contains the appendix with the description of more tunnels. These tunnels further decrease the average time of MD5 collision to 31 seconds. On PC Intel Pentium 4 (3,2 GHz) it is 17 seconds in average.

Note: Revised version of this paper contains the appendix with the description of more tunnels. These tunnels further decrease the average time of MD5 collision to 31 seconds. On PC Intel Pentium 4 (3,2 GHz) it is 17 seconds in average.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash functionMD5collisionmulti-message modification methodtunneltunneling
Contact author(s)
v klima @ volny cz
History
2006-04-17: revised
2006-03-19: received
See all versions
Short URL
https://ia.cr/2006/105
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/105,
      author = {Vlastimil Klima},
      title = {Tunnels in Hash Functions: MD5 Collisions Within a Minute},
      howpublished = {Cryptology ePrint Archive, Paper 2006/105},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/105}},
      url = {https://eprint.iacr.org/2006/105}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.