[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: PGP keyid collisions?
From: [email protected] ([email protected] +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