Short ID Collision

[David Shaw]

On Dec 28, 2011, at 6:13 AM, Jerry wrote:

> Did anyone read about this reported problem with GnuPG and short keys?
> I found this on SlashDot this morning:
> 
> http://yro.slashdot.org/story/11/12/27/0044242/gnupg-short-id-collision-has-occurred?utm_source=headlines&utm_medium=email

The proper title of the article should have been "Easy method for making a OpenPGP short collision re-discovered.  Again."  To his credit, the original blog poster more or less says that.  Unfortunately, as various other sites picked it up, the issue and focus mutated a bit.

Short key ID collisions are nothing new.  They're obvious, and handling them is built into the system.  It's also not hard to make one - just generate keys over and over until you get a collision.  On a fast system, that won't take very long at all.

Now to the "bug", such as it is.  Using the key from the blog post, if I do:

  gpg --recv-keys 70096AD1

I'll get two keys.  The reason for that is that I am requesting something ambiguous.  There are two keys with that short key ID, so the server (correctly) returns both.  It's up to the caller (me) to decide which is the "right" one, using the web of trust, or whatever means I want to verify keys.  The keyserver is just a database, and does not say that a given key is right or wrong.  That's not the problem.

However, if I do:

  gpg --recv-keys EC4B033C70096AD1

I'll also get two keys.  Even though I gave enough information to specify one of the keys in particular, I still got both.  The reason why is due to the history of PGP keyservers.  When the GPG side of the keyserver code was written, the server side (a program called pksd) was not capable of understanding anything *other* than the short key ID.  Because of this, GPG intentionally truncates all key IDs to their short representation when requesting keys from that type of keyserver.  Other keyservers (LDAP) did not have that limitation, and so the longest possible representation is used there.

Since that code was written, time has moved on, and the old pksd server is dead and replaced by the sks server, which is capable of understanding more than the short key ID.  So given that there aren't any pksd servers to support any longer, it has been suggested (see https://bugs.g10code.com/gnupg/issue1340) that we should do like we do for LDAP, which never had this limitation in the first place, and send the longest key ID we can.  It's a reasonable thing to do - if the user gives us 64 bits, use all 64 bits.

So is this a security problem?  No, for many reasons, most of which were mentioned in the responses to the blog post.  Allow me to add one more reason: keyservers aren't capable of saying if a key is the right one or not.  They're just a searchable database that anyone can submit to.  A person who trusts a particular key is correct just because they found it on a keyserver is fooling themselves.  That's what we have a web of trust and/or fingerprint checking for.

David