[messaging] Transparency for E2E encrypted messaging at a centralized service

[Trevor Perrin]

On Tue, Mar 25, 2014 at 8:24 PM, Joseph Bonneau <jbonneau at gmail.com> wrote:
> Here's an idea that arose between Daniel Kahn Gillmor and I (mistakes all my
> own). Imagine you're a centralized web service and you want to offer E2E
> encrypted messaging between your users.
...
> *The service runs a Certificate Transparency-style log for every certificate
> it issues


Interesting, let me try refine the proposal (based on Ben's comments),
and list some obstacles:


How it might work
------------------
If I understand Ben [1,2], the service could maintain a "Sparse Merkle
Tree" which implements an "authenticated dictionary" with these
properties:

 - Given the root hash of the tree, membership of a particular
(username, public key) or (username, <none>) pair can be proven by a
fairly small "merkle path" of hash values showing the connection
between a leaf element and the root.

 - The tree can be efficiently updated by publishing deltas [2].

So the service would publish the Sparse Merkle Tree, using deltas so
changes to the tree could be efficiently processed by 3rd-party
"monitors" (imagine the EFF).


For Alice to verify Bob's public key...

 - Alice would retrieve the tree's root hash from a trusted 3rd-party
monitor.  Alice would query the service for Bob's (username, public
key) and a merkle path showing membership in the tree.  By checking
membership, Alice confirms that the public key has been published.

 - Bob would register with the 3rd-party monitor to receive
notifications when his public key changes.

With this, the service can't change Bob's public key without Bob
hearing about it!


Obstacles
----------
 - This only has value if Alice and Bob are in the tiny fraction of
users who will run 3rd-party clients and setup notifications with a
monitoring service.

 - Even if Bob observes the service being malicious, he has no way to
prove this - it will just be his word against the service.  So the
"herd immunity" value of exposing the service's perfidy seems low.
(In contrast to Certificate Transparency for HTTPS, which is likely to
expose bad/hacked CAs who obviously shouldn't be issuing the revealed
certificates).

 - You're asking the service to publish large numbers of usernames,
which has privacy / business implications.

 - You're asking the service to setup a system designed to detect its
"cheating".  Maybe services want/need to cheat occasionally, to handle
govt requests?  Or maybe they don't want the "shitstorm of false
accusations" this could trigger from crazy users, as Moxie puts it.

 - Social-network messaging services currently do antispam and malware
scanning to keep users safe, so may not want e2e encryption at all.

 - A sophisticated attacker might go after the monitoring service, and
figure out how to suppress / block notifications.


Anyways, I need to think on this more.  There could be real value, but
the costs and obstacles seem pretty high.

It might be nice if the infrastructure and tools for this existed, so
it could be offered to services in a "ready-to-go" form, perhaps some
might be tempted to try...


Trevor

[1] https://moderncrypto.org/mail-archive/messaging/2014/000227.html
[2] http://www.links.org/files/RevocationTransparency.pdf