How to Construct Sufficient Condition in Searching Collisions of MD5

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

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

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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: MD5 Collision Attack Sufficient Condition
Contact author(s): yu339 @ ice uec ac jp
History: 2006-02-24: received
Short URL: https://ia.cr/2006/074
License: CC BY

BibTeX

@misc{cryptoeprint:2006/074,
      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},
      url = {https://eprint.iacr.org/2006/074}
}