Public Key Cryptography infrastructure (PKI) has two main implementations. One is done using certificates and certificate authorities (CAs), and is described in the X.509 standard. It is best suited for structured organizational hierarchies with an implicitly trusted authority that vouches for all issued certificates. It’s the standard that is behind SSL/TLS and S/MIME email encryption.
However, there is also another widely used standard for PKI, which was developed with a specific goal to not require centralized certification authorities, but instead rely on trust relationships between regular users. It was first implemented in the original PGP software back in 1991, and since then has developed into a robust open standard, known as OpenPGP.
If you’ve ever used Linux, you’ve most likely used OpenPGP without even realizing it. The open-source implementation of OpenPGP is called GnuPG (stands for “GNU Privacy Guard”), and nearly all distributions rely on GnuPG for package integrity verification. Next time you run “yum install” or “yum update”, each package will be verified against its cryptographic signature before it is allowed to be installed on your system. This assures that the software has not been altered between the time it was cryptographically signed by distribution developers on the master server, and the time it was downloaded to your system.
However, far fewer people have actually used GnuPG for what it was originally designed for — secure exchange of information in an untrusted medium (such as the internet), and even fewer have a good understanding of how the trust relationships are supposed to work.
In this mini series of articles, we’ll take a look at what the web of trust is and how to use it to set up a secure and trusted communication.
The need for trust
Cryptographic communication concerns itself with two core aspects:
- obfuscation — your enemy must not be able to read the contents of your message even if they can eavesdrop on all your communication
- verification — your friend must be able to verify that the message came from you and that it hasn’t been altered in any way
To obfuscate a message, we encrypt it. To make a message verifiable, we add a cryptographic digital signature to it. A message that is both encrypted and signed satisfies our security requirements. However, before your friend can verify your digital signature, he or she must be pretty certain that the key used to sign the message is actually yours and not the enemy only pretending to be you.
This certainty is what we call “trust.”
Core PKI Concepts
Just so we are on the same page, let’s go over some core PKI concepts. PKI works by relying on some neat mathematical properties of very large prime numbers. The details aren’t really important for this article, so we’ll jump over directly to the practical result. In PKI, you have two keys — one that only you have access to (“Private key”) and one that you freely give out to anyone who wants to securely communicate with you (“Public key”).
Think of it as a fancy lock and two keys — the public key can only lock it, and the private key can only unlock it. If someone wants to send you a message, they first encrypt it with your public key. A message locked with a public key can only be unlocked with the corresponding private key, so when you receive such a message you can be sure that nobody was able to read its contents in transit.
However, since your public key is available to all, anyone can send you an encrypted message. How do you know that the message actually came from your friend Alice and not your enemy Eve, pretending to be Alice? This is where digital signatures come in. Before encrypting the message, Alice signs it with her private key. When you receive the message and decrypt it, you can verify that it came from Alice by comparing the signature with the public key you know belongs to Alice.
As long as both you and Alice do a good job keeping your private keys well-protected, this communication is assured to remain secure and tamper-evident.
The problem of trust
As I stated earlier, “trust” is the certainty that the public key we have for Alice actually belongs to Alice. If you and Alice live in the same house or neighbourhood, establishing such trust is easy — you meet for coffee and exchange your public keys face-to-face.
But what if you need to securely communicate with Chloe? She’s Alice’s good friend, but she lives on the other coast and the two of you have never met. Or what if Chloe invites Dharma and Ezri, who in turn invite Finn and Gabby? How can you trust a key of a person you’ve never met?
This is where X.509 and OpenPGP diverge in their approach to solving this problem. X.509 establishes a system of trusted authorities. Say, everyone on the West coast must have their key verified (signed) by Alice before it is to be trusted, while everyone on the East coast must have their key signed by Chloe. Alice and Chloe cross-sign their own keys, so you end up with a trust hierarchy. As long as you trust Alice, you can securely communicate with everyone else. This is simple and straightforward, but it has one important downside. Evil Eve only needs to get access to Chloe’s private key in order to infiltrate your entire organization.
OpenPGP decided to choose a different approach — instead of having designated trust authorities (CAs) like Alice and Chloe, whom everyone must trust for the CA hierarchy to work, OpenPGP lets you, the user, decide whom you trust, and how much.
The resulting framework is called the “Web of Trust.” Let’s see how that works in more detail.
Alice, Bob and Anne d’Autriche
Cryptographers usually use monikers such as “Alice, Bob and Eve” to describe relationships between friends and eavesdroppers, which is what I’ve done above. However, if we are going to be looking at expansive webs of trust, we’re going to quickly get confused. To help illustrate things, I’m going to bring in the big guns, or, rather, the big muskets — namely, the Three Musketeers. Don’t worry if you don’t quite recall the entire plot. I’ll refresh your memory as we go along.
Direct trust relationships
In the beginning, d’Artagnan arrives into Paris on a yellow horse and then quickly picks a fight with three other people:
- M. de la Fère (Athos)
- M. du Vallon (Porthos)
- M. d’Aramitz (Aramis)
In the middle of their duel, they are ambushed by the guards who try to arrest them for illegal dueling, so the four unite their forces and jointly fight off the guards, becoming close friends in the process.
To seal their friendship, they decide to exchange their public keys. They also sign each-other’s public key as a way of saying that “I, d’Artagnan, vouch that this key belongs to Porthos by adding my signature to it.”
Here’s how that looks on the command line:
dartagnan[~]$ gpg --edit-key porthos
pub 2048R/51CDD613 created: 2014-01-23 expires: never usage: SC
trust: unknown validity: unknown
[ unknown] (1). M. du Vallon (Porthos)
gpg> sign
pub 2048R/51CDD613 created: 2014-01-23 expires: never usage: SC
trust: unknown validity: unknown
Primary key fingerprint: 611C 0C6D 9B61 A091 1439 EE83 B9AE 772F 51CD D613
M. du Vallon (Porthos)
Are you sure that you want to sign this key with your
key "Charles d'Artagnan (d'Artagnan)" (CD3B1D5E)
Really sign? (y/N) y
Understanding key validity
Now if we look at the key belonging to Porthos, it states the following:
dartagnan[~]$ gpg --edit-key porthos
pub 2048R/51CDD613 created: 2014-01-23 expires: never usage: SC
trust: unknown validity: full
[ unknown] (1). M. du Vallon (Porthos)
It is important to understand the difference between “trust” and “validity,” as they are two different sides of the same coin. In GnuPG parlance, “validity” represents our certainty that they key actually belongs to Porthos. In the above output, “validity: full” tells d’Artagnan that he can be absolutely certain that it’s Porthos’ key (in this case, because d’Artagnan himself signed it). But what is the meaning of “trust: unknown”?
In this case “trust” (also called “owner trust”) is how much d’Artagnan trusts Porthos to verify other people’s identities (by looking at passports, asking their mutual friends to vouch for them, etc). Let’s say d’Artagnan fully trusts Porthos to do a good job verifying people’s identities before he signs their keys. He edits Porthos’ key and sets owner trust to “full”:
dartagnan[~]$ gpg --edit-key porthos
pub 2048R/51CDD613 created: 2014-01-23 expires: never usage: SC
trust: unknown validity: full
[ unknown] (1). M. du Vallon (Porthos)
gpg> trust
pub 2048R/51CDD613 created: 2014-01-23 expires: never usage: SC
trust: unknown validity: full
[ full ] (1). M. du Vallon (Porthos)
Please decide how far you trust this user to correctly verify other users' keys
(by looking at passports, checking fingerprints from different sources, etc.)
1 = I don't know or won't say
2 = I do NOT trust
3 = I trust marginally
4 = I trust fully
5 = I trust ultimately
m = back to the main menu
Your decision? 4
pub 2048R/51CDD613 created: 2014-01-23 expires: never usage: SC
trust: full validity: full
[ full ] (1). M. du Vallon (Porthos)
Please note that the shown key validity is not necessarily correct
unless you restart the program.
gpg> q
After d’Artagnan signs the keys for Athos, Porthos and Aramis, his web of trust is very direct and can be shown in a simple graph.
When Porthos sends over Planchet, who is to become d’Artagnan’s new valet, d’Artagnan uses the web of trust to verify that Planchet is who he says he is, because his key bears Porthos’ signature:
dartagnan[~]$ gpg --list-sigs planchet pub 2048R/30EA3A2A 2014-01-23 uid Planchet sig 3 30EA3A2A 2014-01-23 Planchet sig 51CDD613 2014-01-23 M. du Vallon (Porthos)
And GnuPG tells him that the key is fully valid:
dartagnan[~]$ gpg --edit-key planchet
pub 2048R/30EA3A2A created: 2014-01-23 expires: never usage: SC
trust: unknown validity: full
[ full ] (1). Planchet
This is web of trust in action. Since d’Artagnan trusts Porthos to verify people’s identities before signing keys, when Planchet comes along, d’Artagnan knows he is, in fact, Planchet — because Porthos has vouched for him by signing his key.
Setting owner trust
You will notice that we again have “trust: unknown” for Planchet — this is because we’ve not assigned owner trust to his key yet. As a general rule, “validity” is something we calculate from the signatures on the person’s key, while “trust” is something we must assign to each key ourselves in order for it to say something other than “unknown” (except in case of trust-signatures, but we’ll go over that in the next article).
Every time we sign someone’s key, it’s a good practice to also set owner-trust, so that in the future we can use this trust relationship to verify the identity of other people’s keys. In the case of Planchet, d’Artagnan decides that he only trusts him marginally, at least for the time being — after all, they had only just met:
gpg> trust
pub 2048R/30EA3A2A created: 2014-01-23 expires: never usage: SC
trust: unknown validity: full
[ full ] (1). Planchet
Please decide how far you trust this user to correctly verify other users' keys
(by looking at passports, checking fingerprints from different sources, etc.)
1 = I don't know or won't say
2 = I do NOT trust
3 = I trust marginally
4 = I trust fully
5 = I trust ultimately
m = back to the main menu
Your decision? 3
pub 2048R/30EA3A2A created: 2014-01-23 expires: never usage: SC
trust: marginal validity: full
[ full ] (1). Planchet
Please note that the shown key validity is not necessarily correct
unless you restart the program.
gpg> q
He does the same thing for all of his friends’ valets — he sets trust on Bazin’s, Grimaud’s and Mousqueton’s keys to “marginal.” So, now d’Artagnan’s web of trust looks like what is in the graph below. The colour of the boxes shows the trust d’Artagnan assigns to each key (red is full trust, while blue is marginal trust), and the arrows show who signed whose key.
Understanding marginal trust
What happens when we find a key signed by someone whom we only trust marginally? Let’s say one day d’Artagnan meets his landlord, M. Bonacieux, and the only signature on M. Bonacieux’s key is by Planchet? Here is the gpg session:
dargagnan[~]$ gpg --list-sigs bonacieux
pub 2048R/D672573B 2014-01-28
uid M. Bonacieux
sig 3 D672573B 2014-01-28 M. Bonacieux
sig 99CCAC09 2014-01-28 Planchet
dargagnan[~]$ gpg --edit-key bonacieux
pub 2048R/D672573B created: 2014-01-28 expires: never usage: SC
trust: unknown validity: marginal
[marginal] (1). M. Bonacieux
As you can see, the validity is marked as “marginal,” whish is gpg’s way of saying that there is only marginal assurance that this “M. Bonacieux” is actually who he says he is. In fact, if d’Artagnan receives a gpg-signed message from M. Bonacieux and runs “gpg –verify” on it, it will return the following output:
dartagnan[~]$ gpg --verify message-from-bonacieux.asc gpg: Signature made Tue 28 Jan 2014 02:10:41 PM EST using RSA key ID D672573B gpg: Good signature from "M. Bonacieux gpg: WARNING: This key is not certified with sufficiently trusted signatures! gpg: It is not certain that the signature belongs to the owner. Primary key fingerprint: BE8B 2FE0 C433 79A4 7A6B C045 F04F 9E3D D672 573B
If we represent the trust relationship as a graph, we’ll mark M. Bonacieux’s box gray, because there is not enough signatures to assure full validity.
To strengthen the key validity, we need to have either someone else whom we fully trust to sign his key, or we need to find two other people with marginal trust, so there’s a total of 3 marginal-trust signatures on M. Bonacieux’s key. Here’s what happens when Mousqueton and Bazin both add their signatures to M. Bonacieux’s key:
dartagnan[~]$ gpg --verify message-from-bonacieux.asc
gpg: Signature made Tue 28 Jan 2014 02:10:41 PM EST using RSA key ID D672573B
gpg: Good signature from "M. Bonacieux"
Primary key fingerprint: BE8B 2FE0 C433 79A4 7A6B C045 F04F 9E3D D672 573B
dargagnan[~]$ gpg --edit-key bonacieux
pub 2048R/D672573B created: 2014-01-28 expires: never usage: SC
trust: unknown validity: full
[full] (1). M. Bonacieux
Because M. Bonacieux now has three marginally-trusted signatures on his key, his key validity is now marked as “full.”
Recap
This is basically all there is to understanding core concepts of OpenPGP’s web of trust. To recap:
- You vouch for someone’s identity by signing their key.
- Key “validity” is the certainty we have that the key in question belongs to the person with whom we want to communicate. It is calculated based on owner-trust and the number of signatures on the key.
- Key “trust” must be set by you, the user, for each key in your keyring before it is included in the web of trust calculations.
- Trust can be full or marginal. It takes only one fully trusted signature to mark a key as “valid” but at least 3 marginally trusted keys to do the same.
Webs of trust quickly grow pretty big and complex. In the next installment, we look into some mechanisms the OpenPGP-using community has developed to help make trust management easier — namely, we’ll talk about keyservers and delegated trust.
Read part 2, “PGP Web of Trust: Delegated Trust and Keyservers.”
