Re: [Hipsec] HIT collision probability

On 05/05/2014 03:32 PM, Rene Struik wrote:
> Hi Bob:
>
> The formula is roughly p(k,n)=1*(1-1/n)*(1-2/n)*...*(1 - {k-1}/n), 
> which can be approximated as roughly e^{-k^2/(2n)}, where n is the 
> size of the set one takes uniformly selected samples from and where k 
> is the number of drawn samples.

I am doing something wrong in LibreCalc with the formula:

=EXP(-(B6^2)/(2*C6))

Where B6 is the cell with K (3.86e+12) and C6 is n (2^96).  I am getting 
an answer of 99%.

>
> Rene
>
> On 5/5/2014 2:50 PM, Robert Moskowitz wrote:
>>
>> 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²^(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).
>>
>>
>>
>>
>>
>> _______________________________________________
>> Hipsec mailing list
>> Hipsec@ietf.org
>> https://www.ietf.org/mailman/listinfo/hipsec
>
>
> -- 
> email:rstruik.ext@gmail.com  | Skype: rstruik
> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363