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:
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
[email protected]
https://www.ietf.org/mailman/listinfo/hipsec
--
email: [email protected] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________
Hipsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/hipsec
