[messaging] Google End-to-End plans on using key directories with a CT-like verification protocol

[Moxie Marlinspike]

On 08/27/2014 12:32 PM, Tony Arcieri wrote:
> They plan on having email providers run "Key Directories" and using
> encrypted messages to gossip data about the directories, providing a
> CT-like system:
> 
> https://code.google.com/p/end-to-end/wiki/KeyDistribution

I still have some questions about this approach.  My understanding is that:

1) The monitors themselves can't determine whether Google is being
"dishonest," beyond one extremely coarse view of whether Google is
publishing an appropriate data structure.

This is because:

a) Users' keys will be changing constantly under completely normal
circumstances.

b) From running a service that operates as a sort of "key directory," I
know that many times they will even be changing in "suspicious" ways,
ie. from A to B and then back to A again.

This means:

2) Users are the only ones who have the information to determine whether
Google is being dishonest.

This is because:

a) Users are the only ones who know what their keys actually are, and
whether they were supposed to change.

So we're in a situation where the best a "monitor" can do is provide the
user with a view of their key state over time, which the user can verify
with their own knowledge of what their key state should be.  Nobody can
detect an attack but the user themselves, which they depend on a third
party service in order to be able to do.  Everything is dependent on the
user.

I think there are three distinct classes of users:

i) Almost everyone. In the world where all GMail customers are using
E2E, the vast majority of them won't (and shouldn't be expected to) know
what their key state should be, or what a key even is.  So for those
users, Google can make whatever key changes they want with impunity, and
neither the "monitors" nor the users would be the wiser of Google's
nefarious ways.  This may be OK, particularly if there's no way for
Google to distinguish between types of users.

ii) The crypto few. There is a small percentage of users who will know
what a key is and understand how this works well enough to be able to
effectively monitor these changes.

iii) Wingnuts.  Larger than the crypto few, but still a vast minority.
They'll know what a "key" is, but won't *really* understand how this
works, and will become convinced that Google has MITMd them when their
key changed under normal circumstances.

I don't see any way to distinguish the "wingnuts" from "the crypto few."
 If either user steps forward to declare that their key was compromised,
the only information we have is the log.  However, the user is the only
one with the information to determine whether the log is correct or not,
so there's no real "proof" other than the user's word.  Even with all
the monitoring infrastructure available, there's still no information
that a 3rd party can use to determine whether a key was maliciously
inserted or not.

That doesn't really seem to add up to a great situation.  As I see it:

1) This is a *lot* of work.  Servers have to maintain these directories
at volumes (hopefully all gmail users) that are already difficult
enough.  Other organizations will need to be formed with somewhat
considerable resources in order to effectively keep up with the monitoring.

2) Users can be successfully MITM'd, and will only learn about it after
the fact.

3) It creates a potential SPAM problem.

4) It creates a potential reputation problem for the key directory,
since "wingnuts" will constantly be announcing that they've been MITM'd
(complete with "proof" in the form of the log), and there'll be no way
for us to distinguish them from "the crypto few."

So my question is, how is this better than doing the following:

1) Transmitting identity keys in-band.

2) Doing TOFU for keys seen.

3) Make the client notifying the user when a key changes, if the user
has a key change notification preference set.

4) Leaving the key change notification preference off by default.

It seems to me that this has the same security properties as the CT-like
system, except:

a) A *lot* less work, and a lot less complex.  No need for other
organizations to form.

b) Both "wingnuts" and "the crypto few" are notified immediately of a
MITM rather than after the fact.  "Almost everyone" remains blissfully
unaware, but again maybe that's OK if there's no way for the provider to
know with certainty which category a user is in.

c) It's harder for wingnuts to get confused.

d) No SPAM problem.

I'm really interested in hearing why partisans of the CT-style key
directory think the overhead and other drawbacks are worth doing it over
the simpler thing?

- moxie

-- 
http://www.thoughtcrime.org