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

Re: comments on client auth -Reply

My rough rule of thumb for birthday problem attacks is that the chance of at least one collision approaches
50% at approximately the square root of the sample size. So if there is a possibility of 2^1024 keys, it would be 
necessary to generate AND SORT OR OTHERWISE COMPARE 2^512 keys before finding a match.

That's why triple DES (encrypt-decrypt-encrypt) is considered essentially unbreakable, at least by exhaustive 
search -- even given a gazillion DES engines the sorting and searching more than about 2^40 keys in order to find
even one match exceeds the bounds of feasibility at the present time.  That does NOT mean that a 40 bit key is secure -- it just means
that keys, and message digests, have to be at least 80 bits long and preferably 128 to 160 in order to make the probably
of an accidental match infinitesimally small.

So an exhaustive search for matching RSA keys is completely intractable, and is likely to be a for a very, very long time.

However, as several recent events have pointed out, that assumes the completely randomness and statistical 
independence of the key generation mechanism. The threat isn't an accident, but a blunder.

In addition, there is the problem of the user who generates and knows or learns his own private key, and then rolls it over when the
certificate expires (bad practice) and/or reuses that key pair in multiple certificates, thereby making it cryptographically impossible to
state which certificate should be used to validate the user's name/attributes/privileges.

So I'm still interested to learn how a hierarchical certification process helps this problem.

Bob

>>> Ben Laurie <ben@gonzo.ben.algroup.co.uk> 06/20/96 12:23pm >>>
David P. Kemp wrote:
>  > >  > > If key generation were guaranteed to have enough real entropy for the key
> > size, I don't worry about the 2^{-1024} or less chance of duplicate key
> > generation (worse for elliptic curves because keys are smaller, but still
> > infinitessimal).
>  > I'm not a mathematician, but do I remember being surprised back in high
> school to learn that with 38 people in a room, there's a 50% chance that
> two of them have the same birthday.

According to my calculations, at 23 people the probability is 50.73%.

The probability that k things chosen out of n at random will all be different is P=n*(n-1)*...*(n-k)/n^k. If k << n, then, to 1st order, this is
P=(n^k-(1+2+...+k)n^(k-1))/n^k=1-k*(k+1)/2*n
>  > Perhaps someone more proficient with numbers could calculate how many
> certificates would have to exist in the world, each generated with perfect
> 1024 bit entropy, before there was, say, a 1% chance of a collision.

I can't quite be bothered to solve this for n=2^1024 and P=.99 but for the sake of illustration, lets take k=2^100 (=10^33, roughly, or
2*10^23 certificates per person in the world). Then P=1-2^200/2^1025=1-2^(-825).
In other words, the probability of a collision is roughly 1 in 10^275.
Vanishingly small, I would say.

Cheers,

Ben.

>   > > Are you suggesting that a single entity generate all keys so that if there's
> > a weakness it can let out only unique keys and no one becomes aware of the
> > weakness?
>  > No!
>  > > ...that a single entity register all public keys, so that it can say "oops,
> > try that one again -- and we're not telling you why"?
>  > Good question.

--  Ben Laurie                  Phone: +44 (181) 994 6435
Freelance Consultant and    Fax:   +44 (181) 994 6472
Technical Director          Email: ben@algroup.co.uk
A.L. Digital Ltd,           URL: http://www.algroup.co.uk
London, England.