Improved Collision Attack on Hash Function MD5

• 作 者: Jie Liang Xue-Jia Lai
• 机 构: Department of Computer Science and Engineering,Shanghai Jiao Tong University,Shanghai 200240,China
• 出 处: 计算机科学技术学报(英文版)
• 发表日期: 2007年1期
• 关键词: MD5 collision differential attack hash function

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 the Conference EUROCRYPT 2005.We found that the derived conditions for the desired collision differential path were not sufficient to guarantee the path to hold and that some conditions could be modified to enlarge the collision set.By using technique of small range searching and omitting the computing steps to check the characteristics in the attack algorithm, we can speed up the attack of MD5 efficiently.Compared with the Advanced Message Modification technique presented by Wang et al.,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 Pentium4 1.70GHz CPU.