Subject: [Hipsec] HIT collision probability

From: Robert Moskowitz <[email-masked]>
Date: Sun, 04 May 2014 11:40:03 -0400

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

thanks

---

From: Paul Lambert <[email-masked]>
Date: Mon, 5 May 2014 09:38:29 -0700

http://en.wikipedia.org/wiki/Birthday_problem

On 5/4/14, 8:40 AM, "Robert Moskowitz" <[email-masked]> wrote:

>_______________________________________________
>Hipsec mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/hipsec

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 05 May 2014 12:59:10 -0400

> http://en.wikipedia.org/wiki/Birthday_problem

Thanks. I can see I will find the math I need for the HITv2 hash which is

128 - prefix - flag = 128 - 28 - 4 = 96 bits.

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 05 May 2014 13:38:34 -0400

I found the c code at: http://en.wikipedia.org/wiki/Birthday_attack

Of course, I don't do coding and have not done any compiling in years. 
So I have to figure out how to get this compiled so I can pump some 
numbers into it.

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 05 May 2014 14:06:39 -0400

> So I have to figure out how to get this compiled so I can pump some 

I found a nice online compiler:

http://www.compileonline.com/compile_cpp11_online.php

It is producing the known values results, so I am probably good...

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 05 May 2014 14:50:27 -0400

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?
>
> (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.
>

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^(2)^(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).

---

From: Rene Struik <[email-masked]>
Date: Mon, 05 May 2014 15:32:29 -0400

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:
>> Any help on the math would be appreciated.  Also does it change with 
>> PK algorithm or key length?  (seems not to me).
>
> First the population of HITs (96 bits of hash) is: 7.9×10²^(8)
>

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 05 May 2014 16:19:15 -0400

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

>>> 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.
>>>
>> And thus if each person in the world (7B) had 5 endpoints with HITs 
>> on them, the probablity
> email:[email-masked]  | Skype: rstruik

---

From: Rene Struik <[email-masked]>
Date: Mon, 05 May 2014 16:23:59 -0400

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:
> Where B6 is the cell with K (3.86e+12) and C6 is n (2^96).  I am 
> getting an answer of 99%.
>
>
>>
>> Rene
>>
>>>> What population of HIs is needed for a 1%, 10%, 50% probability of 
>>>> a HIT collision?
>>>>
>>>> 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).
>>>

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 05 May 2014 16:50:30 -0400

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

>>> size of the set one takes uniformly selected samples from and where 
>>> k is the number of drawn samples.
>>

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 06 May 2014 09:28:36 -0400

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:
>> 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.
>
>>>>>> What population of HIs is needed for a 1%, 10%, 50% probability 
>>>>>> of a HIT collision?
>>>>>>
>>>>> And thus if each person in the world (7B) had 5 endpoints with 
>>>>> HITs on them, the probablity