MLS meets Matrix

Hubert Chathi <@hubert:uhoreg.ca>

In this talk

What is MLS? Why is it better? How does it work?
How can MLS be done over Matrix? What challenges are there?
How would MLS interact with other things? (SSSS, cross-signing, etc)

What is MLS?

Messaging Layer Security
Upcoming IETF standard for end-to-end encryption in messaging systems
Designed for group messaging, rather than 1-1 messaging
- faster with large groups
- knows about group membership
Many different contributors, has been analyzed by several people, subject of academic research
Multiple implementations (in progress)

High-level overview of MLS

For more detailed explanation, see https://www.youtube.com/watch?v=xOMUG__uEjc
Group members (devices) have public keys stored in the leaves of a binary tree
Internal nodes have public keys too, or are "blank"
- Descendants know the private keys, or are marked as "unmerged"
- Members can update their key and the keys for the nodes between
  their leaf and the root
Root node is never "blank"

Tree gets updated — add/remove members, update keys, etc.
add InitKey of new members to tree, send Welcome messages to new members
Send Commit message to room, which can be decrypted by current members (but not members who were removed)
Changing the tree creates a new "epoch"

Private key at root (along previous initialization secret and pre-shared key) are used to derive several other secrets
- encryption keys
- initialization secret
- and others...

A big problem with MLS and Matrix

MLS assumes that we have a linear sequence of epochs
Matrix doesn't give a linear sequence of events

Decentralised MLS

Add a layer on top of MLS
Allow epochs to fork, but keep track of who created them
When a new epoch is created, pick one to be the "base", make it agree with room membership, and merge in changes from other epochs, using normal MLS operations
Only needs some extra bookkeeping information
Outlined at https://gitlab.matrix.org/matrix-org/mls-ts/-/blob/decentralised2/decentralised.org

How to do MLS over Matrix

MLS defines (binary) encoding for messages/objects 🡒 base64-encode and wrap in JSON object
MLS identity: combination of user ID and device ID e.g. userId|deviceId
InitKey (your leaf node when you are first added to the tree) 🡒 one-time keys
- MLS even proposes using the equivalent to olm fallback keys

Welcome message 🡒 sent as a to-device event

e.g. type: org.matrix.msc2883.mls.v0.welcome

{
  "welcome": <base64-encoded MLS welcome message>,
  "resolves": [ <array of epochs that the commit resolves> ]
}

or possibly type: m.room.encrypted with an algorithm indicating it's a welcome message

MLS messages sent as room messages

type: m.room.encrypted

{
  "algorithm": <MLS_ALGORITHM>,
  "ciphertext": <base64-encoded MLS-encrypted message>,
  "epoch_creator": [<userId>, <deviceId>],
  "resolves": [ <array of epochs that the commits resolves -- if this is a commit> ]
}

Open questions

MLS assumes you see all commit messages, and can decrypt them in order
- Matrix gives you the most recent messages, and allows you to backfill
- How do you retrieve old commits to decrypt the latest ones?
Some parts of MLS have not been investigated yet (PSK, ReInit, external commits...)

What about other parts E2EE?

verification/cross-signing
key backup/forwarding/re-sharing
SSSS

Verification/cross-signing

MLS can use ed25519 keys, so we could just reuse the existing device keys

{
  "user_id": <userId>,
  "device_id": <deviceId>,
  "algorithms": [ <MLS_ALGORITHM> ],
  "keys": {
    ["ed25519:${this.deviceId}"]: <base64 ed25519 key>
  }
}

or add another ed25519 key

verification would not be affected much -- device keys (cross-)signed in same way, verification methods assert the public keys
Or MLS could use ed448 keys -- should we switch to that for
cross-signing keys?

Key backup/forwarding/re-sharing

Need to determine the minimal information to keep about each epoch
Do we back up our private keys too, or just the shared secrets?
Need to be able to handle multiple algorithms/versions (e.g. a Megolm backup and an MLS backup)
How do we determine which is the "better" key?

SSSS

Shouldn't be affected directly by MLS

Conclusion

MLS (modified) in Matrix works!
needs to be reviewed for security
needs to be updated to the latest draft (and eventually, the standard)
needs more work on a lot of details, but most of the hard parts are done
needs good MLS implementation(s) to use

MLS meets Matrix Hubert Chathi <@hubert:uhoreg.ca>