Sequoia Web of Trust

A Rust library for authenticating bindings between User IDs and certificates using OpenPGP's web of trust. This library is designed around OpenPGP's data structures, but it does not require OpenPGP data. Instead, it is possible to manually describe a web of trust.

This crate also includes a CLI tool, sq-wot, for authenticating bindings and exploring a web of trust.

Introduction

The web of trust is a decentralized trust model popularized by PGP. It is a superset of X.509, which is a hierarchical trust model, and is the most popular trust model on the public internet today. As used on the public internet, however, X.509 relies on a handful of global certification authorities (CAs) who often undermine its security.

The web of trust is more nuanced than X.509. Using the web of trust, require multiple, independent paths to authenticate a binding by only partially trusting CAs. This prevents a single bad actor from compromising their security. And those who have stronger security requirements can use the web of trust in a completely decentralized manner where only the individuals they select---who are not necessarily institutions---act as trusted introducers.

Today, the tooling around the web of trust is primitive at best. Many people interpret this lack of good tooling as a sign that the web of trust is intrinsically difficult to use. We disagree and think that efforts like our OpenPGP CA provide evidence that this is not the case.

See the spec for an in-depth discussion of semantics and implementation.

This library provides functionality to find arbitrary paths in a web-of-trust network, and to validate and lint specific paths. This functionality is also exposed via a command-line tool, sq-wot.

Usage

To use sequoia-wot from your project, you should add the following to your crate's Cargo.toml:

[dependencies]
sequoia-wot = "0.8"
sequoia-cert-store = "0.3"
sequoia-openpgp = { version = "1.0.0", default-features = false }

To compile your crate you would then run:

$ cargo build --release --features sequoia-openpgp/default
$ cargo test --features sequoia-openpgp/default
$ cargo doc --no-deps --features sequoia-openpgp/default

If you do not disable the use of sequoia-openpgp's default features, then sequoia-openpgp will select the default cryptographic backend, and your users won't be able to easily compile your crate with a different cryptographic backend.

sequoia-openpgp currently uses Nettle as its default cryptographic backend. sequoia-openpgp also supports OpenSSL (sequoia-openpgp/crypto-openssl), Botan 3 (sequoia-openpgp/crypto-botan), Botan 2 (sequoia-openpgp/crypto-botan2), Windows CNG (sequoia-openpgp/crypto-cng), and Rust Crypto (sequoia-openpgp/crypto-rust). For more information about building sequoia-openpgp, please refer to sequoia-openpgp's README. This also includes information about the different backends' build requirements.

sq-wot

sq-wot is a CLI to the library. It implements five subcommands: authenticate, lookup, identify, list, and path. All commands authenticate something. In this context, authenticate means to establish the degree to which an identity should be associated with an OpenPGP certificate based on assertions that the user and others have made. Typically, there is a minimal trust threshold, and if the aggregate trust amount is below that, then the command fails.

The first four subcommands authenticate bindings by looking for paths in a web-of-trust network. This is done by computing the maximum flow between trust roots and a binding. Due to the complexity, this can be computationally expensive, but it is quite fast in practice: queries tend to take less than a millisecond. The computation cost is normally dwarfed by the time it takes to parse and validate certificates. The last subcommand authenticates and lints a path. Because the path is known, this is very fast.

In short, authenticate works with a specific binding; lookup finds certificates that have been authenticated for a specific User ID or email address; identify finds User IDs that can be authenticated with a particular certificate; list finds all authenticated bindings; and, path checks a path's authenticity.

authenticate a binding

A binding is a pair consisting of a certificate and a User ID. The certificate is usually denoted by its fingerprint or Key ID. An example of a binding is: 8F17777118A33DDA9BA48E62AACB3243630052D9 and Neal H. Walfield <neal@sequoia-pgp.org>. Another example is CBCD8F030588653EEDD7E2659B7DD433F254904A and Justus Winter <justus@sequoia-pgp.org>.

A binding is authentic if there is a valid path from a trust root, via intermediate introducers, to a target binding. A trust root is a certificate that you rely on to assert the authenticity of bindings. A trust root is also sometimes called a trust anchor. Intermediate introducers are certificates that a trust root or other intermediate introducer delegates its introduction capability to. They are also called certification authorities. Trust roots and intermediate introducers are collectively referred to as trusted introducers.

An example of a path is: 8F17777118A33DDA9BA48E62AACB3243630052D9, CBCD8F030588653EEDD7E2659B7DD433F254904A, Justus Winter <justus@sequoia-pgp.org>. This path includes a root and a target binding, but it does not have any intermediate introducers.

sq-wot authenticate tries to authenticate a binding. It looks like this:

$ sq-wot --gpg authenticate CBCD8F030588653EEDD7E2659B7DD433F254904A 'Justus Winter <[email protected]>'
[✓] CBCD8F030588653EEDD7E2659B7DD433F254904A Justus Winter <[email protected]>: fully authenticated (133%)
  Path #1 of 2, trust amount 40:
    ◯ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

  Path #2 of 2, trust amount 120:
    ◯ F7173B3C7C685CD9ECC4191B74E445BA0E15C957 ("Neal H. Walfield (Code Signing Key) <[email protected]>")
    │   certified the following binding on 2022-02-04
    └ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

sq-wot prints out the paths from the trust roots to the specified binding. Because, I also marked the certificate that I'm trying to authenticate as a partially trusted trusted root in gpg, it partially authenticates itself, as the first path shows. The second path is valid, because I directly certified the binding.

The --gpg option tells sq-wot to read my trust roots from gpg and to read gpg's keyring. Trust roots can also be specified explicitly using the --trust-root or -r option. Keyrings can be specified using the --keyring option. For instance, I can confirm that Clint Adams certified dkg's certificate for the User ID <dkg@debian.org>:

$ sq-wot -r F6D3495BB0AE9A02 --keyring /usr/share/keyrings/debian-keyring.gpg authenticate C29F8A0C01F35E34D816AA5CE092EB3A5CA10DBA "<[email protected]>"
[✓] C29F8A0C01F35E34D816AA5CE092EB3A5CA10DBA <[email protected]>: fully authenticated (100%)
  ◯ 2100A32C46F895AF3A08783AF6D3495BB0AE9A02 ("Clint Adams (GNU) <[email protected]>")
  │   certified the following binding on 2021-01-01 (expiry: 2023-12-24)
  └ C29F8A0C01F35E34D816AA5CE092EB3A5CA10DBA "<[email protected]>"

Note that in the above examples, I used the whole User ID, not just the email address. sq-wot also has an --email flag, which causes it to consider all User IDs that contain the specified email address. For instance:

$ sq-wot --gpg authenticate CBCD8F030588653EEDD7E2659B7DD433F254904A --email [email protected]
...

Sometimes it is not possible to authenticate a binding. In that case, there are several things that you can try: you can use a public key server to augment your keyring; you can relax the authentication criteria by treating the web of trust as a certification network instead of an authentication network; and, you can query the web of trust to find out what others, who you haven't directly or indirectly designated as trusted introducers, think of a particular binding.

Using a Public Certificate Store

By default, sq-wot only uses the certificates that you explicitly supply to it. It may be that a missing certificate is preventing you from authenticating a binding. If you specify --network then sq-wot will look for missing certificates on a keyserver. (This defaults to hkps://keyserver.ubuntu.com, which is part of the SKS network, and which delivers third-party certifications.) Note: sq-wot does not check for updates, even if a certificate is expired; if the key is present locally, it is used as is. You can keep your gpg keyring up to date by running parcimonie, or by periodically running something like:

$ gpg --export \
  | sq keyring list \
  | awk '{ print $2}' \
  | while read fpr; do \
    sq keyserver -s hkps://keyserver.ubuntu.com get $fpr; \
  done \
  | gpg --import

If --network is provided, sq-wot will also consult a WKD, but it currently only does so for the target certificate.

Certification Networks

Normally, sq-wot works with an authentication network. In an authentication network, there is a difference between Alice asserting that someone, say Mallory, controls a particular key, and Alice asserting that Mallory can be relied upon to make assertions. That is, in an authentication network, verifying someone's identity is fundamentally different from delegating to them, and unconditionally believing what they claim.

In a certification network, all certifications are treated as delegations. Specifically, all certifications are treated as if they have an infinite trust depth, and no regular expressions.

Using a certification network can be dangerous. If you certified Mallory's certificate, then Mallory can cause you to consider any binding to be authenticated. Nevertheless, there are uses for certification networks.

Because trust is earned over time, a certification network provides insight into who potentially useful trusted introducers may be, and their certifications can then be upgraded individually. For instance, Alice may have certified Bob's certificate when she first met him years ago. Now Alice wants to authenticate Carol's certificate. Alice may discover that there is no path to Alice in her authentication network, but she may discover that Bob certified Alice in her certification network. As Alice has known Bob for years, and he has proven reliable, she might decide to make Bob a trusted introducer. That would then allow her to authenticate Carol using her authentication network.

Another use for certification networks is in small closed communities, like the Linux kernel developers, Debian maintainers, or Arch maintainers. Here it is assumed that all members are more or less trusted. Using a certification network, it is possible to see who has vetted whom.

Certification networks are also used by so-called PGP path finding algorithms. This mode matches their behavior.

To tell sq-wot to treat the web of trust as a certification network instead of an authentication network, use the --certification-network option. Note: this can be used for all of sq-wot's subcommands, not just sq-wot authenticate.

Using this option with our first example, we find additional paths from Neal to Justus including:

$ sq-wot --gpg --certification-network authenticate CBCD8F030588653EEDD7E2659B7DD433F254904A 'Justus Winter <[email protected]>'
...
  Path #4 of 4, trust amount 120:
    ◯ 8F17777118A33DDA9BA48E62AACB3243630052D9 ("Neal H. Walfield <[email protected]>")
    │   certified the following certificate on 2022-10-07
    ├ 653909A2F0E37C106F5FAF546C8857E0D8E8F074 ("Wiktor Kwapisiewicz <[email protected]>")
    │   certified the following certificate on 2018-02-06
    ├ 7420DF86BCE15A458DCE997639278DA8109E6244 ("Guilhem Moulin")
    │   certified the following certificate on 2018-02-10
    ├ 7845120B07CBD8D6ECE5FF2B2A1743EDA91A35B6 ("Darshit Shah <[email protected]>")
    │   certified the following certificate on 2015-11-09
    ├ D4AB192964F76A7F8F8A9B357BD18320DEADFA11 ("Valodim Skywalker <[email protected]>")
    │   certified the following certificate on 2017-11-19
    ├ CBCD8F030588653EEDD7E2659B7DD433F254904A ("<[email protected]>")
    │   certified the following binding on 2023-01-24
    └ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

Gossip

Sometimes there are no paths from a trust root to the binding that you are trying to authenticate in the certification network. In that case, it may still be helpful to find out who has certified a particular certificate. That is, it may be helpful to listen to other's gossip. The --gossip option finds arbitrary paths to a particular certificate by treating all certificates as if they were trust roots albeit with zero trust.

Gossip is useful for identifying alternate ways to authenticate a certificate. For instance, imagine Ed wants to authenticate Laura's certificate, but asking her directly is inconvenient. Ed discovers that Micah has certified Laura's certificate, but Ed hasn't yet authenticated Micah's certificate. If Ed is willing to rely on Micah as a trusted introducer, and authenticating Micah's certificate is easier than authenticating Laura's certificate, then Ed has learned about an easier way to authenticate Laura's certificate.

In the following example, we see that a certificate with the self-signed user ID OpenPGP CA <openpgp-ca@sequoia-pgp.org> has certified Justus's certificate:

$ sq-wot --gpg --gossip authenticate CBCD8F030588653EEDD7E2659B7DD433F254904A 'Justus Winter <[email protected]>'
...
[ ] CBCD8F030588653EEDD7E2659B7DD433F254904A Justus Winter <[email protected]>: not authenticated (0%)
  ◯ 34F9E4B6A0A70BFEC5AE45198356989DF1977575 ("OpenPGP CA <[email protected]>")
  │   certified the following binding on 2022-02-09
  └ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

Note: By default, --gossip uses an authentication network. --gossip can be combined with --certification-network for even more unreliable information.

lookup by User ID or email address

The lookup subcommand finds certificates that are authenticated for the specified User ID. This is useful when you want to find someone's certificate. As before, we can use the --email option:

$ sq-wot --gpg lookup --email [email protected]
[✓] CBCD8F030588653EEDD7E2659B7DD433F254904A Justus Winter <[email protected]>: fully authenticated (133%)
  Path #1 of 2, trust amount 40:
    ◯ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

  Path #2 of 2, trust amount 120:
    ◯ F7173B3C7C685CD9ECC4191B74E445BA0E15C957 ("Neal H. Walfield (Code Signing Key) <[email protected]>")
    │   certified the following binding on 2022-02-04
    └ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

The lookup subcommand is also a useful tool to evaluate the degree to which the same User ID is authenticated for different certificates. This can help distinguish if a certificate is a forgery, or a legitimate replacement.

This is visualized in the following image, which was created using sq-wot's DOT output format option, and converted to SVG using Graphiz's DOT compiler:

$ sq-wot \
    -r 2AC0A42EFB0B5CBC7A0402ED4DC95B6D7BE9892E \
    -r D8AFDDA07A5B6EDFA7D8CCDAD6D055F927843F1C \
    -r 75BD80E4D834509F6E740257B1B73B02CC52A02A \
    -r 91FFE0700E80619CEB73235CA88E23E377514E00 \
    -r 0E8B644079F599DFC1DDC3973348882F6AC6A4C2 \
    -r 69E6471E3AE065297529832E6BA0F5A2037F4F41 \
    -k archlinux.pgp \
    -f dot \
    -a 500 \
    lookup \
    --email [email protected] | dot -Tsvg

identify by certificate

The identify subcommand finds all bindings that can be authenticated for a given certificate. This is useful when you want to figure out who a certificate belongs to:

$ sq-wot --gpg identify CBCD8F030588653EEDD7E2659B7DD433F254904A
[✓] CBCD8F030588653EEDD7E2659B7DD433F254904A Justus Winter <[email protected]>: fully authenticated (133%)
  Path #1 of 2, trust amount 40:
    ◯ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

  Path #2 of 2, trust amount 120:
    ◯ F7173B3C7C685CD9ECC4191B74E445BA0E15C957 ("Neal H. Walfield (Code Signing Key) <[email protected]>")
    │   certified the following binding on 2022-02-04
    └ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

[✓] CBCD8F030588653EEDD7E2659B7DD433F254904A Justus Winter <[email protected]>: fully authenticated (133%)
  Path #1 of 2, trust amount 40:
    ◯ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

  Path #2 of 2, trust amount 120:
    ◯ F7173B3C7C685CD9ECC4191B74E445BA0E15C957 ("Neal H. Walfield (Code Signing Key) <[email protected]>")
    │   certified the following binding on 2022-02-04
    └ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"
...

The identify subcommand also shows that different User IDs on the same certificate may not all be authenticated to the same degree.

This is illustrated in the following graphic, which was created using the DOT output format:

$ sq-wot \
    -r 2AC0A42EFB0B5CBC7A0402ED4DC95B6D7BE9892E \
    -r D8AFDDA07A5B6EDFA7D8CCDAD6D055F927843F1C \
    -r 75BD80E4D834509F6E740257B1B73B02CC52A02A \
    -r 91FFE0700E80619CEB73235CA88E23E377514E00 \
    -r 0E8B644079F599DFC1DDC3973348882F6AC6A4C2 \
    -r 69E6471E3AE065297529832E6BA0F5A2037F4F41 \
    -k archlinux.pgp \
    -f dot \
    -a 500 \
    identify \
    B5971F2C5C10A9A08C60030F786C63F330D7CB92 | dot -Tsvg

list all authenticated bindings

The list subcommand finds all bindings that can be authenticated for all certificates. This is useful for seeing everyone you can authenticate, and why:

$ sq-wot --gpg list
[✓] 8F17777118A33DDA9BA48E62AACB3243630052D9 Neal H. Walfield <[email protected]>: fully authenticated (100%)
  ◯ 8F17777118A33DDA9BA48E62AACB3243630052D9 "Neal H. Walfield <[email protected]>"

[✓] 8F17777118A33DDA9BA48E62AACB3243630052D9 Neal H. Walfield <[email protected]>: fully authenticated (100%)
  ◯ 8F17777118A33DDA9BA48E62AACB3243630052D9 "Neal H. Walfield <[email protected]>"
...
[✓] CBCD8F030588653EEDD7E2659B7DD433F254904A Justus Winter <[email protected]>: fully authenticated (133%)
  Path #1 of 2, trust amount 40:
    ◯ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"

  Path #2 of 2, trust amount 120:
    ◯ F7173B3C7C685CD9ECC4191B74E445BA0E15C957 ("Neal H. Walfield (Code Signing Key) <[email protected]>")
    │   certified the following binding on 2022-02-04
    └ CBCD8F030588653EEDD7E2659B7DD433F254904A "Justus Winter <[email protected]>"
...

This can also be helpful for examining connections within a community. The following graph was generated using sq-wot's DOT output, and shows bindings that can be authenticated using the Linux kernel's keyring from three community members.

$ sq-wot \
  -f dot \
  -r ABAF11C65A2970B130ABE3C479BE3E4300411886 \
  -r 647F28654894E3BD457199BE38DBBDC86092693E \
  -r CA30110FD5285DE49BB238CD17212997986C5765 \
  -k kernel.pgp \
  list | dot -Tsvg

Verify a path

The path subcommand verifies and lints a path. This is particularly useful when you think that a path should be valid, but sq-wot authenticate silently disagrees.

The path is passed to sq-wot path as a list of fingerprints starting with the root's fingerprint or Key ID and ending with the target certificate's fingerprint or Key ID, and a User ID. If the path is valid, it returns success. If it is not valid, it lints the path.

In the following transcript, we first see that sq-wot authenticate unhelpfully tells us that there are no paths from hpa to Greg Kroah-Hartman's certificate. But when we use sq-wot path, we find out that hpa did certify Greg Kroah-Hartman's certificate, but the certification uses SHA-1, which is no longer trusted:

$ sq-wot --keyring kernel.pgp -r BDA06085493BACE4 authenticate 38DBBDC86092693E "Greg Kroah-Hartman (Linux kernel stable release signing key) <[email protected]>"
No paths found.
$ sq-wot --keyring kernel.pgp path BDA06085493BACE4 38DBBDC86092693E "Greg Kroah-Hartman (Linux kernel stable release signing key) <[email protected]>"
[ ] 647F28654894E3BD457199BE38DBBDC86092693E Greg Kroah-Hartman (Linux kernel stable release signing key) <[email protected]>: not authenticated (0%)
  ◯ 7EAAC9693E7D220546BE576CBDA06085493BACE4 ("H. Peter Anvin (hpa) <[email protected]>")
  │   No adequate certification found.
  │   BDA06085493BACE4 did not certify <38DBBDC86092693E, "Greg Kroah-Hartman (Linux kernel stable release signing key) <[email protected]>">
  │   No active certifications by BDA06085493BACE4 for <38DBBDC86092693E, "Greg Kroah-Hartman (Linux kernel stable release signing key) <[email protected]>"> had a trust amount of at least 120
  │   Certification (B122 by BDA06085493BACE4 on 38DBBDC86092693E at 2011-09-23 18:42.09) is adequate, but it is not valid
  │     B122 by BDA06085493BACE4 on 38DBBDC86092693E at 2011-09-23 18:42.09: policy violation
  │     Policy rejected non-revocation signature (GenericCertification) requiring collision resistance
  │     SHA1 is not considered secure since 2013-02-01T00:00:00Z
  └ 647F28654894E3BD457199BE38DBBDC86092693E "Greg Kroah-Hartman (Linux kernel stable release signing key) <[email protected]>"

License

sequoia-wot is distributed under the terms of LGPL 2.0 or later.

See LICENSE.txt and CONTRIBUTING.md for details.