From: "Perry E. Metzger" <perry@imsi.com>
Date: Thu, 25 Aug 94 17:37:35 PDT
To: cypherpunks@toad.com
Subject: Re: $10M breaks MD5 in 24 days
In-Reply-To: <199408260001.TAA00715@omaha.omaha.com>
Message-ID: <9408260037.AA05604@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



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