In article <453a5c6d$0$1142$39db0f71@[EMAIL PROTECTED]
>, Taneli Huuskonen wrote:
> Je 2006-10-20, soneill@[EMAIL PROTECTED]
<soneill@[EMAIL PROTECTED]
>
skribis:
>
>> validator for that message. I believe that an alogrithm like MD5, for
>> example, which produces a 128-bit hash, is guaranteed not to produce
any
>> collisions for strings up to 2^64 bits in length. If the messages
produced by
>> your system are shorter than that, then the MD5 hash value accompanying
a
>> message can almost certainly be accepted as the correct validator for
that
>> message.
>
> I'm afraid you're confusing two things. Any 128-bit hash is guaranteed
> to produce collisions for some strings no longer than 129 bits. On the
> other hand, if you pick substantially less than 2^64 different strings
> at random, no matter what their lengths, then a good 128-bit hash is
> unlikely to produce collisions among the strings. The exact meaning of
> "substantially less" can be calculated given the exact meaning of
> "unlikely" and vice versa.
>
> Taneli Huuskonen
You're right about the confusion. It's been a while since I read the
description of MD5, so I misremembered what Rivest said about the
probablility
of collisions. I found my copy of RFC 1321, and in his summary he
_conjectures_ that finding two messages with the same hash is on the order
of
2^64 operations, and that finding a message with a given hash is on the
order
of 2^128 operations. That was in 1992, before any method of forcing a
collision had been found, so the validity of his conjectures may be open
to
question. OTOH, a ha****ng function like SHA-256 has no known
vulnerabilities
at present, so a message authenticated with it would seem to have almost
no
chance of being false or in error.
SJO
|
