Results of the MD5 collision program and implications
MD5 has been seriously broken for a while, but when I saw the news that
Patrick Stach has posted super-efficient collision-generating code, I was surprised that it was
that broken. I tried the code on a few boxes, and generally had trouble getting it to finish in the time my patience allotted me, but Matt Miller did get it to produce results:
$ time ./md5coll
block #1 done
block #2 done
unsigned int m0[32] = {
0x298640cf, 0x60bd40e2, 0xf2d40369, 0x2883fcb5,
0x5c85f76d, 0x35336462, 0xca28a356, 0xd355d92c,
0x0634ed41, 0x62120dff, 0xa172ecd7, 0x8eb22b63,
0xb9b99104, 0x34698bfa, 0x80ab939e, 0x705166dd,
0x287db57a, 0x52d249c7, 0x6ab58d44, 0xe3e7f0e3,
0xb6cedb4a, 0xfdab2203, 0x36b6dd1a, 0x90054d51,
0x0d3b3725, 0xeb3bd937, 0x87df3006, 0xbd2af47b,
0x7fbaecc0, 0xa494156b, 0xc8e0ec64, 0xfdb9a844,
};
unsigned int m1[32] = {
0x298640cf, 0x60bd40e2, 0xf2d40369, 0x2883fcb5,
0xdc85f76d, 0x35336462, 0xca28a356, 0xd355d92c,
0x0634ed41, 0x62120dff, 0xa172ecd7, 0x8eb2ab63,
0xb9b99104, 0x34698bfa, 0x00ab939e, 0x705166dd,
0x287db57a, 0x52d249c7, 0x6ab58d44, 0xe3e7f0e3,
0x36cedb4a, 0xfdab2203, 0x36b6dd1a, 0x90054d51,
0x0d3b3725, 0xeb3bd937, 0x87df3006, 0xbd2a747b,
0x7fbaecc0, 0xa494156b, 0x48e0ec64, 0xfdb9a844,
};
real 239m18.508s
user 238m34.440s
sys 0m3.390s
Well, that's nice, isn't it? But what does this mean? Well, it means that MD5 is no longer useful as a signature hash: it is no longer the case that you can believe that a person's signed document is identical to your version of that document, even if the checksum matches. More implications of collisions can be found in cryptography.com's Hash Collision Q&A.
These attacks are not, however, preimage attacks. That means that it is still infeasible for an attacker to generate a particular input to a hash function that is guaranteed to produce a particular output. Because of this, many applications, such as the HMAC-related protocols, are unaffected by this break. Still, Schneier reported a 2^106 preimage attack against SHA-1 that is a hell of a lot under the 2^160 work that would be expected by brute force. Totally completely impractical at the moment, but worth keeping in the back of your mind regardless, particularly if you're designing a cryptosystem.