Re: [briar-devel] Multiple devices per user

[Michael R. <m-...@gm...>]

Forward secrecy is the name of my nightmares.

The multi-device proposal would weaken the forward secrecy properties of
simplex connections under the following circumstances:

* Alice creates key pair (d1, d2) for her device d1, and gossips pub(d1,
d2).

* Bob creates key pair (d2, d1) for his device d2, and gossips pub(d2, d1).

* d1 receives pub(d2, d1) and combines it with priv(d1, d2) to derive
the secret shared by d1 and d2.

* d1 destroys priv(d1, d2).

* d1 derives the shared secret for the current forward secrecy period
and destroys the initial shared secret.

* d1 sends a simplex connection to d2.

* Meanwhile, d2 has lost contact with Alice and Bob's other devices, so
it never receives the gossip of pub(d1, d2).

* d2 never destroys priv(d2, d1).

* The simplex connection can be decrypted at any time in the future if
the adversary compromises d2 and any device that received the gossip of
pub(d1, d2).



What's worse, a similar problem applies to introductions.

* Alice wants to introduce her contacts Bob and Carol.

* Bob and Carol each generate an ephemeral key pair and give Alice the
public key.

* Alice gives Carol's public key to Bob.

* Bob combines Carol's public key with his private key to derive the
shared secret.

* Bob destroys his private key.

* Bob derives the shared secret for the current forward secrecy period
and destroys the initial shared secret.

* Bob sends a simplex connection to Carol.

* Meanwhile, Carol loses contact with Alice, so she never receives Bob's
public key.

* Carol never destroys her private key.

* The simplex connection can be decrypted at any time in the future if
the adversary compromises Alice's device (to get Bob's public key) and
Carol's device (to get Carol's private key).



In the case of introductions, we could solve the problem by saying that
all parties must destroy the ephemeral keys at the end of the forward
secrecy period - if the introduction protocol hasn't completed then they
can try again with fresh keys.

But I don't see a similar fix for multiple devices - gossipping fresh
keys for every pair of devices in every forward secrecy period would be
really inefficient (the bandwidth cost per device would be quadratic in
the number of devices) and wouldn't necessarily succeed (there's no
limit on the number of hops the keys would have to travel in a single
period).

It bothers me that the design's getting complex enough to have corner
cases like this. I think it might be time to take a step back and look
for ways to simplify the system model.

Cheers,
Michael