Re: PGP Signatures security BUG!

[haustein () INFORMATIK RWTH-AACHEN DE (Tobias Haustein)]

* Povl H. Pedersen (pope () netguide dk) [000308 11:39]:

> They do NOT have the same keypair, as "John Smith" just like me has 
> an old "silver" PGP 2.5 key, while Mike Evans has a new "gold" key, 
> meaning he uses one of the never non-copyrigthed algorithms and 
> keyset of a different size.

Then, they should not be able to create valid signatures for each
other. The only way to create a valid signature for a given public key
is to use the one private key that corresponds to this public
key. Therefore to forge a signature the key pairs have to be equal.
In your first mail you said that the signature of one user can be
validated with the others key. This is a extremely strong hint for the 
assumption that both keys are identical. 

If both keys are different in algorithm, say key one is using RSA and
key two is using DH/DSS, chances that both produce the same signature
are too small to believe it. 

> The keyID is only 8 hex digits = 4 bytes = ~4.000.000.000 different 
> keys, and there are probably more than this one case of 2 users with 
> same keyID.

As said, the key id is calculated from the key. A V3 key id consists
of the lowest 64 bits of the public modulus ot the RSA key, whereas a
V4 key id equals the lowest 64 bits of the fingerprint of the whole
key. However, the OpenPGP standard (RFC 2440) explicitely says that:

  "Note that it is possible for there to be collisions of key IDs --
  two different keys with the same key ID. Note that there is a much
  smaller, but still non-zero probability that two different keys
  have the same fingerprint." (page 53)

There is another note in this document that talks about problems with
key IDs:

  "V3 keys SHOULD only be used for backward compatibility because of 
  three weeknesses in them. First, it is relatively easy to
  construct a V3 key that has the same key ID as any other key
  because the key ID is simply the low 64 bits of the public
  modulus. Secondly, because the fingerprint of a V3 key hashes the
  key material, but not its length, which increases the opportunity
  for fingerprint collusions. Third, there are minor weaknesses in
  the MD5 hash algorithm that make developers prefer other
  algorithms." (page 36)

> The problem is the keyserver not listing all keys entered that 
> computes to the same keyID, to let the user doing a lookup see that 
> there is multiple registered users with the same key.

As you see, this is known and discussed in the standard. I don't see,
why there is any security problem here. 

If there is a collusion in key IDs and the key server does only list
the other key, the person who uses this key to verify a signature will
get a notification about an invalid signature. This is not really
bothering.

> Or they should start using the fingerprint instead, which is much longer.

When signing a key or deciding whether to trust a key, you _must_
_always_ verify the fingerprint. However, for finding keys the usage
of the shorter key ID is sufficient, since this is only used to help
users to find the correct key. As the key ID of V3 keys is easy to
forge, it is not allowed to use the key ID for anything other as to
help the user to pre-select the key set that might contain the key he
is looking for.

Ciao,

Tobias

-- 
Dipl. Inform. Tobias Haustein

Department of Computer Science IV, Aachen University of Technology
Ahornstr. 55, D-52056 Aachen
Phone +49 (241) 80-21417, Fax +49 (241) 8888-220
E-Mail haustein () informatik rwth-aachen de
Web http://www-i4.informatik.rwth-aachen.de/~haustein/


<HR NOSHADE>
<UL>
<LI>application/pgp-signature attachment: stored
</UL>