Re: [Hipsec] HIT collision probability

Hi Bob:

Let me clarify, the quantity p(k,n) below is the probability that k 
randomly picked elements taken from an n-set are all different (i.e., no 
collision occurs). You may be looking for the probability of having at 
least one collision, which is 1 - p(k,n).

I hope this helps.

Rene

On 5/5/2014 4:19 PM, Robert Moskowitz wrote:
>
> 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
>

-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363