[messaging] Thoughts on keyservers

[Trevor Perrin]

Suppose you want to lookup someone's public key based on their
username (e.g. lookup a PGP key based on email address).

Once you have this key you can do TOFU, fingerprint checks, etc., but
you'd ALSO like to have some trustworthy entity tell you the key.  But
how?

 * Search the "web of trust" of people you know, and people they know,
and so on, hoping there's a path to someone who can vouch for the
subject's key.  But this involves a public social graph of users,
expensive graph searching, and poorly-understood human interface
issues around graphs of trust.

 * Query a "central authority" where everyone registers their public
key.  To mitigate availability and monopoly risk there could be
several such authorities, and users just have to register with one.
But multiple authorities increases the risk of "misissuance", and
mitigating that risk is difficult.  (One approach is for authorities
to also provide a proof that the key was published (Certificate
Transparency), so misissuance can be detected and responded to.
That's promising, but complicated and unproven.)

The "trust agility" in the web of trust seems like a good idea for any
system without the performance constraints of HTTPS.  But using
regular people as trust intermediaries seems unlikely to scale outside
small groups.  So we could combine these:  Bob could register his
public key with several keyservers, and Alice could query several
keyservers she trusts.  Hopefully there's overlap and Alice finds
Bob's key.

But there's still a coordination problem - what if Bob registers his
key someplace, and Alice checks somewhere else?  It's unclear how this
would play out at scale - fragment into islands? centralize around one
authority?  Maybe Bob registers his public key with a central,
widely-known keyserver and also local keyservers based on his
affiliations, but that's a lot of registering, and a lot of keyservers
that's it's unclear why anyone would run.

---

A different approach is to have Bob's service provider, as specified
in his username, be his keyserver (LEAP, STEED, UEE).  For example,
the keyserver for bob at example.com would be example.com.  This
eliminates the coordination problem, makes registration easier (Bob
authenticates to his provider), *might* address the incentive problem
(Bob's service provider would run the keyserver as part of providing
him service), and gives Bob flexibility to choose the keyserver (by
choosing his provider).

Of course, now Alice needs to authenticate example.com.  A DNS
solution (DNSSEC or DNSCurve) seems elegant - if bob at example.com is
vouched for by example.com, then example.com could be vouched for by
com, who's vouched for by the DNS root.  But since example.com is a
public server with administrators, it has plenty of other options
(HTTPS certs, CT logs, pinning via HPKP/TACK or curated pin lists,
etc.).  So we can handwave "Alice authenticates example.com" as being
solvable a bunch of ways.

A sharper criticism is that changing providers and usernames is
costly, so Bob's flexibility is limited.  Moreover, Bob's provider is
on the communication path, thus is one of the most important threats
for end-to-end crypto to protect against.

So provider-based keyservers are convenient (easy for Bob to register
with and Alice to find), but it's unclear how much they should be
trusted.  Maybe they aren't trustworthy but are useful anyways, to
find keys we acquire trust in via TOFU and fingerprint checks.

Or maybe keyservers could be made more trustworthy via auditing.  If
keyservers support lookup over Tor then it's hard for them to deliver
targeted wrong answers.  Keyservers could also support "transparency"
similar to CT, e.g. periodically snapshot their directory so that
3rd-party monitors can fetch the delta of new/deleted entries.  These
monitors could notify Bob if his key changes, and send Alice a root
hash that she uses to check that keyserver responses have been
published [1].

So far we've assumed Bob has a single username.  But Alice might know
Bob via multiple usernames (email, skype, facebook, twitter, etc).  If
all these hosted keyservers, Alice could lookup Bob's public key from
multiple providers.  Even if they don't host keyservers, social media
sites make it easy for Bob to publish information, so could be
leveraged as "keyservers" with some cleverness (see Keybase [2]).

---

In conclusion, there's a lot of ways to distribute keys.  We probably
want more and better keyservers.  It's hard to say who should run
these.  Maybe existing service providers will help, or can be
leveraged regardless - that's worth discussing more.

There are also protocol design questions that could be tackled
independent of who runs things, e.g.
 * How to make keyservers auditable
 * Design of protocols and data formats so that public keys, certs,
fingerprints, revocation data, prekeys, and so on can be published
through a variety of channels

Probably more but this is way too long already...

Anyways, thoughts?


Trevor

[1]
https://moderncrypto.org/mail-archive/messaging/2014/000226.html
https://moderncrypto.org/mail-archive/messaging/2014/000244.html

[2] https://keybase.io/