What was the first MD5 collision ever constructed?

Question

We all know that MD5's collision resistance is severly broken.

But when thinking of "random" strings with great cryptographic importance I've come up with NIST's curve seeds and MD5 collisions. But for this to really work out I'd need the most famous MD5 collision.

So I'm asking: What is the most famous MD5 collision?

As for the definition of famous: The very first published MD5 collision is considered "the most famous" with the only exception of one collision having occured a lot more often and having spread a lot more due to important historical events (Flame?) and being generally considered the most famous one.

Answer 1

The first publication of an MD5 collision was on 17-Aug-2004 17:44 UTC on the eprint archive server: Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (third version). The results where fresh: the authors had just corrected IV endianness, that they got reversed in two earlier versions. Like 8 hours later, the results where presented at the Crypto 2004 Rump Session.

The (first half) of their table showing the first MD5 collision was:
The hurry in which this was prepared shows: the names for messages blocks and halves is inconsistent; the leading zero of some 32-bit values is missing; the 32-bit values are to be converted to bytes in little-endian order, but that's left unstated; $H$ is not an MD5 hash, but the internal result after hashing two 512-bit blocks before hashing the padding.

The notoriety of this message pair is apparent when Googling its actual MD5 hash a4c0d35c95a63a805915367dcfe6b751.

It was quite thrilling when late on 17-Aug-2004 (in Paris, thus still slightly before the rump session) I verified this result, announced it on sci.crypt, made a zip with two distinct files for which md5sum was giving the above hash, and posted it to the forum for the md5crk project (mailing list archives). Perhaps theses are the oldest files online with identical MD5 hashes. Googling md5col.zip file0 file1 brings back other hits, including this.

The later peer-reviewed paper explaining the technique is: Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, in proceedings of Eurocrypt 2005.

Answer 2

Even though Dobbertin could not provide a real collision of MD5, I would say that Hans Dobbertin first publicly described MD5 collision(s) in "The Status of MD5 After a Recent Attack" (PDF) – that was in 1996. To the best of my knowledge he was one of the first who recommended to no longer use MD5 when collision-resistance is needed/expected/required.

On the other hand, the most famous is probably described by Xiaoyun Wang and Hongbo Yu in their paper called "How to Break MD5 and Other Hash Functions" (PDF) (Advances in Cryptology – Lecture Notes in Computer Science 3494. pp. 19–35.) which was published somewhere around 2004/2005 and the spear-head of dozens of alike papers which successively described optimized and related collision-attacks.

When you check their paper, you’ll quickly notice (page 1) that they also reference Dobbertin, which is why I think he should at least be mentioned in this context. His contribution provided the base.

From the paper by Wang and Yu:

Answer 3

I don't understand why this is important, but just want to note that the collision was first presented at the rump session at CRYPTO 2004, and was then later published. The earliest time-stamp is an ePrint report by Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu, called Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. The date is August 16, 2004. The formal publication was at EUROCRYPT 2005, about 9 months later.