OpenPGP: Duplicate keyids - short vs long

Lately there seems to be a lot of discussion around regarding the use of short keyids as a large number of duplicates/collisions were uploaded to the keyserver network as seen in the chart below:

generate_key_bar_chart.php

The problem with most of these posts are they are plain wrong. But lets look at it from a few different viewpoints, one of which is the timing of the articles. For OpenPGP V4 keys the short keyid are the lowest 32 bits of the fingerprint. The specific keys that were published, some 20,000 keys that duplicate the strong set keys, were generated by evil32 in 2014, so nothing is actually new here (except it being published on the keyservers), and adding to that the triviality of short keyid collisions has been known from the start, which is ok, since it is just a short, convenient identifier.

What was interesting with the evil32 keyring however was demonstrating doing this on a large scale, by cloning the full strong set of the common Web of Trust (WoT). A strong set can be described as "the largest set of keys such that for any two keys in the set, there is a path from one to the other".

So what have we learned so far - when discussing keys there is such a thing as a path between keys existing in a strong set (that requires the path to be complete in both directions), the path we're talking about is a signature path, whereby Alice and Bob meet up at a conference and exchange data and check IDs after which they sign each others keys, then a path exists.

So where does duplicate short keyids make things diffused from a security perspective? Absolutely nowhere! The issue arise when people start using OpenPGP without understanding any concept of operational security or key management, and start using encryption and digital signatures "because it is cool" without actually verifying any of the recipients' keys. They go looking for a key on the keyservers, gets two results and are confused, making a large fuss about it.

In many ways we should be thankful that the duplicate keys are on the keyservers and starts confusing people, maybe they will start doing some key verification now? Not likely, when even Computer Emergency Response Teams (CERT) such as the dutch don't understand basic concepts of security and starts wanting to prove the negative and detecting duplicate keyids. In an intentional attack, all the keys found might very likely be an attacker, you should verify positively with the person you want to communicate with, or through your network of trusted peers (that you assign a trust level to when calculating the WoT), never, ever, try to guess what is wrong by proving something is false.

The most common suggestion over the past few days seems to evolve around "Use the long keyid", whereby the short keyid is a 32 bit identifier, the long keyid increases the size to 64 bits, and for GnuPG this can be achieved using "keyid-format 0xlong" in gpg.conf. And sadly, the suggestion is based on the same misconception. For one thing, generating colliding 64 bit keyids is also possible, but the really scary thing is it still assumes users are not properly verifying the keys they are using with the full fingerprint in place, normally along with the algorithm type and creation date, for which purpose I carry around the following slip of paper:

Screenshot from 2016-08-17 18-26-59

The moral? If you actually do your job and validate the keys of your correspondents either directly or through trusted peers (including Certificate Authorities) that have signed the key, whether you're using the short keyid or the long keyid as reference is mostly without importance as the selection of keys you look at are already verified, and the likelihood of having collission on that set of keys is slim.

The one thing that is very sure is that the existence of duplicate/colliding short keyids on the keyserver networks does not impact security if OpenPGP is used properly (if anything it improves it if people start using their brain)

OpenPGP key statistics

Recently there has been some talk about the number of OpenPGP keys available on the various keyservers. My own contribution to this discussion is tracking the development at sks-keyservers.net . As can be seen on both the line chart of total number of keys, and the breakdown to a bar chart for daily addition, new keys are added at a higher rate today than it was just a few years ago, and without any statistical considerations, the change of rate seems to coincidentally correspond to the Snowden leaks.

 

LineChart BarChart

This post will look into some of the underlying data and hopefully provide a bit more information depth. The data was exported from one of my own keyservers yesterday and consists of 3,526,080 primary keys, of which 118 keys were invalid to the point that I've discarded them from the rest of the analysis (unable to properly parse the OpenPGP packets to extract the information). To emphasize; I have not looked into subkeys in any way for the purposes of this post and I have made no attempt to determine whether these keys are expired, revoked or otherwise inactive.

The overall majority (94.74%) were Version 4 keys c.f. RFC4880 with V3 keys representing 4.73% and V2 keys representing 0.53%. DSA keys represented 74.4%, while 25.6% were RSA keys and a minority ElGamal (0.03%), Elliptic Curve keys (35 keys) and keys in the experimental range (32 keys) .

The key lengths spans from 3 keys in the experimental range key with algo id 103 of 224 bits to 32,768 bits (3 keys, two of which are RSA and one DSA). Due to the low occurrence of ECC keys (that have an expectation of lower key lenghts for similar expected security levels -  normally in the 256-521 bit range, although there is a strong possibility that the aforementioned 224 bits keys should also fit in this category) I have not done any adjustment for these. A full 77.4% of the keys are included when looking at the aggregate figures up to and including 1024 bits, roughly 2.7 million of the keys, and the corresponding number when looking at a 2048 and 4096 bits respectively are 95.3% and 99.95% of all keys included.

key_length

OpenPGP Key Signing Parties

After posing Monkeysphere: Easing key management and improving HTTPS security I received some constructive feedback from an acquaintance. The message was clear enough; I need to make an effort in getting more signatures for my key so that it is possible to validate it based on the Web of Trust.

 

There are several ways to get the key better connected, but a popular method is to set up, or simply participating in, key signing parties (KSP). The Keysigning Party HOWTO is a good read, so I won't go into the descriptives too much, except to say that I'm a fan of the List Based Method Party described in the howto. This require a bit more organization ahead of the key signing party, but overall the experience should be a smoother one. The basic idea with this approach is that you have one, or several, organizers that collects the public keys of the participants ahead of time and prepare a list of keys for the participants. Normally there will be a set of requirements for these keys e.g. that they are available on public keyservers such as the sks-keyservers.net pools.

Those wanting to participate then send a copy of the key itself or the keyid or fingerprint for such a key so that it can be retrieved from the keyservers. From an organizer perspective the steps are then to start building up a database of participants, e.g. in a GnuPG keyring, which is what I'll use.

 

Step 1: Create a directory for information about the key signing party

mkdir -p $HOME/Tmp/KeySigningPartyRing

Step 2: For each of the participants, download the keys into a gpg keyring in this home dir

I'm starting with my own keys

gpg2 --homedir $HOME/Tmp/KeySigningPartyRing --keyserver eu.pool.sks-keyservers.net --recv-key 0x0B7F8B60E3EDFAE3

gpg2 --homedir $HOME/Tmp/KeySigningPartyRing --keyserver eu.pool.sks-keyservers.net --recv-key 0x43FE956C542CA00B

These keys are then stored in pubring.gpg in the homedir specified.

 

Step 3: Creating the participant list

To create a list of participants based on the information found in the keyring I personally use a PHP Script that is available at https://bitbucket.org/kristianf/keysigningpartylist

This script take the homedir as an argument, so I run it as

php -f /path/to/keysigningPartyList.php $HOME/Tmp/KeySigningPartyRing

The script can be configured by a file called ksp_conf in the same homedir,  I set the variables as

title: My KSP
date: 2013-12-31

Step 4: Digitally sign the participant list

In order to ensure that the list has not been modified after it is uploaded to a http/ftp location that the participants have access to I then sign the two files generated from the script, which unless otherwise configured in ksp_conf is key_party_list.html and fpr.txt I also sign these files using gpg. To do this, while having the homedir as my working directory,  I run

for f in key_party_list.html fpr.txt; do gpg2 --armor --detach-sign $f; done

 

Step 5: Upload the participant list

I can then upload the participant list, the fingerprint list (this is a convenience file, more on that later) and the relevant digital signatures.

for f in key_party_list.html* fpr.txt*; do scp "$f" "server:/path/to/openpgp_key_signing_party_example/"; done

The result can be seen at http://dev.kfwebs.net/openpgp_key_signing_party_example/ . Each participant will then print the participant list, or the organizer print them and bring along to the key signing party.

Step 6: Holding the KSP

During the KSP each participant then bring a copy of their own fingerprint and key data that can be used to match against the list and verify the ID documents to make sure they match the UID.

 

Step 7: Signing the keys and uploading this for others to see

After the KSP is done, and all keys have been verified, it is time to sign the other's keys. This is where the convenience-file fpr.txt comes in, as this can readily be passed on to tools such as caff and monkeysign or it can just be used to retrieve all the keys from a keyserver.