BugTraq
MD5 To Be Considered Harmful Someday Dec 06 2004 11:29PM
Dan Kaminsky (dan doxpara com) (3 replies)
I've been doing some analysis on MD5 collision announced by Wang et al.
Short version: Yes, Virginia, there is no such thing as a safe hash
collision -- at least in a function that's specified to be
cryptographically secure. The full details may be acquired at the
following link:

http://www.doxpara.com/md5_someday.pdf

A tool, Stripwire, has been assembled to demonstrate some of the attacks
described in the paper. It may be acquired at the following address:

http://www.doxpara.com/stripwire-1.1.tar.gz

Incidentally, the expectations management is by no means accidental --
the paper's titled "MD5 To Be Considered Harmful Someday" for a reason.
Some people have said there's no applied implications to Joux and Wang's
research. They're wrong; arbitrary payloads can be successfully
integrated into a hash collision. But the attacks are not wildly
practical, and in most cases exposure remains thankfully limited, for
now. But the risks are real enough that responsible engineers should
take note: This is not merely an academic threat, systems designed with
MD5 now need to take far more care than they would if they were
employing an unbroken hashing algorithm, and the problems are only going
to get worse.

Some highlights from the paper:

* The attack itself is pretty limited -- essentially, we can create
"doppelganger" blocks (my term) anywhere inside a file that may be
swapped out, one for another, without altering the final MD5 hash. This
lets us create any number of binary-inequal files with the same md5sum.

* MD5 uses an appendable cascade construction -- in other words, if you
happen to find yourself with two files that MD5 to the same hash, an
arbitrary payload can be applied to both files and they'll still have
the same hash. This leads to...

* Attacks are possible using only the proof of concept test vectors
released by Wang -- the actual attack is not necessary.

* Stripwire emits two binary packages. They both contain an arbitrary
payload, but the payload is encrypted with AES. Only one of the
packages ("Fire") is decryptable and thus dangerous; the other ("Ice")
shields its data behind AES. Both files share the same MD5 hash.

* Digital Signature systems are vulnerable, as they almost always sign a
hashed representation of data rather than the data itself.

* This is an excellent vector for malicious developers to get unsafe
code past a group of auditors, perhaps to acquire a required third party
signature. Alternatively, build tools themselves could be compromised
to embed safe versions of dangerous payloads in each build. At some
later point, the embedded payload could be safely "activated", without
the MD5 changing. This has implications for Tripwire, DRM, and several
package management architectures.

* HMAC's invulnerability has been slightly overstated. It's definitely
possible, given the key, to create two datasets with the same HMAC.
Attacker possession of the key violates MAC presumptions, so the impact
of this is particularly questionable.

* Very interesting possibilities open up once the full attack is made
available -- among other things, we can create self-decrypting
executables (fire.exe and ice.exe) that exhibit differential behavior
based on their internal colliding payloads. They'll still have the same
MD5 hash.

* Several doppelgangers may (relatively quickly, as per Joux) be
computed within a single multicollision-friendly block. As such, the
particular selection of doppelganger sets within a file can itself be
made to represent data. It's relatively straightforward to embed a 128
bit signature inside an arbitrary file, in such a way that no matter the
value of the signature, a constant MD5 hash is maintained. This is
curiously steganographic.

* Many popular P2P networks (and innumerable distributed content
databases) use MD5 hashes as both a reliable search handle and a
mechanism to ensure file integrity. This makes them blind to any
signature embedded within MD5 collisions. We can use this blindness to
track MP3 audio data as it propagates from a custom P2P node.
"Strikeback" capacity against executable trafficking is even more
pronounced -- it's possible to create application installers that
self-modify with host identifying characteristics but still successfully
retransmit on P2P networks under the global search hash.

I hope this paper proves useful to the security community at large, and
I welcome feedback.

--Dan Kaminsky
www.doxpara.com
dan (at) doxpara (dot) com [email concealed]

[ reply ]
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 01:46AM
Joel Maslak (jmaslak antelope net) (2 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 09:19PM
Jack Lloyd (lloyd randombit net)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 08:43PM
Jack Lloyd (lloyd randombit net)
MD5 To Be Considered Harmful Today Dec 08 2004 01:39AM
Pavel Machek (pavel ucw cz) (1 replies)
Re: MD5 To Be Considered Harmful Today Dec 08 2004 10:23PM
Dan Kaminsky (dan doxpara com) (1 replies)
Re: MD5 To Be Considered Harmful Today Dec 08 2004 10:40PM
Pavel Machek (pavel ucw cz) (1 replies)
Re: MD5 To Be Considered Harmful Today Dec 08 2004 10:36PM
Dan Kaminsky (dan doxpara com)
Re: MD5 To Be Considered Harmful Someday Dec 07 2004 10:54PM
Gandalf The White (gandalf digital net) (4 replies)
RE: MD5 To Be Considered Harmful Someday Dec 08 2004 04:01AM
David Schwartz (davids webmaster com) (2 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 09:30PM
George Georgalis (george galis org) (1 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 09:44PM
Dan Kaminsky (dan doxpara com)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 04:36AM
Gandalf The White (gandalf digital net) (3 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 09:44PM
Keith Oxenrider (koxenrider sol-biotech com)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 09:17PM
Solar Designer (solar openwall com) (1 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 10:03PM
Dan Kaminsky (dan doxpara com) (2 replies)
Re: MD5 To Be Considered Harmful Someday Dec 11 2004 07:26PM
Solar Designer (solar openwall com)
Re: MD5 To Be Considered Harmful Someday Dec 09 2004 01:47AM
Pavel Kankovsky (peak argo troja mff cuni cz)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 08:48PM
Paul Wouters (paul xtdnet nl) (2 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 11:23PM
Adam Shostack (adam homeport org)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 08:52PM
Dan Kaminsky (dan doxpara com) (1 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 09:05PM
Paul Wouters (paul xtdnet nl)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 01:51AM
Joel Maslak (jmaslak antelope net) (1 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 07:22PM
Steve Friedl (steve unixwiz net)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 12:13AM
Tim (tim-security sentinelchicken org) (2 replies)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 09:35PM
Dragos Ruiu (dr kyx net)
Re: MD5 To Be Considered Harmful Someday Dec 08 2004 06:52PM
David F. Skoll (dfs roaringpenguin com)
Re: MD5 To Be Considered Harmful Someday Dec 05 2004 11:04PM
Ruth A. Kramer (rhkramer fast net)


 

Privacy Statement
Copyright 2010, SecurityFocus