Does PGP scale well?

Perry has repeated a litany here that I have been hearing for years on
the pem-dev list with never a hint of a justification.  That is that
PGP does not scale well.

One of the reasons that I consider this to be untrue is my empirical
experience with two groups that are constantly interested in exactly
who I am: the government and the credit bureaus.  They both chose to
use my SSN even though that has all the same attributes of a KeyID,
except that it is somewhat denser.  Now if this is what happens when
the real world tries to identify me, why is the KeyID such a bad way to
identify keys?

Please note that I do understand that identifying me and finding me are
separate issues.  I'm not sure that the pem-dev folk clearly
discriminate these.

Peace. Tom

Tom Jones says:
> Perry has repeated a litany here that I have been hearing for years on
> the pem-dev list with never a hint of a justification.  That is that
> PGP does not scale well.

I've given plenty of justification. You can't reverse map keys. Isn't
that bad enough?

> One of the reasons that I consider this to be untrue is my empirical
> experience with two groups that are constantly interested in exactly
> who I am: the government and the credit bureaus.  They both chose to
> use my SSN even though that has all the same attributes of a KeyID,
> except that it is somewhat denser.

Ahem.

Next you'll tell us that the hosts.txt database was a great idea and
you see no reason why we should have built the DNS. After all, host
addresses are only 32 bits, so the problem of mapping them into
hostnames should be easy to do in a flat database, right?

If you'd like to volunteer to run the centralized databases containing
the (at least) five billion keys for the population of the planet,
including handling tens to hundreds of billions of hits against them
per day, and probably tens of millions of updates per day (perhaps
you'd like us to enter them by hand, too?) and you'd like to supply
this service for free, then we will certainly be willing to talk.

Until you volunteer, however, leave the engineering to the people with
some experience in building large scale systems?


Perry

(Sure, TRW can store 100 million records in a giant database and index
them purely by a single unstructured number. 'taint cheap or fast,
however, and it certainly isn't amenable to decentralized maintainance
of the data.)

I was just reading RFC1034 about DNS, and one thing I noted was that there is a
"reverse lookup" feature.  This allows you to go from, say, 156.151.1.101
to portal.com.  This problem seems similar in some ways to the key lookup
problem since you have a relatively unstructured number and you want to
use it as a lookup key.

According to the RFC, if you want to know what host machine is at
address 156.151.1.101, you do a lookup of 156.151.1.101.IN-ADDR.ARPA.
The RFC did not make it very clear how this is done.  Does this use a
"flat" database?    Is it distributed in some way?  Or has this method
perhaps been superceded by some other?

I can see that the key problem is worse than the reverse lookup problem
because there are many more users than hosts.  Although in the long run
won't everybody have a computer at home that has an IP address?  Will the
nameserver hierarchy run into problems then?  There is no obvious
hierarchical arrangement as we have now with our .edu and .com sites,
unless we go geographical.  This seems analogous to the PEM/RSA key
certificate hierarchy problem.  In any case the reverse lookup problem
seems like it will be difficult then.

Hal

> From: Hal <hfinney@shell.portal.com>
> 
> I was just reading RFC1034 about DNS, and one thing I noted was that
> there is a "reverse lookup" feature.  This allows you to go from, say,
> 156.151.1.101 to portal.com.  This problem seems similar in some ways to
> the key lookup problem since you have a relatively unstructured number
> and you want to use it as a lookup key.
[...]
> According to the RFC, if you want to know what host machine is at
> address 156.151.1.101, you do a lookup of 156.151.1.101.IN-ADDR.ARPA.
> The RFC did not make it very clear how this is done. [...]

Actually you do a lookup on 101.1.151.156.in-addr.arpa, it is reversed
because of the way addresses are structured.  This is part of the
problem with PGP keys and DNS: PGP key IDs are unstructured and randomly
distributed, IP addresses are not really unstructured and thier
distribution is not random.  A reverse lookup (aka "pointer query") happens
the same way as a regular name lookup, it just reverses the order of the
bytes in the IP address and then resolves it in the same method as a
regular name, from the least specific to most specific parts of the
address. 

With a PGP key ID there is no order to the distribution of the IDs, so it
is not like one could delegate authority for bits in a key ID the same way
taht one can with bits/bytes in an IP address.  The inability to delgate
chunks of the key ID space is what will prevent lookups by keyID; no one
can run a single server that has all the IDs and the organizational
problems with delegating random chunks of the keyID-space are fairly obvious
(e.g. in the DNS model you are responsible for your own address space and
it is in your own self-interest to make sure that it works, the same cannot
be said of keyID-space)

jim

Hal says:
> I was just reading RFC1034 about DNS, and one thing I noted was that
> there is a "reverse lookup" feature.  This allows you to go from,
> say, 156.151.1.101 to portal.com.  This problem seems similar in
> some ways to the key lookup problem since you have a relatively
> unstructured number and you want to use it as a lookup key.
> 
> According to the RFC, if you want to know what host machine is at
> address 156.151.1.101, you do a lookup of 156.151.1.101.IN-ADDR.ARPA.

No, you got that wrong. You do a lookup on 101.1.151.156.IN-ADDR.ARPA
-- note the component reversal. The reversal is very key.

> The RFC did not make it very clear how this is done.  Does this use a
> "flat" database?

No. Its fully distributed. The fact that networks are assigned in
heirarchical chunks should explain how its done, and why the bytes get
reversed for the lookup. As an example, MIT owns network 18, which is
to say that all MIT addresses are 18.XXX.XXX.XXX, and 18.IN-ADDR.ARPA
is a server at MIT. MIT may have sub-servers beyond that level, but
DNS makes us oblivious to this.

For IPv6, the reverse lookup is going to be segregated at the nybble
boundaries rather than at the byte boundaries because of CIDR style
classless allocation. The domain will be IP6.INT rather than IN-ADDR.ARPA

Perry