[messaging] Multiple devices and key synchronization: some thoughts

[Trevor Perrin]

On Sat, Dec 27, 2014 at 7:23 PM, David Leon Gil <coruus at gmail.com> wrote:
>
> So, we all have multiple devices. And any messaging design
> should work as seamlessly as possible (given the particular
> design's security goals) for this "multi-device" case.

Hi David,

Good topic, I agree on some points and disagree on others.  My analysis:

Imagine a user has an initial device with a long-term key pair that is
involved in decrypting messages.  The first question is how to make
this "decryption-involved key", or at least its output, available to
the user's other devices.

There's some nuance to the idea of a "decryption-involved" long-term key, e.g.

 * If you're using a PGP signing key to sign short-lived subkeys I'd
consider the signing key "decryption-involved", since new devices will
need to frequently either sign device-specific subkeys or receive
shared subkeys.

 * If you're using a PGP signing key to *infrequently* sign long-lived
subkeys, then the subkey is the "decryption involved" key that needs
to be available to other devices.

Anyways, short-lived or one-time subkeys / prekeys are a good idea for
forward secrecy.  However, I don't think they affect the rest of this
analysis, so I'll ignore them and focus on the decryption-involved key
pair.

Here's a few possibilities for dealing with it:

(1) The initial device serves as a "decryption gateway" for other
devices.  For example, users might install a home server to handle
decryption, and configure their devices to access messages through it.

(2) All devices have device-specific decryption-involved keys, and
cross-sign each other's keys.

(3) All devices have device-specific decryption-involved keys, and a
master device uses a signing key to authorize subordinate devices.

(4) The initial device copies its decryption-involved key pair to
other devices, which become peers.

Analysis:

I think (1) might have some uses, but isn't a "consumer-grade" user experience.

(2) has the potential benefit that old devices could be revoked and
new devices could be added to the cross-signed set.  However, this
adds a level of complexity that seems impractical:
 * The user ceases to have a single public-key and fingerprint, and
instead has an evolving "cloud" of cross-signed keys.  It's not clear
how you would apply public-key verification like TOFU or
fingerprint-validation in this case.
 * Adding a new device requires acquiring a cross-signature from all
existing devices, which is awkward and has to be managed carefully so
users can't be tricked into signing wrong keys.
 * Revoking or expiring old keys has less value than one might think.
Revocation data might not arrive, and expiration depends on time sync
which is a dangerous assumption for reliability and security reasons.

The UX and security considerations for signing a key (3) and
transferring a private key (4) are similar: in either case, the
receiving device would provide and authenticate a public key (e.g.
over a "local channel"), and the sending device would either sign it
(3) or encrypt the decryption-involved private key to it (4).

(4) is simpler and more efficient, since (3) involves transmitting and
verifying signatures and potentially chains of signatures (if the
initial device authorizes one device, which authorizes another, etc).
(4) also doesn't have the master / subordinate distinction, which
should make it easier for users to understand and work with.

Signatures give you the possibility of binding subordinate devices to
a limited set of privileges, but in the text / email scenario I have
trouble seeing uses for that complexity.  So (4) seems preferable
here.

You criticized (4) on a few grounds I don't agree with:

 * The Whiteout implementation uses a QR code to display a
symmetric-key instead of a public-key.  I agree that seems suboptimal,
but it's not a general problem.

 * You argue that "Anyone who obtains the private key from any device
can impersonate the user."  That's true in any system, multidevice or
not.

 * You argue "If messages aren't signed, [someone who compromises the
private key] can (usually) carry out KCI attacks against the account".
But it's easy to use device-specific key pairs for authenticating the
remote party, so that compromise of one device doesn't enable
key-compromise impersonation (KCI) against other devices.

---

A second question is how to handle the long-term key pairs used for
message authentication.  This question is relevant whether
authentication is done with signatures (e.g. PGP) or key agreement
(e.g. TextSecure).

I'd suggest handling the authentication-involved keypair the same as
the decryption-involved key pair.  In the simplest case, use the same
"identity" key pair for authentication and decryption, and use (4) to
share that key pair between devices (TextSecure will do this [1]).

You mentioned sharing the decryption-involved key per (4), but then
using cross-signed key pairs for authentication.  You suggest the
benefit that "Key compromise can be attributed to a device", but I'm
skeptical that small benefit justifies dragging in the complexity from
(2).

Trevor

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