Re: "Collision for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"
From: Rob Warnock (rpw3_at_rpw3.org)
Date: Mon, 30 Aug 2004 07:33:20 -0500
Peter Pearson <firstname.lastname@example.org> wrote:
| Dr. Robert Meier wrote:
| > "Collision for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"
| > by Xiaoyun Want, Dengguo Feng, Xuejia Lai, and Hongbo Yu 2004.08.17
| Indeed, at the annual IACR cryptography conference in Santa Barbara
| last week, this was the Year of Doom for cryptographic hash functions.
| Not only did this obscure Chinese team burst forth
| and deal the death blow to their handful of respected algorithms,
| but Antoine Joux produced the first collision ever for SHA-0.
For those interested in more details, in the past few days there
have been several *long* threads on "sci.crypt" about these events.
Look for these subject lines [with/without "Re:" in front]:
Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD
Any advance news from the crypto rump session?
RIPEMD broken, *NOT* RIPEMD-128 and RIPEMD-160
MD5 collisions in convenient form
Outrageous claims on cash collision exploits???
HMAC-MD5 not vulnerable?
A bad day at the hash function factory
Chinese researchers break MD4, MD5, HAVAL-128 and RIPMED
Bet on SHA-1 resistance to collisions!
Collision in SHA-0
Collision in SHA-0 - concerns for SHA-1
CRYPTO2004 Rump Session Presentations
These go into great detail on the SHA-0 and MD5 collisions
(especially the latter).
| All these breaks take the form of "I can find two strings whose
| hashes are the same." None of them takes the form of "I can find
| a string whose hash matches some predetermined value."
Correct. Difficulty in the former is called "collision resistance",
and that is what has been broken (somewhat, see below). Difficulty
in the latter is called "(1st) preimage resistance", though what
you probably meant to say was "I can find a *different* string whose
hash matches that of some predetermined string", difficulty with
which is called "2nd preimage resistance", and while that appears
somewhat weakened too [see the details on the collision break below],
I'm not sure it's "broken" yet.
The MD-5 collisions found (*multiple* pairs were published, by the way)
were all of an extremely limited form: Given a random 1024-bit block
(128 bytes), flip six bits in very certain specific positions. The
original and modified blocks now have a higher-than-expected probability
(something like 2**-48 instead of 2**-64) of having the same MD5 hash.
Note that while it would take a very long time to find a colliding pair
if you just picked a random starting block, ran MD5 on it, flipped the
magic six bits, ran MD5 on *that*, and compared the hashes (~8 yrs, for
a medium-speed single-CPU machine), there is apparently a trick for
looking inside the hash as it's working that lets you find the first
half of the "random" block in about an hour, and the second half in
just a few minutes more [per Matt Mahoney, in "sci.crypt"]. As Mahoney
says, since you may have to look at a *lot* of blocks to find one that
"It would be hard to exploit this in a text document, but it
would be easy to write two programs that do whatever you want
and that have the same MD5 checksum."
The trick would be getting people to accept that the first one was
something they wanted to download & run, and only then substitute
the second one for it.
| Similarly, if you are checking the MD5 hash of downloaded code,
| and the expected hash value is published by somebody you trust,
| you are still safe.
Not necessarily. An attacker *might* be able to find a 128-byte
section of some existing program where flipping the magic six bits
*both* left the MD5 has unchanged *and* changed the behavior of
the program in a way that you wouldn't like. Granted, it's *very*
unlikely, but we now know it's not impossible. Fortunately, testing
whether any particular existing binary file is susceptible to that
attack is fairly simple & quick [just loop over the file, flipping
the magic six bits in successive 128-byte blocks, and seeing if the
MD5 hash changed or not -- if not, you have a potential problem].
Rob Warnock <email@example.com>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607