Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 10:01:25AM +0100, Dale Amon wrote:
>
> Hashing (think of cornbeef hash with things all chopped up into bits)
> is a technique to generate fast lookup keys. The discussion here is
> about cryptographic hash functions.
...and I think somewhere in between lie hashing functions like crc32,
as used for detecting transmission errors, for example. Those are
not cryptographic, but possess a sufficiently large output space, so we
can expect few random collisions for most practical purposes.
> I believe the primary difference is that a cryptographic hash is:
>
> * a uniform mapping. For input space n and output space m,
> there are on average n/m strings with the same hash key.
Right, but I believe that a uniform mapping _also_ is a desirable
property (besides speed, of course) of hashing functions as used to
compute table lookup indices -- as this property assures that the data
storage locations will be spread as evenly as possible across the
available buckets, which in turn minimizes the time spent on resolving
collisions (on average). And, as practical considerations in this case
always enforce a rather small output space (i.e. number of buckets)
we're certainly expecting collisions here. [1]
> * randomness. Input strings which differ by 1 bit in any
> position generate hash keys a random distance apart
I'd add:
* huge size of the output space (with its upper limit corresponding
to the number of bits of the hash value). The probability of
accidentally finding a collision is of course directly related to
the size of the output space (assuming a uniform mapping).
I think those are the basic properties that allow for the two desirable
features 'collision resistance' and 'onewayness', which we've been
discussing in this thread -- but I guess I'm not really telling you
anything new... ;)
If anyone knows of any other requirements, please feel free to chime
in... Well, OTOH, this would probably be getting a little off-topic for
debian-security (especially the debian aspect).
Almut
[1] for anyone who doesn't know it already, I'd recommend Bob Jenkins
page on hashing: http://burtleburtle.net/bob/hash/
Reply to: