From: Raph Levien <raph@cs.berkeley.edu>
Date: Thu, 9 May 1996 09:41:34 +0800
To: cypherpunks@toad.com
Subject: Re: Transitive trust and MLM
Message-ID: <3190E8A7.6501A85@cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain


I'm really glad to see this thread. I think this is a problem that is
well worth thinking about.

   I think what is really called for is a model of when keys are likely
to be bogus, and when signatures, etc., are likely to be correct. Before
going into the math, I'll go through some examples.

   Any key that's "well connected" in the MIT keyring is likely to be
good. Specifically, if it's signed by lots of people, and each of those
people is reachable from my trust root, then I'm pretty much willing to
believe the key is good.
   Unfortunately, there are a fair number of reasons why a key may be
bad. A really _cool_ thing to do with a compromised machine would be to
sign a big bunch of bogus keys. Given how easy it is to compromise a
machine, this is a very real worry. I don't know if this attack has been
realized yet, but it's best to assume it could be and will be.
   Another weakness is the "clueless user" who signs keys gotten from
the Net, or otherwise not properly verified.
   I don't claim to know all of the vulnerabilities, but I do think it
would be a good idea to quantify them before designing a key
distribution system.

    Hal calls into question the value of signed keys. To me, this points
to the pressing need for better manual verification of keys, by
communicating secure hashes through the phone and on physical channels,
including business cards. These channels are more secure than the Net,
are more convenient for all but the most hardcore net.heads, and would
actually work quite well, I think. But I do think it would be nice to
have access to "probably good" keys for casual e-mail. With luck, a
densely connected Web of manually obtained keys can serve as a good
foundation for the latter.

   Now for the mathematical model. Signatures can bind keys to e-mail
addresses, or act as assertions that the signed public key is trusted to
transitively sign other keys. Let's assume that each signature has a
certain probability p of being good, and a 1-p probability of being
bogus, and that all probabilities are independent. These are probably
bad assumptions in the real world, but that's the difference between
theory and practice.
   Now we can actually evaluate the probability of a given key being
good. Consider a Monte Carlo process in which each edge in the graph is
present with probability 1-p. For each run, we determine whether the
recipient's public key (actually the binding between public key and
recipient's e-mail address) is reachable from our trust root. The
probability over a large number of runs is (given our assumptions) the
probability of the key being good.
   One encouraging consequence of this model is that densely connected
subgraphs can result in highly trusted keys even if p itself is quite
small. In a clique of size k, the trust is (very) roughly 1-(1-p)^k. For
example, if p is a mere 50%, then in a clique of size 10, each key in
the clique is trusted with a probability of 99.9%.
   This computation is (I think) known as the network reachability
problem, and is probably quite hard to evaluate. In practice, you'd
probably want to compute upper and lower bounds instead,

   Let's see if we can come up with a model that preserves this property
of giving high trust values to densely connected keys, yet is also
highly resistant to (some plausible model) of attacks against the Web of
trust.

Raph