Paper 2012/040

Single-block collision attack on MD5

Marc Stevens

Abstract

In 2010, Tao Xie and Dengguo Feng [ePrint 2010/643] constructed the first single-block collision for MD5 consisting of two 64-byte messages that have the same MD5 hash. Details of their attack, developed using what they call an evolutionary approach, has not been disclosed ``for security reasons''. Instead they have posted a challenge to the cryptology community to find a new different single-block collision attack for MD5. This paper answers that challenge by presenting a single-block collision attack based on other message differences together with an example colliding message pair. The attack is based on a new collision finding algorithm that exploits the low number of bitconditions in the first round. It uses a new way to choose message blocks that satisfy bitconditions up to step 22 and additionally uses three known tunnels to correct bitconditions up to step 25. The attack has an average runtime complexity equivalent to $2^{49.8}$ calls to MD5's compression function.

Note: http://marc-stevens.nl/research/md5-1block-collision/

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
marc @ marc-stevens nl
History
2012-01-29: revised
2012-01-29: received
See all versions
Short URL
https://ia.cr/2012/040
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/040,
      author = {Marc Stevens},
      title = {Single-block collision attack on MD5},
      howpublished = {Cryptology ePrint Archive, Paper 2012/040},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/040}},
      url = {https://eprint.iacr.org/2012/040}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.