Re: [Hipsec] HIT collision probability

[Robert Moskowitz <[e-mail]>]

On 05/04/2014 11:40 AM, Robert Moskowitz wrote:
> What population of HIs is needed for a 1%, 10%, 50% probability of a 
> HIT collision?
>
> I had the math once (like back in '99 or '00) and can't find it 
> (probably did not survive the Eudora to Thunderbird migration). 
> Thought I actually had this in a very early draft, but could not find 
> any such beast. Of course that would have been for HIPv1 HITs, not HIPv2.
>
> Any help on the math would be appreciated. Also does it change with PK 
> algorithm or key length? (seems not to me).

Using the code at: http://en.wikipedia.org/wiki/Birthday_attack
and compiling and running it via: 
http://www.compileonline.com/compile_cpp11_online.php

I get the following probablities for HIT collisions:

First the population of HITs (96 bits of hash) is: 7.9?10^(2)^(8)

Then the probablities of collision are:

.01% 3.98076e+12
.1% 1.25911e+13
1% 3.99066e+13
10% 1.29209e+14

And thus if each person in the world (7B) had 5 endpoints with HITs on 
them, the probablity
of a collision would be 10^-6 % (p=e-8, pop=3.98066e+10).