A different sort of "Fake Linus Torvalds"

A Linux Foundation publicity scheme once (in)famously created a "Fake Linus Torvalds" on Twitter, but a different sort of fake has more recently appeared. A message posted to the linux-kernel mailing list on August 15 announced the existence of a PGP key with the same short key ID as that of Torvalds's real key—something that could potentially lead programs and users to confuse the two keys. The problem with key ID collisions has been known for some time, but the message may have served to raise the profile of the dangers of using short PGP IDs.

PGP keys are typically used for encryption or for digitally signing data of some sort. Those signatures can be used to show that a private key corresponding to a particular public key was used, which strongly implies that the owner of the public key was the one who did it—as long as the private key remains private, of course. Signatures are often used on software distributions of various sorts, including packages, kernels, and, sometimes, commits in Git repositories.

These days, the PGP program itself is not widely used, though the standards (such as OpenPGP) it spawned have been picked up and carried forward by projects like GNU Privacy Guard (GnuPG or GPG). The public key for a PGP user is usually represented as an unwieldy blob of text, however; without some kind of "extra" knowledge, there is no way to know that a given key is really owned by the user it purports to come from. There are two somewhat-related mechanisms to address those problems: keyservers and the web of trust.

Keyservers provide a way for users to get someone else's public key, while the web of trust is a way to provide the user some level of trust that key comes from who it purports to. In order to have a key that is more trusted, users will try to get their key signed by other users' keys. When a new key is examined (normally by GPG or some other program), those signatures can be checked to see if the keys used in the signing are already trusted or if they belong to the "strong set" (a group of well-connected keys within the web of trust). Based on that examination, users can choose a trust level they place in the key.

Unfortunately, all of that is somewhat complex and hard for those who are not particularly technically savvy to understand. So tools are meant to help simplify some of that. But one of those simplifications can lead to problems such that users (both savvy and not) may be tricked into using (and trusting) keys that are not owned by the person or organization they think.

Keys have a "fingerprint" that uniquely identifies them, but they are relatively long hexadecimal strings (20 bytes, so 40 characters), which makes them unwieldy as well—at least for day-to-day use. For that reason, shorter substrings called key IDs (usually either four or eight bytes worth of hexadecimal) are often used to "identify" keys. Ten or fifteen years ago, even four-byte IDs were relatively safe, but these days it is rather easy to generate a key with a key ID that collides with an existing key. That's exactly what was done with Torvalds's key as noted in the mailing post (a key for "Fake Greg Kroah-Hartman" was similarly outed in the message).

In fact, a project called "Evil 32" has created a collision for every 32-bit key ID in the strong set. It used its scallion program to create those collisions, each in roughly four seconds using a GPU. Key collisions might not be that big of a problem, except that GPG and other tools don't treat them as an error, so users can end up with the wrong key. GPG certainly warns that untrusted keys are being used, but that is a relatively common warning in "normal" GPG use so it goes unnoticed.

Evil 32 has an example of how the problem might manifest itself. It uses a package from Puppet Labs for the demonstration (though, now, the instructions at Puppet Labs use its full key fingerprint to avoid the problem). When asking the keyserver for the key ID provided (using the --recv-keys option), GPG would actually accept multiple keys with that key ID and add them to the keyring. Because the signature file contained only the key ID at that time, either of the keys could be used to verify the contents of the package. Thus, a version with a backdoor, say, and signed with the attacker's colliding key could be downloaded and would pass a verification step.

At some level though, the root problem is that the web of trust isn't really being used the way it was envisioned (or, as some would say, the way it should be used). If users were only trusting keys with signatures of other trusted entities or that had other indications of trustworthiness and GPG were configured to reject untrusted keys, the problem would largely not exist. But, for the most part, the "there is no indication that the signature belongs to the owner" warning message is expected by users—if it is even seen.

Given that GPG is used by other encryption tools, some of which also try to simplify the process for novice users, the fact that multiple keys match a particular key ID may be completely hidden by the interface. That's good for reducing complexity, perhaps, but not so good for security and package integrity. GPG has a well-earned reputation for being difficult to use correctly, though it must be said that alternatives don't seem to be overtaking it any way.

Kroah-Hartman reacted to the revelation of his fake key with some cogent observations about the situation:

As he noted, this problem has been known for some time. There is a blog post from 2011 about it that clearly indicates it is a known problem at that point. A recent post that LWN linked to in June noted colliding key IDs had been found in the wild. The longtime existence of "vanity" key IDs (those that spell out some word or are based on an interesting number) clearly shows the problem—if people can choose their key IDs, nothing stops them from choosing someone else's. In the end, this most recent episode just provided yet another reason for users of PGP keys to pay attention and either use full key fingerprints or the web of trust—perhaps both, though that is probably simply overkill.