MD5: hashing, > 1->1

-----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@owlnet.rice.edu

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

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

Karl Lui Barrus says:
> 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).

You can engineer them, actually.

Imagine that you had a 64 bit hash function, and the birthday paradox
thus provided you with a 2^32 difficulty in finding a collision.

Prepare two versions of the document you want to fake the signature
on. Adjust the documents over and over again (trivia like spacing will
do -- find 32 locations and either add or don't add a space) until you
get a colliding pair of hashes. 

This illustrates that hash collisions are actually quite a problem if
you have an insufficiently large hash.

Perry