International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Improved Collision Attack on Hash Function MD5

Authors:
Jie Liang
Xuejia Lai
Download:
URL: http://eprint.iacr.org/2005/425
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12758,
  title={Improved Collision Attack on Hash Function MD5},
  booktitle={IACR Eprint archive},
  keywords={MD5,collision,hash functions},
  url={http://eprint.iacr.org/2005/425},
  note={ luckyaa@sjtu.edu.cn 13111 received 23 Nov 2005, last revised 23 Nov 2005},
  author={Jie Liang and Xuejia Lai},
  year=2005
}