PGP Web of Trust: Delegated Trust and Keyservers

Welcome to the second installment of the “PGP Web of Trust” series. In the previous article, we looked at the very basics of how the web of trust works and now should have a good understanding of the following:

• 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 three marginally trusted keys to do the same.

This is the web of trust in its simplest form, also called the “Classic Trust Model” — you (and only you) must directly assign trust to each key before it is included in any trust calculations. However, in complex hierarchical organizations, where people continuously come and go, this may become difficult to manage. Recognizing this, later versions of PGP have decided to implement trust delegation using multiple levels of “Trusted Introducers.”

In this part, we’ll take a look at the following:

• What are “Trusted Introducers” and “Meta-Introducers” in cryptography
• How PGP implements “Meta-Introducers”
• How PGP trust-signatures work in practice
• What keyservers are and how to use one to keep track of people’s public keys.

Trusted Introducers

We talked about “Certification Authorities” in the previous installment when discussing how X.509 certificates function. In the X.509 world, you don’t assign trust to people’s certificates, but instead pick an authority who signs all the keys. Any key bearing the CA’s signature is implicitly assumed to be fully valid. Usually, there are several levels of authorities, commonly referred to as “Root authorities” and “Intermediary Authorities,” and together they form a “certification chain.”

In cryptography, these are known under general terms of “Trusted Introducers” and “Meta-Introducers”. A hypothetical North American certification chain would look like this:

If Alice trusts signatures made by the “North American CA”, she automatically trusts signatures made by the intermediary authorities, and therefore as far as Alice is concerned, Fiona’s key has full “validity” (to use PGP’s terminology).

Trust signatures

PGP version 5 introduced “trust signatures,” which added support for trust delegation in the PGP world. A trust-signature is basically a way to say: “if you trust my key, you may also give the same amount of trust to these keys I’ve trust-signed.”

Let’s use our old friends the musketeers to visualize how trust signatures work.

D’Artagnan was the captain of the King’s musketeers, reporting directly to his commander, M. De Tréville, who in turn reported directly to King Louis XIII. In the book, the queen-escort Anne d’Autriche and her lover the Duke of Buckingham run the risk of getting exposed due to Cardinal Richelieu’s plotting. In desperation, Anne turns to her trusted courtisane, Constance Bonacieux, asking her to find someone she trusts for a quick trip to England. Cardinal Richelieu finds that out and tasks his henchman, Comte de Rochefort, to make sure the queen’s desperate plot fails.

If we look at the relationship between the key players in this scheme, we can graph it as follows:

When Constance Bonacieux comes to d’Artagnan asking for his help, how does d’Artagnan know that she’s really the queen’s trusted courtisane? He can manually trace the signatures from De Tréville to the King, then to the Queen, and then to Constance, but thankfully there is a quicker and more universal solution he can use.

The king is the ultimate trust authority in France of that time, so we can think of him as the Root Authority. Since he cannot possibly sign the keys of everyone in the French government, he delegates his trust to his underlings with the help of gpg’s tsign command:

louis[~]$ gpg --edit-key anne
pub  2048R/65C953D7  created: 2014-02-21  expires: never       usage: SC
                     trust: unknown       validity: unknown
[ unknown] (1). Queen Anne d'Autriche
gpg> tsign
[..skip..]
Please enter the depth of this trust signature.
A depth greater than 1 allows the key you are signing to make
trust signatures on your behalf.
Your selection? 1
[..skip..]
Are you sure that you want to sign this key with your
key "King Louis XIII" (28133692)
Really sign? (y/N) y
gpg>

What does the “depth of trust” above mean? This describes how far down the chain the King is willing to delegate his trust. Think of it this way:

• level 1: “you can trust this key I’ve signed as much as mine, but that’s as far as I’m willing to vouch“
• level 2: “you can trust this key I’ve signed as much as mine, plus any other key this person trust-signs, if you are so inclined”

In cryptographic parlance, trust-signing a key with “level 1” designates that person as a “Trusted Introducer.” Trust-signing a key with “level 2” designates that person as a “Meta-introducer”.

By itself, level 1 signature is exactly the same as signing a key and setting owner trust, it just combines the two steps into one and makes the results visible to others, if shared (more on that later). To King Louis, the results of “tsign level 1” and classic model’s “sign and set owner trust” behave identically:

Trust-signatures only really come into play for trust delegation when someone else trust-signs such key at a level higher than 1. Let’s see what happens when d’Artagnan trust-signs the King’s key with level-2 (the King becomes d’Artagnan’s meta-introducer):

dartagnan[~]$ gpg --edit-key louis
pub  2048D/28133692  created: 2014-02-21  expires: never       usage: SC
                     trust: unknown       validity: full
[  full  ] (1). King Louis XIII
gpg> tsign
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 trust marginally
  2 = I trust fully
Your selection? 2
Please enter the depth of this trust signature.
A depth greater than 1 allows the key you are signing to make
trust signatures on your behalf.
Your selection? 2
[..skipped..]
Are you sure that you want to sign this key with your
key "d'Artagnan" (65BE833E)
Really sign? (y/N) y
gpg>

With only one trust-signature of the King’s key, d’Artagnan dramatically expands his web of trust to include pretty much everyone in the French court:

The number of levels is not limited to 2 and can go up to 5. Here’s what happens when Planchet trust-signs d’Artagnan’s key as “level 3” (“Meta-Meta-Introducer”):

As you can see, it’s pretty much identical to d’Artagnan’s due to fully inherited delegated trust.

Downsides of trust delegation

Delegated trust is a powerful tool, but has the same important downside as with X.509’s Certification Authorities — to infiltrate an organization, an attacker only needs to compromise the Root Authority (in our case, the private key of King Louis XIII).

If that is a concern to you, you can disable delegated trust entirely by telling GnuPG to always use the “Classic Trust” model by setting “trust-model classic” in your~/.gnupg/gpg.conf, or by simply never using trust-signatures. They never kick in unless you trust-sign someone’s key yourself.

Keyservers

Once you sign someone’s key, how do you let others know about it? If your web of trust consists of only a handful of people, you can simply email the signed public key around, but this obviously is not very efficient as your organization grows. The PGP community recognized this problem early on and set up designated servers for distributing public keys. Many of them have web interfaces that allow searching and downloading public keys, but this functionality is also built-in into the GnuPG command-line tool.

For example, here’s how you would go about downloading Linus Torvalds’ key from the MIT keyserver:

mricon[~]$ gpg --keyserver pgp.mit.edu --search torvalds linux-foundation

There is more than one keyserver and most of them communicate with each-other in order to synchronize public keys and signatures, so a key uploaded to pgp.mit.edu would soon be available from many other keyservers as well.

Here’s how I would go about uploading my own key to the MIT server:

mricon[~]$ gpg --keyserver pgp.mit.edu --send-key 329DD07E
gpg: sending key 329DD07E to hkp server pgp.mit.edu

Now anyone is able to search pgp.mit.edu and download my key from it:

dartagnan[~]$ gpg --keyserver pgp.mit.edu --recv-key 329DD07E
gpg: requesting key 329DD07E from hkp server pgp.mit.edu
gpg: key 329DD07E: public key "Konstantin Ryabitsev" imported
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)

Summary

To recap:

• GnuPG supports trust delegation using “trust signatures.” Trust signatures allow PGP to function similarly to X.509 certificates with its system of Certification Authorities (“Trusted Introducers”).
• Level-1 trust signature designates someone as a “Trusted Introducer.” By trust-signing someone’s key with level 1 you effectively state: “you can trust this key as much as mine, but that’s as far as I’m willing to vouch“
• Level-2 trust signature designates someone as a “Meta-Introducer.” By trust-signing someone’s key with level 2, you effectively state: “you can trust this key as much as mine, plus any other key this person trust-signs, if you are so inclined.”
• Delegated trust is convenient, but introduces the same problems as with X.509’s certification authorities. An attacker only needs to compromise the certification authority in order to infiltrate an organization.
• Delegated trust can be completely disabled by telling GnuPG to always use the “classic model” that only relies on direct trust relationships.

In our final installment, we’ll look at how to revoke keys and signatures if something bad has happened, plus will go over the reasons why you may want to sign a key, but not tell anyone else about it.