Cryptology ePrint Archive: Report 2006/074

How to Construct Sufficient Condition in Searching Collisions of MD5

Yu Sasaki and Yusuke Naito and Jun Yajima and Takeshi Shimoyama and Noboru Kunihiro and Kazuo Ohta

Abstract: In Eurocrypt 2005, Wang et al. presented a collision attak on MD5. In their paper, they intoduced �gSufficient Condition�h which would be needed to generate collisions. In this paper, we explain how to construct sufficent conditions of MD5 when a differential path is given. By applying our algorithm to a collision path given byWang et al, we found that sufficient conditions introduced by them contained some unnecessary conditions. Generally speaking, when a differential path is given, corresponding sets of sufficient conditions is not unique. In our research, we analyzed the differential path found by Wang et al, and we found a different set of sufficient conditions from that of Wang et al. We have generated collisions by using our sifficient conditions.

Category / Keywords: secret-key cryptography / MD5,Collision Attack,Sufficient Condition

Date: received 24 Feb 2006

Contact author: yu339 at ice uec ac jp

Available formats: PDF | BibTeX Citation

Version: 20060224:223758 (All versions of this report)

Discussion forum: Show discussion | Start new discussion