Linux.com

Home Learn Linux Linux Tutorials PGP Web of Trust: Core Concepts Behind Trusted Communication

PGP Web of Trust: Core Concepts Behind Trusted Communication

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.

Direct trust relationship

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

Direct trust relationship

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.

Direct trust relationship

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."

M. Bonacieux now with full trust

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."

 

Comments

Subscribe to Comments Feed
  • Skavoovie Said:

    The main problem with GPG is that it is so closely tied to the user's email address. This makes it necessary to share your email address in public, and on openly-accessible PGP servers. Publishing or publicly distributing your PGP key is a guaranteed way to increase the amount of spam, phishes, and even spear phishes received. A new PGP standard needs to be created that (optionally) generates a one-way hash of the key holder's email address in lieu of the actual email address. If someone already knows the key holder's email address, the PGP software would be able to associate the recipient email address and key by hashing the known email address and matching the hash to the public key's hash, but only if they already know the hey holder's email address. By doing so, users would then be able to freely publish their public keys without receiving lots of spam, phishes, etc. as a result.

  • Esteban Said:

    why the arrow from d'Artagnan box to Planchet box?

  • Norman Said:

    The arrow from d'Artagnan's box to Planchet's box represents the second verification (gpg --verify message-from-bonacieux.asc) which indicates the signature is valid after three have assigned marginal trust to Bonacieux's key in d'Artagnan's web of trust.

  • Esteban Said:

    "the arrows show WHO SIGNED whose key", that said Konstantin Ryabitsev. Sorry I don't understand

  • Konstantin Ryabitsev Said:

    Sorry I missed your comment. Arrows show signatures on keys. So, in the final graph d'Artagnan only directly signed these keys: Porthos, Aramis, Planchet. He never signed Mousqueton's nor Bazin's keys -- which is why there are no arrows going to their boxes from d'Artagnan -- but that step isn't necessary to set owner-trust. Think of it this way -- you have probably never met Linus Torvalds, so you can't personally vouch that you have verified his credentials. However, you can probably set your ownertrust to "Full" for his key if you want to verify kernel releases made by other developers whose keys Linus has signed.

  • Nitin Said:

    It could be to indicate the trust level has been assigned for that key. It is drawn after he explains assigning of marginal trust to Planchet's key. But again it is missing for the other valets. Maybe the author could explain that. But great article, thanks.


Who we are ?

The Linux Foundation is a non-profit consortium dedicated to the growth of Linux.

More About the foundation...

Frequent Questions

Join / Linux Training / Board