Re: [Hipsec] HIT collision probability

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.

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