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 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 --recv-key 0x70096AD1
gpg: requesting key 70096AD1 from hkp server
gpg: key 70096AD1: public key "Asheesh Laroia <>" imported
gpg: key 70096AD1: public key "Asheesh Laroia <>" 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 --refresh-keys
gpg: refreshing 1 key from hkp://
gpg: requesting key 70096AD1 from hkp server
gpg: key 70096AD1: public key "Asheesh Laroia <>" imported
gpg: key 70096AD1: "Asheesh Laroia <>" 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 Tue Dec 27 00: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 Tue Dec 27 01:15:12 2011

My key ID A56E15A3 has conflicted since day 1.

Posted by Hub at Tue Dec 27 01: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 Tue Dec 27 04: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 13:40:05 2011

Hash: SHA1


my key is:

pub  1024D/38EA4970 2002-10-08
uid  Juergen Schmidt <>

I refer to your offer to generate a keypair for

bye, ju
Version: GnuPG v1.4.10 (GNU/Linux)


Posted by Juergen Schmidt at Tue Dec 27 16: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 20:01:35 2011

Hi Juergen,

Please enjoy the following PGP private key:

Version: GnuPG v1.4.11 (GNU/Linux)


Posted by Asheesh Laroia at Tue Dec 27 21: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.


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.

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

Posted by Jon at Tue Dec 27 21: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 23: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 Wed Dec 28 00: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 10: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 18: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 18: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 12: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 for that.

Posted by Asheesh Laroia at Mon Sep 10 16: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 10: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

Posted by Asheesh Laroia at Tue Sep 25 19: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 11: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 06: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 Thu Nov 7 02: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 Thu Nov 7 04: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 22:14:44 2013

A college and I gave a talk about this at DEF CON. We created a tool to find collisions on the GPU, and cloned the Web of Trust's strong set. You can find more info at

Posted by FreeTheNation at Sun Nov 2 04:21:05 2014

Posted by FarEdullypard at Wed Dec 10 09:44:13 2014

Posted by FarEdullypard at Wed Dec 10 10:21:37 2014

Posted by FarEdullypard at Wed Dec 10 10:32:04 2014

Posted by FarEdullypard at Wed Dec 10 11:11:57 2014

Posted by FarEdullypard at Wed Dec 10 18:14:39 2014

Posted by FarEdullypard at Wed Dec 10 18:50:11 2014

Posted by FarEdullypard at Thu Dec 11 00:28:01 2014

Posted by FarEdullypard at Thu Dec 11 03:49:06 2014

Posted by FarEdullypard at Thu Dec 11 04:23:20 2014

Posted by FarEdullypard at Thu Dec 11 04:28:00 2014

Posted by FarEdullypard at Thu Dec 11 04:36:12 2014

Posted by FarEdullypard at Thu Dec 11 04:51:26 2014

Posted by FarEdullypard at Thu Dec 11 04:51:37 2014

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.

Your email address: 
Your website: