Re: Odds of Recurrence for Hash Function

   From: "Fidelis Assis" <[email protected]>

   On Wed, Dec 3, 2008 at 6:20 PM, Bill Yerazunis <[email protected]> wrote:
   >
   >   From: Chris Babcock <[email protected]>
   >
   >   Since the hash is a finite size and there are an infinite number of
   >   possible content bodies, I'm assuming that there is a risk of two
   >   different messages creating the same hash code. How many messages would
   >   I have to process to have ~10% chance of a duplicate hash on a 32-bit
   >   system? Are there any recommendations for salt values so that
   >   concatenating a pair of hash values would minimize the risk of
   >   overwriting a message with a non-duplicate?
   >
   > Well, it's easy enough to do the calculation.
   >
   > The 2nd message has 1 chance in 2^32 of colliding.
   > The 3rd message has 2 chances in 2^32 of colliding
   > The 4th message has 3 chances in 2^32 of colliding
   >
   > so you want N such that SUM (1 to N) = 10% of 2^32

   You can't sum up the probabilities because the events are not
   disjoint. 

Disagree.  The events _are_ disjoint because we're looking for the
first such event.  

Maybe it would have been clearer if I'd said:

 The 2nd message has 1 in 2^32-1 of not colliding
 The 3nd message has 2 in 2^32-2 of not colliding
 ...
and we keep adding up these disjoint, mutually exclusive
chances until we hit a 10% chance.


   That calculation can be done by taking the complement of the
   combined probability of *no collision* for N messages:

   H = 2^32  -- total hashes
   PNC(N) = probability of no collision for N messages
   PNC(N) = (H-1)/H * (H-2)/H * (H-3)/H * ... * (H-N+1)/H

   The *probability of collision* for N messages is the complement: PC(N)
   = 1 - PNC(N).
   The results are 30085 and 1971577270 messages for 32 and 64 bit hashes
   respectively.

Hmmm...  interesting.  I wonder where our assumptions are differing.

	 - Bill Yerazunis


------------------------------------------------------------------------------
SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, Nevada.
The future of the web can't happen without you.  Join us at MIX09 to help
pave the way to the Next Web now. Learn more and register at
http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/