[Hipsec] Final thoughts on - Re: HIT collision probability

[Robert Moskowitz <[e-mail]>]

I hope final thoughts.

These probablity calculations are based on the premise that:

1)    The keypairs are random over the population (of potentially 35B keys!)
2)    THe HIT generation maintains this random distribution (especially 
for DEX HITs which are a fold of the ECDH public key)

Of course this is for the total HIT population for a given algorithm.  
It is unlikely that all HITs will be in a single data collection.  But 
considering this is the age of big data, someone might be interested in 
buliding such a database.

Finally, feel free to use these numbers in any paper on HIP.

On 05/05/2014 04:50 PM, Robert Moskowitz wrote:
>
> 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
>>>>> [e-mail]
>>>>> https://www.ietf.org/mailman/listinfo/hipsec
>>>>
>>>>
>>>> -- 
>>>> email:[e-mail]  | Skype: rstruik
>>>> cell: [phone] | US: [phone]
>>>
>>
>>
>> -- 
>> email:[e-mail]  | Skype: rstruik
>> cell: [phone] | US: [phone]
>
>
>
> _______________________________________________
> Hipsec mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/hipsec