Hagrid: A New Verifying Key Server Built on Sequoia

On Wednesday, Vincent launched a new key server at keys.openpgp.org! What makes this launch special is that keys.openpgp.org is running Hagrid —“The Keeper of Keys”—a new verifying key server, which is written in Rust and based on Sequoia. Even though the launch didn’t receive much media attention, 700 people have already verified their keys in the 48 hours since the announcement.

(Follow this link to read the tl;dr.)

Genesis

We started Hagrid as a toy project. Our original goal wasn’t to develop a production-ready key server. Instead, Hagrid was part of a series of experiments to test Sequoia’s API for completeness and ease of use. Several things convinced us to turn Hagrid into a real project: the state of the SKS key servers ¹, the disconnect between how people assume key servers work and how they actually work, GDPR concerns, and interest from the community in a replacement for the SKS key servers.

A few people told us that we are wasting our time with Hagrid, and that we should just let key servers die. Instead, they said, recent efforts to improve key distribution like p≡p ², Autocrypt, and the Web Key Directory (WKD) make key servers redundant; Hagrid may fix a few problems, but key servers are simply broken.

Although we agree that p≡p, Autocrypt, and WKD have advantages over key servers, none of them have seen significant deployment so far. We think that abandoning key servers for solutions that aren’t widely deployed is a disservice to current users. In fact, we think that if the investment is modest, it makes sense to continue to improve current technologies until their replacements have been adopted.

We also disagree that key servers have no further value: neither p≡p nor Autocrypt fully replace all of the useful functionality that key servers provide. First, whereas p≡p and Autocrypt use email for key distribution, key servers only require HTTPS, which enables more workflows. Second, key servers are also useful for distributing key updates like revocation certificates, new subkeys, first- and third-party certifications, etc.

WKD does largely provide this functionality (modulo third-party distribution of third-party certificates). And, it does so in a more secure manner than key servers can; using a validating key server means also relying on the key server operator to behave. But, WKD requires mail providers to extend their infrastructure to support WKD. And, despite being first published in 2016, only a few minor, privacy-focused email providers currently do that. In contrast, using a verifying key server doesn’t require the email provider to do anything new.

The Status Quo

Anyone who regularly uses the [SKS key servers] can vouch for how slow they are, and how often queries simply fail, particularly in recent times. This appears to be at least partially due to the software’s architecture: SKS is a single-threaded program, and parallelism is bolted on using a proxy. Unfortunately, whatever the actual problem is, it’s unlikely that it will be fixed anytime soon: SKS is written in unidiomatic OCaml, which makes even developers interested in improving the software shy away from contributing, and may explain why development of the SKS software all but stalled several years ago.

Another problem with SKS is that it is effectively a garbage pile. This is by design: the key servers manage a de facto append-only log, and anyone can upload a key in anybody’s name. This would be fine if people used the key servers as intended. That is, as a repository for finding key updates (e.g., revocation certificates, new subkeys, third-party signatures, etc.). But, this is not how people use the key servers in practice. Instead, people assume that the key servers are a directory, like a telephone book, and that the published keys have received some minimal vetting. Unfortunately, the key server interface invites this interpretation: historically it makes looking up keys by email address easy, and up until a few years ago, this actually worked surprisingly well. But since vandalism on the key server infrastructure (e.g., evil32) has become common, the key servers have become increasingly polluted. This understandably confuses many users, and even advanced users and trainers blame the key server operators for not doing something to improve the situation.

Related to this problem is the GDPR, which states that users need to be able to control their personally identifiable information. Since the SKS key servers are an append-only log, users can neither delete their own keys, nor delete keys that were created in their name. Independent of how any individual feels about this, users want this, the law requires it, and SKS’s architecture is incompatible with it.

A Solution

These performance and UX issues are well known to those actively working in the OpenPGP ecosystem. And, when we told some of them about Hagrid, many encouraged us to not only reimplement the key servers to address the performance problems, but to try and fix these UX issues.

Talk, as the saying goes, is cheap. But, their actions showed that they were serious. There are already several external contributors and testers including maintainers of key servers in the SKS key server pool. Vincent, a maintainer of Open Keychain, K9’s OpenPGP implementation, has largely taken over development of Hagrid. Kristian Fiskerstrand, the maintainer of the SKS key server network ¹, hopes that he can eventually retire SKS in favor of an alternative key server network. Phil Zimmermann, the creator of PGP, offered to make the service available under keys.openpgp.org. And the developers of Open Keychain and Enigmail are in the process of changing their mail clients to use keys.openpgp.org by default.

Currently, Hagrid is less than 6000 SLOC. Its only major missing feature relative to SKS is synchronization with other key servers. Supporting this is important for scalability and robustness. But, implementing this feature requires a fair amount of effort and before we invest that time, we want to test Hagrid to see if our approach to solving the UX problems is accepted by the broader OpenPGP community.

A Verifying Key Server

A verifying key server only publishes identifiable information (specifically, User IDs) that have somehow been verified, and for which consent has been given. This idea isn’t terribly novel: in 2004, the PGP Corporation released the PGP Global Directory, a proprietary product now owned by Symantec. And, in 2016, the Mailvelope project began work on their own version based on openpgp.js.

Like the PGP Global Directory and the Mailvelope key server, we decided to verify User IDs using an email-based challenge-response system: when Alice uploads her key, we send an email to the email address in each of the self-signed User IDs in her key, and if she (or someone else) follows the link, then we consider the corresponding User ID to be verified. Users understand this workflow: this is how mailing list subscriptions, and account creation often work.

This email-based challenge response doesn’t provide a strong verification, of course. It only checks that a person who can read the verification email (either the user, the email provider, or a machine in the middle) has followed a link. But this protection is already enough to discourage drive-by vandalism, and untargeted attacks.

We implemented key removal in a similar way: if Alice wants to delete a User ID from the key server, she submits a request via the web page, and the key server emails her a challenge to the requested address. If she responds to this challenge, Hagrid allows her to remove any of the User IDs associated with the key. The reason that Alice doesn’t need to respond to a challenge for each User ID is that she needs to be able to remove User IDs with email addresses that she no longer controls.

Unlike the PGP Global Directory, Hagrid does not currently require the user to respond to a new verification email for each User ID every six months. We decided that this behavior is too spammy.

Hagrid also doesn’t encrypt the challenge to the user’s key. (The Mailvelope Key Server does this.) This would prove not only that the user possesses the private key, but also that the user can decrypt messages encrypted to that key, i.e., that their software is correctly configured. This is perhaps reasonable when determining whether to publish a key (assuming the key includes an encryption key), but removal challenges must be sent in the clear: a common reason that users give for wanting to remove their keys from a key server is that they have lost access to the key. Also, encryption doesn’t really improve security: although it would stop an attacker who uploads a fake key and hopes that the user mistakenly verifies it, it won’t stop the mail provider or a machine in the middle from uploading a fake key.

Since the key server is doing some verification, it might seem useful to turn this into a machine-readable vouch by having the key server certify the verified User IDs like the PGP Global Directory does. Unlike the PGP Global Directory, which recommends that users completely trust their verification process, we don’t think that the verification is strong enough to even warrant a positive certification. Furthermore, doing such certifications would require that the key server be highly secured since it is now effectively a certificate authority. We think that that is too much responsibility for the server operator.

Notes

Verification emails are not sent when the key is uploaded via HKP. Today, this interface is also used to upload third-party certificates. So having it send a verification email would cause Hagrid to spam users. Instead, a user can request a verification email via the web page, and software can use a new interface to upload a key and indicate that the user should get a verification email.

When an email address is verified, any prior association is broken. That is, in Hagrid, an email address is associated with at most one key. Although there are some legitimate use cases for having multiple keys associated with a single email address, these use cases are specialized, and to simplify the UX for normal users, Hagrid imposes this restriction.

The HKP search interface allows for substring matching on User IDs. To improve privacy, Hagrid only allows exact string matching. This way it is much harder to mine the key server for email addresses: instead of guessing a substring (e.g., a domain), the miner must query email addresses individually.

More Than A Verified Directory

Key servers are not only used for looking up keys by email address. They provide a well-known repository for key updates like revocation certificates, new subkeys, first- and third-party certifications, etc. Providing this data for keys that haven’t been verified doesn’t conflict with our goals of providing an authenticated directory, or giving users control over their personally identifiable information.

The mechanism is simple: if no User IDs have been verified, we just return the key as usual without any User IDs. In this case, the key can only be found by its Key ID or fingerprint, but that is exactly the behavior that is desired.

Technically, keys without any User IDs are not valid: RFC 4880 says that an OpenPGP key must have at least one User ID. But, OpenPGP implementations should have no problem merging keys without any User IDs into an existing version of the key with a User ID. Such a key might be available locally if it was received via another channel (p≡p, Autocrypt, WKD, etc.). But, even if only some OpenPGP implementations adopt this behavior, keys without User IDs will not negatively impact the rest: they will just reject such keys as being invalid. OpenPGP implementations have to check key validity anyways as key servers should not generally be trusted.

Of course, the OpenPGP community could decide to provide first-class support for keys without User IDs. These types of keys can still be useful. For instance, an application could map local identifiers (so-called pet names) to fingerprints, and mostly ignore User IDs. (This is actually the approach that Sequoia’s public key store is taking: we prefer presenting an address-book centric view, which people are used to from dealing with smart phones, rather than a key-centric view, which, in our experience, is non-intuitive and OpenPGP specific.)

An alternative is to simply fabricate an empty User ID for keys with no validated User IDs. This is actually allowed by the OpenPGP specification: User IDs do not require a self-signature. Not requiring self-signatures isn’t actually a misfeature. For instance, if Alice knows that the right key to use for bob@example.com, she could send a certification to Carol for exactly that email address, even if Bob never created a User ID with that email address. Although no OpenPGP implementation currently supports these types of signatures (and most don’t support User IDs without a self-signature), we plan to automate the generation of such certifications using a privacy-preserving certification mechanism in Sequoia to facilitate group replies.

Given this support, the Hagrid instance running at keys.openpgp.org has been seeded with the most recent version of the SKS key server dump stripped of any User IDs. Of course, we haven’t sent out confirmation emails; users need to trigger that themselves. Unfortunately, it is currently unclear how Hagrid will stay synchronized with the SKS key server network.

Federation

The SKS key server network is a federated network. But, a verifying key server requires a central authority to manage the authenticated directory. This would appear to preclude federation. In fact, it appears to preclude mirroring, because User IDs should not be wholesale exported due to privacy and GDPR concerns.

Happily, these concerns only apply to the email directory: the rest of the data can be synchronized. Since it is good practice to regularly check for key updates, we expect that most of the load will be directed to this part of the service anyway. Thus, a Hagrid-based key server network can function in a similar way to the SKS key server network, and it can use a similar trust model.

The email directory could be decentralized by having multiple independent services. We hope that this does not happen as verifying a key with a single provider is already a burden for normal users, and having to do it with multiple providers will simply be annoying. Also, given the amount of authority the directory has (i.e., very little), multiple instances don’t really improve security much. Instead, it would be better to modify Hagrid to implement something like certificate transparency.

Currently, Hagrid does not provide a synchronization mechanism. If the OpenPGP community adopts Hagrid, then we plan to add support for this. One issue is that the protocol used by SKS, although peer reviewed, is not well documented.

More

The SKS key servers have a simple HTML frontend that displays details about keys. Because SKS doesn’t verify any signatures, this can lead to confusing output, e.g., showing a key as revoked even though the revocation certificate is invalid, or showing an invalid User ID. Although Hagrid largely validates signatures, to avoid any sort of confusion, Hagrid will not display keys in a human readable form.

Summary

• Hagrid is a new, verifying key server.
• Verification is done using an email-based challenge-response system
  • The user can be confident that downloaded User IDs were verified by the person who controls the email address in the User ID.
  • User IDs can be deleted by the person who controls the email address in the User ID.
  • Searching by email address only returns an exact match to enhance privacy.
  • Mappings between email addresses and keys are unambiguous: any query will yield exactly one or zero results.
• Hagrid publishes all keys, but strips User IDs that are unverified.
  • Other information is useful: key revocations, new subkeys, first- and third-party certifications, etc.
  • If a key has no verified User IDs, all User IDs are stripped.
• The initial deployment at keys.openpgp.org has imported the current SKS dump stripped of all User IDs
  • Verification emails for those keys still need to be explicitly triggered.
• A federated network similar to SKS is planned, but we are waiting on Hagrid’s reception from the OpenPGP community before implementing it.
  • Only keys stripped of User IDs will be gossiped.

Implementation Details

Hagrid is written in Rust and uses Sequoia’s native API. To implement HKP and the web interface, we use Rocket. We don’t use a database to manage keys, but write them directly to disk. This is simpler to implement and deploy, and enables us to exploit the fact that lookups are essentially static requests, and serve them directly from disk via nginx without involving the key server.

As opposed to SKS, which accepts nearly everything that looks like OpenPGP data, Hagrid only allows uploading public keys that are cryptographically sound. For this we use Sequoia’s TPK ³ data type. TPK stands for Transferable Public Key and is OpenPGP speak for a set of public keys, User IDs, and binding signatures that allow an OpenPGP implementation to verify data signed with the associated secret key, and encrypt data to that public key.

Setting it up

To run your own instance of Hagrid, you currently need to build it. You can read build and setup instructions (for both Hagrid and nginx) in the project’s README file.

Check out Sequoia

Sequoia is more than a library to write key servers with, it’s a project to implement the OpenPGP standard in a secure and easy to use way to help you write all kinds of applications. For more information, check out our website the code or talk to us in #sequoia on Freenode. If you are interested in Hagrid, there is also a channel on Freenode dedicated to it, ##hagrid.

Happy Hacking!

Credits

Hagrid has been primarily implemented by Kai Michaelis, Vincent Breitmoser and Justus Winter. David Mjölnir, dkg, Leon Tan, Nico Weichbrodt, Paul Fawkesley, and Wiktor Kwapisiewicz have reported issues and submitted improvements. Hagrid was designed by Justus Winter, Kai Michaelis, Vincent Breitmoser, and Neal H. Walfield. This blog post was written by Kai Michaelis and Neal H. Walfield.