Crate sequoia_wot

source ·
Expand description

A web of trust engine.

§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. A user can partially trust a CA thereby preventing 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.

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 project provide evidence that this is not the case.

§Web of Trust

A web of trust is a network where the nodes are certificates, which are also called public keys, and the edges are certifications. In OpenPGP’s web of trust, edges may include non-local constraints. For instance, the trust depth parameter determines whether the edges of subsequent nodes should be followed. This means that many graph algorithms cannot be used without modification.

This crate implements a web of trust engine. It is designed around OpenPGP’s authentication concepts, but it does not require OpenPGP data structures and, as such, can be used in other contexts.

We model a web of trust using the Network data structure. As shown in the examples below, a Network can be created either directly from OpenPGP data structures (Network::from_certs) or it can be created manually (Network::new). The latter is useful when the web of trust has been cached. It can also be used to build a web of trust from non-OpenPGP data.

To authenticate a binding, you build up a set of query parameters using a Query object. You then call Query::authenticate to authenticate the binding. The method returns the degree to which a binding (a fingerprint and a User ID) can be considered authentic. Because authentication is not binary in the web of trust, and because multiple paths can be combined to increase confidence, this function returns a set of paths using the Paths data structure.

By using a variant of Dijkstra’s algorithm to authenticate a binding, authentication is fast even for large, highly connected web of trusts. Specifically, its run time is O((|V| + |E|) * log(|V|)) where V are the vertices or certificates, and E are the edges or certifications.

OpenPGP defines several authentication mechanisms, but it does not define how they should be used to authenticate a binding. Although both PGP and GnuPG implement a web of trust, neither documents their exact semantics. This engine treats the network as a flow network, which is similar, but not identical, to how PGP 7 and later work.

§OpenPGP’s Authentication Mechanisms

OpenPGP provides four simple, yet powerful and flexible mechanisms to facilitate authentication. These are third-party certifications, a trust amount parameter, a trust depth parameter, and a regular expression parameter.

A third-party certification is a machine-readable artifact that says that the issuer believes that a binding between a User ID and a certificate is correct. OpenPGP distinguishes four different types of third-party certifications (signature types 0x10 through 0x13). This engine treats all of these different signature types identically. In common practice, a persona certification (signature type 0x11) is often treated as an invalid certification. This engine ignores this distinction.

The trust amount parameter is the degree to which the issuer of a certification is convinced that the binding is correct. This can vary from 0 to 255. Values that are 120 or larger mean that the issuer is fully convinced. Traditionally, an issuer uses 60 to indicate that they are partially (aka marginally) convinced, however, any value between 1 and 119 can be used.

This web of trust implementation interprets the trust amount as an amount of evidence. It assumes that evidence is independent and can be combined linearly. That is, if we have two paths that don’t share any edges, say a trust root partially trusts two certification authorities (CAs) and they both certify a binding, then the two paths can be added together.

The trust depth parameter is used to indicate that the target should also be used as a CA. When this type of delegation is done in OpenPGP, the target is sometimes called a trusted introducer.

The trust depth parameter ranges from 0 to 255. A value of 0 means that the target is not a trusted introducer, and this is just a normal certification of the binding. If the issuer of a certification uses a value of 1, it means that they consider the target to also be a trusted introducer. A value of 2 means that not only is the issuer willing to rely on certifications made by the target, but the target can designate other certificates as trusted introducers. A value of 3 means that the third party can delegate the certification capability. In general, a value of n means that a certificate that is at most n steps away from the issuer may be considered a trusted introducer, and certificates that are at most n+1 steps away from the issuer can be authenticated. Consider the following network where the number is the certification’s trust depth parameter:

alice --2--> bob --2--> carol --2--> dave --2--> ed

alice certifies bob and uses a trust depth of 2. This means that she considers bob to be a trusted introducer and that he can delegate that capability to someone else, which he does when he certifies carol and uses a positive trust depth parameter. Then, because carol certifies dave, alice can authenticate dave. That is, alice - bob - carol - dave is a valid path.

But, alice cannot authenticate ed even though dave considers ed to be a trusted introducer. This is because alice does not consider dave to be a trusted introducer: he is too far away; alice would have had to set the trust depth on her certification of bob to 3 for her to consider dave a trusted introducer.

The trust amount and trust depth parameters interact. If alice certifies bob’s certificate and sets a trust depth of 1 and a trust amount of 60, then the trust amount of any certifications that bob makes are limited to 60. Consider:

alice --60/1--> bob --120/0--> carol

In the above network, alice says that bob is a partially trusted introducer (amount = 60). Even though bob has certificated carol’s key with a trust amount of 120, alice only assigns the path alice - bob - carol a trust amount of 60. In general, a path’s trust amount is the minimum trust amount of any certification in the path.

The final parameter is a regular expression. A certification can include zero or more regular expressions. If it includes at least one regular expression, then at least one of them has to match the target User ID for the path to be valid.

Regular expressions are a mechanism for a user to make use of a CA in a limited way. For instance, ed might be willing to rely on ca@nsa.gov to certify other nsa.gov User IDs, but doesn’t want to rely on ca@nsa.gov to make a statement about any other User ID.

This implementation only applies the regular expression parameter to the target User ID; it does not apply it to any CAs along the path. Thus, ca@nsa.gov could consider ca@fbi.gov a CA and ca@fbi.gov might certify paul@nsa.gov. And, even though the regular expression does not match the intermediate CA’s User ID (ca@fbi.gov), it does match the target so that path would be valid.

§Multiple Paths and Maximum Flow

OpenPGP does not only support binary authentication; it also supports degrees of authentication. If the path that this implementation finds does not authenticate the binding to the required degree, then the implementation will look for additional paths. If paths overlap, then the degree of authentication is the maximum flow where the capacity of an edge is the certification’s trust amount. Consider the following web of trust:

        root
         |  90/2
         v
       alice
40/1  /     \  60/1
     v       v
    bob    carol
120   \     /   120
       v   v
       david

There are two paths from root to david: root - alice - bob - david and root - alice - carol - david. The degree of authentication of each of the paths is the minimum trust amount of any certification along the path, which, in this case, is 40 and 60, respectively. Combining these paths only results in a trust amount of 90, however, since both paths use the root - alice certification and its capacity is 90.

§Multiple User IDs

It is possible to use a certificate to certify multiple User IDs on another certificate using different parameters. When this happens, the path finding algorithm is run as usual and considers all certifications to find the best path; no certifications are trimmed a priori.

The algorithm then creates a type of residual network where the path is removed. But instead of subtracting capacity from the edges that occur in the path (i.e., the certifications), the capacity is subtracted from the multi-edges. That is the capacity is removed from all of the certifications between two certificates.

Consider the following network where alice has certified both bob@some.org and bob@other.org on bob’s certificate:

             alice
      40/2  /     \ 30/3
           v       v
bob@some.org - b - bob@other.org
        20/1 /   \ 120/2
            v     v
          carol  dave
            |     | 120/1
        120 |     v
            |     ed
             \   / 120
              v v
             frank

The algorithm first finds the path a - b - c - f, which has a trust amount of 20. When the algorithm is run on the residual network, it finds a - b - d - e - f, which has a trust amount of 10. This is because the algorithm has to use the bob@other.org certification (the bob@some.org certification’s depth parameter is too small) and all certifications between alice and bob are suppressed by 20.

Critically, the paths a - bob@some.org - c - f and a - bob@other.org - d - e - f are not combined for an aggregate trust amount of 70, even though they have no overlapped edges: they share a multi-edge, which is partially suppressed.

§Examples

Authenticating a binding is a two-step process. First, you build the network. Then you query it.

There are two ways to build the network. You can provide OpenPGP data structures and let the library build the network for you. Or, you can describe the network. The latter approach is useful when you’ve saved a network, e.g., in a database, and don’t want reparse and revalidate the OpenPGP data structures, which can be computationally expensive. It is also useful when you don’t actually have OpenPGP data, but want to use the web of trust.

The following two examples show each of these approaches using the following network:

          0xAA, alice@example.org
                   |  40/1/some.org
                   v
            0xCA, ca@some.org
    120/0  /                 \  120/0
          v                   v
0xBB, bob@some.org     0xCC, carol@other.org

(The numbers next to the edges are the trust amount and trust depth. They are sometimes followed by a domain. The domain corresponds to a regular expression that matches email addresses in that domain.)

There are four certificates. alice@example.org has certified ca@some.org to be a partially trusted (amount = 40) trusted introducer (depth = 1), scoped to some.org. And, ca@some.org has certified bob@some.org and carol@other.org.

With alice@example.org as a root, we can partially authenticate bob@some.org, but, due to the scoping rule, we can’t authenticate carol@other.org at all: the User ID doesn’t match the regular expression.

§Using OpenPGP Data Structures

use sequoia_openpgp as openpgp;
use openpgp::Cert;
use openpgp::cert::CertParser;
use openpgp::Fingerprint;
use openpgp::packet::UserID;
use openpgp::parse::Parse;
use openpgp::policy::StandardPolicy;

use sequoia_wot::Network;
use sequoia_wot::Query;
use sequoia_wot::FULLY_TRUSTED;
use sequoia_wot::PARTIALLY_TRUSTED;


let keyring = "-----BEGIN PGP PUBLIC KEY BLOCK-----

    xjMEYW/3iRYJKwYBBAHaRw8BAQdAnjTe1KqODINdZOIHuaG8s9aOoJxNJ+CunEI5
    // ...
    -----END PGP PUBLIC KEY BLOCK-----";

let certs: Vec<Cert> = CertParser::from_bytes(keyring)?
    // Silently discard invalid certifications.
    .filter_map(|r| r.ok())
    .collect();
assert_eq!(certs.len(), 4);

let alice_fpr: Fingerprint =
    "CE398BE65389548EC2334FE8D16CEC58EADF534D"
   .parse().expect("valid fingerprint");
let alice_uid
    = UserID::from("<alice@example.org>");

let ca_fpr: Fingerprint =
    "3707713749BD735F0CBDD55513DEDD9A0FE51A57"
   .parse().expect("valid fingerprint");
let ca_uid
    = UserID::from("<ca@some.org>");

let bob_fpr: Fingerprint =
    "94E2EADBA4C3472A3832D5A1C749E561EAD44914"
   .parse().expect("valid fingerprint");
let bob_uid
    = UserID::from("<bob@some.org>");

let carol_fpr: Fingerprint =
    "B20E8ED31EB5C0FDEB4709EA526D10B8F33C0349"
   .parse().expect("valid fingerprint");
let carol_uid
    = UserID::from("<carol@other.org>");

let p = &StandardPolicy::new();
let n = Network::from_cert_refs(certs.iter(), p, None)?;
let q = Query::new(&n, &[ alice_fpr.clone() ]);

let paths = q.authenticate(bob_uid, bob_fpr.clone(), FULLY_TRUSTED);
assert_eq!(paths.len(), 1);
assert_eq!(paths[0].0.amount(), PARTIALLY_TRUSTED);
assert_eq!(paths[0].0.certificates().map(|c| c.fingerprint()).collect::<Vec<_>>(),
           vec![ alice_fpr, ca_fpr, bob_fpr ]);

let paths = q.authenticate(carol_uid, carol_fpr.clone(), FULLY_TRUSTED);
eprintln!("{:?}", paths);
assert_eq!(paths.len(), 0);

§Building a Network By Hand

use std::time::SystemTime;
use std::iter::once;

use sequoia_openpgp as openpgp;
use openpgp::Fingerprint;
use openpgp::regex::RegexSet;

use sequoia_wot::CertSynopsis;
use sequoia_wot::UserIDSynopsis;
use sequoia_wot::Certification;
use sequoia_wot::Network;
use sequoia_wot::RevocationStatus;
use sequoia_wot::Query;
use sequoia_wot::FULLY_TRUSTED;
use sequoia_wot::PARTIALLY_TRUSTED;

let reference_time = SystemTime::now();

let alice_fpr: Fingerprint =
    "CE398BE65389548EC2334FE8D16CEC58EADF534D"
   .parse().expect("valid fingerprint");
let alice_uid
    = UserIDSynopsis::from("<alice@example.org>");

let ca_fpr: Fingerprint =
    "3707713749BD735F0CBDD55513DEDD9A0FE51A57"
   .parse().expect("valid fingerprint");
let ca_uid
    = UserIDSynopsis::from("<ca@some.org>");

let bob_fpr: Fingerprint =
    "94E2EADBA4C3472A3832D5A1C749E561EAD44914"
   .parse().expect("valid fingerprint");
let bob_uid
    = UserIDSynopsis::from("<bob@some.org>");

let carol_fpr: Fingerprint =
    "B20E8ED31EB5C0FDEB4709EA526D10B8F33C0349"
   .parse().expect("valid fingerprint");
let carol_uid
    = UserIDSynopsis::from("<carol@other.org>");

let alice = CertSynopsis::new(
    alice_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
    once(alice_uid.clone()));
let ca = CertSynopsis::new(
    ca_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
    once(ca_uid.clone()));
let bob = CertSynopsis::new(
    bob_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
    once(bob_uid.clone()));
let carol = CertSynopsis::new(
    carol_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
    once(carol_uid.clone()));

let alice_certifies_ca = Certification::new(
    alice.clone(), Some(ca_uid.userid().clone()), ca.clone(),
    reference_time)
    .set_amount(PARTIALLY_TRUSTED)
    .set_depth(1)
    .set_regular_expressions(
        [ &b"<[^>]+[@.]some.org>$"[..] ].into_iter());

let ca_certifies_bob = Certification::new(
    ca.clone(), Some(bob_uid.userid().clone()), bob.clone(),
    reference_time);

let certs = &[ alice, ca, bob, carol ][..];
let certifications = &[ alice_certifies_ca, ca_certifies_bob ];
let n = Network::from_synopses(
    certs, certifications,
    reference_time)?;
let q = Query::new(&n, &[ alice_fpr.clone() ]);

let paths = q.authenticate(bob_uid.userid().clone(), bob_fpr.clone(),
                           FULLY_TRUSTED);
assert_eq!(paths.len(), 1);
assert_eq!(paths[0].0.amount(), PARTIALLY_TRUSTED);
assert_eq!(paths[0].0.certificates().map(|c| c.fingerprint()).collect::<Vec<_>>(),
           vec![ alice_fpr, ca_fpr, bob_fpr ]);

Modules§

  • store
    A certificate store abstraction.

Structs§

Enums§

Constants§

  • FULLY_TRUSTED
    The amount of trust needed for a binding to be fully trusted.
  • PARTIALLY_TRUSTED
    The usual amount of trust assigned to a partially trusted trusted introducer.