Re: MD5 collisions found - alternative?

[Dale Amon <amon@vnl.com>]

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
	  
While these features are also useful in writing assembler
and compilers, they are not *that* important. I've often
used hash functions as simple as:

	"add the first 8 chars and take the low byte
	 of the integer summand."

Obviously not cryptographic.

-- 
------------------------------------------------------
   Dale Amon     amon@islandone.org    +44-7802-188325
       International linux systems consultancy
     Hardware & software system design, security
    and networking, systems programming and Admin
	      "Have Laptop, Will Travel"
------------------------------------------------------