Cryptology ePrint Archive: Report 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.

Category / Keywords: MD5,collision,hash functions

Date: received 23 Nov 2005, last revised 23 Nov 2005

Contact author: luckyaa at sjtu edu cn

Available format(s): PDF | BibTeX Citation

Note: add 5 tables.

Version: 20051124:052030 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]