Implementing End-to-End Encryption in Matrix clients

The libolm library

End-to-end encryption in Matrix is based on the Olm and Megolm cryptographic ratchets. The recommended starting point for any client authors is with the libolm library, which contains implementations of all of the cryptographic primitives required. The library itself is written in C/C++, but is architected in a way which makes it easy to write wrappers for higher-level languages.

Devices

We have a particular meaning for “device”. As a user, I might have several devices (a desktop client, some web browsers, an Android device, an iPhone, etc). When I first use a client, it should register itself as a new device. If I log out and log in again as a different user, the client must register as a new device. Critically, the client must create a new set of keys (see below) for each “device”.

The longevity of devices will depend on the client. In the web client, we create a new device every single time you log in. In a mobile client, it might be acceptable to reuse the device if a login session expires, provided the user is the same. Never share keys between different users.

Devices are identified by their device_id (which is unique within the scope of a given user). By default, the /login and /register endpoints will auto-generate a device_id and return it in the response; a client is also free to generate its own device_id or, as above, reuse a device, in which case the client should pass the device_id in the request body.

The lifetime of devices and access_tokens are closely related. In the simple case where a new device is created each time you log in, there is a one-to-one mapping between a device_id and an access_token. If a client reuses a device_id when logging in, there will be several access_tokens associated with a given device_id - but still, we would expect only one of these to be active at once (though we do not currently enforce that in Synapse).

Keys used in End-to-End encryption

There are a number of keys involved in encrypted communication: a summary of them follows.

Creating and registering device keys

This process only happens once, when a device first starts.

It must create the Ed25519 fingerprint key pair and the Curve25519 identity key pair. This is done by calling olm_create_account in libolm. The (base64-encoded) keys are retrieved by calling olm_account_identity_keys. The account should be stored for future use.

It should then publish these keys to the homeserver. To do this, it should construct a JSON object as follows:

{
  "algorithms": ["m.olm.v1.curve25519-aes-sha2", "m.megolm.v1.aes-sha2"],
  "device_id": "<device_id>",
  "keys": {
    "curve25519:<device_id>": "<curve25519_key>",
    "ed25519:<device_id>": "<ed25519_key>"
  },
  "user_id: <user_id>"
}

The object should be formatted as Canonical JSON, then signed with olm_account_sign; the signature should be added to the JSON as signatures.<user_id>.ed25519:<device_id>.

The signed JSON is then uploaded via POST /_matrix/client/unstable/keys/upload.

Creating and registering one-time keys

At first start, and at regular intervals thereafter[1], the client should check how many one-time keys the homeserver has stored for it, and, if necessary, generate and upload some more.

The number of one-time keys currently stored is returned by POST /_matrix/client/unstable/keys/upload. (Post an empty JSON object {} if you don’t want to upload the device keys.)

The maximum number of active keys supported by libolm is returned by olm_account_max_number_of_one_time_keys. The client should try to maintain about half this number on the homeserver.

To generate new one-time keys:

• Call olm_account_generate_one_time_keys to generate new keys.

• Call olm_account_one_time_keys to retrieve the unpublished keys. This returns a JSON-formatted object with the single property curve25519, which is itself an object mapping key id to base64-encoded Curve25519 key. For example:

  {
    "curve25519": {
      "AAAAAA": "wo76WcYtb0Vk/pBOdmduiGJ0wIEjW4IBMbbQn7aSnTo",
      "AAAAAB": "LRvjo46L1X2vx69sS9QNFD29HWulxrmW11Up5AfAjgU"
    }
  }
  

• Each key should be signed with the account key. To do this:

  • Construct a JSON object as follows:

    {
      "key": "<curve25519_key>"
    }
    

  • Call olm_account_sign to calculate the signature.

  • Add the signature should be added to the JSON as signatures.<user_id>.ed25519:<device_id>.

  • The complete key object should now look like:

    {
      "key": "wo76WcYtb0Vk/pBOdmduiGJ0wIEjW4IBMbbQn7aSnTo",
      "signatures": {
        "@alice:example.com": {
          "ed25519:JLAFKJWSCS": "dSO80A01XiigH3uBiDVx/EjzaoycHcjq9lfQX0uWsqxl2giMIiSPR8a4d291W1ihKJL/a+myXS367WT6NAIcBA"
        }
      }
    }
    

• Aggregate all the signed one-time keys into a single JSON object as follows:

  {
    "one_time_keys": {
      "signed_curve25519:<key_id>": {
        "key": "<curve25519_key>",
        "signatures": {
          "<user_id>": {
            "ed25519:<device_id>": "<signature>"
          }
        }
      },
      "signed_curve25519:<key_id>": {
        ...
      },
      ...
    }
  }
  

• Upload the object via POST /_matrix/client/unstable/keys/upload.

• Call olm_account_mark_keys_as_published to tell the olm library not to return the same keys from a future call to olm_account_one_time_keys.

Configuring a room to use encryption

To enable encryption in a room, a client should send a state event of type m.room.encryption, and content { "algorithm": "m.megolm.v1.aes-sha2" }.

Handling an m.room.encryption state event

When a client receives an m.room.encryption event as above, it should set a flag to indicate that messages sent in the room should be encrypted.

This flag should not be cleared if a later m.room.encryption event changes the configuration. This is to avoid a situation where a MITM can simply ask participants to disable encryption. In short: once encryption is enabled in a room, it can never be disabled.

The event should contain an algorithm property which defines which encryption algorithm should be used for encryption. Currently only m.megolm.v1-aes-sha2 is permitted here.

The event may also include other settings for how messages sent in the room should be encrypted (for example, rotation_period_ms to define how often the session should be replaced).

Handling an m.room.encrypted event

Encrypted events have a type of m.room.encrypted. They have a content property algorithm which gives the encryption algorithm in use, as well as other properties specific to the algorithm [2].

The encrypted payload is a JSON object with the properties type (giving the decrypted event type), and content (giving the decrypted content). Depending on the algorithm in use, the payload may contain additional keys.

There are currently two defined algorithms:

Handling an m.room_key event

These events contain key data to allow decryption of other messages. They are sent to specific devices, so they appear in the to_device section of the response to GET /_matrix/client/r0/sync. They will also be encrypted, so will need decrypting as above before they can be seen. (These events are generated by other clients - see starting a megolm session).

The event content will contain an 'algorithm' property, indicating the encryption algorithm the key data is to be used for. Currently, this will always be m.megolm.v1.aes-sha2.

Room key events for Megolm will also have room_id, session_id, and session_key keys. They are used to establish a Megolm session. The room_id identifies which room the session will be used in. The room_id, together with the sender_key of the room_key event before it was decrypted, and the session_id, uniquely identify a Megolm session. If they do not represent a known session, the client should start a new inbound Megolm session by calling olm_init_inbound_group_session with the session_key.

The client should remember the value of the keys property of the payload of the encrypted m.room_key event and store it with the inbound session. This is used as above when marking the event as verified.

Downloading the device list for users in the room

Before an encrypted message can be sent, it is necessary to retrieve the list of devices for each user in the room. This can be done proactively, or deferred until the first message is sent. The information is also required to allow users to verify or block devices.

The client should build a JSON query object as follows:

{
  "device_keys": {
    "<user_id>": {},
    [...]
  }
}

Each member in the room should be included in the query. This is then sent via POST /_matrix/client/unstable/keys/query.

The result includes, for each listed user id, a map from device ID to an object containing information on the device, as follows:

{
  "algorithms": [...],
  "device_id": "<device_id>",
  "keys": {
    "curve25519:<device_id>": "<curve25519_key>",
    "ed25519:<device_id>": "<ed25519_key>"
  },
  "signatures": {
    "<userId>": {
      "ed25519:<device_id>": "<signature>"
    },
  },
  "unsigned": {
    "device_display_name": "<display name>"
  },
  "user_id: <user_id>"
}

The client should first check the signature on this object. To do this, it should remove the signatures and unsigned properties, format the remainder as Canonical JSON, and pass the result into olm_ed25519_verify, using the Ed25519 key for the key parameter, and the corresponding signature for the signature parameter. If the signature check fails, no further processing should be done on the device.

The client must also check that the user_id and device_id fields in the object match those in the top-level map [4].

The client should check if the user_id/device_id correspond to a device it had seen previously. If it did, the client must check that the Ed25519 key hasn't changed. Again, if it has changed, no further processing should be done on the device.

Otherwise the client stores the information about this device.

Sending an encrypted event

When sending a message in a room configured to use encryption, a client first checks to see if it has an active outbound Megolm session. If not, it first creates one as per below. If an outbound session exists, it should check if it is time to rotate it, and create a new one if so.

The client then builds an encryption payload as follows:

{
  "type": "<event type>",
  "content": "<event content>",
  "room_id": "<id of destination room>"
}

and calls olm_group_encrypt to encrypt the payload. This is then packaged into event content as follows:

{
  "algorithm": "m.megolm.v1.aes-sha2",
  "sender_key": "<our curve25519 device key>",
  "ciphertext": "<encrypted payload>",
  "session_id": "<outbound group session id>",
  "device_id": "<our device ID>"
}

Finally, the encrypted event is sent to the room with POST /_matrix/client/r0/rooms/<room_id>/send/m.room.encrypted/<txn_id>.

{
  "<user id>": {
    "<device_id>": "signed_curve25519",
    ...
  },
  ...
}

{
  "one_time_keys": {
    "<user id>": {
      "<device_id>": {
        "signed_curve25519:<key_id>": {
          "key": "<curve25519_key>",
          "signatures": {
            "<user_id>": {
              "ed25519:<device_id>": "<signature>"
            }
          }
        },
      },
      ...
    },
    ...
  }
}

Handling membership changes

The client should monitor rooms which are configured to use encryption for membership changes.

When a member leaves a room, the client should invalidate any active outbound Megolm session, to ensure that a new session is used next time the user sends a message.

When a new member joins a room, the client should first download the device list for the new member, if it doesn't already have it.

After giving the user an opportunity to block any suspicious devices, the client should share the keys for the outbound Megolm session with all the new member's devices. This is done in the same way as creating a new session, except that there is no need to start a new Megolm session: due to the design of the Megolm ratchet, the new user will only be able to decrypt messages starting from the current state. The recommended method is to maintain a list of members who are waiting for the session keys, and share them when the user next sends a message.

Sending New Device announcements

When a user logs in on a new device, it is necessary to make sure that other devices in any rooms with encryption enabled are aware of the new device. This is done as follows.

Once the initial call to the /sync API completes, the client should iterate through each room where encryption is enabled. For each user (including the client's own user), it should build a content object as follows:

{
  "device_id": "<our device ID>",
  "rooms": ["<shared room id 1>", "<room id 2>", ... ]
}

Once all of these have been constructed, they should be sent to all of the relevant user's devices (using the wildcard * in place of the device_id) via PUT /_matrix/client/unstable/sendToDevice/m.new_device/<txnId>.

Handling an m.new_device event

As with m.room_key events, these will appear in the to_device section of the /sync response.

The client should download the device list of the sender, to get the details of the new device.

The event content will contain a rooms property, as well as the device_id of the new device. For each room in the list, the client should check if encryption is enabled, and if the sender of the event is a member of that room. If so, the client should share the keys for the outbound Megolm session with the new device, in the same way as handling a new user in the room.

Blocking / Verifying devices

It should be possible for a user to mark each device belonging to another user as 'Blocked' or 'Verified'.

When a user chooses to block a device, this means that no further encrypted messages should be shared with that device. In short, it should be excluded when sharing room keys when starting a new Megolm session. Any active outbound Megolm sessions whose keys have been shared with the device should also be invalidated so that no further messages are sent over them.

Verifying a device involves ensuring that the device belongs to the claimed user. Currently this must be done by showing the user the Ed25519 fingerprint key for the device, and prompting the user to verify out-of-band that it matches the key shown on the other user's device.