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(_dot_)RAA00944(_at_)s20(_dot_)term1(_dot_)sb(_dot_)rain(_dot_)org>,
on 10/16/97
at 07, Hal Finney <hal(_at_)rain(_dot_)org> 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(_at_)pgp(_dot_)com
hal(_at_)rain(_dot_)org
--
---------------------------------------------------------------
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
---------------------------------------------------------------