the problem that destroyed PGP

Return-path: <peace@BIX.com>
Received: by bix.com (CoSy3.31.1.50) id <9502112132.memo.28092@BIX.com>;
 Sat, 11 Feb 1995 21:32:20 -0500 (EST)
From: peace@BIX.com
Date: Sat, 11 Feb 95 21:32:20 EST
To: cyperpunks@toad.com
Message-ID: <9502112132.memo.28092@BIX.com>
Subject: the problem that destroyed PGP

So finding a KeyID is the problem that destroys PGP eh?

Well I would just take that as the problem to solve, not a
reason to throw the baby out with the bath water.

All we need to do is design a distributed, hashed database.
Should be a piece 'o cake, right?

Let's see, first of all the problem is the receiver of a message
who gets just the KeyID.  First of all, the trusted keys should
be expected to be local (in some webby sense).  But lets assume
that the key is new, not in our local cache.  Now my scheme would put
a net of keyservers that ALL know each other.  The local environment
puts in a request to its usual keyserver.  That is the keyserver
that typically has the keys that the receiver is likely to trust.
Now it is certainly possible to imagine a case where a key is not
in the receiver's expected server, so what's next.  Well the 
keyserver knows ALL the other servers, right, so just copy the
original receiver's request to all the other keyservers.  If that
gets to be too big, just build a real net where every keyserver is
at most two hops away from any other one, then the intermediate
servers that could not honor the request would forward it to all 
the servers it knew.  I purposely propose that only two steps would
ever be necessary to limit the explosion, but I see that as no
real limitation, the rule could even be modified if there was
really any need.

Hey look, the net supports archie and a host of other non-structured
search mechanisms.  Why create a search hierarchy where such things
are not natural.  Why create a naming hierarchy where such things are
not natural.

By the way, the dockmaster.ncsc.mil note is a good example of a naming
hierarchy that has nothing to do with the employment of the person.
Anyone working in the security field can get an address there.  And
any member can get acm.org or ieee.org. But I can post from any of
there different net addresses which do not even agree at the very
most basic level.  So why would my KeyID be naturally associated with
any one of .net, .org or .com?

Peace ..Tom

peace@bix.com says:
> So finding a KeyID is the problem that destroys PGP eh?

No, it doesn't "destroy" it. PGP just needs a redesign to pass along
DNSable tags (like joe@some.domain.org) with keyIDs.

> Well I would just take that as the problem to solve, not a
> reason to throw the baby out with the bath water.

No one is proposing throwing it away. People are proposing small
changes to the format.

> All we need to do is design a distributed, hashed database.
> Should be a piece 'o cake, right?

No, we aren't going to do that, because its an administrative
nightmare, and I can't imagine proposing such a thing with a straight
face at an IETF meeting.

> Hey look, the net supports archie and a host of other non-structured
> search mechanisms.

No, it doesn't. Archie is a piece of shit that can't find what I need
about two thirds of the time and is slow as molasses and cannot
scale. It was a nice idea but its at the breaking point.

Perry

Peace@BIX.com writes:
>So finding a KeyID is the problem that destroys PGP eh?
>
...

I don't think anyone has suggested there's any one problem that
"destroys" PGP.  Several people have pointed out a number of problems
that limit PGP's scalability in various ways.  Its flat key ID
namespace is one.  Lack of functional modularity is another.  Its
fixed certification model is still another.  There are more, and
no doubt still others waiting to be discovered as the user base
grows.  Any secure communications system that aspires to large-scale
penetration, whether called "PGP" or something else, will have to
tackle these kinds of issues before it will be successful.  Some
of the issues are obvious, while others only become apparent after
some experience.  Scale, after all, has a way of turning easy
problems into surprisingly hard ones.

For whatever reason, PGP has attracted an almost cult-like following,
and this has so far helped the spread of secure email.  But this
cuts both ways; cult status or not, PGP has to continue to evolve
and adapt to large-scale, mainstream demands by applying the lessons
of other big systems.  If it doesn't, rest assured that companies
like Microsoft and AT&T will do just fine with whatever they decide
the market wants.

-matt

Matt Blaze writes:

> I don't think anyone has suggested there's any one problem that
> "destroys" PGP.  Several people have pointed out a number of problems
> that limit PGP's scalability in various ways.  Its flat key ID
> namespace is one.  Lack of functional modularity is another.  Its
> fixed certification model is still another. 

Certification really does need to be added to the discussion on scaling.
In the sense that I want to be able to download a stranger's key from 
a key server and have some idea of its reliablility, web of trust has
turned out to be a real failure, IMO. There's no "web", rather a large
set of disconnected "islands" of signatures. I'm looking at the latest
keyring from MIT right now, and noticing that most of the keys are
either unsigned or self-signed. The majority of the rest have signatures,
but signatures that are unconnected to me via the web of trust, so that
they are entirely useless. I suspect that my situation is by far the
most common one: the only keys that I have any verifiable authentication
for are ones I've signed myself, or ones that are signed by people 
in my immediate circle. The chain of signatures dies very close to me.

This isn't a criticism of PGP's key certification paradigm -- PGP allows
centralized certification (I see a few keys signed by SLED, for instance),
and it also allows me the flexibility of having mutual certification within
the circle of people I mail regularly. 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. 


                                  -- Will

"W. Kinney" says:
> This isn't a criticism of PGP's key certification paradigm -- PGP allows
> centralized certification (I see a few keys signed by SLED, for instance),
> and it also allows me the flexibility of having mutual certification within
> the circle of people I mail regularly. 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. 

I think the jury is still out on that. Web-of-trust is still really
untested because of the difficulties in widespread deployment of
PGP. As it stands, PGP is still a hacker's toy -- the lack of a
library or an easy to use global key distribution infrastructure mean
that we have yet to see what can be done. I think that mutually
authenticating organizations with small trust pyramids within the
organizations, but without a global key pyramid, may come to prove
very practical.

Perry

Perry Metzger writes:

> I think the jury is still out on that. Web-of-trust is still really
> untested because of the difficulties in widespread deployment of
> PGP. As it stands, PGP is still a hacker's toy -- the lack of a

Perhaps you're right. Your argument here, as I see it, is that web-of-trust
becomes _more_ functional as it becomes adopted on a larger scale. This
might end up being true and it might not, although there seems to be
no evidence as of yet of increasing "connectivity" of signatures as PGP
becomes more widely used, which was the point I was trying to make. The
unresolved question is whether or not there will be a critical point at
which the web will become widely connected. The answer does not seem at
all clear to me.

                               -- Will

"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

Hal Finney writes, in regard to web-of-trust:

> 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.

There are, however, degrees of certainty here. The only person I trust
implicitly to sign keys is myself. If I have a key which is separated from
me by more than one hop in the web of trust, but still connected to me
via a chain of signatures, I have more certainty that this key is valid
than I do for an unsigned key. Granted, if I don't know the actual signator
of a particular key, my level of trust in the key's validity is pretty
low, but it's nonzero as long as it's connected by a chain of signatures.
The ease of mounting of a man-in-the-middle attack decreases with increasing 
signature connectivity, no?

Of course, the reality is that use of totally unverified PGP keys is
widespread, even among people who are well educated on the subject. This
is not a good thing in the long run.


                                  -- Will