Re: [Hipsec] HIT collision probability

On 05/05/2014 04:23 PM, Rene Struik wrote:
> 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.

that was it.  I missed that smallish detail.  thanks.

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