Re: KeyIDs and Key Fingerprints

["William H. Geiger III" <whgiii@xxxxxxxxxx>]

Hi Hal,

Well I really have to say that I don't like this. It basically blows
months of work in the area of keylookup optimization techniques that I
have developed for my products. Due to the uniqueness of the keyid in a
given keyring and the exposure of the keyids in both encryption &
signature blocks I have been able to greatly improve PGP performance both
on the client and sever. I think that perhaps you have undervalued the
"hint" feature of the keyid.

Key Server Identifiers & URL's are of only limited use (communicating to
the keyservers).

Variable KeyId's blow KeyId uniqueness out of the water. should id 123456,
id 5456, & id 456 be considered three unique keys or two unique keys ??

How will PGP match sig block & encrypt blocks to the appropriate key when
due to the reduced key size that match is ambiguous?? Test every
possessible key?? I see very little justification for increasing key
matching & message processing times.

Then we have two golden rules:

- KISS: Keep It Simple Stupid
- Don't fix what ain't broke

There are only 2 cases where KeyID exposure is a problem and this is only
in the encryption block:

-- BCC's: I have discussed my solution to handleing BCC's in an automated
encryption system both on the mailing lists/newsgroups and with several of
the PGP staff. Any e-mail message that contains BCC's a separate message
needs to be sent to each BCC recipient and encrypting it with only the key
for that recipient.

-- Anonymous Posts: any "hint" provided in the encryption block is a
decrease in security. For such messages all identifying information needs
to be stripped from the message including the keyID.

Sorry but if Phil is interested in going this route then he needs to show
that the benefits of doing so outweighs the cost of implementation. Right
now I see the benefits as very low and the costs very high.

In <199710170059.RAA00944@xxxxxxxxxxxxxxxxxxxxx>, on 10/16/97 
   at 07, Hal Finney <hal@xxxxxxxx> said:

>Another thread pointed out the difference between keyIDs and key
>fingerprints as ways of referring to keys.

>Currently, keyIDs and key fingerprints are defined somewhat differently
>for RSA keys than for newer keys.  The RSA definitions are a legacy for
>backwards compatibility, while the new methods have improved properties.

>With RSA keys, the keyID is the low order 64 bits of the RSA modulus. It
>turns out that it is trivial to generate keys which match a target key's
>low 64 bits, hence a keyID is not at all a unique handle for referring to
>a key.  (This is sometimes referred to as the "dead beef" attack, after
>someone demonstrated that they could generate a key with a keyID whose
>low 32 bits were 0xdeadbeef.)

>In most cases, keyIDs are not used in a context where this forgeability
>is a problem.  The most common use of a keyID is to help find a signature
>or decryption key.  It can be thought of as a "hint" to point the
>software to the right key.  However only one key will actually work to
>decrypt or signature-verify the message.  If the hint turns out to be
>ambiguous, it can still be useful.  (We anticipate adding other kinds of
>key-finding hints in the future, perhaps URLs or key server identifiers.)

>The RSA key fingerprint is intended to be more difficult to forge. It is
>an MD5 hash on the numeric data of the RSA modulus and exponent. However
>it turns out that this is not completely immune to forgery, as the hash
>value is not sensitive to where the modulus ends and the exponent begins. 
>You could have different keys with some modulus data moved to the
>exponent, and they would have the same RSA fingerprint.

>These problems were solved in the new keyID and fingerprint algorithms
>introduced in PGP 5.0.  They apply to the non-RSA keys, presently the DSS
>and ElGamal keys.

>The fingerprint is still a hash over the key data, but this time the
>entire public key packet is hashed.  This includes length fields which
>make it effectively impossible to have two keys which hash to the same
>fingerprint.  Furthermore, the fingerprint hash function is changed from
>MD5, which is now suspected to be weak, to SHA-1, a newer, larger, and
>more secure hash.  The new fingerprints are therefore 20 bytes long
>compared to 16 bytes for the old ones.

>KeyIDs for the new keys are defined to be the rightmost 64 bits of the
>fingerprint.  The only way to generate two new keys with the same keyID
>would be to keep trying at random until two of them happened to match, a
>much more difficult problem.

>Phil Zimmermann has suggested that we generalize the keyID concept to
>allow it to be variable length.  Rather than fixing it as a 64 bit
>substring of the fingerprint, we would make it a variable sized
>substring. (Phil would also prefer that it be a left substring rather
>than a right substring, for readability.)

>This allows the software to be flexible about how specific it needs to be
>when it refers to a key.  For most purposes, the 64 bit keyID is about
>right.  To be completely specific, the keyID could be expanded to be the
>full 160 bits of the fingerprint.

>An interesting case arises where you might want the keyID to be smaller.
>In some contexts it is a privacy leak that an encrypted message contains
>the keyID of the key which can decrypt it.  In that case you might want
>the keyID to be just a few bits long.

>(You'd probably want it to be a few bits rather than zero bits, because
>the recipient frequently has more than one decryption key.  Leaking a few
>bits of keyID doesn't significantly hurt privacy, since there would still
>be a very large number of keys which would match.  But it will simplify
>the decryption process, since it will generally still allow a single
>decryption key to be tried.)

>Doing this would allow us to merge the two concepts of keyID and key
>fingerprint into one variable-sized keyID.  The actual number of bits
>shown would then depend on the context in which it was used.

>It would be interesting to hear if there are other cases where being able
>to vary the size and specificity of the keyID would be appropriate. Are
>there any sizes besides small (about 3 bits, perhaps), medium (64 bits),
>and large (160 bits) which seem useful?

>Hal Finney
>hal@xxxxxxx
>hal@xxxxxxxx

-- 
---------------------------------------------------------------
William H. Geiger III  http://www.amaranth.com/~whgiii
Geiger Consulting    Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 2.6.3a at: http://www.amaranth.com/~whgiii/pgpmr2.html                        
---------------------------------------------------------------