How to not have to trust CAs

[Norman Hardy]

I have been reading RFC1422 which describes the hierarchy of authorities
(CA = Certificate Authorities) proposed for distributing public keys for
PEM and such. One must trust the CA which is a leaf of this hierarchy. If
higher elements of the hierarchy are corrupted there is also danger but
perhaps it is less. One interesting thing that I learned is that RFC1422
specifically allows for "personas" as in pseudonyms. Their treatment of
CRLs (Certificate Revocation List) is most of the complexity and hard to
understand and implement. It is a hard problem.

Here is a different scheme that involves such a hierarchy but does not
require one to trust anyone in the hierarchy except concerning denial of
service. The scheme allows one to check the hierarchy. I ignore the
revocation problem in this note.

The idea stems from an idea that came from Belcore I think. The Belcore
idea posits a tree of nodes where each node holds the secure hash of each
of its children. The secure hash of the root node is published in the
Sunday New York Times and a few other places. There are weekly editions of
the tree. If I may want to prove to you in the future that some certain
piece of data exists this week, then I arrange to put a secure hash of that
data in some leaf of next weeks edition of the tree. If I should ever need
to present proof, I display the contents of each of the nodes between my
leaf and the root. (I got that list a few days after I submitted my secure
hash.) You can compute the hashes of each node and observe that they each
occur in the superior node. You compare the secure hash of the root node
with what is in the Times. The only plausible explanation is that someone
had the data  at the date of publication.

My CA scheme is a variation of the above. A certificate is a (name --
public key) pair. The names are stored in a tree in alphabetical order.
Each node in the tree holds a pair (first name in child node, secure hash
of child node) for each of its children. (This is much like a B-tree.)

The tree is available thru an untrusted CA. When you request the public key
from the CA corresponding to some name, all nodes from the leaf with that
name, thru the root are returned. You verify the secure hashes as in the
Belcore scheme. You also verify that name stuff in the intermediate nodes
is correct. The later is to prevent the CA from showing one public key to
some requesters and another key to others.

My secure mail agent queries the data base upon each new edition to ensure
that my own public key is reported correctly. (Besides being published in
the Times, the hash of the top node is transmitted once per minute in video
blank time on NBC.) Since the data base can't tell different requesters
different things, the agent can be sure that all requesters will be
informed of my correct key.

I would prefer to change my public key at most once per month and then only
with a month's notice. This gives me time to verify that the CA is telling
the truth about my PK and warn correspondents otherwise. This avoids the
attack of the CA publishing a bogus public key to which it knows the
private key in order to decipher mail intended for me. In all, changing
public keys may be more dangerous than not!

This system still has several flaws. There is a single point of failure.
Failure is not immediately catastrophic as old keys can continue in use. If
you mistrust the CA you must inform your correspondents quickly, (via a
signed message). If there are several such hierarchies then each user with
a public key must subscribe to each lest one of the hierarchies lie about
his public key.

I think that revocation is better solved (easier code and smaller data) by
Blum filters but that is another story. The policy revocation problems are
still difficult.