Paper 2006/074

How to Construct Sufficient Condition in Searching Collisions of MD5

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


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
MD5Collision AttackSufficient Condition
Contact author(s)
yu339 @ ice uec ac jp
2006-02-24: received
Short URL
Creative Commons Attribution


      author = {Yu Sasaki and Yusuke Naito and Jun Yajima and Takeshi Shimoyama and Noboru Kunihiro and Kazuo Ohta},
      title = {How to Construct Sufficient Condition in Searching Collisions of MD5},
      howpublished = {Cryptology ePrint Archive, Paper 2006/074},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.