This post is part of a series. Read the last part here.

There are two obvious operations your OpenPGP implementation needs to be capable of performing if you want to build a Web-of-Trust. First you need to be able to sign other users public keys (certificates), and second, you need to be able to verify those certifications.

The first is certainly the easier of the two tasks. In order to sign another users certificate, you simply take your own secret key, decide which binding (a tuple of a certificate and a user-id) you want to create a certification for and then simply generate a signature over the user-id and the primary key of the certificate according to the standard.

Now your signature can be distributed, e.g. by mailing it to the user, or by publishing it to a key server. This task is simple, because all the ingredients are well known. You know which key to use to create the signature, you know which user-id you want to certify and you know which key to bind the user-id to. So signing a certificate is more or less straight forward application of the cryptography defined in the specification.

But the task of verifying, whether there is a valid signature by one certificate over another is far more complex of a task. Here, the specification is deliberately vague. Some time ago I wrote an article, describing why signature verification in OpenPGP is hard, and I still stand to my points.

Authentication of a certificate is the task of figuring out how confident you can be that a key that claims to belong to “Alice <alice@example.org>” really was issued by Alice and not by an imposter, in other words you need to proof the authenticity of the binding. To accomplish this task, the Web-of-Trust is scanned for paths that lead from a root of trust (think e.g. a CA or your own certificate) to the binding in question.

Building a Web-of-Trust implementation can be divided in a number of steps which luckily for us stand independent from another:

1. Ingest the set of certificates
2. Verify certifications made on those certificates
3. Build a flow network from the certificates and certifications
4. Perform queries on the network to find paths from or to a certain binding (e.g. using Dijkstra’s algorithm)
5. Interpret the resulting path(s) to infer authenticity of said binding

In the first step we simply want to create an index of all available certificates, such that in later steps we are able to have random access on any certificate via its fingerprint(s) or key-ID(s).

The second step is to go through each certificate one-by-one and attempt to verify third-party certifications made over its primary key or user-ids. Here, the index built in the previous step comes in handy acquire the issuer certificate to perform the signature verification. In this step, we index the certifications we made and keep them available for the next step. Once we successfully performed all signature verifications, the OpenPGP-portion of the task is done.

In step three, we form a flow network from the results of the previous steps. Certificates themselves form the nodes of the network, while each signature represents an edge between the issuer- and target certificate. There can be more than one edge between two certificates.

Step 4 and 5 are the technically most complicated steps, so I will not go into too much detail in this post. For now, I will instead first try to explain the abstract picture of the Web-of-Trust I have in my head:

I imagine the Web-of-Trust as an old, half-rotten fishing net (bear with me); There are knobbly knots, which may or may not be connected to neighboring knots through yarn of different thickness. Some knots are well-connected with others, as ye olde fisherman did some repair work on the net, while other knots or even whole sections of the net have no intact connections left to the rest. Many connections rotted away as the yarn past its expiration date.

When we now attempt to pick up the net by lifting one of the knots into the air, all those knots that are connected either directly or indirectly will also lift up, while disconnected knots or sections will fall to the ground. If we put some weight on the net, some of the brittle connections may even break, depending on how much weight we apply. Others might hold because a knot has multiple connections that share the load.

In this analogy, each knot is a node (OpenPGP certificate), with yarn connections being the certifications. Different thickness of the yarn means different trust-amounts. The knot(s) we chose to pick the net up from are the trust roots. Each knot that lifts up from the ground we can authenticate. The weight we apply to the net can be seen as the amount of trust we require. If we aren’t able to accumulate enough trust-amount for a path, the knot rips off the fishing net, meaning it cannot be authenticated to a sufficient degree.

This analogy is of course not perfect at all. First off, edges in the Web-of-Trust are directed, meaning you can follow the edge in one direction, but not necessarily in the other. Furthermore, the Web-of-Trust has some more advanced attributes that can be put into a certification to give it even more meaning. For example, a trust signature not only has a numeric trust-amount, but also a depth, which limits the number of “hops” you can make after passing over the edge. Certifications can also include regular expressions, limiting to which certificates you can hop next.

Still, to get an initial, rough understanding of the WoT, I find the fishing net analogy quite suitable. In a later post I might go into more detail on steps 4 and 5.