[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: comments on client auth

Ok, let's see if I can remember my math and rederive that formula..

The chance of collision between 2 people selecting from N choices


Assuming that the first two chose uniquely, the chance that the third 
person chose a unique value is


combining the two, you get a probability of

	1/N + (1-1/N)(2/N)

adding a third, you get:

	1/N + (1-1/N)(2/N) + (1-1/N)(1-2/N)(3/N)

for K people, if N is much larger than K, you can treat the (1-i/N)
terms as equal to 1 (this is a conservative estimate)
which reduces to 




now, if N is 2**256 (assuming only 256 bits of entropy per key)
and K is 2**32 (4 billion), you get a chance that there will be a
collision *anywhere* of roughly


which reduces to


i.e., there's a greater chance that someone will be able to guess your
triple-des session key than there will ever be a public key
collision in a population of 4 billion.

The chance of a bug (and that bug can be either a defect, or an
eavesdropper :-) ) in the random number generator is much higher..

					- Bill