Sequoia PGP v1.0 Released: The Seedling's a Sapling

By Neal | December 16, 2020

Version 1.0. It’s here. After three and a half years of development, we are happy to announce the release of version 1.0 of Sequoia!

The release includes the low-level crate sequoia-openpgp, and a program to verify detached signatures geared towards software distribution systems called sqv.

We will support this API with security updates for at least one year. In 9 months, we will announce whether we will extend this commitment. The two main criteria will be our financial situation (please donate, or sponsor a developer or two), and the number of users.

Getting to Version 1.0

We actually almost released version 1.0 about a year ago. All of the features that we had planned for version 1.0 were implemented, we had good test coverage, and we even had a few users. But, we decided to wait. We decided to wait not because we thought of another feature, or because we became aware of a significant bug, but because we decided to take some time to improve our documentation.

Our goal was to make sure that every module had a helpful introduction, and all public methods had a useful description, a link to the standard, when appropriate, and a meaningful example. Dividing the task between five people, we figured it would delay the release by a month, perhaps two. In the end, well, it took nearly a year, and we had to scale our ambitions back a bit. Nevertheless, we’re quite happy with the result.

First, the documentation is much better. It’s of course hard to quantify its quality. But, we can distill a few numbers. When we started our documentation effort shortly after we released version 0.14, the Sequoia library had just over 11k lines of comments including 53 documentation tests, and 37 kSLOC including 12 kSLOC of unit tests. The 1.0 release has over 33k lines of comments (190% more) including 464 documentation tests (780% more), and 44 kSLOC (21% or 7.5 kSLOC more) including 8k SLOC of additional unit tests.

Second, in the process of documenting our public API and writing examples, we discovered many minor annoyances, some inconsistencies, and more than a few bugs. Since we hadn’t yet commited to a stable API, we could and did fix them.

Finally, as the rate of change of the API had decreased, more projects were willing to try out Sequoia. They provided additional useful feedback, which we integrated.

All in all, we feel that with version 1.0 we’ve not only checked the right boxes, but we also have a high-quality API and implementation that we can be proud of.

Background

Sequoia was started 3.5 years ago by Justus Winter, Kai Michaelis and me, Neal Walfield. Prior to working on Sequoia, the three of us had worked together at g10code on GnuPG. The p≡p foundation hired us not only to create a new OpenPGP implementation using a new architecture and programming language, but to improve the ecosystem around privacy-preserving tools as a whole.

The Sequoia library is a first step in that direction. But it is not our end goal. Indeed, over the past three years, we’ve helped other OpenPGP implementations. We’ve reported bugs that we’ve found (thanks in particular to our OpenPGP interoperability test suite), and even contributed some fixes to other OpenPGP implementations.

And, we’ve invested in tooling. We developed Hagrid, a new verifying OpenPGP key server, which powers keys.openpgp.org and is now maintained by Vincent Breitmoser. We’ve helped OpenPGP CA, a tool written by Heiko Schaefer to create federated CAs for groups like activists, lawyers, and journalists, but also companies, who don’t want to trust centralized infrastructure whose primary incentives are monetary. OpenPGP CA significantly simplifies key discovery and authentication for unsophisticated OpenPGP users. We’ve developed Koverto, an SMTP proxy, which makes it easy to sign and encrypt mails sent by services that don’t support OpenPGP out of the box, like most CMSes. We developed a tool, sq-keyring-linter (Debian), to help users update their OpenPGP Certificates, so that we can finally get rid of SHA-1.

We’re thinking big. We’re thinking not only about mail encryption or even encryption in general, but also about integrity and authentication. And, we’re thinking in particular, about PKI. If users can’t easily find the right certificate for a communication partner, encryption and digital signatures are worthless, and possibly even dangerous.

Sequoia, the Library

In designing Sequoia, we took a library-first approach. Although we have a command-line tool, sq, which we are not yet releasing, we intend for the library to always provide a richer, more expressive interface. We agree that there is value in process separation, but we want to avoid the dangerous complexity of safely shelling out to another program.

The sequoia-openpgp crate (Rust’s terminology for a library) is a low-level, policy-free OpenPGP implementation. Our goal was to implement all of RFC 4880, and provide an API that can be used to access and modify pretty much everything, but is simultaneously secure by default.

We understand low-level to mean not only an API that provides getters and setters, but an API that provides interfaces to parse and serialize those fields, and can combine them in ways intended by the standard, and needed by users. For instance, the Cert data structure encapsulates an OpenPGP certificate (casually referred to as an OpenPGP key). It canonicalizes the structure, and makes it easy to query its properties. But, it does so in such a way that it is still possible for a user to inspect and modify the low-level bits themselves without reimplementing the rest of the functionality. Another example is the DecryptionHelper, which makes it easy to parse and decrypt an OpenPGP message.

An example of how we make the API safe by default is that it is hard to accidentally export secret key material. In Sequoia, you have to explicitly opt-in to export it. Similarly, when updating a signature, the creation time, hash algorithm, and issuer are automatically updated. This is usually what the user wants, but is easy to forget, and hard to debug when forgotten. Critically, it is easy to opt out when that behavior is not desired.

While developing Sequoia, we spent a lot of time thinking about extremes and corner cases. For instance, OpenPGP supports notarizations (signatures over signatures), but as far as we know no OpenPGP implementation supports them. We implemented support for it anyway, and it improved the ergonomics of the common case.

Notable Details

The devel is in the details. And while deviloping Sequoia, we paid attention. Here are a few noteworthy details:

SHA-1 has been broken since 2005. And, in 2011 NIST deprecated its use. Initially, we decided to simply reject any signature that used SHA-1. However, we were recently forced to reevaluate that decision: 22% of Debian developers use a certificate that relies on SHA-1 as do 63% of Arch developers. Even the Fedora release keys use SHA-1.

We decided that we couldn’t simply reenable SHA-1. After some consideration, we’ve opted to permit it in contexts where collision attacks similar to the one presented in SHA-1 is a Shambles are harder. We also use a variant of SHA-1 called SHA1CD (SHA-1 Collision Detection), which detects and neutralizes the known attacks against SHA-1. Among others, GitHub uses it. And, we have also decided to start rejecting SHA-1 by default at the beginning of 2023, i.e., in a bit more than two years. This will hopefully give Debian developers and others sufficient time to fix or replace their certificates.

When we create a signature, we include a salt. This makes it harder for an attacker to predict what data a user will sign. And, it foils attacks where an attacker needs multiple signatures over the same message.

Similar to OpenSSH, we encrypt secret key material while it is in memory. This frustrates side-channel attacks.

Sequoia supports padding messages to obfuscate an encrypted message’s length. We include support for the padmé scheme, but other schemes can be plugged in.

To allow users to control the policy while still using higher-level functionality, Sequoia uses a policy object. A policy object is passed to any method that checks something for validity. For instance, when a method needs to determine whether a binding signature should be used, it invokes the policy object’s signature callback. Our experience suggests that this approach greatly simplifies dealing with this cross-cutting concern in a highly flexible manner.

Policy objects can also be embedded in other objects. For instance, a ValidCert encapsulates a Cert and a policy object. This ensures that the application of the policy is consistent, and hard to forget to apply.

In Sequoia, we prefer the use of formal grammars rather than ad-hoc parsing when doing any non-trivial parsing. For instance, when verifying the structure of OpenPGP Certificates and OpenPGP Messages, we use LALRPOP, a parser generator, to generate the parser.

Sequoia implements a streaming API. If not careful, this can lead to a consumer processing unauthenticated data, which was exploited by EFAIL. To mitigate this type of failure, the DecryptionHelper withholds the last O(1) bytes of data, and only releases it if the message can be authenticated. This makes it harder for an attacker to control what is released. And for short messages, nothing is released since the whole message is buffered.

We’ve tried to ensure that data structures that may be used in a side-channel sensitive context use constant time comparisons.

Where possible, we use a device driver-style API so that it is straightforward to add new backends. For instance, our Signer and Decryptor traits make it easy to implement alternative signing and decryption backends. In addition to the in-memory implementations, we already have implementations that use secret key material managed by gpg agent.

We tried hard to provide helpful error messages. This is particularly difficult when looking for a valid self signature, for instance: if all self signatures are ignored, because they are invalid, what should be shown? In this case, we remember why signatures were rejected, and then show one of those error messages. This is less confusing. The following output illustrates this idea:

$ sq inspect md5.pgp
only-md5-pub.pgp: OpenPGP Certificate.

    Fingerprint: 526F D3F8 4EC7 DA9D E565  1B06 C4C9 7B7F A453 52C3
                 Invalid: No binding signature at time 2020-12-16T14:18:21Z
Public-key algo: RSA (Encrypt or Sign)
Public-key size: 2048 bits
  Creation time: 2020-11-05 09:16:25 UTC

         UserID: MD5 All Around <md5-all-around@example.org>
                 Invalid: Policy rejected non-revocation signature (PositiveCertification) requiring second pre-image resistance
                 because: MD5 is not considered secure since 2004-02-01T00:00:00Z

Finally, we thought a lot about forward compatibility. The OpenPGP standard makes provisions for this by using extensible types, and versioning. We are careful to preserve what we don’t understand, and respect these packets as much as possible.

What’s Missing

Sequoia provides a low-level API. As such, we don’t provide a public or private key store. We do, however, plan to develop them (in fact, we already have prototypes). But, they will be released separately. In particular, we are not convinved that a single design is universally appropriate. For instance, a server application may not care about sharing keys with other applications, and it may have its own database.

Sequoia implements most of RFC 4880. But, it is still missing a few features. In particular, we don’t yet support cleartext signatures. The Cert data structure does not yet respect certification revocations. And, we still need to implement OpenPGP regular expressions, which are used to scope trust signatures. We will add support for these features in the near future.

Sequoia does not implement the cryptographic primitives that it uses, but relies on a library. By default, Sequoia uses Nettle. But, on Windows it is also possible to use Windows CNG, which has the advantage that it is already part of the user’s trusted computing base. A consequence of this is that Sequoia is limited to what the libraries support, and neither supports Elgamal keys, or brainpool keys. (For 25519 keys on Windows, we use the ed25519-dalek and associated crates.)

We have also decided to not support AEAD, as its specification for OpenPGP is still a draft, and consensus has not yet been reached.

For further details, please consult our status page.

What’s Next

Our plans for the near future include:

  • Adding high-level services like a public key store and a private key store.

    We’ve already begun work on prototypes, so we are confident that our low-level API is sufficient. A noteworthy goal of the private key store is to use a device driver-like framework so that different backends can be used. The main motivation for this is to handle smartcards. But, it can also be used to transparently access remote keys, and gpg’s agent, which will simplify interoperability.

  • Continuing to work on our CLI tool, sq.

    Although the tool is already quite usable, and useful, there are still some important features missing. In particular, we want to add a REST-style, JSON-based, versioned API as we expect people will end up writing scripts that use sq, and we want to avoid having them screen scrape its output, which will undoubtedly result in security issues.

More generally, we plan to continue our work in the ecosystem with a particular focus on tooling.

Financial Support

Currently, six people are paid to work on Sequoia. They are all paid by the p≡p foundation. Additional financial support has come from a one-time donation from the Wau Holland Foundation in 2018. Phil Zimmermann, the creator of PGP, donated 1000 Euros. And, Proton Mail donated 1000 Euros after our interoperability test suite found several issues in OpenPGP.js and GopenPGP, which they maintain.

Although the p≡p foundation’s finances are secure in the mid term, it is essential for Sequoia’s long-term health that we diversify our funding. You don’t need to directly use Sequoia to be positively impacted by it. For instance, OpenPGP CA is a new tool for creating federated CAs targeted at simplifying the use of OpenPGP for activists, lawyers, and journalists who can’t rely on centralized authentication solutions. So, consider donating. Of course, if your company is using Sequoia, consider sponsoring a developer (or two). Note: if you want to use Sequoia under a license other than the GPLv2+, please contact the foundation.

Thanks

Sequoia is a team effort. The following people have made significant contributions to Sequoia:

  • Azul
  • Claudio Luck
  • Daniel Kahn Gillmor
  • Daniel Silverstone
  • Devan Carpenter
  • Heiko Schaefer
  • Igor Matuszewski
  • Jonas Bernoulli
  • juga
  • Justus Winter
  • Kai Michaelis
  • Neal H. Walfield
  • Nora Widdecke
  • Wiktor Kwapisiewicz

The following people contributed code:

  • Alexander Kjäll
  • amesgen
  • Azul
  • Björn Petersen
  • Damian Poddebniak
  • Daniel Kahn Gillmor
  • Daniel Silverstone
  • David Sastre Medina
  • Doron Behar
  • Gerhard Bräunlich
  • Hartmut Goebel
  • Hussein
  • Igor Matuszewski
  • Jakub Kądziołka
  • Jakub Onderka
  • Jann Röder
  • Jonas Bernoulli
  • juga
  • Justus Winter
  • Kai Michaelis
  • Leonhard Markert
  • Levente Polyak
  • Neal H. Walfield
  • Nora Widdecke
  • phryk
  • Ruben Pollan
  • Sebastian Thiel
  • Tobias Mueller
  • Wesley Moore
  • Wiktor Kwapisiewicz

And, the following people contributed on our issue tracker: