Re: MD5 and SHA-1 Digest: What is the probability of repeating hash-values?

From: Jim Gillogly (jim_at_acm.org)
Date: 10/27/03 

Date: Mon, 27 Oct 2003 21:53:32 GMT

Anton Spaans wrote:
> But i was asking how well MD5 'spreads' all the possible original messages
> over these 2^128 possible hash-values.
> As i came to understand: 'pretty' well. ;-)

That's both stronger and weaker than I would put it. I'd say rather
that we have no reason to believe that MD5 doesn't spread the hash
values very well. That is, so far as I know we don't have theory
to say whether it's spread "pretty well" or even "moderately well",
but also no evidence to say that it's worse than "very well". It's
not even clear what that means: for example, for some applications
you might be made nervous by an n-bit hash function that assigns
each n-bit integer to a different hash value rather than spreading
them out more "randomly"; for others you'd prefer this feature, and
perhaps use an n-bit block cipher with secret key to accomplish it. 

-- 
	Jim Gillogly

Relevant Pages

  • Hash function, Birthday paradox and probabilities.
    ... background but I think this is mainly a probability theory problem. ... return an hash of length N bits ... that takes as input a bit string of length L ... and how to minimize the "spread" of m around its average. ...
    (sci.math)
  • Re: Hashtable efficiency (was: Re: Over-riding equals method dilemma)
    ... >> good a hash that is will depend on the implementation of the JVM. ... >> will not have as much spread as the programmer might naively expect. ... codes, thus fuller buckets because the codes aren't different. ... FirstSQL/J Object/Relational DBMS ...
    (comp.lang.java.programmer)
  • Re: BSD license compatible hash algorithm?
    ... in such a manner as to give a good spread. ... your using a very primitive hash like Knuth's multiplication one.... ... about sixty thousand orders of magnitude. ...
    (freebsd-hackers)
  • Hashtable efficiency (was: Re: Over-riding equals method dilemma)
    ... > good a hash that is will depend on the implementation of the JVM. ... > I have seen real problems caused by this issue; ... but I can't imagine why the spread of the hash codes ...
    (comp.lang.java.programmer)
  • Re: Key Hashing
    ... What is the best function to perform a key hash? ... uint32 psm_hashkey ... A problem with modulus hashing is scalability. ... the 32 bits into n-bit pieces that are xor'ed ...
    (comp.programming)