> As you might know, PGP uses a 32-Bit number, called key-ID, as
> an internal index for storing and recognizing keys. Although
> the key-ID's are quite randomly distributed within 31 of the
> 32 bits (the key-ID is always odd), the scheme how this key id
> is derived from the (public) key is not cryptographically secure.
Actually, PGP uses 64 bits internally; although it only displays 32
bits to the user. However, these 64 bits are, as you say, insecure in
a cryptographic sense. The PGP 5.0 DSS/DH keys are not subject to
this attack, since the keyID is a cryptographic derivation from the
key. Only the old style RSA keys are succeptible, since the keyID is
just the low bits of the public key modulus.
> As a consequence, when obtaining PGP keys from insecure sources,
> you should always check for the existance of a key with the same
> key-ID in your own public keyring. To verify a key, always use
> the fingerprint and never the key-ID.
Actually, there is a problem in PGP's RSA fingerprinting algorithm,
too. You can create a key with the same fingerprint as another key,
however the size and keyid cannot match as well. This means you
should *ALWAYS* check the fingerprint, keyid, AND key size in order to
verify a key; an attacker can only forge at most two of the three
checks.
-derek
--
Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
Member, MIT Student Information Processing Board (SIPB)
URL: http://web.mit.edu/warlord/ PP-ASEL N1NWH
warlord@MIT.EDU PGP key available