Re: Odds of Recurrence for Hash Function

Bill Yerazunis escreveu:
>    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

No. See, for instance, when you say "The 3rd message has 2 chances in
2^32 of colliding" you inform the event "The 3rd message collides" and
the probability you attributed to it: "2/2^32". The event itself does
not exclude previous collisions, hence disjointness is not assured. The
attributed probability is another problem: it's neither the probability
that 3rd message collides, as the sentence suggests, nor the probability
that 3rd message is the first one to collide. It's in fact the
probability that 3rd message collides *given that there was no collision
before*, which is quite different!

> because we're looking for the first such event.

First collision is a better idea. But the probabilities are not those
you listed. You have to impose the precondition "no-previous-collision",
like below, to represent first collision:

C  = Collision
NC = No Collision
H  = 2^32
Probability of first collision at:
Msg 2: 1/H                               -- C
Msg 3: (H-1)/H * 2/H                     -- NC and C
Msg 4: (H-1)/H * (H-2)/H * 3/H           -- NC and NC and C
Msg 5: (H-1)/H * (H-2)/H * (H-3)/H * 4/H -- NC and NC and NC and C
...

In this case, each line represents a mutually exclusive event and we can
sum their probabilities up to get the probability of collision for n
messages. Again, this is equal to (1 - probability-of-no-collision), as
seen before, which is much simpler to calculate.

> 
> 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.

I can't make  sense of this.

> 
> 
>    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.

Disjoint events :-).

-- 
Fidelis


------------------------------------------------------------------------------
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/