Skip to main content.

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:

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."

[] permanent link and comments

While I understand this problem, and tend to use full key fingerprints myself, calling this an "attack" is going a bit far, since signature verifications cannot be spoofed with this technique, so you can only confuse people at the worst.  Nothing is compromised.

Posted by Stephen Paul Weber at Mon Dec 26 19:59:15 2011

It is an attack on humans. We are the weakest link in security. Having tools that help attackers perform social engineering attacks is definitely bad and definitely a vulnerability in the tool.

Posted by foo at Mon Dec 26 20:15:12 2011

My key ID A56E15A3 has conflicted since day 1.

Posted by Hub at Mon Dec 26 20:17:31 2011

I can't say I've ever had this problem. But then again, I can't say I've ever used this software, nor do I even know how I ended up on this fine article of yours. Did the gnomes bring me here? I don't like gnomes. They try to nibble me to death in my sleep! I bet you don't like that either. So why do you send the gnomes after me??? God, so many gnomes...

Posted by Phillip Norbert Årp at Mon Dec 26 23:25:48 2011

I think there's an obvious and simple solution for the GPG issue. For perfect compatibility it can use the short fingerprint to retrieve potential matches. If the long or full fingerprint is available it's used to confirm those potential matches. False matches get discarded.

Posted by Alsee at Tue Dec 27 08:40:05 2011

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

Hello,

my key is:

pub  1024D/38EA4970 2002-10-08
uid  Juergen Schmidt <ju@heisec.de>


I refer to your offer to generate a keypair for
38EA4971

bye, ju
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iEYEARECAAYFAk758+kACgkQ+JUKGDjqSXBQngCeMMmHlDTSASBlJqO41UHWiTcn
V7cAnjYnjbkJ4j/VGo5pQNPyjoewsoR9
=1JWj
-----END PGP SIGNATURE-----

Posted by Juergen Schmidt at Tue Dec 27 11:41:17 2011

Good on you for drawing attention to this. Full-time security geeks are wondering "What's the big deal?" because they've always known that 32-bit ids were second-preimage-vulnerable in this way. However, normal users could possibly get caught out by this.

The fact that the GPG command-line accepts these as arguments is indicative, in my opinion, of a security/usability flaw -- this means users are encouraged to use these ambiguous identifiers as arguments they communicate to the program (GPG). Presumably they are then supposed to inspect the results to make sure that the unambiguous thing (the fingerprint) is correct. That sounds a lot like the sort of UX/security failure that used to be ubiquitous back when this is designed: "It's secure as long as the users do some extra safety-measure steps that real users never do."

One possibility to consider for the longer term is that using hex to show key fingerprint material is a very inefficient way to show it -- inefficient in the sense of using lots of characters of display to communicate relatively few bits of key fingerprint. In the long run, we could switch over to using a more efficient encoding such as base32. Here's a GPG command-line asking to receive your public key using an ambiguous 32-bit identifier to indicate which public key you want GPG to fetch:


gpg --recv-key 70096AD1


Here's the same thing using the full, unambiguous fingerprint in the current chunked hex encoding:


gpg --recv-key D004 36A9 0C4B D120 0202  0A3C 37E1 C175 7009 6AD1


Or if we remove the spaces:


gpg --recv-key D00436A90C4BD12002020A3C37E1C17570096AD1


Here's the full, unambiguous fingerprint in a hypothetical future zbase32 encoding:


gpg --recv-key 4yndpkecjxe1yyonbe6dxaqbqiay14st


One thing to note is that the PGP command-line that GPG is presumably emulating originated in the early 90's, perhaps as early as 1992. Back then it may have seemed like a lot of effort/expense to generate a 32-bit collision. (Although even then it was perfectly well understood to be possible to do so, using only a few days of computation on a reasonably-priced computer, so this should be seen primarily as a problem in UX design rather than as having to do with the evolution of brute force costs.)

We could also use slightly shorter identifiers if we believe that they are still enough bits to unambiguously identify one public key even in the case that an attacker tries to generate a second matching one. For example, if we believed that 2⁸⁰ was more work than anyone would be willing and able to spend against this in the forseeable future, we could use identifiers with 16 base32 characters, like this:


gpg --recv-key 4yndpkecjxe1yyon

Posted by Zooko at Tue Dec 27 15:01:35 2011

Hi Juergen,

Please enjoy the following PGP private key:

-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v1.4.11 (GNU/Linux)

lQcYBEYoMtUBEAC3hlGsFYP6kV/8YM/exZsGGoXNn7vCjA8E1pIU4GpgwaUUmXLe
1ytB4uSuN0Tz0kIiXapj2QgNVJEEHUuua1HJ0Av5sxSI2HVNPhzJEjdS4czAfVi8
N9hx3C2KIAnKA4DF3+NchqsP8KPTNH/g675DlXa+M7UL7ughvlqPrVRIqLWI+PSj
+WiNmH69URTXWaC60N/VhrsXv5JuK0NEU82ROhOjNgu9S3SV1VEmNfZh9iM2p/b/
j7Y5nGVe+N25A8OarOir1hj0YnNe7w6laumYN/ely8im2klSDXJ8dxNYrpbrFRMl
UwpGNaodO/OkspoDPES/t+TdprRct69lXBXuaIt1EkOg88lmoQzfH66TtflwTgs8
vwQ/qkqCr5EehsezIxoBMp0OD9AVjxkWwY2sck2u5Fkizlj9O/P8zZFQuPf3BhKr
5oU4isAxSnE3ONknpxrhRTyhfqDD/TIugBivyQSfFot7NWzqSQb6vtfL6fhjHj1M
oJS5hDiTVPbf2vf3fjiERSzZGxfT2sV8usZBJgOAvMl0mXt6Ki8n64zjAHMfam1x
Q6QBXCIdtZLjE4fs25f3PctP8dOxsB1KeRSOb/gdc2dumZ5CSrM54IrIZvOSrkwi
foypF7CIJuE8bpbiCK6TLgtPRyRk4TPxy/MC3vTxQ0PSCPcR7qqVP86m0wARAQAB
ABAAq96nl+/iVINWj+UeZvNKNhIaorHnxc8itZY44kI0fX58GemG0ThSs3ZIUPtD
oM+UzdhIHRAAYXOEB4Vj/elVhBlJTcQvA+UrHXaAwLFFjGIYPWBl/IaUNjVLlKJi
aISVUTpWE62uf9QNqFrvM3WzDlnoBUIpWA6Z6Bf7ebiKSS1uLONxQCrvhkN81dEc
In02cB3ysWZmylvHR1NOwKt2xX3NLDkOD22dtkA6qf05Sw6WdbYhM76jmhpkOOf5
xS3IPo+Vqm9rmVqlzw8z+ShBsSMg0m0g8VlV9vjO8c8WGCQRBAENmBPHeG8DbDNb
/i6g20zS2XTfadCX8oi3QsZVZgMa4ey8iU9dEVgRA4eCAXUF09YQuGXmv0O+5PgI
+GQL5N7PYx9cJxCjSF9QUimSykrFZ9yBX4g044yBTYxUG5TaTD/H2E965ARy1Ux6
l5xmxsz7l9JYHCpHosWy5LE2YGe8meApQkOBxGLdYA2lrWWl0tX2i7k5X1Qt8xsJ
1jPeqEe12LaXP2SEjnlYk5YWTEMRc8ZktAMqxVwVIm2r4kc8j5RMze+jgQDAWFCL
NhU7ttv7SU1CBRyxSrWE4Dk/l8TKTesyktuF4biEjHLaBMtuTobT8G/x9Xj3OKgt
iNX0WiQEMuTVmawb6pPMOvma7MsJNAyEQ6mvGKk5VU0hIhEIAO9NwJLz6usVtDaH
LAllgod4OM+iJ73g5jFE/uMyDyTJuRaJh43Ao3hGJW+1VnpNeAmRLPKPG6/FNvQs
m2XvYeNL9ILTSWDvgnFhf2yz/rnwKwLtNdKO2yDkRjbsTcqdk8U+uowpr1hJ5YNS
73hYt/SWShSTCo/BQu6FSghsuMrJHCtHlYk171qiIk8iCcIM7ek0BSS1mv5Rd1bX
/e6Z59js0tlQZBuDQz1YrN2fz24hoM2cy9Ra7PpcyweMyNord9Gkq58fHJLz4cXZ
Lglx7L0ELD41Frg3ZEh0IMGvE/SuA/yTfUyr2CjAKglGzRDMx2Jh95FZb8oP5bX3
nmww45kIAMRUSYPPXvV+F2jufLK7ZpWas+FHiDlHu67T6u/Yu51rooDnLO44hkjc
ytFzPH9n/1Rtut4Zx1hrhk6Q1+kwDfSK5jySixR9REgMkCiLMlGCrYRWwoS6M9r5
SesSVYg1LK6Q8UevluEri3ZOy6y2yFTSHDElnFdjRXnx30dOITdyLFQ4nFynzwMR
YzAe4DSIlJjJw9ARb/yQWsgeQ6H337uz74Xt4TImL/omnTUmbJ4WqqftPbzBRliN
kKKI6oGVm7lu+ZiEaKQncRBfi8P7t1k4XXHHAYw4TqdQ2iLHbsHBdWfn2jvZk2IX
AO3hKTHd9VqwM6c+oFYsqmhmSgiXYUsH/j6mmppgAtF9ebwdTkf/nrLiNzya6aPc
sWd5cBTdYnowazjmxH+aMXRc9ZWY+ZLIKdXmoUdMDMDHN7IA9sStSUTSSjd8/cuW
5QQc0LX+xLcklSuYtpaNpsjdVR22OYy/g2LwR7y86F1iiS3bApC1ZV77PrmoELeL
XGepznd2ZkC4fGYsiDf+3mnFU8MF/mveH3Be+hDolLxq7NsWQTCm+Va8G3/bV3cw
AXE2LNjr8nzGv4nyCzfSG9CRcwOxS4BcCaFeXD1YJgeBCFO9cV8/AHsI3ASkL0xK
0ehQ+XgnXMk2W4xEVFSrRlq9dC1gIXwBslyH2DyEo2W0VdY73Oq0c0eA/LQManVA
aGVpc2VjLmRliQI5BBMBCAAjBQJGKDLVAhsBBgsJCAcDAgcVCgkICwMCBBYCAwEC
HgECF4AACgkQVzN0OTjqSXFHJg//WFGz/00p1ZxUwvmfZRaIn0JZlNehbokNu76k
EMhe/THX1Bqxi7jg0RPbVjIZgN8opNoJD/3oWAiL8wxpvSmM2/5JxejMZpG+T8wh
q1v3wHMNu86kx5aLuQv4kKJRfl53aMTNcJofNTrSabFBKSptPmaCiZeuwqx1tGHz
9j9jjYY71w/eFWOI1EXehFaFM07dCNmE9j2fL7+ETch1IZC5oM63oKDkF4DwLrmL
8p2PL+1Fwj8QEUAJJFqjJPiVj7AhBgj0bhT4Blfy4A5U2+uPYeEaY+6F54eglaP/
ak5+AkqgKiib96H+qkreBe1+eE9QFTnSQroUi/+F1MlE78iofkGmxjWuOipBDbVL
HT/DVrr1Oy39KpWh1UnyRmBELWXH3b4Lu6TIp1E4963q7ZrRaf9cXNYqll4UcuQY
kKAaQHRS6MucqCNy+DFkWHOZJK1jh7mDj5G6AZDF1WEhG7A+nfPgZj05wEGK0+ZU
1rEikMvzRESlMSJGSNfhvqTdbsHvsX6ZwYSi8i5LOlKgdB1NAboK9HpCUZM3QgFx
BbGaCQvyDU7efr6zFifkB5apXRDFuABqg7sDvoAfXKGGTI/wKnj8On/EaKgKWXA1
nxUHwjTDRYCYp3YwIxa0ayfu1ahsjxVkgopq0VBeiHWw+Oqq5wSTztA/Zl3ONErR
+RlQ9Ww=
=QHZ5
-----END PGP PRIVATE KEY BLOCK-----

Posted by Asheesh Laroia at Tue Dec 27 16:31:50 2011

This isn't nearly the issue you claim, and not an attack at all. It's well-known, and people have created 32-bit collisions for probably about 20 years now. However, even going back to PGP's early days, the software dealt with 64-bit key ids, and software in general does the right thing.

Stephen Paul Weber above points out correctly that if you ever get stuck with with the wrong key, signatures won't be valid, encryption won't work, etc. As he says, it can cause nothing worse than confusion.

In the example you give yourself, GPG does the correct thing! There are now two keys on the MIT key server with the same truncated key id, but they have different 64-bit key IDs. GPG goes and gets both keys, which is exactly what it should be doing.

If you create a key with a 32-bit collision to PRZ's, Werner's, mine, or whomever's, nothing bad will happen. You cannot forge a signature, you cannot mis-encrypt. Sorry, you're wrong on that.  Nothing bad will happen. If you don't believe me, try it.

Lastly, both RFC 2440 and RFC 4480 say:

A Key ID is an eight-octet scalar that identifies a key. Implementations SHOULD NOT assume that Key IDs are unique.

and

Note that it is possible for there to be collisions of Key IDs -- two different keys with the same Key ID.  Note that there is a much smaller, but still non-zero, probability that two different keys have the same fingerprint.

Yes, you're right that the user experience of a command-line program that allows you to type in a subset of a 64-bit number can lead to confusion -- you got led there. But it's not an attack and not a security problem.

Regards,
Jon, OpenPGP co-author and co-founder of PGP.

Posted by Jon at Tue Dec 27 16:35:04 2011

Hi Jon,

I'm honored that you took the time to comment!

The only thing here that I call an "attack" is the collision finding tool. I agree that it's not fundmentally a security flaw, as I stated clearly in the introductory paragraph. It's just that using 32-bit key IDs is a bad idea.

Zooko explained clearly what I meant -- there is a usability problem that makes it easy to mis-use GNU Privacy Guard in an insecure way.

It seems to me that GPG and other similar tools should be modified to only accept 64-bit key IDs to avoid users hitting this problem.

In the case of the --refresh-keys issue I described, it is hard to argue that this is correct behavior. Can you clarify that point?

Posted by Asheesh Laroia at Tue Dec 27 18:18:05 2011

As an attorney, I've been relying on OpenPGP with GPG for a few years. My key is hosted at MIT, just like yours. At the time, it was generated using recommended defaults; thus not affected by collision. I've added a note specifying the use of 64-bit (or longer) key IDs for clients using PGP. Thanks for pointing this out.

Posted by Maria Olaru at Tue Dec 27 19:34:53 2011

You do not need to grep gpg --list-keys output: you can give it a key ID or FP as argument!

Posted by Elessar at Wed Dec 28 05:34:15 2011

It would be interesting to see how this affects systems like the RIPE DB.

LIRs updating records in the RIPE DB often do so by signed emails, but first you must put a key into the database and specify that it is to be used for authentication for objects "owned" by your "maintainer" object.  While I imagine that the RIPE DB won't accept your duplicate key, you could create an interesting "denial of service" by registering a key with someone else's 32-bit ID into the RIPE DB, thus preventing them from using their key (and having to generate another one).

There may be other exploits would could happen based on this.  I should perhaps draw the RIPE DB working group's attention to this work.

Posted by Marek at Wed Dec 28 13:06:54 2011

Hi Marek!

Yes -- reading through the RIPE FAQ on the use of PGP, it seems that they use 32-bit key IDs. They give this example: auth: PGPKEY-XXXXXXXX

That is probably a vulnerable use of OpenPGP. It seems like they are vulnerable to attack by someone who generates a key whose ID is the same as an existing "mtner" key.

If necessary, I can work with you to create a proof-of-concept for this.

Posted by Asheesh Laroia at Wed Dec 28 13:13:14 2011

I'd be interested in learning how you can collide a 32-bit key so quickly on a simple netbook. I'm currently using --batch and a shell script to brute force it, and on my 8 core Intel, I can only move along about 5 million keys per day, which would take over 2.5 years to completely exhaust the keyspace, assuming a uniform distribution. If you don't mind emailing me the code, that would be great.

Posted by Aaron Toponce at Mon Sep 10 08:42:23 2012

Hi Aaron,

The key is to keep the public key material constant, but to loop over fingerprints.

To do this fast, it's important to understand what the fingerprint is: a SHA1 hash of some data. Which data exactly? Take a look at http://tools.ietf.org/html/rfc4880#section-5.5.2 for that.

Posted by Asheesh Laroia at Mon Sep 10 12:17:16 2012

Marek's example is a great proof-of-principal for what you're pointing out.

Of course, this isn't just an issue of expanding the visible entropy of the hash, because SHA-1 has known collision vulnerabilities, right? So even if you used the entire fingerprint, it'd still be possible (with enough time!) to spoof the entire fingerprint, which would be far harder to detect by even seasoned crypto-heads.

Is it possible to opt for a better hash algorithm for generating fingerprints, or do the keyservers only support SHA-1?

Posted by Cathal at Tue Sep 11 06:56:17 2012

Hi Cathal! Yes, it's a matter of expanding the visible entropy -- throwing away everything but 32 bits is a bad idea.

About SHA1's collision resistance, I won't comment on that; I'd have to go read more papers before commenting intelligently.

As for if SHA1 is required -- yes, it's part of the OpenPGP definition of  "fingerprint". See http://tools.ietf.org/html/rfc4880#section-12.2

Posted by Asheesh Laroia at Tue Sep 25 15:35:26 2012

Haha! @...

Ian Jackson's reply "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."

Posted by Matthew M. Kaufman at Sun Dec 2 06:17:23 2012

I sent a link to this page in reply to somebody claiming their sort ID was enough to verify an e-mail address based search on the Ubuntu Keyserver.

Imagine my horror when I checked your "about" page:
"OpenPGP encrypted email: 0x70096AD1 (my key is in the strong set)"

It apears people just don't like how the longer IDs appear I guess. I my e-mail, I simply link to my public key; stored in armored plain-text. Proper key verification requires out-of-band communication anyway.

Posted by James Phillips at Sun Oct 6 02:45:38 2013

Hi Asheesh,

"It takes about 3 hours to loop through all key IDs on a dinky little netbook."

How long would it take you to create collision for 64-bits keyID?

Posted by Marvin at Wed Nov 6 21:32:59 2013

Hi Asheesh,

"It takes about 3 hours to loop through all key IDs on a dinky little netbook."

How long would it take you to create collision for 64-bits keyID?

Posted by Marvin at Wed Nov 6 23:14:37 2013

oh, not that long... Only about 1470879 years. Im sure the collision will be 0x000000000000002a ;)

Posted by Sascha at Wed Dec 18 17:14:44 2013

Comment form

  • The following HTML is supported: <a href>, <em>, <i>, <b>, <blockquote>, <br/>, <p>, <abbr>, <acronym>, <big>, <cite>, <code>, <dfn>, <kbd>, <pre>, <small> <strong>, <sub>, <sup>, <tt>, <var>
  • I do not display your email address. It is for my personal use only.

Name: 
Your email address: 
Your website: 
 
Comment: