Paper 2006/104

Fast Collision Attack on MD5

Marc Stevens

Abstract

In this paper, we present an improved attack algorithm to find two-block collisions of the hash function MD5. The attack uses the same differential path of MD5 and the set of sufficient conditions that was presented by Wang et al. We present a new technique which allows us to deterministically fulfill restrictions to properly rotate the differentials in the first round. We will present a new algorithm to find the first block and we will use an algorithm of Klima to find the second block. To optimize the inner loop of these algorithms we will optimize the set of sufficient conditions. We also show that the initial value used for the attack has a large influence on the attack complexity. Therefore a recommendation is made for 2 conditions on the initial value of the attack to avoid very hard situations if one has some freedom in choosing this initial value. Our attack can be done in an average of about 1 minute (avg. complexity $2^{32.3}$) on a 3Ghz Pentium4 for these random recommended initial values. For arbitrary random initial values the average is about 5 minutes (avg. complexity $2^{34.1}$). With a reasonable probability a collision is found within mere seconds, allowing for instance an attack during the execution of a protocol.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
MD5collisiondifferential cryptanalysis
Contact author(s)
m m j stevens @ student tue nl
History
2006-03-19: received
Short URL
https://ia.cr/2006/104
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/104,
      author = {Marc Stevens},
      title = {Fast Collision Attack on MD5},
      howpublished = {Cryptology ePrint Archive, Paper 2006/104},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/104}},
      url = {https://eprint.iacr.org/2006/104}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.