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

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

--------------020501080006090709020804-- From nobody Mon May 5 12:32:45 2014 Return-Path:

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:

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

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--------------040402080906010604060207-- From nobody Mon May 5 13:19:36 2014 Return-Path:

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

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

--------------020807040007080407090001-- From nobody Mon May 5 13:24:14 2014 Return-Path:

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:

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:

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

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--------------000706090505010808030409-- From nobody Mon May 5 13:50:52 2014 Return-Path:

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:

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

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

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

--------------010800080900070208030805-- From nobody Tue May 6 06:28:58 2014 Return-Path:

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:

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:

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

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

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

--------------040108040200090803000001-- From nobody Mon May 19 11:09:11 2014 Return-Path: