Re: MD5 To Be Considered Harmful Someday

[Tim <tim-security () sentinelchicken org>]

> From my reading it appears that you need the original source to create the
> doppelganger blocks.  It also appears that given a MD5 hash you could not
> create a input that would give that MD5 back.  Passwords encoded with MD5
> would not fall prey to your discovery.  Is this correct?

Correct, it sounds as though the attacks are not a first preimage
attack.  However, first preimage resistance is a necessary but not
sufficient condition for security.  I have not read the paper yet, but I
imagine most of these results would imply either second preimage, or
collision insecurity.

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

good day,
tim