Evil 32: Check Your GPG Fingerprints

GPG usage has grown steadily while the tooling that supports it remains stagnant despite staggering hardware advancement. 32bit key ids were reasonable 15 years ago but are obsolete now. Using modern GPUs, we have found collisions for every 32bit key id in the WOT's (Web of Trust) strong set. Although this does not break GPG's encryption, it further erodes the usability of GPG and increases the chance of human error.

Stop using 32bit key ids

It takes 4 seconds to generate a colliding 32bit key id on a GPU (using scallion). Key servers do little verification of uploaded keys and allow keys with colliding 32bit ids. Further, GPG uses 32bit key ids throughout its interface and does not warn you when an operation might apply to multiple keys.

Check your fingerprints

Key servers do not use transport encryption (e.g. SSL) and GPG does not verify keys received when using --recv-keys leaving communicaiton with key servers vulnerable to MITM (man in the middle) or DNS attacks. GPG assumes you have manually checked your keys with --fingerprint.

Patched in new versions of GPG!

Examples

32bit key ids are not secure

In the example below, a key is requested with its 32bit key id. The key server has two keys with the specified key id and GPG imports both keys. It is easy to generate and publish a key that looks identical if you only use 32 bits when specifying a key.

free@turing ~$ gpg --keyserver pgp.mit.edu --recv-keys 10000001

gpg: requesting key 10000001 from hkp server pgp.mit.edu
gpg: key 10000001: public key "John Doe" imported
gpg: key 10000001: public key "Jane Doe" imported
gpg: Total number processed: 2
gpg:            imported: 2  (RSA: 2)

GPG does not verify received keys

GPG simply imports whatever the key server sends. No verfication of the response is done before importing. GPG assumes users will manually verify keys received with --recv-keys. In the example below, a key is requested and GPG blindly imports a different key.

free@turing ~$ gpg --keyserver pgp.mit.edu --recv-keys 10000001

gpg: requesting key 10000001 from hkp server pgp.mit.edu
gpg: key 0BADBEEF: public key "Evil32" imported
gpg: Total number processed: 1
gpg: imported: 1 (RSA: 1)

In-depth real world example

Q&A

Where is the source code for the tool you used to duplicate the strong set?

The tool is called Scallion and the source can be found at https://github.com/lachesis/scallion.

Is your clone of the strong set publicly available?

Yes. You can download an 89MiB tar.gz file which contains all generated keys.

I saw that your clone of the strong set is revoked?

Someone downloaded our copy of the strong set and uploaded all of the keys to the SKS keyserver network. :( While we took on this project to help prompt GPG to build a more secure ecosystem, this mass clone made the keyservers harder for everyone to use. Of course anyone could use our tools to regenerate their own strong set clone and do this again, but we'd rather our keys not be used that way.

How could GPG be fixed?

Key exchange is hard and there are no perfect solutions. That being said, there are some changes that could be made to GPG to make things better.

  • When it's ambiguous what key an operation should act on (because of key id collisions or uuid collisions) GPG should refuse to perform the operation automatically. This would fix the issue of receiving keys.
  • If you specify a key id or fingerprint when using --recv-keys GPG should verify that the key/keys returned by the key server actually have the key id or fingerprint you requested.

Aren't you suppose to use the Web of Trust to verify the authenticity of keys?

Absolutely! The web of trust is a great mechanism by which to verify keys but it's complicated. As a result, it is often not used. There are examples of GPG being used without the Web of Trust all over the web.

The Warning: "no ultimately trusted keys found" means that gpg was not configured to ultimately trust a specific key. Trust settings are part of OpenPGPs Web-of-Trust which does not apply here. - Debian SecureApt Wiki

I know about the problems with 32bit key ids, am I safe now?

That depends. Many tools use GPG behind-the-scenes and have the same problems, but never directly show you fingerprints or prompt you. Check that maintainers of software you use are aware of these problems as well.

Who should I contact with questions?

If you have questions related to this page or scallion you should email scallion@aftbit.com

Who authored this page?

Richard Klafter
Email:
GPG fingerprint: CB7C8A7B567FB2C2ACC2873B04FAC2E9CC21424A
GPG key: download here
Eric Swanson
Email:
GPG fingerprint: 9E15397E4D537E3A3A238F87E620C8A74BAF5D09
GPG key: download here

Evil32 logo is free to use under the Creative Commons Attribution 3.0 License.

Page posted 2014-07-03 15:49 UTC.

Updated to reflect GPG patch 2014-12-01 02:01 UTC.