From: Hal <hfinney@shell.portal.com>
Date: Tue, 1 Feb 94 08:10:34 PST
To: cypherpunks@toad.com
Subject: Re: PGP keyid collisions?
Message-ID: <199402011607.IAA22359@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


From: wcs@anchor.ho.att.com (bill.stewart@pleasantonca.ncr.com +1-510-484-6204)
> Hal points out that brute-forcing a 24-bit Key-ID isn't all that hard;
> the usual formulas tell you what fraction of numbers are prime in the 
> desired range, though without looking them up I'd expect it would take
> around 2**30 - 2**35 tries to find a specific one; I suppose this 
> means the NSA has already done it :-)

Right, but the point is that you have to search for a prime q anyway;
PGP's algorithm is basically to repeat q += 2 until you find a q which
is prime.  It uses a sieve to speed this up a lot.  I was pointing out
that you can basically change the 2 to a 2^24, still use a sieve, and
find a key just about as fast.  So matching an existing key ID should not
take much if any longer than just generating a PGP key in the first place.

> > I understand there is already at least one 24-bit collision on the
> > public key servers, not unexpected given a few thousand keys.
> 
> I assume PGP does the right thing, except in cases of pilot error
> (e.g. doing key lookup by KeyID) ?  Even if it does, this has
> some design impact on systems using random public-private key generation
> for meet-me remailer cutouts.
> 		Bill

PGP actually uses a 64-bit key ID internally, only displaying the lower
24 bits for conciseness.  It would be practically impossible to get a
64-bit key ID collision by accident (well, almost impossible, anyway).
However, the technique I mentioned could easily generate such collisions.
PGP does check for the case of matching key ID and does something, but I
forget what.  24-bit key ID matches shouldn't have any effect except for,
as Bill says, extracting/deleting keys based on key ID.

Hal