Data structures for OpenPGP Web of Trust calculations

This library defines data structures to model OpenPGP Web of Trust graphs.

In OpenPGP, certificates (also known as "public keys") are composite objects that are typically associated with one or more identities. OpenPGP certificates are complex data structures, which evolve over time. The validity of certificates and their components may change over time, and both first-party and third-party vouches about identities may be added or revoked.

The data model in this crate formalizes a normalized representation of a subset of this data, geared towards Web of Trust calculations.

Specifically, the "Web of Trust" deals with the associations between certificates and claimed identities. The raw ingredients of Web of Trust calculations - as modeled by this crate - are:

• Certificates
• Identities
• Assertions about the relationships between certificates and identities (in the form of certifications and delegations.)

Note that this crate doesn't prescribe any particular trust model or algorithm for trust calculations.

See https://codeberg.org/openpgp/wot for more context and a description of one particular approach to trust calculations on a wot-network.

See https://codeberg.org/heiko/wot-network-rpgpie for a library that generates a wot-network from a set of OpenPGP certificates.

Nodes

This WoT model uses two types of nodes:

• Certificates: to represent OpenPGP certificates (or "public keys")
• Bindings: to represent the relation between a certificate and an identity

Edges

This WoT model uses two types of edges:

• Certifications, which always point from a certificate to a binding
• Delegations, which always point from a certificate to another certificate

"Amount" value on edges

Each edge in a WoT network has an associated "trust amount", which quantifies how much this edge can be "relied on".

Certification edges have an implicit fixed "amount" of 120. Delegation edges have a user-defined amount.

Each individual "trust amount" in a WoT network graph is limited to a maximum value of 120 (this value is a convention in OpenPGP, it models "full trust").

"Depth" value on delegation edges

In addition to an "amount", delegation edges have a "trust depth". This depth value signifies how many hops the issuer is willing to follow a path:

A value of "1" means that the issuer of the delegation only wants to rely on certifications that were made directly by the target certificate.

A value of "2" means that the issuer is willing to additionally rely on certifications that involve following a second delegation edge, before the final certification edge that points at a binding node (and so on for higher values).

Limiting delegations with regexes

Delegation edges can have "regex" constraints. A regex on a delegation edge constrains the target identity that may be authenticated along any path that uses this edge.

Typically, regexes limit the domain name part of a target identity. E.g. a delegation edge may only allow identities in the domain "example.com".

If a delegation edge has any "regex" constraints, then at least one of these regexes must match the target identity, so that the delegation edge is valid in that context.

In a multistep path, each delegation edge that applies regex constrains (that is, each delegation edge that has one or more regexes set) must have one regex that matches the identity in the target binding. E.g. if the target binding is an identity in "example.org", then each delegation edge that has one or more regex constraints must have one regex for "example.org", otherwise the path is not valid.

A delegation edge that has regexes, but none that match the identity of the target binding in a search, is treated as though it does not exist, in the context of that search.

Basic example WoT network graph

flowchart TD
    A -->|120/1| B

    B -..-> b0
    A -..-> b0
    b0([B, bob])

    A -..-> b1
    b1([A, alice])

classDef bind stroke-dasharray: 5 5
class b0,b1 bind;

This graph shows:

• Two "certificates" A and B, shown as rectangular boxes. These represent "OpenPGP certificates (or public keys)".
• Two "bindings", shown as rounded boxes. A "binding" is a (claimed) connection between a certificate and an identity: A is linked to the identity alice, while B is linked to the identity bob. The identities (alice and bob) correspond to "OpenPGP User IDs".
• Three edges that represent "certifications", shown as dotted lines. A certification is a statement by the issuer that they consider a binding to be valid. In this network, A and B are certifying their own identity bindings respectively (A certifies her connection to the identity alice, and B his connection to the identity bob). Additionally, A certifies the binding between B and bob.
• One edge that represents a "delegation", shown as a solid line. With it, A delegates authentication decisions to B.

Note that each edge (both certifications and delegations) have an associated "amount", in this case the one delegation edge has an explicit amount of "120", while certifications always have an implicit trust amount of "120".

Only the delegation edge has a second, additional, "depth" value. Here, the "depth" value on A's delegation to B is 1 (which means thatA is willing to rely on certifications issued by B, but not willing to rely on additional delegations by B).

Example WoT graph with a regex constraint

In the following diagram, A delegates to B, with amount 120, depth 2, and a regex limiting target identities to the domain "example.org". This means that any path starting from A and going through B can only lead to binding nodes with an identity under the domain "example.org".

flowchart TD
    A -->|120/2/example.org| B
    B -->|120/1| C

    C -..-> b0
    C -..-> b1
    b0([C, carol\@example.org])
    b1([C, carol\@other.org])

classDef bind stroke-dasharray: 5 5
class b0,b1 bind;

Because of the regex constraint, when starting from A, only the path that leads to the binding <C, carol@example.org> is valid.

The delegation by A is saying "I am willing to rely on B, but only for identities under example.org". One reason for this could be that B is a representative of the organization "example.org", and A is willing to rely on B to authenticate identities within their own organization.

However, the binding <C, carol@other.org> cannot be validated via the delegation edge from A to B.

Note that the regex constraint doesn't deal with any identities that might be associated with B. Regex constraints only apply to identities in a target binding.

Certifications and Delegations in OpenPGP format

Note that in OpenPGP format, certifications and delegations co-exist in a shared wire-format representation, namely "certifying signatures".

It is useful, however, to logically separate the two concepts for the purposes of this data model. The separation simplifies graph searches, and is also conceptually clarifying.

Delegations may additionally be modeled as "direct key signatures" in OpenPGP format.