Stop it with those short PGP key IDs!
Debian is quite probably the project that most uses a OpenPGP implementation (that is, GnuPG, or gpg) for many of its internal operations, and that places most trust in it. PGP is also very widely used, of course, in many other projects and between individuals. It is regarded as a secure way to do all sorts of crypto (mainly, encrypting/decrypting private stuff, signing public stuff, certifying other people’s identities). PGP’s lineage traces back to Phil Zimmerman’s program, first published in 1991 — By far, not a newcomer
PGP is secure, as it was 25 years ago. However, some uses of it might not be so. We went through several migrations related to algorithmic weaknesses (i.e. v3 keys using MD5; SHA1 is strongly discouraged, although not yet completely broken, and it should be avoided as well) or to computational complexity (as the migration away from keys smaller than 2048 bits, strongly prefering 4096 bits). But some vulnerabilities are human usage (that is, configuration-) related.
Today, Enrico Zini gave us a heads-up in the #debian-keyring IRC channel, and started a thread in the debian-private mailing list; I understand the mail to a private list was partly meant to get our collective attention, and to allow for potentially security-relevant information to be shared. I won’t go into details about what is, is not, should be or should not be private, but I’ll post here only what’s public information already.
What are short and long key IDs?
I’ll start by quoting Enrico’s mail:
there are currently at least 3 ways to refer to a gpg key: short key ID (last 8 hex digits of fingerprint), long key ID (last 16 hex digits) and full fingerprint. The short key ID used to be popular, and since 5 years it is known that it is computationally easy to generate a gnupg key with an arbitrary short key id. A mitigation to this is using "keyid-format long" in gpg.conf, and a better thing to do, especially in scripts, is to use the full fingerprint to refer to a key, or just ship the public key for verification and skip the key servers. Note that in case of keyid collision, gpg will download and import all the matching keys, and will use all the matching keys for verifying signatures.
So… What is this about? We humans are quite bad at recognizing and remembering randomly-generated strings with no inherent patterns in them. Every GPG key can be uniquely identified by its fingerprint, a 128-bit string, usually encoded as ten blocks of four hexadecimal characters (this allows for 160 bits; I guess there’s space for a checksum in it). That is, my (full) key’s signature is:
AB41 C1C6 8AFD 668C A045 EBF8 673A 03E4 C1DB 921F
However, it’s quite hard to recognize such a long string, let alone memorize it! So, we often do what humans do: Given that strong cryptography implies a homogenous probability distribution, people compromised on using just a portion of the key — the last portion. The short key ID. Mine is then the last two blocks (shown in boldface): C1DB921F. We can also use what’s known as the long key ID, that’s twice as long: 64 bits. However, while I can speak my short key ID on a single breath (and maybe even expect you to remember and note it down), try doing so with the long one (shown in italics above): 673A03E4C1DB921F. Nah. Too much for our little, analog brains.
This short and almost-rememberable number has then 32 bits of entropy — I have less than one in 4,000,000,000 chance of generating a new key with this same short key ID. Besides, key generation is a CPU-intensive operation, so it’s quite unlikely we will have a collision, right?
Well, wrong.
Previous successful attacks on short key IDs
Already five years ago, Asheesh Laroia migrated his 1024D key to a 4096R. And, as he describes in his always-entertaining fashion, he made his computer sweat until he was able to create a new key for which the short key ID collided with the old one.
It might not seem like a big deal, as he did this non-maliciously, but this easily should have spelt game over for the usage of short key IDs. After all, being able to generate a collision is usually the end for cryptographic systems. Asheesh specifically mentioned in his posting how this could be abused.
But we didn’t listen. Short key IDs are just too convenient! Besides, they allow us to have fun, can be a means of expression! I know of at least two keys that would qualify as vanity: Obey Arthur Liu’s 0x29C0FFEE (created in 2009) and Keith Packard’s 0x00000011 (created in 2012).
Then we got the Evil 32 project. They developed Scallion, started (AFAICT) in 2012. Scallion automates the search for a 32-bit collision using GPUs; they claim that it takes only four seconds to find a collision. So, they went through the strong set of the public PGP Web of Trust, and created a (32-bit-)colliding key for each of the existing keys.
And what happened now?
What happened today? We still don’t really know, but it seems we found a first potentially malicious collision — that is, the first “nonacademic” case.
Enrico found two keys sharing the 9F6C6333 short ID, apparently belonging to the same person (as would be the case of Asheesh, mentioned above). After contacting Gustavo, though, he does not know about the second — That is, it can be clearly regarded as an impersonation attempt. Besides, what gave away this attempt are the signatures it has: Both keys are signed by what appears to be the same three keys: B29B232A, F2C850CA and 789038F2. Those three keys are not (yet?) uploaded to the keyservers, though… But we can expect them to appear at any point in the future. We don’t know who is behind this, or what his purpose is. We just know this looks very evil.
Now, don’t panic: Gustavo’s key is safe. Same for his certifiers, Marga, Agustín and Maxy. It’s just a 32-bit collision. So, in principle, the only parties that could be cheated to trust the attacker are humans, right?
Nope.
Enrico tested on the PGP pathfinder & key statistics service, a keyserver that finds trust paths between any two arbitrary keys in the strong set. Surprise: The pathfinder works on the short key IDs, even when supplied full fingerprints. So, it turns out I have three faked trust paths into our impostor.
What next?
There are several things this should urge us to do.
- First of all, configure your local GPG to never show you short IDs. This is done by adding the line keyid-format 0xlong to ~/.gnupg/gpg.conf.
- I just checked both in /usr/share/gnupg/options.skel and /usr/share/gnupg2/gpg-conf.skel, and that setting is not yet part of the packages' defaults. I'll check a bit deeper and file bugs right away if needed!
- Have you written or maintained any program that deals with GPG keys in any way? Make sure it specifies --keyid-format long or 0xlong in any relevant call. It might even be better to use the machine-oriented representation instead: --with-colons.
- ...Of course, your computer will not feel tired or confused at comparing 160-bit full fingerprints instead of 64-bit long IDs, so it's better if our scripts use the full version for everything.
- Only sign somebody else's key if you see and verify its full fingerprint (this is not a new issue, but given we are talking about it, and that DebConf is around the corner, and that we will have a KSP as usual...)
And there are surely many other important recommendations. But this is a good set of points to start with.
[update] I was pointed at Daniel Kahn Gillmor’s 2013 blog post, OpenPGP Key IDs are not useful. Daniel argues, in short, that cutting a fingerprint in order to get a (32- or 64-bit) short key ID is the worst of all worlds, and we should rather target either always showing full fingerprints, or not showing it at all (and leaving all the crypto-checking bits to be done by the software, as comparing 160-bit strings is not natural for us humans).
[update] This post was picked up by LWN.net. A very interesting discussion continues in their comments.
Comments
Anonymous 2016-06-03 23:51:40
Hi, your post can’t be read
Hi,
your post can’t be read unless I add a slash to the URL — you may want to fix the server config :)
Anonymous 2016-08-15 11:21:44
Linus Torvalds became the next victim
It seems like the entire strong set is going to be completely replicate with fake key, creating a shadow strong set.
Now, Linus Torvalds, Greg Kroah-Hartman and other core developers have became victims.
Search Result of 0x00411886: https://pgp.mit.edu/pks/lookup?search=0x00411886&op=index (two keys) Fake Linus Torvalds: 0F6A 1465 32D8 69AE E438 F74B 6211 AA3B [0041 1886] Real Linus Torvalds: ABAF 11C6 5A29 70B1 30AB E3C4 79BE 3E43 [0041 1886]
Search Result of 0x6092693E: https://pgp.mit.edu/pks/lookup?search=0x6092693E&op=index (two keys) Fake Greg Kroah-Hartman: 497C 48CE 16B9 26E9 3F49 6301 2736 5DEA [6092 693E] Real Greg Kroah-Hartman: 647F 2865 4894 E3BD 4571 99BE 38DB BDC8 [6092 693E]
And it looks like that the community is still not aware of the expansion of the attack, Gunnar Wolf, please spread the words for warnings.
Anonymous 2017-05-01 08:21:06
PGP pathfinder
The PGP pathfinder at https://pgp.cs.uu.nl/ now uses long key ID’s.
Gijs 2016-09-22 23:43:00
Also mentioned in treeware Dutch Linux Magazine
This post is also mentioned in treeware Dutch Linux Magazine
gwolf 2016-06-07 17:06:10
Not so much that I forgot…
I rather didn’t have them in mind :)But yes, those are clearly vanity keys as well. ;-)
gwolf 2016-06-10 21:21:34
Sigh My broken blog…
It is not a broken link, it’s a broken assumption somewhere between my blog configuration and my hosting provider’s low memory thresholds. My blog does not get slashdotted ever, because it starts producing errors way before that :-P
Jonathan 2016-06-06 01:47:59
vanity short-ids
You forgot my vanity short ID, 0x06AAAAAA ;) My never-used work one is one too, 0xBADBAAC. I did contemplate trying to generate vanity longer-IDs but I think I agree with the general point that they’re not safe, just not as not-safe as the short ones.
Jonathan 2016-06-09 06:30:13
incoming link from LWN broken
The link from LWN.net is also without the trailing slash so broke too