So, Trevor asked Yan to get me to write up some tentative thoughts on using multiple devices with modern messaging cryptosystems. (My thoughts on this owe a great deal to Yan, but any mistakes are entirely mine.)
These notes are on GitHub, and may be more legible with formatting: https://github.com/coruus/zero-one/blob/master/multidevice-keysync.markdown # Multiple devices and key synchronization Though I'm presently thinking mainly about mail-like services, I've tried to make this note as general as possible, perhaps at the cost of legibility. ## Introduction: The multi-device problem 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. ## Preliminaries (Skip ahead and come back.) Note: I don't cover the security of stored messages. This is really important, but a topic for a separate mail. ### Definitions A *user* is a human. An *account* is, well, an account with a service provider. An *identity* is some mapping between a set of accounts and a user or users. A *device* is a platform-provided data compartment (this may be, e.g., a single physical device, a user account on a device, or a browser profile). A device is *enrolled* when it is able to send and receive messages for an account. ### Framework I'll assume the following, toy authentication and key distribution/rotation framework: *Providers* operate "account authorities", which sign statements that attest to a device's control of an account. (E.g., by ordinary user login authentication.) There is a trustworthy *keyserver* which any account may query to obtain the current set of keys associated with another account. (More on this in another mail.) And the following, with respect to keys: - Encryption and signing keys are separate; encryption keys are signed by a signing key. - Each account has, associated with it, a "recovery" signing key, whose private component is stored offline. Keys may be rotated by cross-signing a new key, which is uploaded to the keyserver. Keys may always be revoked by a signature on a revocation statement by the recovery key. (And in some of the options I present, under other circumstances.) ### Security goals Security goals are standard for a messaging system that doesn't promise cryptographic deniability.[^traceability] The adversary is the global active adversary; it knows all internet packet's routes, can drop or replace them at will, and will conduct any computationally feasible attack that cannot be attributed to them. In addition, it has access to the (possibly encrypted) contents of every server. (I'm also very concerned about weaker adversaries: Script kiddies, APTs, etc., but the GAA described here models that threat reasonably well for this part of the problem.) [^traceability]: In particular, signatures will be used at least for some protocol messages. (In the particular scheme I'm most interested in at the moment, practically all messages will be signed.) ### Local channels A *local channel* is some method for transmitting secrets that does not involve packets transiting the internet. (E.g., QR code, Bluetooth, NFC, various more-or-less platform-specific stuff.) A *user-auditable local channel* is a local channel where it is blindingly obvious to the user if there is a MitM attack taking place. (E.g., it's obvious if someone sticks a piece of paper with a QR code on it in front of your phone, which is also displaying a QR code.) A *one-way local channel*. Again, QR codes are the best example: They only support data transmission in one direction. (So you can't conveniently conduct an authenticated-key-exchange -- AKE -- with them.) I'll assume that if a non-user-auditable local channel is used, something like an SAS protocol (see infra) is used to conduct a local AKE to prevent MitM attacks. ## Solutions to the multi-device problem ### Don't bother This is TextSecure's current solution, AFAIK. This is both an unacceptable user experience, and needlessly compromises security: A user needs to bootstrap each trust relationship (and suffers the possibility of being MitMed) with every new device they use. #### Minimal option? An idea for a minimal option for deniable messaging services: Synchronize the known public keys of other users from device0 to device1 using a key derived from both a network channel and a local channel. Send the public key of device1 to device0; have device0 then send that public key to all recipients that have a current stored axolotl state. (I've thought about this only a very little; so this may well be a horrible idea.) ### Synchronize a single private keypair A typical example is Whiteout.io: Encrypt the private keypair under a strong symmetric key. In order to enroll a new device, device0 displays a QR code containing the symmetric key for device1 to scan. device1 then authenticates to the server and downloads the encrypted private key blob. See [Tankred Hase's discussion on this list][wio_keysync] and Whiteout.io's [Github repos][wio] for more details. #### The good parts Really simple. #### The bad parts **Prone to bad implementations.** The implementation described by Whiteout.io on this list is characteristic: - Encrypted private keys are stored on non-US servers[^nonus] - The QR code *is* the symmetric key, so that anyone with <256 pixels on the screen[^qraont] **Devices are indistinguishable.** It is impossible to cryptographically distinguish the different devices enrolled for an account.[^ind_and_tor] Several consequences ensue: 1. Anyone who obtains the private key from any device can impersonate the user. If messages aren't signed, they can (usually) carry out KCI attacks against the account. (So this is completely unsuitable for strongly deniable messaging designs...) 2. It isn't possible to revoke (untrust) a single device. In order to distrust one device, the user has to, e.g., sign a message with their long-term recovery key. [^nonus]: So, e.g., the NSA has the encrypted key blobs, and can distribute them to any member of its "community" with essentially no legal limitations under current caselaw. And: If a user displays a QR code in a public place, it is possible that, under current law, they have no right to privacy in that QR code. (So, think: airports, train stations, near federal buildings, or anywhere vast numbers of 4k video cameras might soon be deployed.) [^ind_and_tor]: This could be useful if you are building a system that uses Tor exclusively, but pretty much useless otherwise. (Pond's "multi-device" solution is essentially this: Synchronize the password- protected state file to a new device. If devices take locks on the file, this is safe.) [^qraont]: QR codes should only be as legible as is needed for them to work reliably. And 32-byte QR codes are way too legible. This is easily fixed by using an All-or-Nothing-Transform to expand the key material. (512 bytes seems quite feasible for most devices.) Question: Does anyone do this already? ### Separate signing keys, shared encryption key Device0 is already enrolled. Device1 generates a new signing key. Device0 and device1 authenticate a network AKE using a local channel, and derive a shared secret from both the local channel's shared secret and the network AKE. Device0 sends the private asymmetric encryption key to device1 encrypted under the shared secret. The devices (in no particular order) use the shared secret to authenticate each other's keys, cross-sign them, and upload them to the keyserver. #### The good parts *All devices can decrypt all messages.* It isn't possible for an adversary to, e.g., target malware to a specific device by encrypting only to that device. *Key compromise can be attributed to a device.* If all messages are signed, a user can distinguish which of a set of devices associated with an account has been compromised. (They then may be able to use, e.g., a password change and a message from a trusted device to revoke the compromised device's signing key, without having to resort to using -- and exposing to possible compromise -- their long-term recovery key.) #### The bad parts *The still-trusted devices may not have any key-material to exchange a new symmetric encryption key.* Since they have independent signing keys, they can, of course, do key-exchanges to share the new private encryption key. But this adds a lot of complexity to a little-used code-path. (This occurs only when removing the corrupted device makes the device enrollment graph disconnected.) *All devices can decrypt all messages.* It's impossible for an account to designate some devices as more trustworthy than others. ### Separate keypairs Devices authenticate each other as above -- a local channel plus a network channel -- but they just use the shared secret to authenticate each other.[^messages_at_rest] To send a mail to an account, the sender encrypts to all encryption keys (with valid signature chains) returned by the keyserver. #### The good parts *Particularly important messages can be encrypted only to the keys of particularly trustworthy devices.* Here's one possible use-case: Suppose that I don't want someone with my phone to be able to get both 2FA codes and password-reset emails for the various accounts associated with my email address. I might tell an encrypting proxy to not encrypt such mails to my phone. *Recovering from a corrupted device is simple.* Since devices don't share an encryption key, they don't all need to change their encryption keys immediately. #### The bad parts *Targeted malicious messages.* The flip side of all devices being able to decrypt all messages, as above. *Lots of keys.* N devices means N ECDH operations for the sender. N devices means N times as large of a keyset to download from the keyserver. Etc. ## Notes ### Fingerprints for manual verification of account identity The most natural equivalent to a traditional OpenPGP fingerprint in this setting would be some string derived from the recovery signing key. The best option is passkdf(salt=accountid, m=signingkey) where `passkdf` is a sequential-hard KDF. Pace Joe, preventing multitarget attacks is worthwhile. ### Short authentication strings Trevor Perrin has described a very simple SAS protocol [on this list][trevp_sas]. ZRTP uses an SAS protocol, but the full description is split among many sections [of the spec][zrtp_sas]. A trivial modification to the protocol Trevor has described can be used to increase the difficulty of mounting a successful attack: "Stretched" simple SAS: A = a*G B = b*G A->B: H(A) A<-B: B A->B: A K = H(a*b*G) SAS = passkdf(salt=A||B, m=K) (This same modification is applicable to more intricate SAS protocols.) But I dislike SAS protocols when used over the internet: It is rare that user agents take appropriate measures to detect (and take appropriate countermeasures to) attacks. [trevp_sas]: https://moderncrypto.org/mail-archive/messaging/2014/000036.html "Trevor Perrin. Short auth strings. Email to [email protected]. 2014-01-31T09:24-08. (See infra for a slightly better approach.)" [zrtp_sas]: http://tools.ietf.org/html/rfc6189#section-7 "RFC 6189 - ZRTP, section 7: Short Authentication String" [wio]: https://github.com/whiteout-io [wio_keysync]: https://moderncrypto.org/mail-archive/messaging/2014/000521.html "Tankred Hase. Whiteout secure PGP key sync. Email to [email protected], 2014-07-11T03:02-07" _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
