PGP (Pretty Good Privacy) and its free counterpart, the GNU Privacy Guard (GPG) are encryption suites that allow users to securely over the internet. They can also be used for digital signing and trusted identification. To do this, they utilize a pair of keys, one private and one public. Information that is encrypted using the public key can only be decrypted by someone holding the private key, and the private key can be used to create a digital signature for some data so that anyone holding the public key can verify that the signature was made by the private key. Such a signature can only be created by the private key and any change to the signed data will invalidate the signature.

While this may seem like a panacea for identifying people over the internet, there is a problem with key management and key trust. Specifically, while you can verify that a specific email was signed by key #C34AA484, how do you know that this key actually belongs to me (Benjamin Seidenberg). The key does have my name on it, but the name was user-supplied at the time the key was generated. The same issue occurs with trusting SSL certificates for secure web browsing - yes, the encryption to a website is encrypted, but how do you ensure that the website is actually what it claims to be?

There are two approaches to this problem. Websites use a central authority to verify certificates. Your browser trusts several companies such as Verisign. When you visit a secure website, your browser sees that Verisign has verified the identity of the website for you and proceeds without incident. However, there is no similar infrastructure for GPG keys.

Instead, GPG/PGP keys use a model called the web of trust. Every key is capable of signing other keys. This signature is a cryptographic statement that means “I <key 1> (believe/know) that <key 2> actually belongs to the real-life person whose name is on it.” (The human event in which this takes place is called a key signing and usually involves checking a government-issued ID). These signatures allow us to construct a network of keys, using a directed graph. This network is called the web of trust. Every key is a node, and every signature is a directed edge. Paths from one key to another are called trust paths. If I have signed the key of person A, and they signed the key of person B who signed the key of person C, there is a trust path from me to C and I have reason to believe that this key actually belongs to him or her.

One interesting aspect of the web of trust is that there has emerged what is known as “the strong set”. This is a large connected sub-graph within the web of trust. To enter the strong set, a key merely needs to be signed by a key already within the strong set. Because this network is easily parsed by computers, there are automatically generated reports with statistics about the set. One important statistic is the Mean Shortest Distance (MSD) of a key. The MSD is the average of the length of the shortest path from every key in the set to the key in question. This shows how connected a key is. Keys with a low MSD tend to act like hubs or focal points and represent the more social individuals.

Based on the report from 2/17/08, an examination of 201,989 publicly available keys found a strong set of 110,957 keys (about 54% of the sample). In this strong set, the average MSD was 6.3449. The most connected key belongs to Peter Palfrader and has an MSD of 3.5588. One interesting phenomenon is that all of the top (most connected) 25 keys and all but 12 of the top 50 keys belong to people involved with the Debian project. The Debian project relies very heavily on GPG for authentication and demands that members be in the web of trust before they can join.

References:

http://dtype.org/keyanalyze/explanation.php

http://keyserver.kjsl.com/~jharris/ka/2008-02-17/

http://www.debian.org

See Also:

http://pgp.cs.uu.nl/plot/