Paper 2005/425

Improved Collision Attack on Hash Function MD5

Jie Liang and Xuejia Lai

Abstract

In this paper, we present a fast attack algorithm to find two-block collision of hash function MD5. The algorithm is based on the two-block collision differential path of MD5 that was presented by Wang et al. in EUROCRYPT 2005[6]. We found that the derived conditions for the desired differential path in [6] were not sufficient to guarantee the differential path to hold and that some conditions could be relaxed to enlarge the collision set. By using technique of small range searching and omitting the computing steps to check the characteristics in algorithm, we can speed up the attack of MD5 efficiently. Compared with the Advanced Message Modification technique [5,6], the small range searching technique can correct 4 more conditions for the first iteration differential and 3 more conditions for the second iteration differential, thus improving the probability and the complexity to find collisions. The whole attack on the MD5 can be accomplished within 5 hours using a PC with Pen-tium4 1.70GHZ CPU.

Note: add 5 tables.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
MD5collisionhash functions
Contact author(s)
luckyaa @ sjtu edu cn
History
2005-11-24: revised
2005-11-23: received
See all versions
Short URL
https://ia.cr/2005/425
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/425,
      author = {Jie Liang and Xuejia Lai},
      title = {Improved Collision Attack on Hash Function MD5},
      howpublished = {Cryptology ePrint Archive, Paper 2005/425},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/425}},
      url = {https://eprint.iacr.org/2005/425}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.