Re: MD5 To Be Considered Harmful Someday

[Dragos Ruiu <dr () kyx net>]

On December 7, 2004 04:13 pm, Tim wrote:
> > Unfortunately when "The Press" publicized the MD5 hash discovery by Joux
> > and Wang it almost sounded like "The Press" was surprised to find
> > collisions in the MD5 domain (intuitive to me, a limited number of
> > outputs and a infinite number of inputs = Collisions).  I assume that a
> > "good" hash would have a even distribution of collisions across the
> > domain and that the larger number of bits for the output the better the
> > hash (assuming no cryptographic algorithm errors).
>
> Yes, collisions are a fact of life with message digests.  However, being
> able to efficiently *predict* how to create a collision between two
> messages is very bad for the security of a hash.  Suppose you and I
> agree to a contract, and I have you digitially sign a hash of it.
> Unbeknownst to you, I had earlier created a second contract with
> different wording, but which also hashes to the same value.  Due to the
> slowness of public key, most digital signatures are performed on a
> digest of the original document.
>
> I have both sources at my disposal from the beginning in this attack,
> and am able to tweak each before giving you one (eg add whitespace,
> comments in markup language used...).


Which brings up a good point: Proving the existence of collisions is not the
same thing as being able to predict the collisions.

Dan, your attack application(s) presumes that there is a way to predict
the collisions in a general form, and more so is primarily useful only
if there is a way to predict collisions for ANY arbitrary hash.

AFAIK the only thing proven so far is that there are collisions, and though
this certainly increases the probability of a generalized collision method,
it is not discovered/documented yet.

Your proposal is an interesting application(s) of collisions - and certainly
does much to dispel some of the belittling of the collision discovery.
However the extent of the collisionabililty (collideability?) of md5
is still under debate afaik... feel free to correct me if I am wrong.

It may still be a little early to prepare applications for something we 
haven't discovered yet - though we can have a debate on the likelyhood of
this discovery again over tequila at your leisure :-). It's a neat attack
scenario, certainly worth consideration, and you bring up
a number of interesting points about md5, but without the 
collision logic it remains a theoretical concern for education
and a future attack vector caveat.

cheers,
--dr

-- 
World Security Pros. Cutting Edge Training, Tools, and Techniques
Vancouver, Canada       May 4-6 2005  http://cansecwest.com
pgpkey http://dragos.com/ kyxpgp