[tor-talk] Why the Web of Trust Sucks

[Mike Perry]

Joel R. Voss:
> Hi Mike,
> 
> I'm writing a blog post about web of trust. I'm looking for any weaknesses I 
> can find in it because I'm writing a piece of software that would be designed 
> to help grow it. I'd appreciate if you could give me a few points that I can 
> research. I'd be happy to send you my findings so far if you want to read them. 
> This is a fairly important subject because many people rely upon it for 
> software signing, encrypted e-mail, and soon we could use it much more widely.

The web of trust has three main problems:

1. It leaks information.

This includes social graph metadata, time and place of interaction, and
in some cases government/slave-name identity. This issue has been
discussed at length, of course.


2. It has many single points of failure.

Because by default GPG uses shortest-weighted paths to establish trust
in a key, and moreover because nothing authenticates the *entire* Web of
Trust graph, each and every member of the "Strong Set" essentially
functions as a CA, especially for keys only weakly connected to the
Strong Set. If you compromise just one of those keys, you get to use
that key to certify arbitrary keys for any name you like.

To understand how and why this is a problem, let's walk through a
typical Web of Trust workflow. 

Let's say we have a GPG user named Edward who wants to send an encrypted
email about the extreme level of corruption at his workplace to a
journalist that he has never met. Let's call that journalist Glenn. For
the sake of argument, let's say that both individuals are active
participants in the Web of Trust.

Edward also knows that the network systems administrators at his
workplace are very sophisticated, and intercept all encrypted
communications for purposes of active MITM attacks to obtain the
communications content. So Edward decides to download Glenn's key from
subkeys.pgp.net, and requests that his gpg client provide him with a
trust value for Glenn's key.

Now, the network systems administrators at Edward's workplace have
anticipated this. They have a compromised HTTPS CA cert, as well as have
compromised a couple of highly trusted keys from the Web of Trust. Let's
call one of these GPG keys Roger.

When Edward goes to download a key to use for Glenn, the network systems
administrator gives him a new fake key that they generate on the spot.
The network systems administrator also attaches a fully trusted
signature using Roger's compromised key. They also block the actual key
for Glenn from reaching Edward.

Edward's GPG client has trust in a couple keys. It turns out that one of
his trusted keys, Bruce, has full trust in Roger's key (the compromised
key).

Edward's GPG client then computes a fully trusted path from Bruce to
Roger to the fake Glenn, and Edward then sends an encrypted email to
fake Glenn that is then subsequently read by the network systems
administrator.

Game over for Edward :/.

This scenario is possible against arbitrary keys using any of the high
degree keys in the Strong Set. They effectively function as single point
of failure CAs for the Web of Trust, which destroy its utility as an
independent key authentication mechanism.


3. It doesn't scale very well to the global population.

The amount of storage to maintain the Web of Trust for the whole world
would be immense. For the level of authentication it provides, it just
doesn't make sense to have this much storage involved.



So what should we do instead?

Well, I think it is important to take a step back and think about what
the Web of Trust is trying to accomplish. Aside from being a global
popularity contest and some kind of weird quasi-religious hacker ritual,
it is an authentication mechanism for the keys that you retrieve.

It turns out there are lots of ways to authenticate keys using multipath
authentication that do not suffer from the Web of Trust's downsides**.

Here's a few examples:

1. Every time GPG downloads a new key, re-download it several times via
multiple Tor circuits to ensure you always get the same key.

2. Every time I verify a signature from a key sent to an email address
that is not mine (like a mailinglist), my mail client adds a tiny amount
of trust to that key (since each new public email+signature downloaded
represents an observation of the key via a potentially distinct network
path that should also be observed by multiple people, including the
sender).

3. Every time I am about to encrypt mail to a key, check the key servers
for that email address, download the key, and make sure it is still the
same (SSH/TOFU-style).

4. When downloading a key, GPG could verify that the same email to key
mapping exists on multiple key servers, with each key server
authenticated by an independent TLS key that is stored in the GPG source
code or packaging itself. (Perspectives/notary-style cryptographic
multipath authentication).



** The Web of Trust is technically capable of multipath authentication
by itself, but only if you are aware of all of the multiple paths that
*should* exist. Unfortunately, nothing authenticates the whole Web of
Trust in its entirety, so it is impossible to use it to reliably verify
that multiple paths to a key do actually exist and are valid.


-- 
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-talk/attachments/20130928/197f18b2/attachment.sig>