This document is based on tests and some source code analysis of GnuPG. It has been written because available sources weren't enough for me to understand how the web of trust works.

Properties

Validity

indicates if a signature made by an individual is going to be approved or if a warning about uncertainty of one's identity pops up,
validity is calculated by the web of trust algorithm,
validity == "full" or "ultimate" means that the identity is considered true.

Trust

indicates how much I trust an individual when it comes to him/her verifying identity of others,
in others words - how much his/her signature on keys of other individuals influences validity of these keys,
trust is set manually by the user.

Current validity of keys can be printed using the following command:
$ gpg --list-keys --list-options show-uid-validity

Web of trust algorithms

In the GnuPG manual following methods are listed:

pgp,
classic,
direct,
always.

Currently pgp is the one used by default and described in this document.

Chaotic keywords

Terminology is chaotic. According to some sources the property called validity takes one of these values:

undefined,
marginal,
complete.

According to the same source the property called trust takes one of these values:

don't know,
untrustworthy,
marginal,
full.

As far as GnuPG is concerned the same set of values is used for both properties. Whenever there is not enough data to determine the trust the "unknown" label is used.

If the user does not know if some individual's signatures can be trusted one can indicate it setting trust to "undefined".

"Untrustworthy" becomes "never". "Marginal" stays "marginal". The "complete" label is divided into more specific "full" and "ultimate".

"Ultimate" is a special label used only for user's own keys.

There are two other labels used in the source code: "expired" and "revoked". They are not described in this document.

Deceiving keywords

I think labels "marginal" and "full" are deceiving. In reality in case of trust they indicate if an individual is believed to be able to verify identity of others by himself or only as a member of a group. By default GnuPG finds a key valid (validity == "full") if a key has:

1 signature of a person with
trust == "full" and validity == "full"
or
3 signatures of people with
trust == "marginal" and validity == "full".

These thresholds are not saved in the web of trust file (trustdb.gpg). They can be set on the command line using parameters:

--marginals-needed,
--completes-needed

or similarly in the configuration file (gpg.conf).

Validity == "full"

When a user signs a key GnuPG considers that key to have validity == "full" (from that user's point of view).

Calculating validity through iterations

The validity calculation starts from an "ultimate" key and goes towards more remote keys.

The calculation process does not skip missing graph edges. So for a key to be considered valid there has to be a path from an "ultimate" key to that key. That path cannot be longer than the threshold set by the max-cert-depth setting (5 by default).

It means that a key will not become valid if it is signed by an individual with the trust property set but there is no path leading to that user (from an "ultimate" key).

The user can force the web of trust rebuilding executing the following command:
$ gpg --update-trustdb

The algorithm uses only those keys which get validity == "full" during the calculation. The "marginals-needed" and "completes-needed" are associated with the manually set trust property, not with the validity property.

The algorithm continues to go deeper while at least one of the "marginals-needed" or "completes-needed" conditions is true. It means to continue while there were enough keys with validity == "full" and trust == "ultimate"/"full"/"marginal" in the previous iteration to create another key with validity == "full".

During the last iteration keys being reachable but without enough signatures (but still with at least one signature made with a key with validity == "full") are labeled with validity == "marginal".

An example of a web of trust

$ gpg --homedir me --update-trustdb --marginals-needed 2
gpg: 2 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   1  signed:   2  trust: 0-, 0q, 0n, 0m, 0f, 1u
gpg: depth: 1  valid:   2  signed:   4  trust: 0-, 0q, 0n, 2m, 0f, 0u
gpg: depth: 2  valid:   3  signed:   1  trust: 0-, 3q, 0n, 0m, 0f, 0u
gpg: next trustdb check due at 2012-09-30

There were 3 iterations.

At level (depth) 0 my key gets validity == "ultimate" because it has my signature and trust == "ultimate" (1u).

At level 1 the GnuPG stumbles upon 4 keys signed by 2 individuals with trust == "marginal" (2m).

At level 2 the GnuPG stumbles upon 1 key signed by 3 individuals with trust == "undefined" (3q).

The printed description of the process becomes more complicated when there are multiple paths with different lengths leading to a key. This can be seen in this example as well. A key at level 3 is signed by:

1 individual from level 1 and
3 individuals from level 2.

As we can see we did not get to to level 3 iteration. But a key at this level is reachable -- it has signatures but not enough of them. This is why it gets validity == "marginal".

This is the signatures structure:
me → friends → guys → alien,
additionally Friend Two has signed the Alien's key.

$ gpg --homedir me --list-keys --list-options show-uid-validity
--------------
pub   2048R/AFA302BF 2011-10-01
uid       [ultimate] The Me 
sub   2048R/E4FF8420 2011-10-01

pub   1024R/6921DF3D 2011-10-01 [expires: 2012-09-30]
uid       [  full  ] The Friend 
uid       [ unknown] The Friend (alternate) 
sub   1024R/DD37730B 2011-10-01 [expires: 2012-09-30]

pub   1024D/1E71B2C3 2011-10-01
uid       [  full  ] Friend Two 
sub   1024g/B2F94583 2011-10-01

pub   1024D/0DE1BC29 2011-10-01
uid       [  full  ] Guy 1 
sub   1024g/ACA329E3 2011-10-01

pub   1024D/0FC4A4A7 2011-10-01
uid       [  full  ] Guy Two 
sub   1024g/38445EB3 2011-10-01

pub   1024D/9674B894 2011-10-01
uid       [  full  ] Guy Drei 
sub   1024g/95A9CB7E 2011-10-01

pub   1024D/AC4EC9F7 2011-10-01
uid       [marginal] Alien 
sub   1024g/4A46043E 2011-10-01

Penguin Copter

niedziela, 9 października 2011

Web of Trust