Define how the AKE should behave in a multi-device environment

[juniorz]

Problem

The OTR AKE (SPAWN) requires the initiator to store prekeys in order to "verif[y] that g^i is a prekey that [the initiator has] previously sent and remains unused"[1]. An responder could send AKE messages to a different device than where the AKE was initiated.

The problem affects both the interactive and the non-interactive setting, because the network model does not specify any restriction regarding multi-device environments.

Background:

OTRv3 solves the multi-device problem using instance tags. Every message is sent with a number that identifies the sender device ID and the receiver device ID. Each device will ignore received messages containing a instance tag that does not match the device ID.

In the XMPP context, a user can be logged in to the same account on multiple devices - which poses the following problems to its implementation:

Problem Scenarios

Alice has multiple devices A1 and A2 that can be independently online/offline.

1. Alice generates pre-keys on device A1, but the reply is received on device A2 only. If she is logged in on device A2 (and device A1 is offline), for example.
   1. If device A2 does not support OTRv4, Alice will see a OTRv4 message (unreadable by humans) and she will never receive the encrypted data message on A1. This is not solved by OTRv3, and may not be solvable by us unless we use a XMPP-specific approach.
   2. If device A2 supports OTRv4, the AKE will fail (it wont be able to verify g^i is a pre-key). This is solvable by using instance tags only, but this couples the pre-key with OTRv4 in the sense we need to store pre-keys together with instance tags. This would associate all pre-keys generated on the same device (revealing this information). Note that TextSecure does a similar thing by sending prekeys "within a JSON structure consisting of a keyID z, a prekey g^xa,i , and the long-term key g^a"[1]. Note A1 is still not able to receive the message which is just lost. This is an existing issue in OTRv3 and seems to be fixed by OMEMO in a XMPP-specific way.
2. Alice generates pre-keys on device A1, and the reply is received on both devices.
   1. If device A2 does not support OTRv4, Alice will see a OTRv4 message (unreadable by humans) on A2 but she will be able to finish the AKE on A1 and will see the encrypted data. This is not solved by OTRv3, and may not be solvable by us unless we use a XMPP-specific approach.
   2. If device A2 supports OTRv4, the AKE will fail on A2 (it wont be able to verify g^i is a pre-key) but will succeed on A1. This can also be solved by using instance tags: A1 will succeed and A2 will ignore the message (because it has a different instance tag).
3. Alice generates pre-keys on device A1, and the reply is received on A1 only (even if A2 is online). There is no problem to solve here.
4. Alice generates pre-keys on device A1, and the reply is received on A2 only (even if A1 is online). SAME AS case (1).

   Solutions Specific to XMPP:

The same problem happens on the interactive setting, because the way XMPP clients send responses in a multi-device environment is implementation specific (you can't control if the other client will reply using a JID that includes a resource identifier)[2].

For the interactive setting we could recommend XMPP clients to reply AKE messages using a "full JID", and for the non-interactive we would need to associate the ¨full JID¨ to the pre-key.

With this solution, conversations would be restricted to a single device.

1 - See: "How Secure is TextSecure?". 2 - https://stackoverflow.com/questions/5048092/xmpp-receive-messages-sent-to-different-resource

[juniorz]

How other protocols approach this:

1. Facebook Messenger Secret Conversations limits an encrypted conversation to only one device
2. OMEMO shares pre-keys across all registered devices

[juniorz]

We believe this issue is done but we need to write this into the spec.