Mon, 26 Dec 2011
Short key IDs are bad news (with OpenPGP and GNU Privacy Guard)
Summary: It is important that we (the Debian community that relies on OpenPGP through GNU Privacy Guard) stop using short key IDs. There is no vulnerability in OpenPGP and GPG. However, using short key IDs (like 0x70096AD1) is fundementally insecure; it is easy to generate collisions for short key IDs. We should always use 64-bit (or longer) key IDs, like: 0x37E1C17570096AD1 or 0xEC4B033C70096AD1.
TL;DR: This now gives two results: gpg --recv-key 70096AD1
Some background, and my two keys
Years ago, I read dkg's instructions on migrating the Debian OpenPGP infrastructure. It told me that the time and effort I had spent getting my key into the strong set wasn't as useful as I thought it had been.
I felt deflated. I had put in quite a bit of effort over the years to strongly-connect my key to a variety of signatures, and I had helped people get their own keys into the strong set this way. If I migrated off my old key and revoked it, I'd be abandoning some people for whom I was their only link into the strong set. And what fun it was to first become part of the strong set! And all the eyebrows I raised when I told people I was going meet up with people I met on a website called Biglumber... I even made it my Facebook.com user ID. So if I had to generate a new key, I decided I had better really love the short key ID.
But at that point, I already felt pretty attached to the number 0x70096AD1. And I couldn't come up with anything better. So that settled it: no key upgrade until I had a new key whose ID is the same as my old key.
That dream has become a reality. Search for my old key ID, and you get two keys!
$ gpg --keyserver pgp.mit.edu --recv-key 0x70096AD1 gpg: requesting key 70096AD1 from hkp server pgp.mit.edu gpg: key 70096AD1: public key "Asheesh Laroia <asheesh@asheesh.org>" imported gpg: key 70096AD1: public key "Asheesh Laroia <asheesh@asheesh.org>" imported gpg: no ultimately trusted keys found gpg: Total number processed: 2 gpg: imported: 2 (RSA: 1)
I also saw it as an opportunity: I know that cryptography tools are tragically easy to mis-use. The use of 32-bit key IDs is fundamentally incorrect -- too little entropy. Maybe shocking people by creating two "identical" keys will help speed the transition away from this mis-use.
A neat stunt abusing --refresh-keys
Thanks to a GNU Privacy Guard bug, it is super easy to get my new key. Let's say that, like many people, you only have my old key on your workstation:
$ gpg --list-keys | grep 70096AD1 pub 1024D/70096AD1 2005-12-28
Just ask GPG to refresh:
$ gpg --keyserver pgp.mit.edu --refresh-keys gpg: refreshing 1 key from hkp://pgp.mit.edu gpg: requesting key 70096AD1 from hkp server pgp.mit.edu gpg: key 70096AD1: public key "Asheesh Laroia <asheesh@asheesh.org>" imported gpg: key 70096AD1: "Asheesh Laroia <asheesh@asheesh.org>" not changed gpg: Total number processed: 2 gpg: imported: 1 (RSA: 1) gpg: unchanged: 1 gpg: no ultimately trusted keys found
You can see that it set out to refresh just 1 key. It did that by querying the keyserver for the short ID. The keyserver provided two hits for that query. In the end, GPG refreshes one key and actually imports a new key into the keyring!
Now you have two:
$ gpg --list-keys | grep 70096AD1 pub 1024D/70096AD1 2005-12-28 pub 4096R/70096AD1 2011-03-11
There is a bug filed in GNU Privacy Guard about this. It has a patch attached. There is, at the moment, no plan for a new release.
A faster attack, but nothing truly new
My friend Venkatesh tells me there is an apocryphal old Perl script that could be used to generate key ID collisions. Here in the twenty-first century, l33t h4x0rz like Georgi Guninski are trying to create collisions.
In May 2010, "halfdog" posted a note to the full-disclosure list that generates PGP keys with chosen short key IDs. I haven't benchmarked or tested that tool, but I have used a different tool (private for now) that can generate collisions in a similar fashion. It takes about 3 hours to loop through all key IDs on a dinky little netbook.
You don't have to use any of these tools. You can just rent time on an elastic computing service or a botnet, or your own personal computer, and generate keys until you have a match.
I think that it's easy to under-estimate the seriousness of this problem: tools like the PGP Key Pathfinder should be updated to only accept 64-bit (or longer) key IDs if we want to trust their output.
My offer: I will make you a key
I've been spending some time wondering: What sort of exciting demonstration can I create to highlight that this is a real problem? Some ideas I've had:
- Publish a private/public key pair whose key ID is the same as Phil Zimmerman's, original author of PGP
- Publish a private/public key pair whose key ID is the same as Werner Koch's, maintainer of GNU Privacy Guard
- Publish a set of public keys that mimic the entire PGP strong set, except where I control the private key of all these keys
The last one would be extremely amusing, and would be a hat-tip to some work discussed in Raph Levien's Google Tech Talk about Advogato.
For now, here is my offer: If you send me a request signed with a key in the strong set, I will create a 4096-bit RSA public/private key pair whose 32-bit key ID is one greater than yours. So if you are 0x517DD4E4 I will generate 0x517DD4E5.
I will post the keys here, along a note about who requested it, and instructions on how to import them into your keyring. (Note: I will politely decline to create a new key whose 32-bit key ID would create a collision; apologies if your key ID is just one away from someone else's.)
P.S. The prize for best sarcastic retort goes to Ian Jackson. He said, "I should go and create a lot of keys with your key ID. I'll set the real name to 'Not Asheesh Laroia' so everyone is totally clear about what is going on."
