From: Hal <hfinney@shell.portal.com>
Date: Sun, 12 Feb 95 10:20:57 PST
To: cypherpunks@toad.com
Subject: Re: the problem that destroyed PGP
In-Reply-To: <199502121757.KAA12098@bogart.Colorado.EDU>
Message-ID: <199502121820.KAA04736@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


"W. Kinney" <kinney@bogart.Colorado.EDU> writes:

>But web of trust _in and of itself_
>is not proving to be effective when applied to the problem of providing
>reliable key certification on the scale of the internet as a whole. 

Here is something I posted on this topic last year:

> From owner-cypherpunks@toad.com  Wed Mar 30 09:19:30 1994
> Date: Wed, 30 Mar 1994 09:17:40 -0800
> From: Hal <hfinney@shell.portal.com>
> Message-Id: <199403301717.JAA14861@jobe.shell.portal.com>
> To: cypherpunks@toad.com
> Subject: Web of Trust?
> Sender: owner-cypherpunks@toad.com
> Precedence: bulk
> Status: RO
> 
> One of the key concepts widely used to describe PGP is the "web of trust".
> This brings to mind a network of connections between people who know and
> communicate with each other.  Two people who want to communicate can do
> so securely if there is a path of connections in the form of signed keys
> that joins them.
> 
> But this is not quite right.  The fundamental fact about PGP key signatures,
> which is often misunderstood, is this:
> 
> You can only communicate securely with someone whose key is signed by a person
> you know, either personally or by reputation.
> 
> In other words, if I want to communicate with joe@abc.com, I can only do so
> if one of the signators of his key is a person I know.  If not, I have no way
> of judging the validity of his key.
>  
> This belies simple interpretations of the "web of trust".  I may have signed
> A's key, A has signed B's, B has signed C's, C has signed D's, and D has signed
> Joe's, but this is of no value unless I know D.  Only then can I trust Joe's
> key.
> 
> This means that, in the "web" picture, I can only communicate securely with
> people who are at most two hops away in the web of connections.  I can
> communicate with the people I know, and I can communicate with the people they
> know, and that is it.
> 
> This is unfortunate, because the simple web model ties into some famous
> research which suggests that any two people chosen at random are only about
> half a dozen steps apart in the web of who-knows-whom connections.  (This
> result is where the title of the movie "Six Degrees of Separation" comes from.)
> If you had a system which actually supported communications via such a web
> model, it actually would have hope of letting two people communicate who did
> not have a very long chain between them.  But PGP, with a maximum chain length
> of two, will not allow this.
> 
[Discussion of possible extensions elided]
> 
> Without this, I think we will continue to have problems with PGP being unable
> to validate keys of people we want to communicate with.  People will collect
> huge laundry lists of signatures in the hopes that whoever wants to commu-
> nicate with them will know one of those people.  Centralized key validators
> will appear (as in the case of the SLED service being started now, which will
> sign a key based on a signed check with your name on it).  The result may be
> a choice between using an unsigned key or using one signed by some faceless
> bureaucracy, which is no better than the original PEM conception.
> 
> (People may be confused by this essay because they thought PGP worked this
> way already.  PGP does have a follow-the-web model, but that is only for
> following signatures.  In the example above, where I wanted to talk to Joe
> and there was a chain to him through A, B, C, and D, we have to first sup-
> pose that I know and trust all of A, B, C, and D.  Given that, what PGP can
> do is to determine whether I have valid keys for all of those people.  It will
> notice that A has signed B's key, so it is valid.  I know B and told PGP he
> was trustworthy, and he signed C's key, so therefore that one is valid.  Sim-
> ilarly, I know C and I know D so PGP can follow the chain through them.  Fin-
> ally we come to Joe, whom I don't know, but because I know D and PGP followed
> the web to determine that D's key is valid, PGP can determine that Joe's key
> is valid.  But again, that was only because I knew D and everyone else in
> the chain.  The bottom line is still that I can only communicate with people
> who know someone I know.)
>  
> Hal