Re: Weakness in PGP key fingerprints?

Raph Levien (raph@c2.org)
Fri, 16 Feb 1996 18:06:10 -0800 (PST) 

On Fri, 16 Feb 1996, James A.Donald wrote:

> On the info.pem.dev newsgroup you wrote
> 
> >   I should point out that none of the protocols do a good job
> > with this one. PGP has three ways of naming keys: a
> > fingerprint", the 8 least significant hex digits of the
> > modulus, and the user id. The fingerprint contains a
> > cryptographic weakness, meaning it is quite straightforward to
> > generate collisions in all three namespaces. Even if the
> > fingerprint were sound, then it still can't be used by PGP 2.6
> > as an index into the key database. As a result, the
> > responsibility falls squarely on the user to keep the database
> > free of name collisions.
> 
> What is the cryptographic weakness in the key fingerprint, and 
> why has it not be fixed.  (I realize that to fix it would 
> introduce a backwards compatibility problem, but big deal.)

   The fingerprint is the MD5 hash of the concatenation of the byte 
strings representing the modulus and exponent of the key. The weakness is 
that the byte strings contain no size information. Thus, (123, 45) and 
(1234, 5) hash to the same fingerprint, if one ignores the distinction 
between base-256 and decimal.
   It hasn't been corrected because the PGP development process is a bit
dysfunctional. 
   It is worth noting that the combination of fingerprint and keysize is 
cryptographically sound, but inconvenient. For example, the (fingerprint, 
keysize) value cannot be used as an index to the key database.

> It is not apparent to me that one can easily obtain a collision 
> with a given key using the eight least significant hex digits 
> of the modulus, though of course one can generate two keys that 
> collide.

   We should check with somebody who knows more number theory, but I see 
several attacks.
   First, it is not out of the question to simply generate 2^63 or so
keys. Because of the birthday paradox, the more PGP keys in existence,
the more chances for a collision. 
   Second, I think it is plausible that a key might be generated to order
having 64 low-order bits predetermined. Let a equal those low-order bits. 
The modulus will be pq having, say, 1024 bits. Choose a 512-bit prime p at
random. Now, choose x randomly having 512-64=448 bits. Then, let q be (((a
- 2p) ((px)^-1)) mod 2^64) x + 2. Check that q is prime. Simple algebra
shows that a = (pq) mod 2^64. 
   I don't do this for a living, so it's not unlikely that I've made a 
mistake. If so, I'm sure it will be corrected by one of our resident 
cryptographers.
   I figured people might be curious about this, so I cc'ed the workshop 
mailing list.

Raph