MD5: hashing, > 1->1

[Karl Lui Barrus]

-----BEGIN PGP SIGNED MESSAGE-----

>> is based upon the fact that *finding* two messages that hash to the
>> same value is as difficult as a brute-force attack, which requires
>> 2^128 trials (maybe it's 2^127, but I don't think that really

> This is incorrect, with a large memory, this is the birthday paradox in 
> action, and it takes about 2^64 tries, which puts SHS right up there at 
> 2^80 same as skipjack.

Geez, I did it again (deleted the original message - the one Derek
sent).

So from memory, I beleive that in the context in which Derek was
describing the "finding two messages" above, his statement about the
difficulty (2^128) is correct.

The birthday paradox is the situation when you are looking for *any*
two messages that hash to the same value.  In this case, 2^64 is the
expected work.

However, if you are given a particular hash and you are looking for
another message which has the same hash, then the difficulty is 2^128.

This is the situation which is (more) important since it corresponds
to forging MD5 hashes for a signed message.  Say you are given a
message and you want to find another which has the same hash.  2^128
applies.

The birthday paradox situation corresponds to just finding two
messages with the same hash.  In this case the expected work is 2^64,
but then the two messages that you discover with the same hash may be
random (and thus worthless).

Karl Barrus
klbarrus at owlnet.rice.edu

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQCVAgUBLhnrj8SF/V8IjI8hAQGlmQP6AshYEwjoJGbN8cZZRiPAEdhZO9AAWG2Y
P08YcQ/wUWNEAOAvi4WISPobIWxO6oRk+fBRvUMWv7wyU4eRA/7yj95nlDaui5oW
rDaFrh+IBnC8Epce2hing6TqWdBxL5uKBCuq1CrKnUkDO2uESoZkN/aDpbnvueC9
05aqKfQ9P+U=
=Lscb
-----END PGP SIGNATURE-----