From: don@cs.byu.edu
Date: Sat, 16 Mar 1996 18:41:38 +0800
To: cypherpunks@toad.com
Subject: Announce: WEB OF TRUST keyring
Message-ID: <199603150223.TAA00183@wero.cs.byu.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

March 14, 1996:

I announce the first true "web of trust" PGP keyring.

Last year, I attempted to create a keyring containing the web of trust. I
did so, because I was beginning the process of integrating PGP into my
mail and news, and realized that a valid signature did not mean much if I
had to reason to trust the key, not to mention that keyrings were
approaching 5 megabytes, which drastically slowed down searching through
the keyrings. 

In a web of trust, if A has signed B, then if A is in the keyring, B is
added. My project last year, as a result very crude methods I was using,
added B if B had signed A. This made for significant numbers of junk keys.
I promptly dubbed the keyring the "Web of Nobodies" keyring. 

There are many people in a much better position than I to do what I have
done. My methods are still somewhat crude. I have written, however, a
program that will generate the keyring with minimal user intervention,
using a seed key as its center.  I am considering releasing the source
instead of just the keyring. The code is sloppy, the methods crude. I
understand that PGP 3.0 will include the capability, so the program is
merely a short term solution to a short term problem. If there is a large
enough demand for the code, I will probably make it available. (Note: I
rely on PGP itself to extract the keys, which takes about 8 hours to
process on an HP9000) I would certainly appreciate feedback from anyone
who uses the keyring. 

The master keyring I used was a 9.3 megabyte keyring I obtained from the
Norwegian key site at uit.no (sorry bal, but I couldn't find yours).  I
obtained the keyring in late February. As the seed for the web of trust, I
used Derek Atkins's key. I have also inserted the following keys: 

Pr0duct Cypher  (0x97558a1d)
CancelMoose[tm] (0x538d56a1)
Scamizdat       (0x37a541d1)
Cypherpunk Enq. (0xaa5f5c9d)
Maude X         (0x1ead5e8d)

Black Unicorn was not inserted due to one key being revoked, and the other 
unsigned. I couldn't find Alice's key, and figured it wasn't worth the
trouble since it's fake anyway. (Or at least that's what the imposter has
convinced everyone.) I don't know of any other keys that should have made
this list.

The keyring is _significantly_ larger than I expected, 2.9 megabytes
uncompressed, although still a third the size of the original master.

Because of the size, I have also put together a second keyring using
stricter parameters. Only keys that were 4 hops from the "center keys"
(specifically, 5 keys between itself and Derek Atkins) were included,
with the additional constraint that _no_ keys with fewer than two links
toward the center (see below) were processed. The resulting keyring was
1 megabyte in size. (Note: the PGP extraction from the "big" keyring took
under 30 minutes)

The keyrings are named weboftrust.big.pgp.gz and weboftrust.small.pgp.gz
respectively. They are both available by anonymous ftp exclusively at
ftp.hacktic.nl / utopia.hacktic.nl, in /pub/replay/pub/pgp/pgp-key-ring.

C2 did not respond to either of two enquiries.

Detached PGP signatures of the .gz files follow:

- -----BEGIN PGP MESSAGE-----
Version: 2.6.2

iQB1AwUAMUfE3cLa+QKZS485AQHE5gL8DOAkT5s+BzIik5uK+NBW1ithL4DCfmll
pqin/4Bhs3LOP7zj11vvufMNGzDvcVonTO9meQEjPL4hanouxizzB7XM6CKidbK+
uAAxLvjkNKuRu1Ci1Tw6jbdd5WdG73us
=dXm9
- -----END PGP MESSAGE-----

- -----BEGIN PGP MESSAGE-----
Version: 2.6.2

iQB1AwUAMUfNKMLa+QKZS485AQG5FgL+Oy62xLT8zMJHpmyFez6uC7UJKFaOAxFB
nnWCUOLyp9X9KB+Kasn8Oex4glg1pEMOMB4ZiDT7iVJDuOmm1p07pC3pULmj0+O/
tnNEGbyOpyzeEnAb3vLVvHamzvZ+YPp/
=soxN
- -----END PGP MESSAGE-----

I have also done some analysis.

In the big keyring, there are 2910 keys. The longest trust chain length is
287 keys. The maximum connections any key had was 66. The average
"connectivity" among the keys was 4.3. (Hello to my friends at the NSA)

In the small keyring, there are 551 keys. The longest trust chain length
is, of course, 6 keys. The maximum connections any key had was 68. (I
have no explaination for why this is 2 more than the big ring, other than
coding changes) The average "connectivity" among the keys was 3.1.

For reference, the web of nobodies, built 6 months ago, had 734 connected
keys, a max depth of 104, maximum connectivity of 47, and average
connectivity of 5.6. 

For further information, by using the "big" keyring and not processing
any keys with fewer than _3_ links back to the "center keys", but with
no depth restriction, there are 1348 keys, producing a max chain length
of 83 keys. The average connectivity is 4.6. Meaning, there are several
people that would be very difficult to spoof. Go meet one of them.

In order to prevent loops, I keep track of whether a key had been visited.
By incrementing the visited field on a key each time I encountered it (but
exploring no further), I was able to roughly gauge how well (versus depth
== how close) connected the keys are, relative to the root. I used this
number in making the small keyring. 

I encourage Someone[tm] to start a keyserver servicing only the web of
trust.

Don
don@cs.byu.edu

Note to the curious: The reason I picked Derek is because I met someone
claiming to be Derek who not only gets mail at warlord@mit, but also has
control of the key. Hence, I'm merely picking the only key that comes with
PGP that I also happen to trust. 

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQB1AwUBMUjUAsLa+QKZS485AQGPCQL/bWRgDsE0QSwEf96aB3X4M+Wan7DGeeab
A9NuSpYF6RAm307mFIv7O7iSCcuuRlZmFZh9Bzmh456+8NdbuPSZBEk1+MNjHqmI
hhDFidL+IFpjNKItnIFCj1C9aOmyWRuN
=NZ0I
-----END PGP SIGNATURE-----
<don@cs.byu.edu>           fRee cRyPTo!   jOin the hUnt or BE tHe PrEY
PGP key - http://students.cs.byu.edu/~don   or PubKey servers (0x994b8f39)
  June 7&14, 1995: 1st amendment repealed.  Hello to my friends at the NSA.
* This user insured by the Smith, Wesson, & Zimmermann insurance company *