2.1. Overview
Asynchronous key agreement protocols like X3DH enable one party to create a message encryption session and use that session to encrypt an initial message to a recipient, even if the recipient is offline [1]. The recipient can later retrieve the message and use it to calculate a matching session which is used to decrypt the message.
Ratcheting algorithms like the Double Ratchet allow these two parties to update session keys as they communicate, for forward secrecy [2].
Combining these algorithms in a practical context introduces some new concerns:
Alice and Bob might each have several devices, so encrypting a message from Alice to Bob might require creating sessions from Alice's sending device to all of Bob's devices, and also to Alice's other devices (so they receive a copy of the message).
Alice and Bob might add and remove devices, so they will have to add and delete sessions to handle these changes.
Alice and Bob might simultaneously initiate a new session with each other, so that two new sessions are created. For the Double Ratchet to be maximally effective Alice and Bob must send and receive messages using matching sessions, so somehow they must agree on which matching sessions to use.
Alice might choose to erase her device's session state, or restore from a backup, thus causing either her or Bob to possess orphaned sessions which no longer match one of the other party's sessions.
Any solutions to the above must consider that messages might be lost or arrive out-of-order, that clock synchronization is not reliable, and that attackers might compromise devices and/or interfere with communication.
The Sesame algorithm manages the creation, deletion, and use of sessions to support these requirements. A central idea is for each device to keep track of an "active" session for each other device it is communicating with, and use the active session when sending to that device. When a message is received on an "inactive" session, that becomes the new active session. By this process each device converges on using a single session for each remote device it communicates with.
2.2. Assumptions
Sesame is based on the following assumptions:
Server
- There is a server which stores the current record of all users and devices.
- The server temporarily stores the messages that devices send to each other, until the messages are fetched.
Users
- At any point in time there is a set of users.
- Users might be added or deleted at any time.
- Each user has a UserID (e.g. a username or phone number).
- After a user is deleted, its UserID can be taken by a new user.
Devices
- At any point in time each user has a nonempty set of devices.
- Users can add or delete devices at any time.
- Each device has a DeviceID which is unique for the UserID.
- Devices can ask the server for information about other users and devices.
- Devices can maintain state, but at any point in time this state might be deleted in whole or part (e.g. by hardware failure or a user action), or rolled back to an earlier state (e.g. by restoring a backup).
- Devices have clocks that can measure elapsed time, but are not synchronized.
Mailboxes
- The server stores a mailbox for each device.
- A mailbox holds a set of messages that were sent to the device.
- Messages are removed from the mailbox when fetched.
- Devices can send messages to other devices' mailboxes. The server stores the sending device's UserID and DeviceID alongside the message.
- Devices can fetch messages from their own mailbox. The recipient device fetches the message and the sender's UserID and DeviceID from the server.
- Messages sent to a mailbox are unreliable in normal operation - they may be corrupted, deleted, reordered, delayed, or duplicated before arriving at the mailbox.
- In normal operation, a message that hasn't arrived at a mailbox within some time interval (MAXLATENCY) has been lost.
- Messages sent to a mailbox might be subject to adversary actions - an attacker (including the server) might corrupt, delete, reorder, duplicate, or forge messages before they arrive at the mailbox.
Sessions
- Messages can be encrypted and decrypted using a session, which is some secret data stored by a device.
- Decrypting a message might fail (e.g. if the ciphertext has been tampered with or forged, and thus fails an authentication check).
- An encrypted message can only be decrypted using a matching session.
- There is some SessionID which uniquely identifies each session.
- A session might contain different data after encrypting or decrypting a message (e.g. keys might be deleted after they are used, for forward secrecy).
Session creation for senders
- Each device has an identity key pair consisting of a public key and private key.
- A device can create a new initiating session at any time.
- Creating an initiating session requires specifying the identity public key for the intended recipient device which will receive the matching session.
- Creating a new session might fail (e.g. the sending device may have to fetch and cryptographically authenticate parameters associated with the recipient device, such as prekeys [1]).
Session creation for recipients
- All messages encrypted by an initiating session are initiation messages.
- All initiation messages contain the sending device's identity public key in an unencrypted header.
- Upon receiving an initiation message, the intended recipient device can create a matching session which is used to decrypt the initiation message.
- Creating a matching session may fail (e.g. if cryptographic authentication of the initiation message fails).
- Upon decrypting a message for the first time, an initiating session becomes a regular (non-initiating) session, and thus stops producing initiation messages.