[tor-talk] Why the Web of Trust Sucks

Tue Oct 1 01:02:59 UTC 2013

Mike Perry transcribed 6.8K bytes:
> 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.

Actually, this only works, given that Edward has *ultimate* trust in
Bruce. Most people only give ultimate trust to keys which they control.

> 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).

See the options for the 'auto-key-locate' settings, specifically 'pka',
'cert', 'keyserver-URL', and 'ldap'. Don't ask me how the LDAP one works, I've
never messed with it.

1. DNS PKA

   For the DNS PKA setting, you'd need to add a TXT record to your DNS. [1][2]
   To see mine, do "host -t TXT isis._pka.patternsinthevoid.net". It looks
   like in my zone file:

   isis._pka       14400   TXT "v=pka1;fpr=0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35;uri=http://blog.patternsinthevoid.net/0xA3ADB67A2CDB8B35.asc"

   It unfortunately doesn't work if the specified URI is HTTPS, but it does
   work with crappy old protocols like finger. Go figure. However, there is
   some of the functionality you want, if you also add "pka-lookups
   pka-trust-increase" to the "verify-options" setting in gpg.conf (doing so
   would automatically increase your trustdb calculation for that key, if it
   has a DNS PKA TXT record and that the fingerprint specified there matches
   the fingerprint on the key you already have).

   Also, a warning: gpg totally disrespects any proxy settings for DNS
   resolutions. The only way around this (safe in my tests so far, which have
   been going for almost a year now) is to resolve the domain of whatever
   keyserver you use, and then use it's IP address instead. For example, in my
   gpg.conf, it goes like this (for hkps://keys.indymedia.org)[3]:

   keyserver hkps://204.13.164.120
   keyserver-options verbose verbose verbose include-revoked include-disabled no-auto-key-retrieve no-honor-keyserver-url no-honor-pka-record include-subkeys no-include-attributes ca-cert-file=~/scripts/certs/keys.indymedia.org http-proxy=socks://127.0.0.1:59050

   Also, using HTTPS or HKPS generally doesn't work, or is a huge pain in the
   ass to get working. These people still use finger, for fucks sake. I don't
   think they've heard the word "privacy" before.

2. DNS CERT

   Essentially the same as DNS PKA, but you need to compile GnuPG, including
   the tools/ subdirectory to get the make-dns-cert script. This actually puts
   your GPG key in a DNS TYPE37 record, [4] and (I think?) it works the same as
   DNS PKA for the trust increase stuff.

3. Preferred Keyserver notation packets

   For the '--auto-key-locate keyserver-URL' setting, see also the
   'preferred-keyserver-url' setting, which adds a Preferred Key Server
   notation packet [0] to all signatures and certifications. For example,
   looking at the last commit I made on BridgeDB (I sign all my commits):

    * commit 44606980d4674548048e164106cf2d2e73cd6a08 (HEAD, tpo-isis/feature/9199-improved-logging-2-r2
    | gpg: Signature made Mon 30 Sep 2013 02:04:07 UTC
    gpg:                using RSA key 5C17776E27F7E84D
    gpg: Good signature from "Isis! <isis at patternsinthevoid.net>" [ultimate]
    gpg:                 aka "Isis <isis at torproject.org>" [ultimate]
    gpg:                 aka "Isis <isis at leap.se>" [ultimate]
    gpg:                 aka "Isis! <isis at riseup.net>" [ultimate]
    gpg: Signature policy: https://blog.patternsinthevoid.net/policy.txt
    gpg: Preferred keyserver: https://blog.patternsinthevoid.net/isis.txt
    gpg: Signature notation: isis at patternsinthevoid.net=FC63AA5CD193869C3237145A5C17776E27F7E84D
    gpg: Signature expires Tue 30 Sep 2014 02:04:07 UTC
    Author:     Isis Lovecruft <isis at torproject.org>
    | AuthorDate: 81 minutes ago
    | Commit:     Isis Lovecruft <isis at torproject.org>
    | CommitDate: 77 minutes ago
    |
    |     Add bridgedb.utils package, and add bridgedb.utils.parsers module.
    |
    |  lib/bridgedb/utils/__init__.py |  9 +++++++++
    |  lib/bridgedb/utils/parsers.py  | 32 ++++++++++++++++++++++++++++++++
    |  requirements.txt               |  1 +
    |  setup.py                       |  3 ++-
    |  4 files changed, 44 insertions(+), 1 deletion(-)

   A normal gpg client would use https://blog/patternsinthevoid.net/isis.txt
   as the keyserver for updating and re-fetching my key. (The push updates
   don't work so well, I just get a denied resource in my webserver logs,
   which get shredded like every three hours or something.)

   To see all the extra crap on my signature on this email...you'd need to do
   "gpg --verify-options show-policy-urls show-notations show-user-notations
   show-keyserver-urls pka-lookups pka-trust-increase --verify
   <this_email_file>".

> 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).

This already exists, see the 'ca-cert-file' option under 'keyserver-options'
in the gpg man page. It seems like a bad idea to hardcode it, because then I'm
dependent upon Werner Koch to update the code when the cert for
keys.mayfirst.org or keys.indymedia.org changes (and then also dependent upon
the distro maintainer of gpg to backport the patches, if I were to use a
packaged version).

Also see my above note under "1. DNS PKA" above, on HKPS/HTTPS keyservers.

> ** 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.

Alright, but your problems are GnuPG-centric, and there are other ways of
checking trust paths. Try wotsap, lysator, [5] or footsie. [6] Just because
GnuPG and the most of the keyservers are exceptionally outdated (and IMO
crappy to begin with), doesn't mean that the WOT model is broken. I mean,
sure, it's centralised, hard to understand, requires trust-on-first-use, is
prone to all kinds of timing correlations attacks and enables social network
graphing. But that doesn't mean it's broken, right?

You know what, Mike Perry? I think you're just jealous that all the other Tor
developers are in the Strong Set. You know, we could put you in the Strong Set
pretty fast, I could put that cronjob back... :D [7]

I'm conflicted. I think GnuPG is a piece of shit, and that it's actively
hindering security via the difficulty of its use. GnuPG means that I can't
safely talk to my mom; I hate the thing. And I hate the WOT, just as much as
you do, if not proportionally more given my familiarity with it.

Fuck it. It's broken.  Not for the reasons you've listed, though. I think for
the most part the problems you mention are GnuPG-centric and I've invalidated
a good chunk of them (not excusing the GnuPG implementation of the OpenPGP
spec, which could likely be re-implemented in a substantially more robust and
user-friendly way). I think it's broken only because my mom's been coding
since before I was born and she can't fucking use the damned thing.

Somebody please write a replacement. One, two, three, not it. Or give Pond a
decent peer review. [8]

References:
[0]: "Preferred Key Server" https://tools.ietf.org/html/rfc4880#section-5.2.3.18
[1]: "OpenPGP in DNS" http://www.df7cb.de/blog/2007/openpgp-dns.html
[2]: "Publishing PGP keys in DNS" http://www.gushi.org/make-dns-cert/HOWTO.html
[3]: The simplest way to get the the cert:
     openssl s_client -connect keys.indymedia.org:11372 </dev/null 2>/dev/null | \
         openssl x509 -in /dev/stdin
     The port for keyservers is 11372 (usually) if it's encrypted, and 11371
     otherwise.
[4]: "RFC 4398: Storing Certificates in the Domain Name System (DNS)"
     https://www.ietf.org/rfc/rfc4398.txt
[5]: http://pgp.cs.uu.nl/ http://www.staff.science.uu.nl/~penni101/henkp/pgp/
[6]: http://www.parisc-linux.org/~willy/wot/footsie/
[7]: https://twitter.com/isislovecruft/status/383404810369638400
     https://twitter.com/isislovecruft/status/383404897611157505
     https://twitter.com/isislovecruft/status/383407186279292929
     https://twitter.com/isislovecruft/status/384061132291321856
     https://twitter.com/isislovecruft/status/383443291653435392
[8]: https://pond.imperialviolet.org/

-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
GPG: 4096R/A3ADB67A2CDB8B35
Current Keys: https://blog.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1036 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-talk/attachments/20131001/c4f3ec91/attachment-0001.sig>