"Collision for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"

A friend of mine pointed me at a recent paper.

"Collision for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"
by Xiaoyun Want, Dengguo Feng, Xuejia Lai, and Hongbo Yu
2004.08.17
http://eprint.iacr.org/2004/199/

They claim ability to generate
an arbitrary count of
md5 128b collision pairs
in about 15s (after a one-time 1hr procedure)
on an IBM P690
for any initialization vector

I am unfamilar with the performance numbers for a P690, but believe
this implies a dramatic reduction (to 31b or less) in the strength
of md5.

Is the above correct?
What am I missing?

TIA,
--
Dr. Robert J. Meier
Server Vantage Agent Infrastructure

Dr. Robert Meier wrote:

> A friend of mine pointed me at a recent paper.
>
> "Collision for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"
> by Xiaoyun Want, Dengguo Feng, Xuejia Lai, and Hongbo Yu
> 2004.08.17
> http://eprint.iacr.org/2004/199/
>
> They claim ability to generate
> an arbitrary count of
> md5 128b collision pairs
> in about 15s (after a one-time 1hr procedure)
> on an IBM P690
> for any initialization vector
>
> I am unfamilar with the performance numbers for a P690, but believe
> this implies a dramatic reduction (to 31b or less) in the strength
> of md5.
>
> Is the above correct?
> What am I missing?
>
> TIA,

What strength ? None of these are encyryption functions, they are
hashes.Collisions are guaranteed (though theoretically rare)

If you want to improve probability of signature "uniqueness" use several of
them.
--
+---+
| n | www.n-gate.net
+---+

Angus Marshall wrote:
> Dr. Robert Meier wrote:
>>A friend of mine pointed me at a recent paper.
>>
>>"Collision for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"
>>by Xiaoyun Want, Dengguo Feng, Xuejia Lai, and Hongbo Yu
>>2004.08.17
>>http://eprint.iacr.org/2004/199/
>>
>> [snip]
>
>
> What strength ? None of these are encyryption functions, they are
> hashes.Collisions are guaranteed (though theoretically rare)
>
> [snip]

They're not encryption functions, but they are cryptographic functions.
The point of the works cited is that collisions may not be so rare.

http://www.securityfocus.com/news/9363

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
> http://eprint.iacr.org/2004/199/
>
[snip]
> I am unfamilar with the performance numbers for a P690, but believe
> this implies a dramatic reduction (to 31b or less) in the strength
> of md5.
>
> Is the above correct?
> What am I missing?

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.
SHA-1 remains undefeated, but at this point I doubt any cryptologist
would bet his life that it won't succumb to a similar disease. Faith
in hash-function design strategies has been badly shaken.

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." Thus, the
degree of your alarm depends on the manner in which you're using
hash functions. For example, if you write a document and sign it
(which usually means signing its hash value), you're still safe.
In contrast, if somebody presents you with a document to sign, and
the document looks innocuous, you have to worry that he has *another*
document with the same hash, less innocuous, which you will also in
effect be signing.

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.

Hope this helps.

Peter

--
To email me, replace the three words with
the letters R, C, and N.

In article <10iljmmbapdrn8b@corp.supernews.com>, Peter Pearson wrote:

> 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."

I can't see a way for the former attack to be of any benefit
when trying to suborn HMAC (RFC 2104), and even the latter attack
(should someone discover one) would be very hard to apply, since
the attacker wouldn't know the initialization vector (actually
vectors since there are two rounds in HMAC). This is even asserted
in the RFC.

But am I missing something? I wouldn't be too surprised...

--

Sincerely,

Ray Ingles (313) 227-2317

The above opinions are probably not those of Compuware Corp.
Yet.

Ray Ingles wrote:

> In article <10iljmmbapdrn8b@corp.supernews.com>, Peter Pearson wrote:
>
>> 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."
>
> I can't see a way for the former attack to be of any benefit
> when trying to suborn HMAC (RFC 2104), and even the latter attack
> (should someone discover one) would be very hard to apply, since
> the attacker wouldn't know the initialization vector (actually
> vectors since there are two rounds in HMAC). This is even asserted
> in the RFC.
>
> But am I missing something? I wouldn't be too surprised...

No, your analysis is fine: HMAC still looks strong. The crypto
community, however, had become awfully fond of assuming that
reputable hash functions were equivalent to "random oracles"
(see below). The discovery that some of the best designs failed to
achieve this goal makes everybody worry that other important
assumptions may also be wrong. Other cryptographic dam-breaks
have been preceded by innocent-looking trickles.

A Random Oracle is a hypothetical construct, accessible to all
parties including adversaries, who takes an input string and looks
it up in a big book. If there's an entry for that string in the
book, the Result recorded for that string is returned; otherwise,
a Result is generated by flipping a coin, recorded, and returned.
The desired property is that the result gotten for one string is
completely uncorrelated with the results gotten for all other strings.
Random oracles are useful in proofs of security.

--
To email me, replace the three words with
the letters R, C, and N.

Peter Pearson <ppearson@are.see.enn.com> 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
works:

"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

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607