[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: MD5 collisions found - alternative?

On Wed, Aug 25, 2004 at 10:01:25AM +0100, Dale Amon wrote:
> On Wed, Aug 25, 2004 at 06:02:22AM +0200, Almut Behrens wrote:
> > Somewhat more seriously: are there generally any defining criteria for
> > something one would call a 'hash function', saying that it always must
> > map some larger input space to some smaller output space?
> Yes. A hash function is any mapping function
> 	y = map(x)
> where the space y is smaller than the space x. 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. 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.
> 	* randomness. Input strings which differ by 1 bit in any
> 	  position generate hash keys a random distance apart

Add to that:

* An output dependence on both the value and position of *every* input byte.

Kind of implied by your second postulate, but worth mentioning explicitly.
Especially when people think that a simple sum is cryptographically sound --
any combination of the input letters (or other matching combinations) will
produce the same hash value.

- Matt

Attachment: signature.asc
Description: Digital signature

Reply to: