Subject: KeyID as left vs right substring of fingerprint

From: [email-masked]
Date: Thu, 25 May 2000 09:45:24 -0700

Currently in V4 keys, the keyid is defined to be the rightmost 64 bits
of the fingerprint.  Phil Zimmermann has often complained about this
and expressed the opinion that this was a blunder, and that we should
have chosen the leftmost bits rather than the rightmost bits.

He says that this would facilitate a generalization of the keyid to be
the leftmost N bits of the fingerprint.  N could be as long as the entire
fingerprint, to have an essentially unambiguous pointer to a given key.
Or N could be short, just a few bits, to have a nearly-"anonymous"
key, where the set of possible keys was understood by all parties to be
very small.

He also suggests that this would facilitate going to a key server storage
model where a length-N keyid was the index.  N could be shorter or longer,
and by using left substrings rather than right, he says that the server
would have an easier time adapting to the variable length indexes.

PGP 7.0, to be released shortly, will allow creation of V4 RSA keys for
the first time.  These will use the hash method to derive the fingerprint
and keyid, as with other V4 keys.

Phil proposed to me that we change the keyid calculation for these keys to
use a left substring of the fingerprint rather than the right substring.
More generally, all new key types would use left substrings.

The only keys that used right substrings would be "legacy" DSA and ElGamal
keys (assuming that no one else has implemented RSA V4 keys, which I am
not sure about).  We might do some kind of upgrade to DSA keys when the
new larger hash is announced later this year, and they could switch at
that time.  Maybe some arbitrary change could be made to ElGamal as well.

I will refrain from giving my own opinion about this idea, its
justification, its timing, and its impact.  Input from others is welcome.

Hal

---

From: [email-masked]
Date: Fri, 26 May 2000 08:55:22 +0900

From: [email-masked]
Subject: KeyID as left vs right substring of fingerprint
Date: Thu, 25 May 2000 09:45:24 -0700
Message-ID: <[email-masked]>

> have chosen the leftmost bits rather than the rightmost bits.

is the idea of giving the leftmost N bits a name other than "keyid"
doable?  then both concepts can continue to exist and "keyid" can be
deprecated.  some names that came to mind (in no particular order):

   left keyid,
   lkeyid, 
   general keyid,
   revised keyid

---

From: Jon Callas <[email-masked]>
Date: Thu, 25 May 2000 17:28:41 -0700

I agree that in retrospect, it would have been better to have the key id be
the high-order bits of the fingerprint rather than the low-order bits. I,
too, think this was a mistake. However, that decision was made before this
working group was formed. (And before I joined PGP, Inc. for that matter.)

I believe that changing this and making it be dependent on the algorithm
type would be utterly wrong. It would add one more little gnarly bit into a
system that is already filled with too many gnarly bits.

If this blunder needs to be fixed, the correct way to fix it is to make a
V5 key structure. (For that matter, there are a couple other things I'd
fix, too, if we made a V5 key structure.) However, I think that as
unfortunate as this is, simplicity and compatibility override aesthetics,
and we should just live with things as they are.

	Jon

---

From: "L. Sassaman" <[email-masked]>
Date: Fri, 26 May 2000 00:35:31 -0700 (PDT)

I agree with Phil on this point.

As it stands right now, we have only two types of keys in use: v3 RSA and
v4 DSA/ElG keys. (I am ignoring ElGamal signing keys since I don't see
anyone using them on any significant scale).

Presently, both of the key types obtain their keyid in different ways, and
there haven't been any problems with that.

Granted, changing the scheme once again for obtaining the keyid would add
confusion to the spec, but I think that obtaining the keyid from the left
of the fingerprint would add considerable benefit.

In fact, if we were to do it this way, the fingerprint itself would become
the keyid, and users or implementations could provide as much or as little
of the fingerprint as was determined necessary for a unique match. 

This would also allow for cases where a unique match was not desirable,
such as anonymous communication where the user did not wish to have the
key id of the recipient visible in the encrypted blob, but wished to
provide a "hint" to the recipient as to which key it was encrypted. This
would be useful for those with several private keys on the same keyring.

A "v5" signature format would probably be the cleanest way to go (and then
we could possibly convert all existing keys to v5 as well), but we run
into backward compatability problems.

As for other implementations using RSA v4 keys, I know that GnuPG doesn't
generate them (though I provided Werner with an RSA v4 test keypair a
while back).

Thoughts?

- --Len.

__

L. Sassaman

System Administrator                |  "It's a nice day 
Technology Consultant               |   to start again."
icq.. 10735603                      |    
pgp.. finger://ns.quickie.net/rabbi |        --Billy Idol

---

From: "L. Sassaman" <[email-masked]>
Date: Fri, 26 May 2000 00:45:14 -0700 (PDT)

> and we should just live with things as they are.

It's not just aesthetics. This issue was brought up by Marc Horowitz at
the Keyserver Symposium this week. He thinks that it could have a positive
impact on the internal workings of the keyservers, and would simplfy
seaches for the user. However, I do agree that we should not break more
than we fix. If the benefits of doing keyids this way do not outweigh the
drawbacks, we probably shouldn't do it.

Out of curiosity, what are the other things you would like to fix, given
the chance to do a v5 key structure?

__

L. Sassaman

---

From: Marc Horowitz <[email-masked]>
Date: 26 May 2000 09:14:40 -0400

"L. Sassaman" <[email-masked]> writes:

>> seaches for the user. 

I think Len is putting words in my mouth.  I do have some ideas which
came out of the meeting for changes which would have a positive impact
on the internal workings of the keyservers, and on the externally
visible functioning of the network as a whole, but changing how keyids
are generated and interpreted isn't one of them.

To address Phil's concerns as described by Hal, there's no reason that
you couldn't use the variable rightmost N bits of the fingerprint to
identify a key with arbitrary specificity today.  For people's
keyrings, the linear search won't take any more or less time.  For the
keyserver, if people wanted this feature, it would be possible to
start keeping an index of the fingerprint in reverse bit order.
Changes would be necessary in the keyserver to support lookup by
anything but a fixed position+length of the fingerprint, anyway.  This
isn't pretty, but it would be complexity hidden from the user.

I agree with everyone else that using the leftmost N bits would have
been prettier, but isn't strictly necessary.

		Marc

---

From: Paul Koning <[email-masked]>
Date: Fri, 26 May 2000 15:26:32 -0400 (EDT)

>>>>> "Jon" == Jon Callas <[email-masked]> writes:

 Jon> I agree that in retrospect, it would have been better to have
 Jon> the key id be the high-order bits of the fingerprint rather than
 Jon> the low-order bits. I, too, think this was a mistake. However,
 Jon> that decision was made before this working group was
 Jon> formed. (And before I joined PGP, Inc. for that matter.)

 Jon> I believe that changing this and making it be dependent on the
 Jon> algorithm type would be utterly wrong. It would add one more
 Jon> little gnarly bit into a system that is already filled with too
 Jon> many gnarly bits.

I agree that it should not be changed.  For that matter, I am
thoroughly puzzled why anyone would say that it's better to use high
order bits than low order bits.  We're talking about taking a subset
of the bits of a hash function, right?  Any old subset is as good as
any other.  A random subset of the bits would be just as good, or just
as bad, as the high order bits, or the low order bits.

   paul

---

From: Paul Koning <[email-masked]>
Date: Fri, 26 May 2000 15:34:02 -0400 (EDT)

>>>>> "L" == L Sassaman <[email-masked]> writes:

 L> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

 L> On Thu, 25 May 2000, Jon Callas wrote:

 >> If this blunder needs to be fixed, the correct way to fix it is to
 >> make a V5 key structure. (For that matter, there are a couple
 >> other things I'd fix, too, if we made a V5 key structure.)
 >> However, I think that as unfortunate as this is, simplicity and
 >> compatibility override aesthetics, and we should just live with
 >> things as they are.

 L> It's not just aesthetics. This issue was brought up by Marc
 L> Horowitz at the Keyserver Symposium this week. He thinks that it
 L> could have a positive impact on the internal workings of the
 L> keyservers,...

That doesn't compute.

If key servers want to have "high order" bits used as lookup index,
perhaps so standard database mechanisms that search for "match on
leading bits" can be used, that's fine.  This does NOT require a
protocol change!  A key server is perfectly well entitled to swizzle
the data around in any way it chooses for its own convenience; all
that is expected of it is that it unswizzles it before sending it back
out.

So if it's good for key servers, let the key servers internally turn
the fingerprint end for end.  Trivial coding and no protocol change
needed.  Not only that, but if you use a different database where this
approach is not useful, or even counterproductive, or a different
optimization is better, then you just do something else instead.  But
all of this is an internal implementation detail.

    paul

---

From: "L. Sassaman" <[email-masked]>
Date: Fri, 26 May 2000 12:50:56 -0700 (PDT)

> are generated and interpreted isn't one of them.

Sorry about that. I didn't mean to imply you suggested we change the
keyids (though I see that my paragraph above looks like I meant
that). But, if I am recalling correctly, you had thought it was something
that "would have been nice" if done the way Phil had wanted.

But then again, my recollection might be totally wrong... ;)
 
> isn't pretty, but it would be complexity hidden from the user.

Completely hidden from the user, but not as fluid as a leftmost
keyid. Expanding from the right is less natural to users whose language
reads from left to right, in my opinion.
 
> been prettier, but isn't strictly necessary.

Then it is probably best to leave this as it is, and not make the
change. Unless Jon can think of other things this group has discussed that
would justify a v5 key format on their own...

- --Len.

__

L. Sassaman

---

From: Jon Callas <[email-masked]>
Date: Fri, 26 May 2000 17:10:36 -0700

I think it really is just aesthetics whether you use the left or right bits
as a key id. I also believe that the left bits are the more aesthetic ones
to use, and I say that as a confirmed little-endian.

I'll also concur that the key server can use whatever bytes it wants.
That's no biggie.

If I were to make a V5 key structure, the thing I'd change would be *not*
to include the key creation time in with the SHA-1 hash for the
fingerprint. This was unfortunate. It means that two keys that have the
same key material, but different creation times have different key ids. At
one time I thought this was a feature, and I've come to believe it's a bug.

If I were really going to roto-till the spec, I'd get rid of key ids
altogether and only use fingerprints. There have already been problems with
key id collisions, and it would be much better to just use fingerprints. We
already say that you SHOULD NOT assume they're unique, but arguably that
really should be MUST NOT.

However, I think that none of those changes can be made. There comes a
point in any protocol's life where you just live with the warts because
correcting them causes more problems. The key id selection is one of those.
If we change things, we add more cruft into a system that already has cruft
in it.

There is already a separate algorithm for V3 keys and V4 keys. This would
give us another one, and one that exists for no good reason. And as Hal has
mentioned, the proper proper fix would be to make the UI that shows a 32
bit key id show the left 32 bits rather than the right ones. Fortunately,
we've managed to bury that issue completely and not even mention them. 32
bit key ids only exist in implementations.

	Jon

---

From: Werner Koch <[email-masked]>
Date: Sun, 28 May 2000 14:12:25 +0200

> altogether and only use fingerprints. There have already been problems with

I'd second this.  However, the user will not see a difference as we
can still present him a keyID, although we are not using it anymore.
Using the keyID as a way to select a key is still a nice feature
because typing the whole fingerprint is not that easy.  

  Werner

-- 
Werner Koch				OpenPGP key 621CC013
OpenIT GmbH                             tel +49 211 239577-0
Birkenstr. 12                           email   [email-masked]
D-40233 Duesseldorf                     http://www.OpenIT.de