$10M breaks MD5 in 24 days

I am not attending the Crypto conference, but I sat in on the evening
"rump session" the other day.  One of the more interesting papers had
a claim (with little detail, unfortunately) that for ten million dollars
you could build a machine that would "break" MD5, in the sense of finding
another message which would hash to the same as a chosen one, in 24
days.  This result did not depend on any internal structure in MD5, but
was purely a result of the hash size (128 bits) and the time it takes
to calculate a hash.

The main new result which allowed this was a more efficient way of
handling a parallel search for collisions (two messages which hash to
the same thing).  In some earlier methods, n machines provide only a
sqrt(n) speedup.  The new method improves this, although my notes don't
show exactly how close they come to an n-fold speedup.

The Secure Hash Standard (SHS, aka SHA) is, they said, 64K times slower,
hence this technique would take 64K times longer (or cost ~64K times
more?) to break that hash.

I don't think this is probably anything to really worry about, but
maybe it points out a need for a longer hash in the next few years.

Hal

P.S. The paper was by Paul C. van Oorschot & Michael J. Wiener.

> One of the more interesting papers had a claim (with little detail,
> unfortunately) that for ten million dollars you could build a machine that
> would "break" MD5, in the sense of finding another message which would
> hash to the same as a chosen one, in 24 days.

This in itself wouldn't give an attacker much of anything would it?  I 
mean, once they discovered a message which hashed to a given value, the 
new message wouldn't be in the proper format, would it?  Wouldn't it just 
be noise, instead of text in english, crypto keys, etc.?

On Aug 25,  7:01pm, alex wrote:
> Subject: Re: $10M breaks MD5 in 24 days
> > One of the more interesting papers had a claim (with little detail,
> > unfortunately) that for ten million dollars you could build a machine that
> > would "break" MD5, in the sense of finding another message which would
> > hash to the same as a chosen one, in 24 days.

> This in itself wouldn't give an attacker much of anything would it?  I
> mean, once they discovered a message which hashed to a given value, the
> new message wouldn't be in the proper format, would it?  Wouldn't it just
> be noise, instead of text in english, crypto keys, etc.?

Not necessarily.  If you're forging some packet, certificate or file, it is
often adequate to have just a couple of fields (potentially a few bits)
which contain data you want, and the rest can be garbage.  If your search
engine could fix these and play with the rest of the packet, the chances are
good (but decreasing with the more bits you use for a fixed size packet) that
you will find a packet which will have the correct signature _and_ contain the
forged data you need.  If you can play with the packet size, then your chances
of finding a match increase.

							Ian.

alex says:
> > One of the more interesting papers had a claim (with little detail,
> > unfortunately) that for ten million dollars you could build a machine that
> > would "break" MD5, in the sense of finding another message which would
> > hash to the same as a chosen one, in 24 days.
> 
> This in itself wouldn't give an attacker much of anything would it?  I 
> mean, once they discovered a message which hashed to a given value, the 
> new message wouldn't be in the proper format, would it?  Wouldn't it just 
> be noise, instead of text in english, crypto keys, etc.?

Schneier has a good discussion of this. Suffice it to say, if I have a
magic collision search box, I might very well be able to produce an
interesting result very easily.

Imagine the existance or nonexistance of a space at some number of
locations in a document as being a bit. Then, imagine that I have a
hash signed by you. If I can search very fast, I could compose a
contract that you never signed, and search through the trivial
variations of that contract with spaces present or absent at some
number of points. I can thus trivially generate the number of
variations on the contract needed to find a collision -- if I can only
search those variations fast enough you lose.

Given that ten million dollars isn't real money, if this is true MD5
isn't worth that much any longer -- it certainly isn't safe for use in
signing digital drafts, for example.

Perry

Hal says:
> The Secure Hash Standard (SHS, aka SHA) is, they said, 64K times slower,
> hence this technique would take 64K times longer (or cost ~64K times
> more?) to break that hash.

Well, I suppose this demonstrates that the NSA knew what they were
doing when they set the SHA's length to 160 bits. Let it never be said
that they aren't right on top of everything...

Perry

>Well, I suppose this demonstrates that the NSA knew what they were
>doing when they set the SHA's length to 160 bits. Let it never be said
>that they aren't right on top of everything...

On the other hand, I can't imagine that NSA is unaware that strong
cryptographic hash functions designed for authentication are also
useful building blocks for a confidentiality cipher. Which might make
them less than wholly enthusiastic about doing their best on a public
standard like SHA.

Caveat emptor NSA. (John Cleese, if you're out there, feel free to
correct my Latin).

Phil

Phil Karn says:
> >Well, I suppose this demonstrates that the NSA knew what they were
> >doing when they set the SHA's length to 160 bits. Let it never be said
> >that they aren't right on top of everything...
> 
> On the other hand, I can't imagine that NSA is unaware that strong
> cryptographic hash functions designed for authentication are also
> useful building blocks for a confidentiality cipher. Which might make
> them less than wholly enthusiastic about doing their best on a public
> standard like SHA.

True enough. However, we don't have a lot of alternatives right now.
MD6, anyone?

.pm