An e-mail web of trust (was: Some thoughts on SMTP Verification)

On 2004-02-28 21:15:41 -0500, Yakov Shafranovich wrote:
> This kind of like the "chain of trust" used in PGP. Sounds like an
> interesting idea to me! What would spammers do in theory to get around
> such system?

I wrote up some ideas about an email web of trust some time ago. I
intended to expand on it a bit (especially on the trust metric) before
publishing it but it seems that now is a good time to throw it into the
discussion:

(HTML version at http://www.hjp.at/projekte/mail-wot/outline.rxml)

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

 1. is computationally expensive (esp. if the web is expanded to include all
    mail users).
 2. can be done in a MUA or any MTA on the way if all keys and signatures are
    public.
 3. 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!)

8. Alternative to public key servers

public key servers have problems:

  * privacy concerns
  * scalability (sync between servers, data per server)

Therefore:

  * Public keys (with signatures) are included in first mail (but how does the
    sender get the keys of the intermediaries?)


--
   _  | Peter J. Holzer    | I think we need two definitions:
|_|_) | Sysadmin WSR       | 1) The problem the *users* want us to solve
| |   | [email protected]         | 2) The problem our solution addresses.
__/   | http://www.hjp.at/ |    -- Phillip Hallam-Baker on spam

[demime 0.99d.1 removed an attachment of type application/pgp-signature]