January 23, 2015

Multi-end to multi-end encryption


It’s a week until the XMPP Summit in Brussels, which I won’t be able to attend. How­ever, I do have some thoughts about two of the subjects that are on the agenda that I wanted to share.

Carbons/MAM and e2e-encryption seem to be moving in two completely opposite directions: MAM wants to store messages server-side, while e2e protocols like OTR want to ensure those stored messages are useless. But I don’t think they’d have to be mutually exclusive. I think it would be possible to find a solution that unifies the two concepts.

Background

Many chat services nowadays offer synchronizing the most recent messages between all devices. Given the choice between something that is more secure and something that does synchronize, I fear many people will choose the convenience of synchronization.

So far, everything that I’ve looked at fails on at least one of the following:

  1. History synchronization.
  2. e2e-encrypted one-to-one chats.
  3. Forward-secrecy.

With Carbons/MAM you get 1, but if you turn on OTR, you only get 2 and 3. I could go into detail about a number of other services, but the bottom line is: nothing currently offers all 3. Yet I still think it is possible to make a protocol that does. TextSecure does seem to be working on it, but as far as I know, it’s not possible yet.

Goals

Lets make it a little bit more clear what it is that I think we should aim to achieve:

  1. History synchronization: Every message I receive should go to every device I have. Every message I send should also become visible on every other device I have. When a device has been offline (for a reasonable amount of time), it should receive all the messages I sent and received since it went offline (up to some practical limit).
  2. Messages I send should be e2e-encrypted over every path they take (to each device of the recipient, to each other device I have).
  3. The encryption should be forward-secret: obtaining any long-term private key should not allow the decryption of past messages. Of course we will have to compromise on forward-secrecy a bit, as devices that are offline should still be able to decrypt messages when they come back online. This means whatever is stored to that device’s disk is enough to decrypt all incoming messages while it was offline. However, the stored data should only allow decryption of as few as possible other messages.

I prefer an easy to use over a maximally secure solution: I want users with no idea of what e2e encryption is or why they would want it to be using this opportunistically, without being bothered by it. There are enough ways to achieve good security for people who know what they’re doing, I want to give a (lower) level of security to everyone. For example, manually copying a private key to all your devices is not an acceptable solution. Of course this means the server can tamper with the encrypted chats, but I’d rather have a protocol where the server needs to actively tamper with communications than something where the server can quietly log everything.

Proposal

The following is just an incomplete suggestion of how this could be implemented:

  • I use Axolotl (the TextSecure protocol) to set up sessions between every device I have and every device the recipient of my message has, and among every pair of my own devices.
  • When encrypting a message, the message is first encrypted and authenticated using new, random keys. Then, for every device that should be able to decrypt it, I add an encrypted header that encrypts the keys I’ve just generated. The header also contains the extra data needed for Axolotl (for example, to update the ratchet).
  • The (normal) Carbons extension will make sure this message is delivered to everyone that can decrypt it.
  • Storing messages in MAM is fine and requires no changes to MAM, a device that was offline and comes back online can decrypt all new messages as it saved its Axolotl keys.
  • Even if the MAM archive expires messages after a number of days/weeks/etc. this can still work. Axolotl can detect and recover from missing messages.
  • This does need something that publishes the list of devices someone has, with their public keys (and maybe some “pre-keys”, as TextSecure has). I think PEP could work here, but I haven’t checked.

Some fake FAQs

Why Axolotl, and not OTR?

Axolotl handles sending messages to offline devices better and the cryptographic primitives used are more modern.

Why not draft-miller-xmpp-e2e?

  • Forward-secrecy is completely unspecified by the current version of the draft.
  • There are no “sessions”, messages are encrypted individually. So, there is no protection against an attacker dropping some of the messages.

Conclusion

Of course this is still far from a concrete specification, but I am convinced it is possible to do. Instead of half the XMPP world working on history synchronization and the other half working on breaking that, lets look for a unified solution.