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 "Sufficient Condition" 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 format(s): PDF | BibTeX Citation

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

Short URL:

[ Cryptology ePrint archive ]