[messaging] Transparency for a key directory without publishing usernames

[Joseph Bonneau]

On Wed, Oct 8, 2014 at 2:58 AM, Trevor Perrin <trevp at trevp.net> wrote:
>
> Suppose that each day the key directory constructs a "Sparse Merkle
> tree" [1] that maps usernames to the user's identity public key(s) for
> the previous 24 hours.  The "signed tree head" (STH) is a signed hash
> of the sparse Merkle tree root and the previous day's STH.
>

Like the idea. Actually I think it's even better than your post suggests.


> Users could gossip the latest STH by including it in their encrypted
> messages to each other.  Users would request proofs from the directory
> that STHs are consistent, and that identity keys are consistent with
> STHs.
>

What would you check "consistency" with? I think the log can just publish
signature(Merkle root of entire current data structure, epoch #) every
epoch. Maybe the epoch is 1 day but this is a trade-off. The tree can
change arbitrarily every epoch and that's okay. You still need gossip to
check that they don't sign two trees in the same epic, but otherwise
consistency is basically available "for free."

Users can request proofs on demand that their desired key material is
correctly included every day at the hash of their username. Your software
can automate this. Each proof would be 1 signature plus 256*256 bits of
Merkle proof (perhaps less if we can drop collision resistance in the hash,
which may be safe but haven't thought it through. Plus a signature. Less
than 10kB total (maybe down to just a few kB).

Your software can ping you if your data ever changes in a way it didn't
expect. If you go offline, you can catch up (though you won't detect the
attack until later obviously). Basically this is like monitoring except you
can do it yourself locally. You could have an offline monitor check for you
as well. The key point is that checking for N users takes work linear in N
with no overhead from tracking the whole structure like you have in some
other systems.

So I think this has some cool advantages.

Further comments:

1) Self-enforcing security

Digging into the Crypto Bag Of Tricks there's an interesting and
potentially stronger approach: tagged one-time signatures [1]. With this
approach, if the server ever signs two Merkle roots for the same epoch #,
you can use the two signatures to re-construct their private key. You still
need gossip to discover this, but this is a big disincentive to the server
ever cheating.

Perhaps this is a bad idea-it's a big loaded gun and the system will
collapse spectacularly if the log screws up. Maybe we want the flexibility
for a misbehaving log to explain itself publicly and be forgiven, or maybe
we explicitly want a Sword of Damocles over their head to avoid them being
able to do so.

2) Key Directory vs. Short-lived certificates

Two approaches are possible for privacy: in one version, the log functions
as a key directory and will respond to anonymous queries for a given
username. In this case you have to deal with DoS and people trying to
brute-force to find usernames. Maybe privacy goes down.

Alternately, it can function as a type of "certificate authority". Your
"certificate" is the proof that your cert is included in a specific epoch.
You can give this to anybody else (size < 10kB) and they can check that
this really is the key for the username you just claimed. The log would
only give this proof to the user themselves (perhaps authenticated however
they authenticate changes to that user's log entry), after which you can
give your proof to whomever you want through other channels. Privacy seems
higher here, though everybody has to download a new cert every epoch so the
epoch probably need to be longer and revocation is worse. Which leads to
the net point.

3) Dealing with immediate issuance

In the simple approach, you can't add new data to the log until the next
epoch. Maybe we can drive this down to a matter of minutes (and users will
accept data from a slightly out-of-date epoch). At some point the cost of
downloading your proofs at every epoch becomes prohibitive, which probably
means that you can't immediately download the chat app, make a new
username, and start talking. That might be the "fatal flaw" in practice.
One approach is issuing SCTs to use before inclusion but that seems to pull
in a lot of complexity. You might also have some side data structure for
newly issued certs, though that seems to invite MITM attack by inserting
things there. Or maybe there's a really elegant extension of the tree with
things changing at different epochs to be discovered.

Seems worth exploring further to me.

Joe

[1] http://link.springer.com/chapter/10.1007%2F978-3-642-36362-7_20
(apologies, couldn't find a non-paywalled link)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141008/32ba94fd/attachment.html>