From: Hal <hfinney@shell.portal.com>
Date: Thu, 25 Aug 94 13:58:33 PDT
To: cypherpunks@toad.com
Subject: $10M breaks MD5 in 24 days
Message-ID: <199408252058.NAA12488@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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.