Paper 2005/400

Improved Collision Attack on MD5

Yu Sasaki, Yusuke Naito, Noboru Kunihiro, and Kazuo Ohta

Abstract

In EUROCRYPT2005, a collision attack on MD5 was proposed by Wang et al. In this attack, conditions which are sufficient to generate collisions (called ``sufficient condition") are introduced. This attack raises the success probability by modifing messages to satisfy these conditions. In this attack, 37 conditions cannot be satisfied even messages are modified. Therefore, the complexity is $2^{37}$. After that, Klima improved this result. Since 33 conditions cannot be satisfied in his method, the complexity is $2^{33}$. In this paper, we propose new message modification techniques which are more efficient than attacks proposed so far. In this method, 29 conditions cannot be satisfied. However, this method is probabilistic, and the probability that this method work correctly is roughly 1/2. Therefore, the complexity of this attack is $2^{30}$. Furthermore, we propose a more efficient collision search algorithm than that of Wang et al. By using this algorithm, the total complexity is reduced into roughly 5/8.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
MD5collision attackmessage modificationsufficient condition
Contact author(s)
yu339 @ ice uec ac jp
History
2005-11-14: received
Short URL
https://ia.cr/2005/400
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/400,
      author = {Yu Sasaki and Yusuke Naito and Noboru Kunihiro and Kazuo Ohta},
      title = {Improved Collision Attack on MD5},
      howpublished = {Cryptology ePrint Archive, Paper 2005/400},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/400}},
      url = {https://eprint.iacr.org/2005/400}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.