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

*To*: ben@algroup.co.uk, ben@gonzo.ben.algroup.co.uk, dpkemp@missi.ncsc.mil*Subject*: Re: comments on client auth -Reply*From*: bjueneman@novell.com (Bob Jueneman)*Date*: Thu, 20 Jun 1996 17:25:44 -0400*Cc*: spki@c2.org*Sender*: owner-spki@c2.org

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.

- Prev by Date:
**Re: comments on client auth** - Next by Date:
**Re: comments on client auth** - Prev by thread:
**Re: comments on client auth -Reply** - Next by thread:
**Private keys and the emperor's clothes** - Index(es):