Building a Web of Trust for E-Mail

1. Introduction

One of the problems with spam is that in E-Mail it is generally impossible to tell whether the (presumed) sender of the mail exists at all and if so, whether he sent the email.

Cryptographic methods exist to sign e-mail and to certify that a certain public key belongs to a person. However, such methods are not widely deployed. In part this is because these methods are commonly regarded as too complicated for the layman, and in part because they are usually used at a level of security which is not necessary for casual exchange of e-mails. For example, if I get mail from "John Smith" , I usually do not care whether his name is really John Smith (which normally means that he is in possession of a document issued by some government which says his name is John Smith). What I do care is that my reply sent back to will be read by the person who sent me the email.

This paper describes a simple method to use PGP to build a web of trust in which PGP is used to certify that an e-mail address is used for personal communication.

2. Six Degrees of Separation

There is a common belief that any two people on earth can be linked by a chain of at most 6 aquaintances. Experiments have been conducted which support this idea. Similarly, for the strongly connected subset of the PGP web of trust, any two PGP keys can usually be linked by a short link of signatures.

Therefore it seems plausible that somebody who wants to send mail to a stranger may make his existance as an individual plausible by claiming that he regularly exchanges email with A who exchanges email with B ... who exchanges email with the recipient, and these claims can be automatically verified. The recipient can then examine the chain and decide whether he accepts the mail.

This usage of the web of trust differs in some important point from the traditional PGP web of trust. The PGP web of trust is not transitive. Just because I have seen someones Id at a keysigning party and have signed his public key doesn't mean that I trust the person to properly check ids also. However the web of e-mail contacts is transitive. I accept mail from people who have something (to me) interesting to write. Presumably, those people behave the same, so the people they accept from, write something which is interesting to them and to a lesser degree, to me. As the distance increases, the probability decreases.

3. Path checking

is computationally expensive (esp. if the web is expanded to include all mail users).
can be done in a MUA or any MTA on the way if all keys and signatures are public.
Because of 1, the path (or several alternate paths) should be computed by the sender.

4. Problems

PGP is not widely deployed although it is more than 10 years old.
There are at least 3 different "standards" to sign mails. Inline signatures, PGP/MIME, and the X-PGP-Signature used to sign Usenet control messages.
A server known to verify signatures might be DOSed by sending it a large number of messages.
The distributed nature of the web of trust provides no financial incentive to deploy the system (unlike a system based on X.509 signatures, in which the established certification authorities have an incentive to establish it, because it would mean that every person who wants to send mail has to pay them).
A public register of who accepts mail from whom can be seen as a huge invasion of privacy.

5. Why PGP

PKI already in place (but does it scale to 1E9 users?)

6. MUA implementation

create key pair
upload key to keyserver
When sending mail: for each recipient
1. sign recipient's address and upload sig to key server (unless already done).
2. compute path to recipient
3. include path in message
4. sign message
When receiving mail: Verify signature. Verify path chain.

7. MTA behaviour

MAY check signature and chain
MAY reject on inconsistency
MUST NOT reject if no chain is provided or it cannot be checked for lack of information or computing power (unless the recipient decided on this policy!)