duplicate keyid survey results

[David Shaw]

On Sun, Mar 03, 2002 at 06:09:40PM -0800, Len Sassaman wrote:
> The thing that comes to mind immediately for me is that you should allow
> for a 64-bit key-ID search.
> 
> When 32-bit key ID collisions occur, you may want your key server to
> display a warning in the user-interface.
> 
> Remember that 32-bit collisions could be accidental, so not reporting them
> would prevent the distribution of legitimate keys. (And you mention the
> possibility of an intential DOS.)
> 
> I personally think that public key servers should do little more than
> accept, store, and report data that it contains. Preventing the display of
> keys with duplicate IDs steps over that line a bit too much for me.

I strongly agree with Len on this.  Since the user's program must
validate the keys via signatures anyway, a keyserver does not need to,
and should not try to work out valid or invalid keys.

A quick look at the list of duplicate key ids seems to show that they
are all old-style v3 RSA keys which are known to have a problem with
having easy to create arbitrary 32 *or* 64-bit key ids.  Did I miss
any v4 keys on the list?

Creating a matching key id with the newer v4 key format requires
either brute force creating keys until the key id matches, or breaking
SHA-1, a problem that may not be impossible someday, but is difficult
to the point of effectively impossible today.

All that said, the 64-bit OpenPGP keyid space is very large but not
infinite.  There are going to be naturally occuring collisions
eventually (plus, one can certainly generate a v3 RSA key with the
same key id (but not fingerprint) as a v4 key).  This should be
harmless since the keys are validated based on the signatures and not
on anything the keyserver does or does not do.

If a duplicated keyid is requested from the current HKP and NAI LDAP
keyservers, *all* matching keys are returned.  This is the correct
behavior, as it lets the receiving program and the user decide which
(if any) of the returned keys is the right one.

David

-- 
   David Shaw  |  dshaw@jabberwocky.com  |  WWW http://www.jabberwocky.com/
+---------------------------------------------------------------------------+
   "There are two major products that come out of Berkeley: LSD and UNIX.
      We don't believe this to be a coincidence." - Jeremy S. Anderson