RE: MD5 To Be Considered Harmful Someday
Some things to note....
1 - Wang and Joux's attacks do not allow determination of original
inputs from a given hash.
2 - The interesting and newsworthy part of Wang's paper is not that
there are collisions in MD5 (and the other hash algs they produced
collisions for), but that they can produce colliding inputs by some
process other than random or bruteforce searching. They have some
method that allows them to produce colliding inputs at will with a
minimal amount of work - 32way 1.7ghz system produces unique 128byte
colliding texts in under 1.5hrs. They have proven this is more than just
random/bruteforce luck by providing two pairs of colliding inputs with
wrong initial values for MD5, and in the same day (at Crypto2004)
produced 2 new pairs of colliding inputs for the corrected MD5 init
values.
To truly understand the impacts of Wang's attacks, the actual collision
prediction/search method needs to be published. From the information
released so far, Wang is relying on very particular 128byte sequences
with bits flipped in 6 or 7 bit positions between the two 128 byte
sequences. It does not appear that a colliding input can be produced for
just any arbitrary input/text with this attack -- it appears the
original input needs to meet some very specific requirements to allow
creation of a colliding (alternate) input that will produce the same
output hash. More detail on Wang's alg/method is needed to know the full
extent of the applied impacts.
Regards,
Anton Rager
arager@xxxxxxxxx
-----Original Message-----
From: Gandalf The White [mailto:gandalf@xxxxxxxxxxx]
Sent: Tuesday, December 07, 2004 3:55 PM
To: Dan Kaminsky; BugTraq
Subject: Re: MD5 To Be Considered Harmful Someday
Greetings and Salutations:
On 12/6/04 5:29 PM, "Dan Kaminsky" <dan@xxxxxxxxxxx> wrote:
<snip>
> Some highlights from the paper:
> * The attack itself is pretty limited -- essentially, we can create
> "doppelganger" blocks (my term) anywhere inside a file that may be
> swapped out, one for another, without altering the final MD5 hash.
This
> lets us create any number of binary-inequal files with the same
md5sum.
>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?
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).
Thanks,
Ken
---------------------------------------------------------------
Do not meddle in the affairs of wizards for they are subtle and
quick to anger.
Ken Hollis - Gandalf The White - gandalf@xxxxxxxxxxx - O- TINLC
WWW Page - http://digital.net/~gandalf/
Trace E-Mail forgery - http://digital.net/~gandalf/spamfaq.html
Trolls crossposts - http://digital.net/~gandalf/trollfaq.html