Improved Collision Attack on Hash Function MD5

Jie Liang; Xuejia Lai

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: MD5 collision hash 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: 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},
      url = {https://eprint.iacr.org/2005/425}
}