RFC 9420
The Messaging Layer Security (MLS) Protocol
RFC 9420 ๐ The Messaging Layer Security (MLS) Protocol
okay bestie, this is the MLS protocol doc, and it's giving group chat security done RIGHT ๐ฅ It's an IETF Standards Track document, dated July 2023, with ISSN 2070-1721. The authors are R. Barnes (Cisco), B. Beurdouche (Inria & Mozilla), R. Robert (Phoenix R&D), J. Millican (Meta Platforms), E. Omara, and K. Cohn-Gordon (University of Oxford) ๐
The title block doesn't have an "Obsoletes" or "Updates" line, so this doc doesn't list any RFCs it replaces or changes ๐ง
Abstract โจ
so messaging apps are getting really into end-to-end security, which means only the people actually talking can read the messages, not the servers passing them along ๐ The tricky part is group chats, where more than two clients need to agree on a key but aren't always online at the same time ๐ญ This doc specifies a key establishment protocol that gives efficient asynchronous group key establishment with forward secrecy (FS) and post-compromise security (PCS) for groups from two all the way up to thousands of members ๐
Status of This Memo ๐
this is an Internet Standards Track document ๐
it's a product of the Internet Engineering Task Force (IETF) and it represents the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG) ๐ซถ If you want more on Internet Standards, check Section 2 of RFC 7841 ๐ฆ
for the current status, any errata, and how to send feedback, go to https://www.rfc-editor.org/info/rfc9420 ๐
Copyright Notice ๐ธ
Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved. ๐
this doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as of the publication date. Please actually read those, bestie, because they explain your rights and restrictions for this doc ๐ Any Code Components pulled out of this doc must include the Revised BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as the Revised BSD License describes โญ
Table of Contents ๐ง
1. Introduction
2. Terminology
2.1. Presentation Language
2.1.1. Optional Value
2.1.2. Variable-Size Vector Length Headers
3. Protocol Overview
3.1. Cryptographic State and Evolution
3.2. Example Protocol Execution
3.3. External Joins
3.4. Relationships between Epochs
4. Ratchet Tree Concepts
4.1. Ratchet Tree Terminology
4.1.1. Ratchet Tree Nodes
4.1.2. Paths through a Ratchet Tree
4.2. Views of a Ratchet Tree
5. Cryptographic Objects
5.1. Cipher Suites
5.1.1. Public Keys
5.1.2. Signing
5.1.3. Public Key Encryption
5.2. Hash-Based Identifiers
5.3. Credentials
5.3.1. Credential Validation
5.3.2. Credential Expiry and Revocation
5.3.3. Uniquely Identifying Clients
6. Message Framing
6.1. Content Authentication
6.2. Encoding and Decoding a Public Message
6.3. Encoding and Decoding a Private Message
6.3.1. Content Encryption
6.3.2. Sender Data Encryption
7. Ratchet Tree Operations
7.1. Parent Node Contents
7.2. Leaf Node Contents
7.3. Leaf Node Validation
7.4. Ratchet Tree Evolution
7.5. Synchronizing Views of the Tree
7.6. Update Paths
7.7. Adding and Removing Leaves
7.8. Tree Hashes
7.9. Parent Hashes
7.9.1. Using Parent Hashes
7.9.2. Verifying Parent Hashes
8. Key Schedule
8.1. Group Context
8.2. Transcript Hashes
8.3. External Initialization
8.4. Pre-Shared Keys
8.5. Exporters
8.6. Resumption PSK
8.7. Epoch Authenticators
9. Secret Tree
9.1. Encryption Keys
9.2. Deletion Schedule
10. Key Packages
10.1. KeyPackage Validation
11. Group Creation
11.1. Required Capabilities
11.2. Reinitialization
11.3. Subgroup Branching
12. Group Evolution
12.1. Proposals
12.1.1. Add
12.1.2. Update
12.1.3. Remove
12.1.4. PreSharedKey
12.1.5. ReInit
12.1.6. ExternalInit
12.1.7. GroupContextExtensions
12.1.8. External Proposals
12.2. Proposal List Validation
12.3. Applying a Proposal List
12.4. Commit
12.4.1. Creating a Commit
12.4.2. Processing a Commit
12.4.3. Adding Members to the Group
13. Extensibility
13.1. Additional Cipher Suites
13.2. Proposals
13.3. Credential Extensibility
13.4. Extensions
13.5. GREASE
14. Sequencing of State Changes
15. Application Messages
15.1. Padding
15.2. Restrictions
15.3. Delayed and Reordered Application Messages
16. Security Considerations
16.1. Transport Security
16.2. Confidentiality of Group Secrets
16.3. Confidentiality of Sender Data
16.4. Confidentiality of Group Metadata
16.4.1. GroupID, Epoch, and Message Frequency
16.4.2. Group Extensions
16.4.3. Group Membership
16.5. Authentication
16.6. Forward Secrecy and Post-Compromise Security
16.7. Uniqueness of Ratchet Tree Key Pairs
16.8. KeyPackage Reuse
16.9. Delivery Service Compromise
16.10. Authentication Service Compromise
16.11. Additional Policy Enforcement
16.12. Group Fragmentation by Malicious Insiders
17. IANA Considerations
17.1. MLS Cipher Suites
17.2. MLS Wire Formats
17.3. MLS Extension Types
17.4. MLS Proposal Types
17.5. MLS Credential Types
17.6. MLS Signature Labels
17.7. MLS Public Key Encryption Labels
17.8. MLS Exporter Labels
17.9. MLS Designated Expert Pool
17.10. The "message/mls" Media Type
18. References
18.1. Normative References
18.2. Informative References
Appendix A. Protocol Origins of Example Trees
Appendix B. Evolution of Parent Hashes
Appendix C. Array-Based Trees
Appendix D. Link-Based Trees
Contributors
Authors' Addresses1. Introduction ๐ท
okay so picture a group of users who want to send each other encrypted messages. They need a way to derive shared symmetric encryption keys, and honestly this problem is super well studied for two parties ๐ง The Double Ratchet is the main solution everyone uses, as described in [DoubleRatchet] [Signal] โจ Channels built on the Double Ratchet get fine-grained forward secrecy AND post-compromise security, and they're still efficient enough for heavy use over low-bandwidth networks ๐
now for a group of more than two, the usual move is to pass out symmetric "sender keys" over existing 1:1 secure channels. Then each member encrypts their messages to the group using their own sender key ๐ซถ This is a big upgrade over sending every message pairwise, and it gives forward secrecy too (with a hash ratchet added on top) ๐ฆ BUT, and this is a big but ๐ญ, getting post-compromise security with sender keys is hard. You need a number of key update messages that scales as the square of the group size. Also, an adversary who learns a sender key can often indefinitely and passively eavesdrop on that member's messages. Generating and distributing a fresh sender key does give a form of post-compromise security for that sender, but it needs computation and communication resources that scale linearly with the size of the group ๐
so in this doc, we describe a protocol built on tree structures that gives asynchronous group keying with forward secrecy and post-compromise security ๐ณ It's based on earlier work on "asynchronous ratcheting trees" [ART]. The protocol uses an asynchronous key-encapsulation mechanism for tree structures, which lets the members of the group derive and update shared keys with costs that scale as the log of the group size ๐ That's the whole glow-up, bestie โจ
Part 1 of 30 ๐ more parts coming, so stay tuned!
2. Terminology โจ
Okay bestie, first things first: some of these capitalised words are secretly rules ๐ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" are read the BCP 14 [RFC2119] [RFC8174] way, but ONLY when they show up in all caps like this. Lowercase is just normal chatting ๐ซถ
Now the vocab list, because we need to be on the same page ๐ง
- Client: An agent that uses this protocol to establish shared cryptographic state with other clients. A client is defined by the cryptographic keys it holds ๐
- Group: A group is a logical collection of clients that share a common secret value at any given time. Its state is a linear sequence of epochs, where each epoch depends on the one before it ๐
- Epoch: A state of a group in which a specific set of authenticated clients hold shared cryptographic state ๐
- Member: A client that's included in the shared state of a group, and so has access to the group's secrets ๐
- Key Package: A signed object describing a client's identity and capabilities. It includes a hybrid public key encryption (HPKE) [RFC9180] public key that can be used to encrypt to that client. Other clients can use a client's KeyPackage to introduce them to a new group ๐
- Group Context: An object that summarises the shared, public state of the group. It's usually distributed in a signed GroupInfo message, which is handed to new members to help them join a group ๐ฆ
- Signature Key: A signing key pair used to authenticate the sender of a message โจ
- Proposal: A message that proposes a change to the group, like adding or removing a member ๐ธ
- Commit: A message that puts into effect the changes proposed in a set of Proposals ๐
- PublicMessage: An MLS protocol message that is signed by its sender and authenticated as coming from a member of the group in a particular epoch, but it is not encrypted ๐
- PrivateMessage: An MLS protocol message that is signed by its sender, authenticated as coming from a member of the group in a particular epoch, and encrypted so that only the members of the group in that epoch can read it ๐
- Handshake Message: A PublicMessage or PrivateMessage carrying an MLS Proposal or Commit object, as opposed to application data ๐ค
- Application Message: A PrivateMessage carrying application data ๐
Terminology specific to tree computations is described in Section 4.1 ๐ณ
Quick word on secrets: symmetric values get called "keys" or "secrets" interchangeably, and either way they are a value that MUST be kept confidential to a client ๐คซ When we label individual values, "secret" means a value used to derive further secret values, and "key" means a value used with an algorithm like Hashed Message Authentication Code (HMAC) or an Authenticated Encryption with Associated Data (AEAD) algorithm ๐ง
The PublicMessage and PrivateMessage formats are defined in Section 6. Security notions like forward secrecy and post-compromise security are defined in Section 16 ๐ก๏ธ
As detailed in Section 13.5, MLS uses the "Generate Random Extensions And Sustain Extensibility" (GREASE) approach to keep things extensible. Senders insert random values into fields where receivers are required to ignore unknown values, which is a vibe-check for future-proofing ๐ Specific "GREASE values" for this purpose are registered in the appropriate IANA registries ๐
2.1. Presentation Language
We use the TLS presentation language [RFC8446] to describe the structure of protocol messages ๐ On top of the base syntax, we add two extra features: fields can be optional, and vectors can have variable-size length headers. Iconic upgrades ๐
2.1.1. Optional Value
An optional value is encoded with a presence-signaling octet, followed by the value itself if it's present. When decoding, a presence octet with a value other than 0 or 1 MUST be rejected as malformed ๐ โโ๏ธ
struct {
uint8 present;
select (present) {
case 0: struct{};
case 1: T value;
};
} optional<T>;2.1.2. Variable-Size Vector Length Headers
In the TLS presentation language, vectors are encoded as a sequence of encoded elements, prefixed with a length. The length field has a fixed size, set by specifying the minimum and maximum lengths of the encoded sequence of elements ๐
In MLS, lots of vectors vary over huge ranges, so a fixed-size length field just won't cut it ๐ญ Instead we use a variable-size length, based on the variable-length integer encoding from Section 16 of [RFC9000]. The only difference is that this one requires a minimum-size encoding. Instead of min and max values, the vector description just includes a V. For example:
struct {
uint32 fixed<0..255>;
opaque variable<V>;
} StructWithVectors;A vector like that can hold values from 0 bytes all the way up to 2^30 bytes ๐ The variable-length integer encoding uses the two most significant bits of the first byte to encode the base 2 logarithm of the integer encoding length in bytes. The integer value goes in the remaining bits, so the whole value is in network byte order ๐ง The encoded value MUST use the smallest number of bits required to represent the value. When decoding, values using more bits than necessary MUST be treated as malformed ๐ซ
So integers get encoded in 1, 2, or 4 bytes, and they can hold 6-, 14-, or 30-bit values, respectively ๐
+========+=========+=============+=======+============+
| Prefix | Length | Usable Bits | Min | Max |
+========+=========+=============+=======+============+
| 00 | 1 | 6 | 0 | 63 |
+--------+---------+-------------+-------+------------+
| 01 | 2 | 14 | 64 | 16383 |
+--------+---------+-------------+-------+------------+
| 10 | 4 | 30 | 16384 | 1073741823 |
+--------+---------+-------------+-------+------------+
| 11 | invalid | - | - | - |
+--------+---------+-------------+-------+------------+Table 1: Summary of Integer Encodings ๐
Vectors that start with the prefix "11" are invalid and MUST be rejected. No exceptions, no vibes-based parsing ๐ โโ๏ธ
Some examples, so you can see it in action ๐
- The four-byte length value
0x9d7f3e7ddecodes to494878333. ๐ - The two-byte length value
0x7bbddecodes to15293. ๐ฆ - The single-byte length value
0x25decodes to37. ๐ธ
The following figure adapts the pseudocode provided in [RFC9000] to add a check for minimum-length encoding ๐
ReadVarint(data):
// The length of variable-length integers is encoded in the
// first two bits of the first byte.
v = data.next_byte()
prefix = v >> 6
if prefix == 3:
raise Exception('invalid variable length integer prefix')
length = 1 << prefix
// Once the length is known, remove these bits and read any
// remaining bytes.
v = v & 0x3f
repeat length-1 times:
v = (v << 8) + data.next_byte()
// Check if the value would fit in half the provided length.
if prefix >= 1 && v < (1 << (8*(length/2) - 2)):
raise Exception('minimum encoding was not used')
return vUsing variable-size integers for vector lengths means vectors can grow really, really big, up to 2^30 bytes ๐ Implementations should take care not to let vectors overflow the storage that's available ๐งฏ To make interop bugs easier to debug, implementations SHOULD provide a clear error when such an overflow condition occurs. Future-you will thank present-you ๐ซถ
Big vectors are a big deal. Overflow without a clear error is the kind of plot twist nobody wants ๐
3. Protocol Overview ๐ธ
MLS is designed to operate in the context described in [MLS-ARCH] ๐บ๏ธ In particular, we assume that the following services are provided:
- An Authentication Service (AS) that lets group members authenticate the credentials presented by other group members ๐ชช
- A Delivery Service (DS) that routes MLS messages among the participants in the protocol ๐ฌ
MLS assumes a trusted AS but a largely untrusted DS. Section 16.10 describes the impact of compromise or misbehavior of an AS. MLS is designed to protect the confidentiality and integrity of the group data even if the DS gets compromised. In general, the DS is only expected to reliably deliver messages, so it's basically the mail carrier ๐ฎ Section 16.9 describes the impact of compromise or misbehavior of a DS.
The core functionality of MLS is continuous group authenticated key exchange (AKE) ๐ Like other authenticated key exchange protocols (such as TLS), the participants agree on a common secret value, and each participant can verify the identity of the other participants ๐ช That secret can then protect messages sent from one participant in the group to the others, using the MLS framing layer, or it can be exported for use with other protocols ๐ฆ MLS provides group AKE in the sense that there can be more than two participants, and continuous group AKE in the sense that the set of participants can change over time ๐
The core organising principles of MLS are groups and epochs ๐ A group represents a logical collection of clients that share a common secret value at any given time. The history of a group is divided into a linear sequence of epochs. In each epoch, a set of authenticated members agree on an epoch secret that is known only to the members of the group in that epoch ๐คซ The set of members can change from one epoch to the next, and MLS makes sure that only the members in the current epoch have access to the epoch secret ๐ From the epoch secret, members derive further shared secrets for message encryption, group membership authentication, and so on ๐ง
The creator of an MLS group creates the group's first epoch unilaterally, with no protocol interactions ๐ฑ After that, the members advance their shared cryptographic state from one epoch to another by exchanging MLS messages ๐
- A KeyPackage object describes a client's capabilities and provides keys that can be used to add the client to a group ๐๏ธ
- A Proposal message proposes a change to be made in the next epoch, such as adding or removing a member โ๏ธ
- A Commit message starts a new epoch by telling the members of the group to implement a collection of proposals ๐
- A Welcome message gives a new member the information they need to initialise their state for the epoch in which they were added, or in which they want to add themselves to the group ๐
KeyPackage and Welcome messages are used to start a group or introduce new members, so they get exchanged between group members and clients who aren't in the group yet ๐ซ A client publishes a KeyPackage via the DS, which lets other clients add it to groups ๐ฃ When a group member wants to add a new member, they use the new member's KeyPackage to add them, and then construct a Welcome message so the new member can set up their local state ๐
Proposal and Commit messages are sent from one member of a group to the others. MLS provides a common framing layer for sending messages within a group. A PublicMessage gives sender authentication for unencrypted Proposal and Commit messages ๐ A PrivateMessage gives encryption and authentication for both Proposal and Commit messages, as well as any application data ๐ Main character energy, honestly ๐โจ
3.1. Cryptographic State and Evolution ๐
okay so the cryptographic state at the heart of MLS is split into three areas of responsibility, and honestly it's giving organized ๐
.- ... -.
| |
| | |
| | | Key Schedule
| V |
| epoch_secret |
. | | | .
|\ Ratchet | | | Secret /|
| \ Tree | | | Tree / |
| \ | | | / |
| \ | V | / |
| +--> commit_secret --> epoch_secret --> encryption_secret -->+ |
| / | | | \ |
| / | | | \ |
| / | | | \ |
|/ | | | \|
' | V | '
| epoch_secret |
| | |
| | |
| V |
| |
'- ... -'Figure 1: Overview of MLS Group Evolution โจ
- A ratchet tree ๐ณ that represents the membership of the group. It gives group members a way to authenticate each other and to efficiently encrypt messages to subsets of the group. Each epoch has a distinct ratchet tree, and it seeds the key schedule.
- A key schedule ๐๏ธ that describes the chain of key derivations used to move from epoch to epoch (mainly using the init_secret and epoch_secret), plus the derivation of a bunch of other secrets (see Table 4). For example:
- An encryption secret that is used to initialize the secret tree for the epoch. ๐
- An exporter secret that lets other protocols use MLS as a generic authenticated group key exchange. ๐ฆ
- A resumption secret that members can use to prove they're in the group, e.g., when creating a subgroup or a successor group. ๐
- A secret tree ๐ธ derived from the key schedule. It represents the shared secrets the group members use for encrypting and authenticating messages. Each epoch has a distinct secret tree.
Every member keeps a partial view of these components of the group's state. MLS messages are what set up those views and keep everyone synced as the group hops between epochs. bestie, that's the whole vibe ๐ซถ
Each new epoch kicks off with a Commit message ๐. The Commit tells existing members to update their view of the ratchet tree by applying a set of Proposals, and it uses the updated ratchet tree to hand out fresh entropy to the group. That fresh entropy goes only to members in the new epoch, not to anyone who's been removed. So Commits keep the property that the epoch secret stays confidential to the members of the current epoch. iconic behaviour, no notes ๐
For every Commit that adds one or more members, there are one or more matching Welcome messages ๐ง. Each Welcome gives the new members what they need to set up their views of the key schedule and ratchet tree, so their views line up with the ones the other members hold in this epoch. ngl this is the glue holding the whole thing together ๐
3.2. Example Protocol Execution โจ
okay bestie, let's talk about the three big moves in a group's life ๐ฆ there are only three: adding a member (a current member starts it), updating the keys that represent a member in the tree, and removing a member ๐
each of these gets "proposed" by sending a message of the matching type (Add / Update / Remove). but the group's state doesn't actually change until a Commit message shows up to bring in fresh entropy ๐ so a proposal is kinda like a vibe check, and the Commit is the moment it becomes real ๐
in these examples, every proposal gets committed right away ๐ธ in fancier real deployments, an app might collect a bunch of proposals and commit them all at once ๐ง also, the diagrams show Proposal and Commit messages directly, but in real life they'd be wrapped up in a PublicMessage or PrivateMessage object ๐ฆ
before a group even exists, clients publish their KeyPackages to a directory run by the DS (see Figure 2) ๐
Delivery Service
|
.--------' '--------.
| |
Group
A B C Directory Channel
| | | | |
| KeyPackageA | | | |
+------------------------------------------------->| |
| | | | |
| | KeyPackageB | | |
| +-------------------------------->| |
| | | | |
| | | KeyPackageC | |
| | +--------------->| |
| | | | |
Figure 2: Clients A, B, and C publish KeyPackages to the directorynow Figure 3 is the glow-up ๐ say client A wants a group with B and C. A starts out with a group state that's just itself, then downloads KeyPackages for B and C. For each member, A makes an Add proposal plus a Commit to add that person, and broadcasts both to the group ๐ข A also makes a Welcome message and sends it straight to the new member (no need to send it to the whole group, bestie ๐). And here's the important part: A only updates its own state to show the new member after its Commit comes back from the Delivery Service ๐ฅ
once A has updated, the new member has processed the Welcome, and everyone else has processed the Commit, they'll all have matching views of the group state ๐ซถ that includes a group secret that only the members of the group know โจ the new member can read and send new messages to the group, but anything sent before they joined stays hidden from them ๐
Group
A B C Directory Channel
| | | | |
| KeyPackageB, KeyPackageC | |
|<-------------------------------------------+ |
| | | | |
| | | | Add(A->AB) |
| | | | Commit(Add) |
+--------------------------------------------------------------->|
| | | | |
| Welcome(B) | | | |
+------------->| | | |
| | | | |
| | | | Add(A->AB) |
| | | | Commit(Add) |
|<---------------------------------------------------------------+
| | | | |
| | | | |
| | | | Add(AB->ABC) |
| | | | Commit(Add) |
+--------------------------------------------------------------->|
| | | | |
| | Welcome(C) | | |
+---------------------------->| | |
| | | | |
| | | | Add(AB->ABC) |
| | | | Commit(Add) |
|<---------------------------------------------------------------+
| |<------------------------------------------------+
| | | | |
Figure 3: Client A creates a group with clients B and Cadding more people later works the exact same way ๐ฆ any member can grab a KeyPackage for a new client, broadcast the Add and Commit that everyone else uses to update their state, and send a Welcome so the newcomer can set up and join ๐
now for the security glow-up ๐ to keep forward secrecy and post-compromise security going, each member regularly refreshes the keys that represent them to the group โจ you can do that by sending a Commit (even one with no proposals!) or by sending an Update that another member commits for you (see Figure 4) ๐ once the others have processed these messages, the group's secrets become unknown to an attacker who had compromised the secrets for the sender's leaf in the tree ๐ญ by the end of Figure 4, the group has post-compromise security with respect to both A and B ๐
- Update messages SHOULD be sent at regular intervals of time as long as the group is active, and members that don't update SHOULD eventually be removed from the group.
the app gets to decide how much time goes between Updates โฐ the whole point is to shrink a compromise window, so the right rhythm is usually hours or days, not milliseconds ๐ for example, an app could send an Update each time a member sends an application message after receiving a message from someone else, or once a day if nobody's chatting ๐ธ
the MLS architecture recommends running MLS over a secure transport (see Section 7.1 of [MLS-ARCH]) ๐ those transports usually handle stuff like congestion control, which keeps an MLS app from hogging the network and wrecking everyone else's apps ๐ so apps should be careful not to send MLS messages at a rate that causes trouble like network congestion, especially if they're not using that recommended transport (for example, sending MLS straight over UDP instead) ๐
Group
A B ... Z Directory Channel
| | | | |
| | Update(B) | | |
| +------------------------------------------->|
| | | | Update(B) |
|<----------------------------------------------------------+
| |<-------------------------------------------+
| | |<----------------------------+
| | | | |
| Commit(Upd) | | | |
+---------------------------------------------------------->|
| | | | Commit(Upd) |
|<----------------------------------------------------------+
| |<-------------------------------------------+
| | |<----------------------------+
| | | | |
Figure 4: Client B proposes to update its key, and client A
commits the proposalremoving someone works in a similar way, as Figure 5 shows ๐ซ any member can send a Remove proposal followed by a Commit ๐ the Commit brings new entropy to everyone except the person being removed โจ that fresh entropy gets mixed into the epoch secret for the new epoch, so the removed member never learns it ๐ but heads up, this doesn't mean any member is actually allowed to kick people out ๐ groups can layer their own access control policies on top of these basic mechanisms ๐
Group
A B ... Z Directory Channel
| | | | |
| | | Remove(B) | |
| | | Commit(Rem) | |
| | +---------------------------->|
| | | | |
| | | | Remove(B) |
| | | | Commit(Rem) |
|<----------------------------------------------------------+
| |<-------------------------------------------+
| | |<----------------------------+
| | | | |
Figure 5: Client Z removes client B from the groupquick reminder: these flows are just examples, and apps can arrange messages in other ways ๐ง for instance:
- Welcome messages don't have to go straight to new joiners. They're encrypted to the new joiners, so they could be spread more widely, like if the app only had a broadcast channel for the group ๐ป
- Proposal messages don't have to go out to every member right away. They just need to be available to the committer before it generates a Commit, and to the other members before they process that Commit ๐ฌ
- The sender of a Commit doesn't necessarily have to wait for its own Commit to come back before moving its state forward. It only needs to know its Commit will be the next one the group applies, maybe based on a promise from an orchestration server ๐
3.3. External Joins ๐ฆ
okay so besides the Welcome-based flow (where existing members add someone), there's also a way to join by yourself using an "external Commit" ๐
This is useful when the existing members don't have a KeyPackage for the new person, like in an "open" group that anyone can hop into without asking permission first โจ
Figure 6 shows a typical message flow for an external join. To let a new member join this way, a member of the group (A, B) publishes a GroupInfo object. It includes the GroupContext for the group and a public key that can be used to encrypt a secret to the existing members ๐ When the new member Z wants in, they download the GroupInfo object and use it to form a Commit of a special form that adds Z to the group (as detailed in Section 12.4.3.2). The existing members process this external Commit in a similar way to a normal Commit, advancing to a new epoch where Z is now a member ๐
Group
A B Z Directory Channel
| | | | |
| GroupInfo | | | |
+------------------------------------------->| |
| | | GroupInfo | |
| | |<-------------+ |
| | | | |
| | | Commit(ExtZ) | |
| | +---------------------------->|
| | | | Commit(ExtZ) |
|<----------------------------------------------------------+
| |<-------------------------------------------+
| | |<----------------------------+
| | | | |
Figure 6: Client A publishes a GroupInfo object, and Client Z
uses it to join the group3.4. Relationships between Epochs ๐ธ
okay this one is giving time travel ๐ง A group has a single linear sequence of epochs. Groups and epochs are usually independent of each other. BUT sometimes it's super useful to link epochs together cryptographically, either inside one group or across different groups ๐ MLS derives a resumption pre-shared key (PSK) from each epoch, so entropy pulled from one epoch can be injected into a future epoch. A group member who wants to inject a PSK issues a PreSharedKey proposal (Section 12.1.4) describing the PSK to be injected. When that proposal is committed, the matching PSK gets incorporated into the key schedule as described in Section 8.4 ๐
Linking epochs this way guarantees that members entering the new epoch agree on a key if and only if they were members of the group during the epoch the resumption key was extracted from. Iconic accountability energy ๐
MLS has two ways to tie a new group to an existing one, shown in Figures 7 and 8. Reinitialization closes one group and creates a new group with the same members but different parameters ๐ Branching starts a new group with a subset of the original group's participants, and the original group isn't affected at all ๐ฟ In both cases, the new group is linked to the old group via a resumption PSK.
epoch_A_[n-1]
|
|
|<-- ReInit
|
V
epoch_A_[n] epoch_B_[0]
. |
. PSK(usage=reinit) |
.....................>|
|
V
epoch_B_[1]
Figure 7: Reinitializing a Groupepoch_A_[n] epoch_B_[0]
| |
| PSK(usage=branch) |
|....................>|
| |
V V
epoch_A_[n+1] epoch_B_[1]
Figure 8: Branching a GroupApplications can also use resumption PSKs to link epochs in other ways ๐ฆ For example, Figure 9 shows a resumption PSK from epoch n being injected into epoch n+k. This shows that the members of the group at epoch n+k were also members at epoch n, no matter what changes happened to their keys through Updates or Commits in between. Receipts secured ๐งพ
epoch_A_[n]
|
| PSK(usage=application)
|.....................
| .
| .
... ...
| .
| .
V .
epoch_A_[n+k-1] .
| .
| .
|<....................
|
V
epoch_A_[n+k]
Figure 9: Reinjecting Entropy from an Earlier Epoch4. Ratchet Tree Concepts ๐ณ
okay the big idea here is "ratchet trees" ๐ฒ MLS uses them to derive shared secrets among a group of clients. A ratchet tree is an arrangement of secrets and key pairs spread across the members of a group, set up so secrets can be updated efficiently whenever the group changes ๐
Ratchet trees let a group remove any member efficiently by encrypting new entropy to a subset of the group ๐ค A ratchet tree assigns shared keys to subgroups of the overall group. So, for example, encrypting to all but one member only takes log(N) encryptions to subtrees, instead of the N-1 encryptions you'd need to encrypt to each participant one by one (where N is the number of members in the group). Efficiency is literally the whole personality ๐
This remove operation is how MLS gets post-compromise security efficiently ๐ก๏ธ In an Update proposal or a full Commit message, an old (possibly compromised) representation of a member gets removed from the group and replaced with a freshly generated one. Fresh start, no drama ๐งผ
4.1. Ratchet Tree Terminology ๐
okay time for vocab, bestie ๐ Trees are made of nodes. A node is a leaf if it has no children. Otherwise, it's a parent. All parents in our trees have precisely two children, a left child and a right child ๐๐ A node is the root of a tree if it has no parent, and intermediate if it has both children and a parent. The descendants of a node are that node's children, plus the descendants of those children. We say a tree contains a node if that node is a descendant of the root of the tree, or if the node itself is the root. Nodes are siblings if they share the same parent ๐ฏ
A subtree of a tree is the tree given by any node (the head of the subtree) and its descendants. The size of a tree or subtree is the number of leaf nodes it contains. For a given parent node, its left subtree is the subtree with its left child as head, and its right subtree is the subtree with its right child as head ๐ณ
Every tree used in this protocol is a perfect binary tree. In other words, it's a complete balanced binary tree with 2^d leaves, all at the same depth d. This structure is unique for a given depth d ๐
There are multiple ways an implementation might represent a ratchet tree in memory ๐ง A super convenient property of left-balanced binary trees (including the complete trees used here) is that they can be represented as an array of nodes, with node relationships computed from the nodes' indices in the array. A more traditional representation based on linked node objects can also be used. Appendices C and D give some details on how to implement the tree operations MLS needs in these representations. MLS places no requirements on implementations' internal representations of ratchet trees. An implementation may use any tree representation and associated algorithms, as long as they produce correct protocol messages. Freedom of expression, but make it valid ๐ฆ
4.1.1. Ratchet Tree Nodes ๐งฉ
Each leaf node in a ratchet tree gets an index (or leaf index), starting at 0 on the left and going up to 2^d - 1 on the right (for a tree with 2^d leaves). A tree with 2^d leaves has 2^(d+1) - 1 nodes, including parent nodes ๐ค
Each node in a ratchet tree is either blank (containing no value), or it holds an HPKE public key with some associated data:
- A public key (for the HPKE scheme in use; see Section 5.1)
- A credential (only for leaf nodes; see Section 5.3)
- An ordered list of "unmerged" leaves (see Section 4.2)
- A hash of certain information about the node's parent, as of the last time the node was changed (see Section 7.9)
As described in Section 4.2, different members know different subsets of the private keys corresponding to the public keys in the nodes of the tree. The private key for a parent node is only known to members at leaf nodes that are descendants of that node. The private key for a leaf node is only known to the member at that leaf node. A leaf node is unmerged relative to one of its ancestor nodes if the member at the leaf node doesn't know the private key for that ancestor node. Secrets stay need-to-know ๐คซ
Every node, whether blank or populated, has a corresponding hash that summarizes the contents of the subtree below that node. The rules for computing these hashes are described in Section 7.8 ๐
The resolution of a node is an ordered list of non-blank nodes that together cover all non-blank descendants of that node. The resolution of the root contains the set of keys that are collectively needed to encrypt to every node in the group. The resolution of a node is basically a depth-first, left-first walk through the nearest non-blank nodes below it:
- The resolution of a non-blank node is the node itself, followed by its list of unmerged leaves, if any.
- The resolution of a blank leaf node is the empty list.
- The resolution of a blank intermediate node is the resolution of its left child concatenated with the resolution of its right child, in that order.
For example, check out this subtree, where the _ character stands for a blank node and unmerged leaves are shown in square brackets ๐
...
/
_
______|______
/ \
X[B] _
__|__ __|__
/ \ / \
_ _ Y _
/ \ / \ / \ / \
A B _ D E F _ H
0 1 2 3 4 5 6 7
Figure 10: A Tree with Blanks and Unmerged LeavesIn this tree, all of the rules above are in play โจ
- The resolution of node X is the list
[X, B]. - The resolution of leaf 2 or leaf 6 is the empty list
[]. - The resolution of the top node is the list
[X, B, Y, H].
4.1.2. Paths through a Ratchet Tree ๐ค๏ธ
okay so the direct path of a root is just an empty list ๐ because the root has no parent to climb up to. For any other node, the direct path is its parent, followed by that parent's direct path. So it's basically the whole climb up to the top, step by step โจ
The copath of a node is the node's sibling, plus the siblings of every node on its direct path, except the root ๐ฆ
The filtered direct path of a leaf node L is its direct path, but with any node removed whose child on L's copath has an empty resolution. (And keep in mind that any unmerged leaves of that copath child count toward its resolution ๐) Those removed nodes don't need their own key pairs, because encrypting to that node's key pair would be the same as encrypting to its non-copath child. Iconic efficiency, honestly ๐ญ๐ซถ
Let's look at an example tree ๐ธ Blank nodes are marked with _, and I gave them labels so we can talk about them.
W = root
|
.-----+-----.
/ \
_=U Y
| |
.-+-. .-+-.
/ \ / \
T _=V X _=Z
/ \ / \ / \ / \
A B _ _ E F G _=H
0 1 2 3 4 5 6 7
Figure 11: A Complete Tree with Five Members, with Labels for
Blank Parent NodesWith that tree, here are the direct paths, copaths, and filtered direct paths for each leaf ๐
+======+=============+=========+======================+
| Node | Direct path | Copath | Filtered Direct Path |
+======+=============+=========+======================+
| A | T, U, W | B, V, Y | T, W |
+------+-------------+---------+----------------------+
| B | T, U, W | A, V, Y | T, W |
+------+-------------+---------+----------------------+
| E | X, Y, W | F, Z, U | X, Y, W |
+------+-------------+---------+----------------------+
| F | X, Y, W | E, Z, U | X, Y, W |
+------+-------------+---------+----------------------+
| G | Z, Y, W | H, X, U | Y, W |
+------+-------------+---------+----------------------+
Table 24.2. Views of a Ratchet Tree ๐
We generally assume that every participant keeps a complete and up-to-date view of the group's public ratchet tree. That includes the public keys for all nodes and the credentials attached to the leaf nodes ๐
No participant in an MLS group knows the private key for every node in the tree ๐ Instead, each member gets assigned to a leaf, and that leaf decides which subset of private keys they know. The credential stored at that leaf is the one the member provided.
MLS keeps everyone's view of the tree in a way that maintains the tree invariant ๐
The private key for a node in the tree is known to a member of the group only if the node's subtree contains that member's leaf.
In other words, if a node isn't blank, it holds a public key. The matching private key is known only to members sitting on leaves below that node โจ
The reverse isn't true, though ๐ A member may not know the private key of an intermediate node above them. That member has an unmerged leaf at that intermediate node. Encrypting to an intermediate node means encrypting to that node's public key, plus the public keys of every unmerged leaf below it. A leaf is unmerged with regard to all of its ancestors when it's first added, because adding it doesn't give it access to the private keys of all the nodes above it. Leaves become "merged" as they receive the private keys for nodes, which is described in Section 7.4 ๐ฆ
Let's walk through an example ๐ง Say a four-member group (A, B, C, D) exists, where the node above the right two members is blank. (This is what the tree would look like if A created a group with B, C, and D.) Here's the public state of the tree, plus what each participant can see of the tree's private keys. In these diagrams, _ means a blank node, ? means an unknown private key, and pk(X) means the public key matching the private key X ๐
Public Tree
============================
pk(ABCD)
/ \
pk(AB) _
/ \ / \
pk(A) pk(B) pk(C) pk(D)
Private @ A Private @ B Private @ C Private @ D
============= ============= ============= =============
ABCD ABCD ABCD ABCD
/ \ / \ / \ / \
AB _ AB _ ? _ ? _
/ \ / \ / \ / \ / \ / \ / \ / \
A ? ? ? ? B ? ? ? ? C ? ? ? ? DNotice how the tree invariant plays out here ๐ซถ Each member only knows their own leaf. The AB private key is known only to A and B, and ABCD is known to all four members. There's also a bigger lesson: there can be "holes" on the path from a member's leaf up to the root, where the member knows the key both above and below a given node but not for that node itself. D is the example of this ๐ญ
5. Cryptographic Objects ๐
5.1. Cipher Suites ๐
Each MLS session uses a single cipher suite. That suite specifies the following primitives for group key computations:
- HPKE parameters:
- A Key Encapsulation Mechanism (KEM)
- A Key Derivation Function (KDF)
- An Authenticated Encryption with Associated Data (AEAD) encryption algorithm
- A hash algorithm
- A Message Authentication Code (MAC) algorithm
- A signature algorithm
MLS uses HPKE for public key encryption [RFC9180] ๐ The DeriveKeyPair function tied to the cipher suite's KEM maps octet strings to HPKE key pairs. Just like HPKE, MLS assumes that an AEAD algorithm produces a single ciphertext output from AEAD encryption (lining up with [RFC5116]), instead of a separate ciphertext and tag ๐ฆ
Cipher suites are represented with the CipherSuite type, and they're defined in Section 17.1 โจ
5.1.1. Public Keys ๐
HPKE public keys are opaque values in a format defined by the underlying protocol. (Check out Section 4 of [RFC9180] for more info ๐)
opaque HPKEPublicKey<V>;Signature public keys are also opaque values, just in a format defined by the cipher suite's signature scheme ๐ธ
opaque SignaturePublicKey<V>;For cipher suites using the Edwards-curve Digital Signature Algorithm (EdDSA) signature schemes (Ed25519 or Ed448), the public key is in the format specified in [RFC8032] ๐
For cipher suites using the Elliptic Curve Digital Signature Algorithm (ECDSA) with the NIST curves (P-256, P-384, or P-521), the public key is represented as an encoded UncompressedPointRepresentation struct, as defined in [RFC8446] ๐
5.1.2. Signing โ๏ธ
The signature algorithm in a group's cipher suite is the mandatory algorithm for signing messages within the group. It MUST be the same as the signature algorithm specified in the credentials in the leaves of the tree (this includes the leaf node information in KeyPackages used to add new members) ๐ซถ
The signatures in this document are encoded as specified in [RFC8446]. To be specific, ECDSA signatures are DER encoded, and EdDSA signatures are the concatenation of R and S, as specified in [RFC8032] ๐ฅ
To tell different MLS signatures apart, every signed value gets prefixed with a label, like this ๐ท๏ธ
SignWithLabel(SignatureKey, Label, Content) =
Signature.Sign(SignatureKey, SignContent)
VerifyWithLabel(VerificationKey, Label, Content, SignatureValue) =
Signature.Verify(VerificationKey, SignContent, SignatureValue)
Where SignContent is specified as:
struct {
opaque label<V>;
opaque content<V>;
} SignContent;
And its fields are set to:
label = "MLS 1.0 " + Label;
content = Content;The Signature.Sign and Signature.Verify functions are defined by the signature algorithm. If MLS extensions need signatures from group members, they should reuse the SignWithLabel construction, using a distinct label. To avoid collisions in these labels, there's an IANA registry defined in Section 17.6 ๐โจ
5.1.3. Public Key Encryption ๐
Just like with signing, MLS includes a label and context in encryption operations, so ciphertexts made for different purposes don't get mixed up ๐ Encryption and decryption with this label and context work like this ๐
EncryptWithLabel(PublicKey, Label, Context, Plaintext) =
SealBase(PublicKey, EncryptContext, "", Plaintext)
DecryptWithLabel(PrivateKey, Label, Context, KEMOutput, Ciphertext) =
OpenBase(KEMOutput, PrivateKey, EncryptContext, "", Ciphertext)
Where EncryptContext is specified as:
struct {
opaque label<V>;
opaque context<V>;
} EncryptContext;
And its fields are set to:
label = "MLS 1.0 " + Label;
context = Context;The SealBase and OpenBase functions are defined in Section 6.1 of [RFC9180] (with "Base" as the MODE), and they use the HPKE algorithms from the group's cipher suite. If MLS extensions need HPKE encryption operations, they should reuse the EncryptWithLabel construction, using a distinct label. To avoid collisions in these labels, there's an IANA registry defined in Section 17.7 ๐ง
5.2. Hash-Based Identifiers ๐งฉ
Some MLS messages refer to other MLS objects by hash ๐ For example, Welcome messages refer to the KeyPackages of the members being welcomed, and Commits refer to the Proposals they cover. These identifiers are computed like this ๐
opaque HashReference<V>;
HashReference KeyPackageRef;
HashReference ProposalRef;
MakeKeyPackageRef(value)
= RefHash("MLS 1.0 KeyPackage Reference", value)
MakeProposalRef(value)
= RefHash("MLS 1.0 Proposal Reference", value)
RefHash(label, value) = Hash(RefHashInput)
Where RefHashInput is defined as:
struct {
opaque label<V>;
opaque value<V>;
} RefHashInput;
And its fields are set to:
label = label;
value = value;For a KeyPackageRef, the value input is the encoded KeyPackage, and the cipher suite specified in the KeyPackage decides which KDF gets used. For a ProposalRef, the value input is the AuthenticatedContent carrying the Proposal. In both of those cases, the KDF is decided by the group's cipher suite ๐โจ
5.3. Credentials
okay so every member of a group shows up with a credential ๐. It's basically an ID card that gives the member one or more identities and ties them to the member's signing key โจ. The Authentication Service in use for the group is the one that verifies those identities and that signing key ๐.
It's totally up to the app which identifiers to use at the app level ๐
. For example, a certificate in an X509Credential can vouch for a bunch of domain names or email addresses in its subjectAltName extension. The app can show all of them to the user, or if it already knows the "desired" domain name or email address, it can check that the desired one is on the list ๐ฆ. Borrowing the terms from [RFC6125], a credential gives you "presented identifiers," and the app has to supply a "reference identifier" for the authenticated client, if there is one ๐.
// See the "MLS Credential Types" IANA registry for values
uint16 CredentialType;
struct {
opaque cert_data<V>;
} Certificate;
struct {
CredentialType credential_type;
select (Credential.credential_type) {
case basic:
opaque identity<V>;
case x509:
Certificate certificates<V>;
};
} Credential;A "basic" credential is just a bare assertion of an identity, with no extra info attached ๐ธ. The app decides how the encoded identity is formatted.
For an X.509 credential, each entry in the certificates field is one DER-encoded X.509 certificate ๐. The chain is ordered so that certificates[0] is the end-entity certificate. The public key in the subjectPublicKeyInfo of that end-entity certificate MUST be identical to the signature_key in the LeafNode holding this credential, no exceptions ๐
โโ๏ธ. Also, a chain MAY leave out any non-leaf certificates that supported peers are already known to have, so it's a little space-saver ๐ง.
5.3.1. Credential Validation
The app using MLS is responsible for deciding which identifiers it finds acceptable for each member in a group ๐. So following the model that [RFC6125] describes for TLS, the app keeps a list of "reference identifiers" for the members, and the credentials bring the "presented identifiers." A member gets authenticated by first checking that their credential legit represents some presented identifiers, and then making sure the member's reference identifiers are authenticated by those presented identifiers ๐.
The parts of the system doing these jobs are collectively called the Authentication Service (AS) [MLS-ARCH] ๐ก๏ธ. A member's credential is said to be validated with the AS when the AS confirms that the credential's presented identifiers are correctly tied to the signature_key field in the member's LeafNode, and that those identifiers match the member's reference identifiers ๐.
Whenever a new credential shows up in the group, it MUST be validated with the AS ๐จ. Specifically, this happens at these moments in the protocol:
- When a member receives a KeyPackage that it will use in an Add proposal to add a new member to the group
- When a member receives a GroupInfo object that it will use to join a group, either via a Welcome or via an external Commit
- When a member receives an Add proposal adding a member to the group
- When a member receives an Update proposal whose
LeafNodehas a new credential for the member - When a member receives a Commit with an
UpdatePathwhoseLeafNodehas a new credential for the committer - When an
external_sendersextension is added to the group - When an existing
external_sendersextension is updated
When a member's credential is being replaced, like in the Update and Commit cases above, the AS MUST also verify that the set of presented identifiers in the new credential is valid as a successor to the set in the old credential, according to the app's policy ๐ฆ. Main character energy for policy checks, honestly ๐ฌ.
5.3.2. Credential Expiry and Revocation
In some credential schemes, a valid credential can "expire" or become invalid after a certain point in time โฐ. For example, every X.509 certificate has a notAfter field, which is a time after which the certificate is not valid anymore ๐.
Expired credentials can cause operational problems given the validation requirements of Section 5.3.1 ๐ญ. Apps can use some operational practices and tweaks to their Authentication Service policies to soften these impacts ๐ซถ.
In general, to avoid problems like new joiners rejecting expired credentials in a group, apps that use these credentials should ensure, to the extent practical, that all of the credentials in use in a group are valid at all times โจ.
If a member finds that its credential has expired (or will soon), it should issue an Update or Commit that replaces it with a valid credential ๐. For this reason, members SHOULD accept Update proposals and Commits issued by members with expired credentials, as long as the credential in the Update or Commit is valid ๐ .
Similarly, when a client is processing messages that were sent a while ago (like when it's catching up with a group after being offline), the client SHOULD accept signatures from members with expired credentials ๐ฐ๏ธ. The credential might have been valid back when the message was sent, so it's fair game ๐.
If a member finds that another member's credential has expired, they may issue a Remove that removes that member ๐งน. For example, an app could require a member who's about to issue a Commit to check the tree for expired credentials and include Remove proposals for those members in the Commit ๐. When the group tree is known to the DS, the DS could also keep an eye on the tree for expired credentials and issue external Remove proposals ๐.
Some credential schemes also let credentials get revoked ๐ซ. Revocation is kind of like expiry in that a previously valid credential becomes invalid, so most of the stuff above also applies to revoked credentials ๐. But apps may want to treat revoked credentials differently, for example by removing members with revoked credentials while still giving members with expired credentials time to update ๐.
5.3.3. Uniquely Identifying Clients
MLS implementations will presumably give apps a way to request protocol operations on other clients (like removing clients) ๐งโโ๏ธ. Those functions need to refer to the other clients using some kind of identifier. MLS clients have a few types of identifiers, and they behave differently operationally ๐.
Inside the protocol, group members are uniquely identified by their leaf index ๐ข. BUT a leaf index is only valid for referring to members in a given epoch. In a later epoch, that same leaf index might point to a different member, or to nobody at all ๐ต.
The Credentials presented by the clients in a group authenticate application-level identifiers for those clients ๐ชช. These identifiers might not be unique, though. For example, if a user has multiple devices all in the same MLS group, those devices' clients could all present the user's application-layer identifiers ๐ฑ๐ป.
If needed, apps can add their own application-specific identifiers to the extensions field of a LeafNode object, using the application_id extension ๐ท๏ธ.
opaque application_id<V>;Okay, real talk, this part is so important ๐จ: applications MUST NOT rely on the data in an application_id extension as if the Authentication Service had authenticated it. Also, apps SHOULD gracefully handle cases where the identifier presented is not unique. Be nice to your future self and handle duplicates! ๐ซถ
6. Message Framing ๐
okay bestie, handshake messages and application messages all wear the same outfit ๐โจ That outfit is the framing structure! It gives you encryption so only the group can read the stuff inside (confidentiality ๐), plus signing so everyone knows who actually sent it ๐ซถ
In most of the protocol, messages get handled as AuthenticatedContent objects ๐ These hold the message content itself plus the info needed to prove who sent it (see Section 6.1). Then, before the message can travel over an untrusted channel, you wrap it up as a PublicMessage or PrivateMessage, which is what gets sent as an MLSMessage ๐ฆ The extra protections for that trip, group membership authentication or AEAD encryption, get added at that step. Going the other way, the receiver checks those protections (membership verification or AEAD decryption) when they unwrap a PublicMessage or PrivateMessage back into an AuthenticatedContent ๐ฆ
PrivateMessage is the signed AND encrypted one, protecting both the content and the metadata around it ๐คซ PublicMessage is only signed, not encrypted ๐ Applications MUST use PrivateMessage to encrypt application messages, and they SHOULD use PrivateMessage for handshake messages too. The exception: they MAY send handshake messages as PublicMessage objects when the Delivery Service needs to be able to look at them ๐ธ
enum {
reserved(0),
mls10(1),
(65535)
} ProtocolVersion;
enum {
reserved(0),
application(1),
proposal(2),
commit(3),
(255)
} ContentType;
enum {
reserved(0),
member(1),
external(2),
new_member_proposal(3),
new_member_commit(4),
(255)
} SenderType;
struct {
SenderType sender_type;
select (Sender.sender_type) {
case member:
uint32 leaf_index;
case external:
uint32 sender_index;
case new_member_commit:
case new_member_proposal:
struct{};
};
} Sender;
// See the "MLS Wire Formats" IANA registry for values
uint16 WireFormat;
struct {
opaque group_id<V>;
uint64 epoch;
Sender sender;
opaque authenticated_data<V>;
ContentType content_type;
select (FramedContent.content_type) {
case application:
opaque application_data<V>;
case proposal:
Proposal proposal;
case commit:
Commit commit;
};
} FramedContent;
struct {
ProtocolVersion version = mls10;
WireFormat wire_format;
select (MLSMessage.wire_format) {
case mls_public_message:
PublicMessage public_message;
case mls_private_message:
PrivateMessage private_message;
case mls_welcome:
Welcome welcome;
case mls_group_info:
GroupInfo group_info;
case mls_key_package:
KeyPackage key_package;
};
} MLSMessage;Messages from senders who aren't in the group get sent as PublicMessage ๐โโ๏ธ Check out Sections 12.1.8 and 12.4.3.2 for the full tea โ
Here's the structure that fully describes the data sent in plaintexts or ciphertexts, so no mystery bits ๐ง
struct {
WireFormat wire_format;
FramedContent content;
FramedContentAuthData auth;
} AuthenticatedContent;The figure below shows how all these structures connect to each other, plus the high-level operations that make and read them. It's giving flowchart energy ๐
Proposal Commit Application Data
| | |
+--------------+--------------+
|
V
FramedContent
| | -.
+--------+ | |
| | |
V | +-- Asymmetric
FramedContentAuthData | | Sign / Verify
| | |
+--------+ | |
| | |
V V -'
AuthenticatedContent
| -.
+--------+--------+ |
| | +-- Symmetric
V V | Protect / Unprotect
PublicMessage PrivateMessage -'
| |
| | Welcome KeyPackage GroupInfo
| | | | |
+-----------------+-----+----------+----------+
|
V
MLSMessage
Figure 12: Relationships among MLS Objects6.1. Content Authentication ๐
FramedContent gets authenticated using the FramedContentAuthData structure. Let's see what's inside ๐
struct {
ProtocolVersion version = mls10;
WireFormat wire_format;
FramedContent content;
select (FramedContentTBS.content.sender.sender_type) {
case member:
case new_member_commit:
GroupContext context;
case external:
case new_member_proposal:
struct{};
};
} FramedContentTBS;
opaque MAC<V>;
struct {
/* SignWithLabel(., "FramedContentTBS", FramedContentTBS) */
opaque signature<V>;
select (FramedContent.content_type) {
case commit:
/*
MAC(confirmation_key,
GroupContext.confirmed_transcript_hash)
*/
MAC confirmation_tag;
case application:
case proposal:
struct{};
};
} FramedContentAuthData;The signature is made with SignWithLabel, using the label "FramedContentTBS" ๐๏ธ It covers the message content AND the wire format used for that message. If the sender's sender_type is member, the signature also covers the GroupContext for the current epoch, so signatures are specific to one group and one epoch. Trรจs iconic ๐
The sender MUST use the private key that matches the signature key for their sender_type:
- member: The signature key contained in the LeafNode at the index indicated by leaf_index in the ratchet tree.
- external: The signature key at the index indicated by sender_index in the external_senders group context extension (see Section 12.1.8.1). The content_type of the message MUST be proposal and the proposal_type MUST be a value that is allowed for external senders.
- new_member_commit: The signature key in the LeafNode in the Commit's path (see Section 12.4.3.2). The content_type of the message MUST be commit.
- new_member_proposal: The signature key in the LeafNode in the KeyPackage embedded in an external Add proposal. The content_type of the message MUST be proposal and the proposal_type of the Proposal MUST be add.
Recipients of an MLSMessage MUST verify the signature using the key that matches the sender's sender_type, as described above ๐ง No skipping this step, babe!
The confirmation tag is the proof that all the members of the group ended up in the same state of the group โจ A FramedContentAuthData is called valid when both its signature and its confirmation_tag fields are valid. Main character energy for those two fields ๐
6.2. Encoding and Decoding a Public Message ๐
Messages that are authenticated but NOT encrypted get encoded using the PublicMessage structure ๐ฃ
struct {
FramedContent content;
FramedContentAuthData auth;
select (PublicMessage.content.sender.sender_type) {
case member:
MAC membership_tag;
case external:
case new_member_commit:
case new_member_proposal:
struct{};
};
} PublicMessage;The membership_tag field in a PublicMessage authenticates the sender's membership in the group ๐ชช For messages sent by members, it MUST be set to the following value:
struct {
FramedContentTBS content_tbs;
FramedContentAuthData auth;
} AuthenticatedContentTBM;
membership_tag = MAC(membership_key, AuthenticatedContentTBM)When decoding a PublicMessage into an AuthenticatedContent, the application MUST check membership_tag and MUST check that the FramedContentAuthData is valid. Double checks, no exceptions ๐
6.3. Encoding and Decoding a Private Message ๐คซ
Authenticated AND encrypted messages get encoded using the PrivateMessage structure ๐โจ
struct {
opaque group_id<V>;
uint64 epoch;
ContentType content_type;
opaque authenticated_data<V>;
opaque encrypted_sender_data<V>;
opaque ciphertext<V>;
} PrivateMessage;encrypted_sender_data and ciphertext both get encrypted with the AEAD function from the cipher suite in use ๐ The inputs are the SenderData and PrivateMessageContent structures. Lowkey the best-kept secrets in the whole protocol ๐ง
6.3.1. Content Encryption ๐
okay so first things first, the content you wanna encrypt gets wrapped up in a PrivateMessageContent struct ๐
struct {
select (PrivateMessage.content_type) {
case application:
opaque application_data<V>;
case proposal:
Proposal proposal;
case commit:
Commit commit;
};
FramedContentAuthData auth;
opaque padding[length_of_padding];
} PrivateMessageContent;so the padding ๐ซง gets set by the sender. they encode the content (via the select) and the auth field first, and then tack on however many zero bytes they picked. on the receiving end, you decode the content and the auth field out of the plaintext from PrivateMessage.ciphertext, and whatever bytes are left over? that's your padding. the padding field MUST be filled with all zero bytes. a receiver MUST verify that there are no non-zero bytes in the padding field, and if that check fails, the enclosing PrivateMessage MUST be rejected as malformed.
zero bytes only, or the whole message gets tossed as malformed ๐ โโ๏ธ
why so strict? bc it keeps the padding process deterministic, so padding can't be used as a covert channel. that's a whole vibe check ๐ต๏ธโโ๏ธ
now the key schedule ๐ in MLS, the sender makes two separate key ratchets for every member of the group: one for handshake messages and one for application messages. when encrypting, the sender looks at the ratchets they derived for their own member and picks an unused generation from either the handshake ratchet or the application ratchet, depending on the content type. that generation gets used to derive a provisional nonce and key โจ
before the nonce gets used in the encryption operation, it's XORed with a fresh random value to guard against reuse. and here's the tea: because the key schedule makes nonces deterministically, a client MUST keep persistent state about where it is in the key schedule. if that persistent state gets lost or corrupted, a client might reuse a generation that's already been used, which means reusing a key/nonce pair. yikes ๐ญ
so to avoid that disaster, the sender of a message MUST generate a fresh random four-byte "reuse guard" value and XOR it with the first four bytes of the nonce from the key schedule before using the nonce for encryption. the sender MUST include the reuse guard in the reuse_guard field of the sender data object, so the recipient can use it to compute the nonce for decryption. bestie, that's the whole trick ๐ซถ
+-+-+-+-+---------...---+
| Key Schedule Nonce |
+-+-+-+-+---------...---+
XOR
+-+-+-+-+---------...---+
| Guard | 0 |
+-+-+-+-+---------...---+
===
+-+-+-+-+---------...---+
| Encrypt/Decrypt Nonce |
+-+-+-+-+---------...---+next up, the Additional Authenticated Data (AAD) input to the encryption holds an object shaped like this, with the values used to identify the key and nonce ๐ฆ
struct {
opaque group_id<V>;
uint64 epoch;
ContentType content_type;
opaque authenticated_data<V>;
} PrivateContentAAD;when decoding a PrivateMessageContent, the application MUST check that the FramedContentAuthData is valid. no skipping that step, periodt ๐
it's up to the application to decide what authenticated_data to provide and how much padding to add to a given message (if any). and the overall size of the AAD and ciphertext MUST fit within the limits set for the group's AEAD algorithm in [CFRG-AEAD-LIMITS]. size matters, even in crypto ๐๐ธ
6.3.2. Sender Data Encryption ๐ง
the "sender data" that tells you which key to use for content encryption gets encrypted with the cipher suite's AEAD. the key and nonce come from both the sender_data_secret and a sample of the encrypted content ๐ before encryption, the sender data gets encoded like this:
struct {
uint32 leaf_index;
uint32 generation;
opaque reuse_guard[4];
} SenderData;when building a SenderData object from a Sender object, the sender MUST verify that Sender.sender_type is member, and then use Sender.leaf_index for SenderData.leaf_index. the main character here is the leaf index ๐
the reuse_guard field holds that fresh random value that helps avoid nonce reuse when state gets lost or corrupted, as described in Section 6.3.1. callback moment ๐
the key and nonce for the AEAD are computed as the KDF of the first KDF.Nh bytes of the ciphertext generated in the previous section. if the ciphertext is shorter than KDF.Nh, the whole ciphertext gets used. in pseudocode, it goes like this:
ciphertext_sample = ciphertext[0..KDF.Nh-1]
sender_data_key = ExpandWithLabel(sender_data_secret, "key",
ciphertext_sample, AEAD.Nk)
sender_data_nonce = ExpandWithLabel(sender_data_secret, "nonce",
ciphertext_sample, AEAD.Nn)the AAD for the SenderData ciphertext is the first three fields of PrivateMessage ๐
struct {
opaque group_id<V>;
uint64 epoch;
ContentType content_type;
} SenderDataAAD;when parsing a SenderData struct as part of message decryption, the recipient MUST verify that the leaf index in the leaf_index field identifies a non-blank node. no ghost leaves allowed ๐ป
7. Ratchet Tree Operations ๐ณ
okay now we're in the ratchet tree era ๐ the ratchet tree for an epoch describes the membership of a group in that epoch. it gives you the public key encryption (HPKE) keys that let you encrypt to subsets of the group, plus the info needed to authenticate the members. whenever the membership changes from one epoch to the next, the tree changes to match ๐ฆ this section walks through what's in the tree and which operations you're allowed to do on it.
7.1. Parent Node Contents ๐
remember from Section 4.1.1 that the nodes of a ratchet tree hold a few different kinds of data. leaf nodes describe individual members, and parent nodes describe subgroups of the group. parent nodes are simpler, so here's their shape:
struct {
HPKEPublicKey encryption_key;
opaque parent_hash<V>;
uint32 unmerged_leaves<V>;
} ParentNode;the encryption_key field holds an HPKE public key. its private key is only held by the members at the leaves among that node's descendants ๐ the parent_hash field holds a hash of this node's parent node, as described in Section 7.9 ๐งฉ and the unmerged_leaves field lists the leaves under this parent node that are unmerged, going by their indices among all the leaves in the tree. the entries in the unmerged_leaves vector MUST be sorted in increasing order. sorted, always, no exceptions ๐โจ
7.2. Leaf Node Contents โจ
okay so a leaf node is basically a client's whole look in the group, and it's signed by that client ๐๏ธ๐ it also does double duty inside client KeyPackage objects, where it stores everything needed to add someone to a group ๐
enum {
reserved(0),
key_package(1),
update(2),
commit(3),
(255)
} LeafNodeSource;
struct {
ProtocolVersion versions<V>;
CipherSuite cipher_suites<V>;
ExtensionType extensions<V>;
ProposalType proposals<V>;
CredentialType credentials<V>;
} Capabilities;
struct {
uint64 not_before;
uint64 not_after;
} Lifetime;
// See the "MLS Extension Types" IANA registry for values
uint16 ExtensionType;
struct {
ExtensionType extension_type;
opaque extension_data<V>;
} Extension;
struct {
HPKEPublicKey encryption_key;
SignaturePublicKey signature_key;
Credential credential;
Capabilities capabilities;
LeafNodeSource leaf_node_source;
select (LeafNode.leaf_node_source) {
case key_package:
Lifetime lifetime;
case update:
struct{};
case commit:
opaque parent_hash<V>;
};
Extension extensions<V>;
/* SignWithLabel(., "LeafNodeTBS", LeafNodeTBS) */
opaque signature<V>;
} LeafNode;
struct {
HPKEPublicKey encryption_key;
SignaturePublicKey signature_key;
Credential credential;
Capabilities capabilities;
LeafNodeSource leaf_node_source;
select (LeafNodeTBS.leaf_node_source) {
case key_package:
Lifetime lifetime;
case update:
struct{};
case commit:
opaque parent_hash<V>;
};
Extension extensions<V>;
select (LeafNodeTBS.leaf_node_source) {
case key_package:
struct{};
case update:
opaque group_id<V>;
uint32 leaf_index;
case commit:
opaque group_id<V>;
uint32 leaf_index;
};
} LeafNodeTBS;The encryption_key field holds an HPKE public key whose private key lives only with the member sitting in this leaf (or, for a LeafNode inside a KeyPackage, with whoever issued that KeyPackage) ๐ The signature_key field holds the member's public signing key โ๏ธ And the credential field carries info that authenticates both the member's identity and that signing key, see Section 5.3 ๐
The capabilities field is the client's feature menu ๐ง It lists the protocol versions, cipher suites, credential types, non-default proposal types, and non-default extension types the client supports. The following proposal and extension types count as "default" and MUST NOT be listed ๐
โโ๏ธ
- Proposal types:
0x0001 - add0x0002 - update0x0003 - remove0x0004 - psk0x0005 - reinit0x0006 - external_init0x0007 - group_context_extensions
- Extension types:
0x0001 - application_id0x0002 - ratchet_tree0x0003 - required_capabilities0x0004 - external_pub0x0005 - external_senders
There are no defaults for the other fields of a capabilities object, so the client MUST list every single value it supports for each respective parameter ๐ฏ
Any non-default extension showing up in a LeafNode's extensions field MUST also be listed in the capabilities extensions field, and the credential type the LeafNode uses MUST be in the capabilities credentials field ๐ซถ
Like Section 13 says, unknown values in capabilities MUST be ignored ๐ And whoever creates a capabilities field SHOULD toss in some random GREASE values so other clients actually learn to ignore unknown stuff ๐งช
The leaf_node_source field tells everyone how this LeafNode ended up in the tree ๐ณ It signals whether the leaf needs a lifetime or parent_hash, and whether the group_id gets added as context to the signature. These fields are included selectively, because the creator of a LeafNode can't always compute all of them. For example, a KeyPackage gets made before the client knows which group it'll be used in, so its signature can't bind to a group_id ๐ญ
When a leaf was added based on a pre-published KeyPackage, the lifetime field is the window during which clients consider the LeafNode valid โฐ These times are absolute, measured in seconds since the Unix epoch (1970-01-01T00:00:00Z). Applications MUST define a maximum total lifetime that's acceptable for a LeafNode, and reject any LeafNode whose total lifetime is longer than that duration ๐ซ To avoid disagreements about whether a LeafNode's lifetime is valid, the clients in a group SHOULD keep their time synchronized (e.g., using the Network Time Protocol [RFC5905]) โฑ๏ธ
When a leaf node got inserted into the tree via a Commit message, the parent_hash field holds the parent hash for that leaf (see Section 7.9) ๐ฟ
LeafNodeTBS covers the fields above the signature in the LeafNode. When the leaf node was created in the context of a group (the update and commit cases), the group ID gets added as context to the signature too ๐
LeafNode objects stored in the group's ratchet tree get updated as the tree evolves. Each modification of LeafNode content MUST be reflected by a change in its signature ๐ซ That lets other members verify the LeafNode's validity at any time, especially when a newcomer joins the group ๐ฏ
7.3. Leaf Node Validation ๐
The validity of a LeafNode needs to be checked at these moments ๐
- When a LeafNode is downloaded in a KeyPackage, before it is used to add the client to the group
- When a LeafNode is received by a group member in an Add, Update, or Commit message
- When a client validates a ratchet tree, e.g., when joining a group or after processing a Commit
The client runs through these steps to verify a LeafNode ๐
- Verify that the credential in the LeafNode is valid, as described in Section 5.3.1.
- Verify that the signature on the LeafNode is valid using
signature_key. - Verify that the LeafNode is compatible with the group's parameters. If the GroupContext has a
required_capabilitiesextension, then the required extensions, proposals, and credential types MUST be listed in the LeafNode'scapabilitiesfield. - Verify that the credential type is supported by all members of the group, as specified by the
capabilitiesfield of each member's LeafNode, and that thecapabilitiesfield of this LeafNode indicates support for all the credential types currently in use by other members. - Verify the
lifetimefield:- If the LeafNode appears in a message being sent by the client, e.g., a Proposal or a Commit, then the client MUST verify that the current time is within the range of the
lifetimefield. - If instead the LeafNode appears in a message being received by the client, e.g., a Proposal, a Commit, or a ratchet tree of the group the client is joining, it is RECOMMENDED that the client verifies that the current time is within the range of the
lifetimefield. (This check is not mandatory because the LeafNode might have expired in the time between when the message was sent and when it was received.)
- If the LeafNode appears in a message being sent by the client, e.g., a Proposal or a Commit, then the client MUST verify that the current time is within the range of the
- Verify that the extensions in the LeafNode are supported by checking that the ID for each extension in the
extensionsfield is listed in thecapabilities.extensionsfield of the LeafNode. - Verify the
leaf_node_sourcefield:- If the LeafNode appears in a KeyPackage, verify that
leaf_node_sourceis set tokey_package. - If the LeafNode appears in an Update proposal, verify that
leaf_node_sourceis set toupdateand thatencryption_keyrepresents a different public key than theencryption_keyin the leaf node being replaced by the Update proposal. - If the LeafNode appears in the
leaf_nodevalue of the UpdatePath in a Commit, verify thatleaf_node_sourceis set tocommit.
- If the LeafNode appears in a KeyPackage, verify that
- Verify that the following fields are unique among the members of the group:
signature_keyencryption_key
7.4. Ratchet Tree Evolution โจ
okay so whenever a member starts an epoch change (aka they commit, see Section 12.4 ๐), they may need to refresh the key pairs for their leaf and for the nodes on their leaf's direct path. that's how we keep forward secrecy and post-compromise security ๐๐
the member starting the change makes the fresh key pairs with the procedure below. it's built so group members can efficiently pass the fresh secret keys to each other, as described in Section 7.6 ๐ซถ
a member updates the nodes along its direct path like this:
- Blank all the nodes on the direct path from the leaf to the root.
- Generate a fresh HPKE key pair for the leaf.
- Generate a sequence of path secrets, one for each node on the leaf's filtered direct path, as follows. In this setting,
path_secret[0]refers to the first parent node in the filtered direct path,path_secret[1]to the second parent node, and so on.
path_secret[0] is sampled at random
path_secret[n] = DeriveSecret(path_secret[n-1], "path")- Compute the sequence of HPKE key pairs (node_priv,node_pub), one for each node on the leaf's direct path, as follows.
node_secret[n] = DeriveSecret(path_secret[n], "node")
node_priv[n], node_pub[n] = KEM.DeriveKeyPair(node_secret[n])the node secret is derived as a temporary intermediate secret so that each secret only gets used with one algorithm ๐ฆ the path secret goes into DeriveSecret, and the node secret goes into DeriveKeyPair. no mixing, no cap.
for example, say there's a group with four members, with C an unmerged leaf at Z:
Y
|
.-+-.
/ \
X Z[C]
/ \ / \
A B C D
0 1 2 3
Figure 13: A Full Tree with One Unmerged Leafif member B then generates an UpdatePath based on a secret "leaf_secret", it would generate this sequence of path secrets ๐
path_secret[1] ---> node_secret[1] -------> node_priv[1], node_pub[1]
^
|
|
path_secret[0] ---> node_secret[0] -------> node_priv[0], node_pub[0]
^
|
|
leaf_secret ------> leaf_node_secret --+--> leaf_priv, leaf_pub
| |
'-------. .-------'
|
leaf_node
Figure 14: Derivation of Ratchet Tree Keys along a Direct Pathafter applying the UpdatePath, the tree looks like this ๐
node_priv[1] --------> Y'
|
.-+-.
/ \
node_priv[0] ----> X' Z[C]
/ \ / \
A B C D
^
leaf_priv -----------+
0 1 2 3
Figure 15: Placement of Keys in a Ratchet Tree7.5. Synchronizing Views of the Tree
after generating fresh key material and applying it to their local tree state (as described in Section 7.4 ๐), the generator broadcasts the update to the other members in a Commit message. everyone applies it to keep their local views of the tree in sync with the sender's โจ more specifically, when a member commits a change to the tree (like adding or removing someone), they send an UpdatePath containing a set of public keys and encrypted path secrets for the intermediate nodes in the filtered direct path of their leaf. the other members use these values to update their view of the tree, lining up their copy with the sender's ๐ง
an UpdatePath contains the following info for each node in the filtered direct path of the sender's leaf, including the root:
- The public key for the node
- One or more encrypted copies of the path secret corresponding to the node
the path secret for a given node gets encrypted to the subtree rooted at the parent's non-updated child, aka the child on the copath of the sender's leaf node. there's one encryption of the path secret to each public key in the resolution of the non-updated child ๐
a member of the group updates their direct path by computing new values for their leaf node and the nodes along their filtered direct path, like so:
- Blank all nodes along the direct path of the sender's leaf.
- Compute updated path secrets and public keys for the nodes on the sender's filtered direct path.
- Generate a sequence of path secrets of the same length as the filtered direct path, as defined in Section 7.4.
- For each node in the filtered direct path, replace the node's public key with the node_pub[n] value derived from the corresponding path secret path_secret[n].
- Compute the new parent hashes for the nodes along the filtered direct path and the sender's leaf node.
- Update the leaf node for the sender.
- Set the leaf_node_source to commit.
- Set the encryption_key to the public key of a freshly sampled key pair.
- Set the parent hash to the parent hash for the leaf.
- Re-sign the leaf node with its new contents.
since the new leaf node basically updates an existing leaf node in the group, it MUST adhere to the same restrictions as LeafNodes used in Update proposals (aside from leaf_node_source). the application MAY specify other changes to the leaf node, like providing a new signature key, updated capabilities, or different extensions ๐
then the member encrypts path secrets to the group. for each node in the member's filtered direct path, they do the following:
- Compute the resolution of the node's child that is on the copath of the sender (the child that is not in the direct path of the sender). Any new member (from an Add proposal) added in the same Commit MUST be excluded from this resolution.
- For each node in the resolution, encrypt the path secret for the direct path node using the public key of the resolution node, as defined in Section 7.6 ๐ฅ
the recipient of an UpdatePath does the matching steps. first, the recipient merges UpdatePath into the tree:
- Blank all nodes on the direct path of the sender's leaf.
- For all nodes on the filtered direct path of the sender's leaf:
- Set the public key to the public key in the UpdatePath.
- Set the list of unmerged leaves to the empty list.
- Compute parent hashes for the nodes in the sender's filtered direct path, and verify that the parent_hash field of the leaf node matches the parent hash for the first node in its filtered direct path.
- Note that these hashes are computed from root to leaf, so that each hash incorporates all the non-blank nodes above it. The root node always has a zero-length hash for its parent hash.
second, the recipient decrypts the path secrets:
- Identify a node in the filtered direct path for which the recipient is in the subtree of the non-updated child.
- Identify a node in the resolution of the copath node for which the recipient has a private key.
- Decrypt the path secret for the parent of the copath node using the private key from the resolution node.
- Derive path secrets for ancestors of that node in the sender's filtered direct path using the algorithm described above.
- Derive the node secrets and node key pairs from the path secrets.
- Verify that the derived public keys are the same as the corresponding public keys sent in the UpdatePath.
- Store the derived private keys in the corresponding ratchet tree nodes.
for example, to pass along the example update from Section 7.4, the member at node B would send these values ๐
+=============+====================================================+
| Public Key | Ciphertext(s) |
+=============+====================================================+
| node_pub[1] | E(pk(Z), path_secret[1]), E(pk(C), path_secret[1]) |
+-------------+----------------------------------------------------+
| node_pub[0] | E(pk(A), path_secret[0]) |
+-------------+----------------------------------------------------+
Table 3in this table, node_pub[i] is the public key derived from node_secret[i], pk(X) is the current public key of node X, and E(K, S) is the public key encryption of the path secret S to the public key K (using HPKE) ๐ฆ
a recipient at node A decrypts E(pk(A), path_secret[0]) to get path_secret[0], then uses it to derive path_secret[1] and the resulting node secrets and key pairs. so A ends up with the private keys to nodes X' and Y', matching the tree invariant ๐ง
a recipient at node D decrypts E(pk(Z), path_secret[1]) to get path_secret[1], then uses it to derive the node secret and key pair for node Y'. and yes, as the tree invariant requires, node D does not get the private key for X', since X' isn't an ancestor of D ๐
after processing the update, each recipient MUST delete outdated key material, specifically: - The path secrets and node secrets used to derive each updated node key pair. - Each outdated node key pair that was replaced by the update.
7.6. Update Paths ๐
as described in Section 12.4, each Commit message may optionally contain an UpdatePath, with a new LeafNode and a set of parent nodes for the sender's filtered direct path. for each parent node, the UpdatePath has a new public key and an encrypted path secret. the parent nodes stay in the same order as the filtered direct path ๐ธ
struct {
opaque kem_output<V>;
opaque ciphertext<V>;
} HPKECiphertext;
struct {
HPKEPublicKey encryption_key;
HPKECiphertext encrypted_path_secret<V>;
} UpdatePathNode;
struct {
LeafNode leaf_node;
UpdatePathNode nodes<V>;
} UpdatePath;for each UpdatePathNode, the resolution of the corresponding copath node MUST exclude all new leaf nodes added as part of the current Commit. the length of the encrypted_path_secret vector MUST be equal to the length of the resolution of the copath node (excluding new leaf nodes), with each ciphertext being the encryption to the respective resolution node ๐
the HPKECiphertext values get encrypted and decrypted like this:
(kem_output, ciphertext) =
EncryptWithLabel(node_public_key, "UpdatePathNode",
group_context, path_secret)
path_secret =
DecryptWithLabel(node_private_key, "UpdatePathNode",
group_context, kem_output, ciphertext)here node_public_key is the public key of the node the path secret is encrypted for, group_context is the provisional GroupContext object for the group, and the EncryptWithLabel function is as defined in Section 5.1.3 ๐
7.7. Adding and Removing Leaves โจ
okay so besties, the tree doesn't just update along paths ๐ณ sometimes we need to add or remove leaves too, because members join and leave the group (see Sections 12.1.1 and 12.1.3) ๐ and since the tree is always full, adding or removing leaves means the tree gets deeper or shallower, so the number of leaves doubles or halves ๐ซถ these operations are also called _extending_ and _truncating_ the tree ๐ฆ
leaves always get added and removed on the right edge of the tree ๐ when the tree needs to grow, a brand new blank root gets added, with the old tree on its left and a new all-blank subtree on its right ๐ธ this usually happens when a new member joins the group ๐ง
_ <-- new blank root _ __|__ __|__ / \ / \ X ===> X _ <-- new blank subtree ===> X _ / \ / \ / \ / \ / \ A B A B _ _ A B C _ ^
new member --+ </pre>
Figure 16: Extending the Tree to Make Room for a Third Member
Okay wait, the other way around ๐ญ when the right subtree of the tree has no non-blank nodes left, it can be safely removed ๐ the root and that right subtree get thrown out (whether or not the root is blank) ๐ the left child of the root becomes the new root, and the left subtree becomes the whole new tree ๐ this usually happens after a member gets removed from the group ๐
Y Y __|__ __|__ / \ / \ X _ ===> X _ ==> X <-- new root / \ / \ / \ / \ / \ A B C _ A B _ _ A B ^
removed member --+
Figure 17: Cleaning Up after Removing Member C
ngl the concrete algorithms for these operations on array-based and link-based trees live in Appendices C and D ๐ those algorithms are non-normative, so an implementation can use any algorithm it likes as long as it ends up with the correct tree in its internal representation ๐ iykyk ๐
7.8. Tree Hashes ๐ธ
okay so MLS hashes the tree contents in two different ways to check different properties of the tree ๐ฅ _tree hashes_ are defined right here, and _parent hashes_ get their own spot in Section 7.9 ๐ฆ
each node in a ratchet tree has a tree hash that summarizes the subtree under that node ๐ the root's tree hash is what the GroupContext uses to confirm the whole group agrees on the whole tree ๐ tree hashes get computed recursively, starting from the leaves and building up to the root ๐ซถ
P --> th(P) ^ ^ / \ / \ th(L) th(R)
Figure 18: Composition of the Tree Hash
the tree hash of a single node is the hash of that node's TreeHashInput object ๐ that object can hold either a LeafNodeHashInput or a ParentNodeHashInput, depending on what kind of node it is ๐ LeafNodeHashInput objects hold the leaf_index and the LeafNode (if there is one) ๐ง ParentNodeHashInput objects hold the ParentNode (if there is one) plus the tree hashes of the node's left and right children ๐ for both parent and leaf nodes, the optional node value MUST be absent if the node is blank, and MUST be present if the node has a value ๐จ๐
enum {
reserved(0),
leaf(1),
parent(2),
(255)
} NodeType;
struct {
NodeType node_type;
select (TreeHashInput.node_type) {
case leaf: LeafNodeHashInput leaf_node;
case parent: ParentNodeHashInput parent_node;
};
} TreeHashInput;
struct {
uint32 leaf_index;
optional<LeafNode> leaf_node;
} LeafNodeHashInput;
struct {
optional<ParentNode> parent_node;
opaque left_hash<V>;
opaque right_hash<V>;
} ParentNodeHashInput;the tree hash of a whole tree is just the tree hash of the root node ๐ and it gets computed recursively, starting at the leaves and building up ๐ซง โจ
7.9. Parent Hashes ๐
okay so while tree hashes summarize what the tree looks like at one moment in time, parent hashes capture info about how the keys in the tree got filled in ๐ฐ๏ธโจ
when a client sends a Commit to change the group, it can include an UpdatePath to assign new keys to the nodes along its filtered direct path ๐ฆ when a client computes an UpdatePath (as defined in Section 7.5), it computes and signs a parent hash that summarizes the tree after the UpdatePath has been applied ๐ these summaries get built in a chain from the root down to the member's leaf ๐ so the part of the chain closer to the root can get overwritten when nodes set by one UpdatePath are reset by a later UpdatePath ๐ธ
ph(Q)
/
/
V
P.public_key --> ph(P)
/ ^
/ \
V \
N.parent_hash th(S)Figure 19: Inputs to a Parent Hash
so the signature over the parent hash in each member's leaf basically signs the subtree that hasn't changed since that leaf was last changed in an UpdatePath ๐ซถ a new member joining the group uses these parent hashes to check that the parent nodes were set by members of the group, and NOT by some sneaky external attacker ๐ค๐ซ for an example of how this works, check out Appendix B ๐
Consider a ratchet tree with a non-blank parent node P and children D and S (for "parent", "direct path", and "sibling"), with D and P in the direct path of a leaf node L (for "leaf") ๐ง
...
/
P
__|__
/ \
D S
/ \ / \
... ... ... ...
/
LFigure 20: Nodes Involved in a Parent Hash Computation
the parent hash of P changes whenever an UpdatePath object gets applied to the ratchet tree along a path from a leaf L that goes through node D (and so also through P) ๐ the new "Parent hash of P (with copath child S)" comes from hashing P's ParentHashInput struct ๐
struct {
HPKEPublicKey encryption_key;
opaque parent_hash<V>;
opaque original_sibling_tree_hash<V>;
} ParentHashInput;the field encryption_key holds the HPKE public key of P ๐ if P is the root, the parent_hash field is set to a zero-length octet string ๐ซง otherwise, parent_hash is the parent hash of the next node after P on the filtered direct path of leaf L ๐ฆ this way, P's parent hash fixes the new HPKE public key of each non-blank node on the path from P up to the root ๐ the path from P to the root may contain some blank nodes that P's parent hash does NOT fix ๐ฌ but for every node that has an HPKE key, that key IS fixed by P's parent hash ๐โจ
last but not least, original_sibling_tree_hash is the tree hash of S in the ratchet tree after being modified like this: for each leaf L in P.unmerged_leaves, blank L and remove it from the unmerged_leaves sets of all parent nodes ๐งน
observe this, bestie: original_sibling_tree_hash does NOT change between updates of P ๐ this property is crucial for the correctness of the protocol ๐ฅ
note that original_sibling_tree_hash is the tree hash of S, not the parent hash ๐ the parent_hash field in ParentHashInput captures info about the nodes above P. the original_sibling_tree_hash captures info about the subtree under S that is not being updated (so it's the subtree that a path secret for P would be encrypted to, according to Section 7.5) ๐
for example, in the following tree:
W [F]
______|_____
/ \
U Y [F]
__|__ __|__
/ \ / \
T _ _ _
/ \ / \ / \ / \
A B C D E F G _Figure 21: A Tree Illustrating Parent Hash Computations
with P = W and S = Y, original_sibling_tree_hash is the tree hash of the following tree:
Y
__|__
/ \
_ _
/ \ / \
E _ G _because W.unmerged_leaves includes F, F gets blanked and removed from Y.unmerged_leaves ๐
note that no recomputation is needed if the tree hash of S hasn't changed since the last time P was updated ๐ that's the case when computing or processing a Commit whose UpdatePath goes through P, since the Commit itself resets P ๐ (in other words, you only need to recompute the original sibling tree hash when validating a group's tree on joining ๐ง) more generally, if none of the entries in P.unmerged_leaves are in the subtree under S (so no leaves got blanked), then the original tree hash at S is just the tree hash of S in the current tree โจ
if you do need to recompute the original tree hash of a node, you can make it faster by caching intermediate tree hashes ๐ that way you don't have to recompute the subtree every time it shows up in multiple parent hashes ๐ซถ a subtree hash can be reused as long as the intersection of the parent's unmerged leaves with the subtree is the same as in the earlier computation ๐ธ
7.9.1. Using Parent Hashes ๐ฆ
in ParentNode objects and in LeafNode objects with leaf_node_source set to commit, the parent_hash field holds the parent hash of the next non-blank parent node above the node in question (the next node in the filtered direct path) ๐ using the node labels from Figure 20, the parent_hash field of D equals the parent hash of P with copath child S ๐ง and that's true even when D is a leaf node ๐ซง
the parent_hash field of a LeafNode is signed by the member ๐ so that signature attests to which keys the group member put into the ratchet tree and to whom the matching secret keys were sent, along with the rest of the LeafNode's contents ๐ this stops malicious insiders from building fake ratchet trees with a node D whose HPKE secret key the insider knows, while the insider isn't assigned a leaf in the subtree rooted at D ๐๐ซ and honestly, a tree like that would break the tree invariant ๐๐ฅ
7.9.2. Verifying Parent Hashes ๐
Okay bestie, parent hashes get checked at two moments: when you join a group, and when a Commit gets processed. It's giving security check ๐
The parent hash in a node D is valid with respect to a parent node P if all of these criteria hold. Here C and S are the children of P (for "child" and "sibling"). C is the child that's on the direct path of D (possibly D itself), and S is the other child. โจ
Dis a descendant ofPin the tree.- The
parent_hashfield ofDis equal to the parent hash ofPwith copath childS. Dis in the resolution ofC, and the intersection ofP'sunmerged_leaveswith the subtree underCis equal to the resolution ofCwithDremoved.
These checks confirm that D and P got updated at the same time (in the same UpdatePath) ๐ซถ. They were also neighbors in the UpdatePath, because the nodes in between them would have been left out of the filtered direct path. Lowkey genius.
A parent node P is "parent-hash valid" if it can be chained back to a leaf node this way. So basically, if there's a leaf node L and a sequence of parent nodes P_1, ..., P_N where P_N = P, and every step in the chain is authenticated by a parent hash, then L's parent hash is valid with respect to P_1, P_1's parent hash is valid with respect to P_2, and so on ๐.
When joining a group, the new member MUST authenticate that each non-blank parent node P is parent-hash valid. You can do this bottom up by building chains up from the leaves and checking that every non-blank parent node is covered by exactly one of those chains. Or you can do it top down by checking that there's exactly one descendant of each non-blank parent node for which that parent node is parent-hash valid. Both work, pick your fave ๐ธ
When processing a Commit message that includes an UpdatePath, clients MUST recompute the expected value ofparent_hashfor the committer's new leaf and verify that it matches theparent_hashvalue in the suppliedleaf_node. Once the UpdatePath nodes are merged into the tree, they form a parent-hash chain from the committer's leaf all the way up to the root. Iconic chain behavior ๐
8. Key Schedule ๐
Group keys are derived using the Extract and Expand functions from the KDF for the group's cipher suite, plus the functions defined below. Let's gooo ๐ง
ExpandWithLabel(Secret, Label, Context, Length) =
KDF.Expand(Secret, KDFLabel, Length)
DeriveSecret(Secret, Label) =
ExpandWithLabel(Secret, Label, "", KDF.Nh)Where KDFLabel is specified as:
struct {
uint16 length;
opaque label<V>;
opaque context<V>;
} KDFLabel;And its fields get set like this:
length = Length;
label = "MLS 1.0 " + Label;
context = Context;The value KDF.Nh is the size of an output from KDF.Extract, in bytes. In the diagram below:
KDF.Extracttakes its salt argument from the top and its Input Keying Material (IKM) argument from the left.DeriveSecrettakes its Secret argument from the incoming arrow.0represents an all-zero byte string of lengthKDF.Nh.
When processing a handshake message, a client combines these three things to derive new epoch secrets ๐:
- The init secret from the previous epoch
- The commit secret for the current epoch
- The GroupContext object for the current epoch
Given these inputs, the derivation of secrets for an epoch goes like this ๐:
init_secret_[n-1]
|
|
V
commit_secret --> KDF.Extract
|
|
V
ExpandWithLabel(., "joiner", GroupContext_[n], KDF.Nh)
|
|
V
joiner_secret
|
|
V
psk_secret (or 0) --> KDF.Extract
|
|
+--> DeriveSecret(., "welcome")
| = welcome_secret
|
V
ExpandWithLabel(., "epoch", GroupContext_[n], KDF.Nh)
|
|
V
epoch_secret
|
|
+--> DeriveSecret(., <label>)
| = <secret>
|
V
DeriveSecret(., "init")
|
|
V
init_secret_[n]
Figure 22: The MLS Key ScheduleA bunch of values get derived from the epoch secret for different jobs ๐ฆ:
+==================+=====================+=======================+
| Label | Secret | Purpose |
+==================+=====================+=======================+
| "sender data" | sender_data_secret | Deriving keys to |
| | | encrypt sender data |
+------------------+---------------------+-----------------------+
| "encryption" | encryption_secret | Deriving message |
| | | encryption keys (via |
| | | the secret tree) |
+------------------+---------------------+-----------------------+
| "exporter" | exporter_secret | Deriving exported |
| | | secrets |
+------------------+---------------------+-----------------------+
| "external" | external_secret | Deriving the external |
| | | init key |
+------------------+---------------------+-----------------------+
| "confirm" | confirmation_key | Computing the |
| | | confirmation MAC for |
| | | an epoch |
+------------------+---------------------+-----------------------+
| "membership" | membership_key | Computing the |
| | | membership MAC for a |
| | | PublicMessage |
+------------------+---------------------+-----------------------+
| "resumption" | resumption_psk | Proving membership in |
| | | this epoch (via a PSK |
| | | injected later) |
+------------------+---------------------+-----------------------+
| "authentication" | epoch_authenticator | Confirming that two |
| | | clients have the same |
| | | view of the group |
+------------------+---------------------+-----------------------+
Table 4: Epoch-Derived SecretsThe external_secret is used to derive an HPKE key pair whose private key is held by the entire group ๐:
external_priv, external_pub = KEM.DeriveKeyPair(external_secret)The public key external_pub can be published as part of the GroupInfo struct, so non-members can join the group using an external Commit. Main character entrance energy ๐ชโจ
8.1. Group Context ๐ธ
Each member of the group keeps a GroupContext object that summarizes the state of the group:
struct {
ProtocolVersion version = mls10;
CipherSuite cipher_suite;
opaque group_id<V>;
uint64 epoch;
opaque tree_hash<V>;
opaque confirmed_transcript_hash<V>;
Extension extensions<V>;
} GroupContext;The fields in this state mean the following ๐:
- The
cipher_suiteis the cipher suite used by the group. - The
group_idfield is an application-defined identifier for the group. - The
epochfield represents the current version of the group. - The
tree_hashfield contains a commitment to the contents of the group's ratchet tree and the credentials for the group's members, as described in Section 7.8. - The
confirmed_transcript_hashfield contains a running hash over the messages that led to this state. - The
extensionsfield contains the details of any protocol extensions that apply to the group.
When a new member gets added to the group, an existing member provides them with a Welcome message. The Welcome message has all the info the new member needs to initialize its GroupContext. Hype ๐
Different changes to the group have different effects on the group state. Those effects are covered in their own subsections of Section 12.1. These general rules apply, no cap ๐ง :
- The
group_idfield is constant. - The
epochfield goes up by one for each Commit message that gets processed. - The
tree_hashgets updated to represent the current tree and credentials. - The
confirmed_transcript_hashfield gets updated with the data for an AuthenticatedContent encoding a Commit message, as described below. - The
extensionsfield changes when a GroupContextExtensions proposal gets committed.
Okay that's the key schedule and group context done, we ate and left no crumbs ๐ ๐
8.2. Transcript Hashes ๐งพโจ
okay so the transcript hashes are basically a running hash over every Proposal and Commit that's ever been sent in a group ๐ . Commits get included directly, and Proposals sneak in indirectly through the Commit that applied them ๐ฆ. Both types get hashed by way of the AuthenticatedContent object they were sent in. Iconic. ๐ธ
The transcript hash is made of two individual hashes ๐:
- A
confirmed_transcript_hashthat represents a transcript over the whole history of Commit messages, up to and including the signature of the most recent Commit. - An
interim_transcript_hashthat covers the confirmed transcript hash plus theconfirmation_tagof the most recent Commit.
New members compute the interim transcript hash using the confirmation_tag field of the GroupInfo struct, while existing members can compute it directly ๐ซถ.
Each Commit updates these hashes through its enclosing AuthenticatedContent. That struct gets split into ConfirmedTranscriptHashInput and InterimTranscriptHashInput. The first one updates the confirmed transcript hash, and the second one updates the interim transcript hash. Main character energy ๐.
struct {
WireFormat wire_format;
FramedContent content; /* with content_type == commit */
opaque signature<V>;
} ConfirmedTranscriptHashInput;
struct {
MAC confirmation_tag;
} InterimTranscriptHashInput;
confirmed_transcript_hash_[0] = ""; /* zero-length octet string */
interim_transcript_hash_[0] = ""; /* zero-length octet string */
confirmed_transcript_hash_[epoch] =
Hash(interim_transcript_hash_[epoch - 1] ||
ConfirmedTranscriptHashInput_[epoch]);
interim_transcript_hash_[epoch] =
Hash(confirmed_transcript_hash_[epoch] ||
InterimTranscriptHashInput_[epoch]);Okay so in this notation, ConfirmedTranscriptHashInput_[epoch] and InterimTranscriptHashInput_[epoch] are based on the Commit that kicked off the epoch with epoch number epoch. Lowkey confusing, but here's the tea ๐: the epoch field in that Commit gets set to epoch - 1, since it's sent inside the previous epoch ๐.
The transcript hash ConfirmedTranscriptHashInput_[epoch] is used as the confirmed_transcript_hash input to the confirmation_tag field for this Commit. So each Commit confirms the whole transcript of Commits up to that point, except for the latest Commit's confirmation tag. It's giving full-history receipts ๐งพ๐.
...
|
|
V
+-----------------+
| interim_[N-1] |
+--------+--------+
|
.--------------. +------------------+ |
| Ratchet Tree | | wire_format | |
| Key Schedule |<-------+ content | |
'-------+------' | epoch = N-1 +------------+
| | commit | |
V | signature | V
+------------------------+ +------------------+ +-----------------+
| confirmation_key_[N] +-->| confirmation_tag |<--+ confirmed_[N] |
+------------------------+ +--------+---------+ +--------+--------+
| |
| V
| +-----------------+
+------------>| interim_[N] |
+--------+--------+
|
.--------------. +------------------+ |
| Ratchet Tree | | wire_format | |
| Key Schedule |<-------+ content | |
'-------+------' | epoch = N +------------+
| | commit | |
V | signature | V
+------------------------+ +------------------+ +-----------------+
| confirmation_key_[N+1] +-->| confirmation_tag |<--+ confirmed_[N+1] |
+------------------------+ +--------+---------+ +--------+--------+
| |
| V
| +-----------------+
+------------>| interim_[N+1] |
+--------+--------+
|
V
...Figure 23: Evolution of the Transcript Hashes through Two Epoch Changes ๐ฆ
8.3. External Initialization ๐ช๐ซ
So besides starting a new epoch through those KDF invocations we already covered, an MLS group can also start a new epoch through an asymmetric interaction using the external key pair from the previous epoch ๐. This happens when a new member joins via an external commit ๐.
Here's the vibe: the joiner sends a new init_secret value to the group using the HPKE export method ๐คซ. Then the joiner uses that init_secret, along with the info from the GroupInfo and an external Commit, to set up their own copy of the key schedule for the new epoch ๐.
kem_output, context = SetupBaseS(external_pub, "")
init_secret = context.export("MLS 1.0 external init secret", KDF.Nh)Then the members of the group receive the kem_output in an ExternalInit proposal and do the matching calculation to get the init_secret value ๐.
context = SetupBaseR(kem_output, external_priv, "")
init_secret = context.export("MLS 1.0 external init secret", KDF.Nh)8.4. Pre-Shared Keys ๐๏ธ๐ท
Groups that already have an out-of-band way to generate shared group secrets can inject them into the MLS key schedule ๐ง. That brings in extra external entropy for the computation of the MLS group secrets. Super smart, honestly ๐ง โจ.
Injecting an external PSK can level up security when doing a full run of Updates across all members is too expensive ๐ธ. It also helps if the external group key establishment mechanism gives stronger security against classical or quantum adversaries ๐ก๏ธ.
ngl this part is important: a PSK might have a different lifetime than an Update, so it doesn't automatically give the same forward secrecy or post-compromise security guarantees as a Commit message ๐ญ. Unlike the key pairs put in the tree by an Update or Commit, which are always freshly generated, PSKs can be pre-distributed and stored. That means a PSK could get compromised during distribution or storage ๐. So the security the group gets from injecting a PSK depends on both the entropy of the PSK and the risk of compromise. These factors are outside the scope of this document, but application designers relying on PSKs should definitely consider them ๐.
Each PSK in MLS has a type that says how it was provisioned ๐ฆ. External PSKs are provided by the application, while resumption PSKs are derived from the MLS key schedule and used when you need to authenticate a member's participation in a prior epoch ๐ฐ๏ธ.
The injection of one or more PSKs into the key schedule is signaled in two ways. Existing members get told through PreSharedKey proposals covered by a Commit, and new members added in that Commit get told through the GroupSecrets object in the Welcome message for that Commit ๐. To make sure existing and new members compute the same PSK input to the key schedule, the Commit and GroupSecrets objects MUST indicate the same set of PSKs, in the same order ๐ .
enum {
reserved(0),
external(1),
resumption(2),
(255)
} PSKType;
enum {
reserved(0),
application(1),
reinit(2),
branch(3),
(255)
} ResumptionPSKUsage;
struct {
PSKType psktype;
select (PreSharedKeyID.psktype) {
case external:
opaque psk_id<V>;
case resumption:
ResumptionPSKUsage usage;
opaque psk_group_id<V>;
uint64 psk_epoch;
};
opaque psk_nonce<V>;
} PreSharedKeyID;Each time a client injects a PSK into a group, the psk_nonce of its PreSharedKeyID MUST be set to a fresh random value of length KDF.Nh, where KDF is the KDF for the cipher suite of the group the PSK is going into ๐ฒ. This makes sure that even when a PSK gets used multiple times, the value that goes into the key schedule is different every single time โจ.
When a receiving client gets a Commit with a PreSharedKey proposal, or a GroupSecrets object with the psks field set, it includes those PSKs in the key schedule. They go in the order listed in the Commit, or in the psks field, respectively ๐. For resumption PSKs, the PSK is defined as the resumption_psk of the group and epoch specified in the PreSharedKeyID object. Here's how psk_secret gets computed ๐งฎ:
struct {
PreSharedKeyID id;
uint16 index;
uint16 count;
} PSKLabel;
psk_extracted_[i] = KDF.Extract(0, psk_[i])
psk_input_[i] = ExpandWithLabel(psk_extracted_[i], "derived psk",
PSKLabel, KDF.Nh)
psk_secret_[0] = 0
psk_secret_[i] = KDF.Extract(psk_input_[i-1], psk_secret_[i-1])
psk_secret = psk_secret_[n]Here 0 stands for the all-zero vector of length KDF.Nh 0๏ธโฃ. The index field in PSKLabel matches the PSK's position in the psk array, and the count field holds the total number of PSKs. Basically, the PSKs get chained together with KDF.Extract invocations (labeled "Extract" in the diagram, because we're lazy like that ๐), like this:
0 0 = psk_secret_[0]
| |
V V
psk_[0] --> Extract --> ExpandWithLabel --> Extract = psk_secret_[1]
|
0 |
| |
V V
psk_[1] --> Extract --> ExpandWithLabel --> Extract = psk_secret_[2]
|
0 ...
| |
V V
psk_[n-1] --> Extract --> ExpandWithLabel --> Extract = psk_secret_[n]Figure 24: Computation of a PSK Secret from a Set of PSKs ๐
In particular, if there are no PreSharedKey proposals in a given Commit, then the resulting psk_secret is psk_secret_[0], the all-zero vector. Zero drama, zero PSKs, all vibes ๐ซง๐.
8.5. Exporters โจ
okay bestie, the main MLS key schedule hands you an exporter_secret ๐ฆ and any application can use it to cook up brand new secrets for stuff that lives outside of MLS. so periodt ๐
Here's the formula. MLS-Exporter takes a Label, a Context and a Length, and it's basically DeriveSecret on the exporter_secret with your label, then ExpandWithLabel with the fixed word "exported", the Hash of your Context, and the Length you asked for:
MLS-Exporter(Label, Context, Length) =
ExpandWithLabel(DeriveSecret(exporter_secret, Label),
"exported", Hash(Context), Length)Okay so, applications SHOULD give every MLS-Exporter call a unique label that says what the secret is for ๐ This keeps the same secret from getting made and used in two different places, which would be a total mess. And to stop different apps from picking the same label, there's an IANA registry for these labels in Section 17.8 ๐ธ
The exported values are tied to the group epoch that the exporter_secret came from, so they basically reflect one exact vibe of the group at one moment in time โจ
It is RECOMMENDED that the app generating exported values refreshes them after a Commit gets processed ๐ฅ (the girl just wants fresh secrets, no cap)
8.6. Resumption PSK ๐
The main MLS key schedule also gives you a resumption_psk ๐ It's a PSK that carries entropy from one epoch over into another. This is the move used in the reinitialization and branching processes in Sections 11.2 and 11.3, but apps are allowed to use it for other stuff too ๐ง
Some resumption PSK uses might want PSKs from older, historical epochs ๐ The application SHOULD set an upper limit on how many past epochs the resumption_psk can be stored for. Keep it tidy bestie ๐ซถ
8.7. Epoch Authenticators ๐
The main MLS key schedule gives every epoch its own epoch_authenticator ๐ If an active attacker is impersonating one member of the group, the epoch_authenticator that member's client computes will be different from the ones everyone else computes. Lowkey iconic, right? ๐ญ
This is a big deal because you can build defenses against impersonation that still work even if members' signature keys got compromised ๐ Here's a super simple example: say the users in an MLS group meet up in person and reliably confirm their epoch authenticator values match, using some decent user interface. Then each person knows nobody else is being impersonated in the current epoch ๐ BUT the second the epoch changes, they'd have to do the whole check again! The group's state changed, and an attacker could have snuck in ๐
More generally, if the group wants real authentication protection from the epoch_authenticator, they have to use it inside some secondary protocol (like that face-to-face thing above) ๐ฆ That protocol is what decides the actual authentication protections the MLS group ends up with. It's giving teamwork ๐ซถ
9. Secret Tree ๐ณ
For encryption keys and nonces, the key schedule starts with the encryption_secret at the root and derives a whole tree of secrets ๐ The tree has the same shape as the group's ratchet tree, and each leaf in the secret tree belongs to the same group member as the matching leaf in the ratchet tree. Iconic structure, bestie โจ
If N is a parent node in the secret tree, the children's secrets are defined like this (left(N) and right(N) are N's children):
tree_node_[N]_secret
|
|
+--> ExpandWithLabel(., "tree", "left", KDF.Nh)
| = tree_node_[left(N)]_secret
|
+--> ExpandWithLabel(., "tree", "right", KDF.Nh)
= tree_node_[right(N)]_secret
Figure 25: Derivation of Secrets from Parent to Children within a
Secret TreeThe secret sitting in a leaf of the secret tree kicks off two symmetric hash ratchets ๐ From those you get a stream of single-use keys and nonces, as described in Section 9.1. The root of each ratchet is computed like so:
tree_node_[N]_secret
|
|
+--> ExpandWithLabel(., "handshake", "", KDF.Nh)
| = handshake_ratchet_secret_[N]_[0]
|
+--> ExpandWithLabel(., "application", "", KDF.Nh)
= application_ratchet_secret_[N]_[0]
Figure 26: Initialization of the Hash Ratchets from the Leaves of
a Secret Tree9.1. Encryption Keys ๐
As described in Section 6, MLS encrypts three different kinds of info ๐
- Metadata (sender information)
- Handshake messages (Proposal and Commit)
- Application messages
The sender information used to look up the key for content encryption gets encrypted with an AEAD ๐ The key and nonce come from both sender_data_secret and a sample of the encrypted message content. Wild, right? ๐
For handshake and application messages, a sequence of keys is derived through a "sender ratchet" ๐ธ Every sender has their own sender ratchet, and each step along it is called a "generation" โจ
Here's a secret tree for a four-member group, showing the handshake and application ratchets member D uses for sending, plus the first two application keys and nonces ๐
G
|
.-+-.
/ \
E F
/ \ / \
A B C D
/ \
HR0 AR0--+--K0
| |
| +--N0
|
AR1--+--K1
| |
| +--N1
|
AR2 Figure 27: Secret Tree for a Four-Member GroupA sender ratchet starts from a per-sender base secret that comes from a Secret Tree, as described in Section 9 ๐ฆ That base secret kicks off a symmetric hash ratchet, which spits out a sequence of keys and nonces. The sender uses the j-th key/nonce pair in that sequence to encrypt (using the AEAD) the j-th message they send during that epoch. Each key/nonce pair MUST NOT be used to encrypt more than one message ๐ (non-negotiable, bestie)
Keys, nonces, and the secrets inside ratchets all get derived using DeriveTreeSecret ๐ The context for any given call is the current position in the ratchet.
DeriveTreeSecret(Secret, Label, Generation, Length) =
ExpandWithLabel(Secret, Label, Generation, Length)Generation gets encoded as a big endian uint32 โจ
ratchet_secret_[N]_[j]
|
+--> DeriveTreeSecret(., "nonce", j, AEAD.Nn)
| = ratchet_nonce_[N]_[j]
|
+--> DeriveTreeSecret(., "key", j, AEAD.Nk)
| = ratchet_key_[N]_[j]
|
V
DeriveTreeSecret(., "secret", j, KDF.Nh)
= ratchet_secret_[N]_[j+1]AEAD.Nn and AEAD.Nk are the lengths in bytes of the nonce and key for the AEAD scheme defined by the cipher suite ๐
9.2. Deletion Schedule ๐๏ธ
It is important to delete all security-sensitive values as soon as they are _consumed_ ๐ฅ A sensitive value S counts as _consumed_ if:
- S was used to encrypt or (successfully) decrypt a message, or
- a key, nonce, or secret derived from S has been consumed. (This goes for values derived via DeriveSecret as well as ExpandWithLabel.)
S can be the init_secret, commit_secret, epoch_secret, or encryption_secret, or any secret in a secret tree or one of the ratchets ๐
As soon as a group member consumes a value, they MUST immediately delete (all representations of) that value ๐ This is crucial for forward secrecy on past messages. Members MAY keep unconsumed values around for some reasonable amount of time to handle out-of-order message delivery ๐ซถ
For example, say a group member encrypts or (successfully) decrypts an application message using the j-th key and nonce in the ratchet of leaf node L in some epoch n. Then, for that member, at least the following values have been consumed and MUST be deleted ๐ญ
- the commit_secret, joiner_secret, epoch_secret, and encryption_secret of that epoch n, as well as the init_secret of the previous epoch n-1,
- all node secrets in the secret tree on the path from the root to the leaf with node L,
- the first j secrets in the application data ratchet of node L, and
- application_ratchet_nonce_[L]_[j] and application_ratchet_key_[L]_[j].
Concretely, look at the secret tree in Figure 27 ๐ Client A, B, or C would generate the illustrated values on receiving a message from D with generation equal to 1, without having received a message with generation 0 (for example, because of out-of-order delivery). In that case, these values get consumed:
- The key K1 and nonce N1 used to decrypt the message
- The application ratchet secrets AR1 and AR0
- The tree secrets D, F, and G (recall that G is the encryption_secret for the epoch)
- The epoch_secret, commit_secret, psk_secret, and joiner_secret for the current epoch
Other values may be retained (not consumed):
- K0 and N0 for decryption of an out-of-order message with generation 0
- AR2 for derivation of further message decryption keys and nonces
- HR0 for protection of handshake messages from D
- E and C for deriving secrets used by senders A, B, and C
10. Key Packages โจ
Okay so, to let people get added to a group whenever they want (no waiting around for everyone to be online ๐), clients can pre-publish KeyPackage objects. These hold some public info about a user, and a KeyPackage specifies:
- a protocol version and cipher suite that the client supports,
- a public key that others can use to encrypt a Welcome message to this client (an "init key"), and
- the content of the leaf node that should be added to the tree to represent this client.
KeyPackages are meant to be used only once, and they SHOULD NOT be reused, except for a "last resort" KeyPackage (see Section 16.8) ๐ซถ. Clients MAY generate and publish multiple KeyPackages so they can support multiple cipher suites. Main character energy, honestly ๐ .
The value for init_key MUST be a public key for the asymmetric encryption scheme defined by cipher_suite, and it MUST be unique among the set of KeyPackages created by this client. Likewise, the leaf_node field MUST be valid for the cipher suite, including both the encryption_key and signature_key fields. The whole structure is signed with the client's signature key. A KeyPackage object with an invalid signature field MUST be considered malformed ๐ซ.
The signature is computed by the function SignWithLabel, using the label KeyPackageTBS and a Content input that contains all of the fields except for the signature field.
struct {
ProtocolVersion version;
CipherSuite cipher_suite;
HPKEPublicKey init_key;
LeafNode leaf_node;
Extension extensions<V>;
/* SignWithLabel(., "KeyPackageTBS", KeyPackageTBS) */
opaque signature<V>;
} KeyPackage;
struct {
ProtocolVersion version;
CipherSuite cipher_suite;
HPKEPublicKey init_key;
LeafNode leaf_node;
Extension extensions<V>;
} KeyPackageTBS;If a client receives a KeyPackage inside an MLSMessage object, then it MUST verify that the version field of the KeyPackage has the same value as the version field of the MLSMessage. This matters because the KeyPackage's version is an explicit signal of the intended version to the other members of the group when they receive it in an Add proposal ๐ฃ.
The field leaf_node.capabilities tells everyone which protocol versions, cipher suites, credential types, and non-default proposal/extension types the client supports. (As Section 7.2 explains, some proposal and extension types in this document count as "default" and so aren't listed ๐ค.) This is the secret sauce that keeps MLS session establishment safe from downgrade attacks on those parameters (more on that in Section 11), while each KeyPackage still only advertises one version and one cipher suite. Iconic. ๐
The field leaf_node.leaf_node_source of the LeafNode in a KeyPackage MUST be set to key_package.
Extensions included in the extensions or leaf_node.extensions fields MUST be included in the leaf_node.capabilities field. As Section 13 covers, unknown extensions in KeyPackage.extensions MUST be ignored, and the creator of a KeyPackage object SHOULD include some random GREASE extensions ๐ง. Those help make sure other clients correctly ignore unknown extensions, which is so smart ngl.
10.1. KeyPackage Validation
A KeyPackage's validity needs checking at a couple of stages:
- When a KeyPackage is downloaded by a group member, before it gets used to add the client to the group
- When a KeyPackage is received by a group member in an Add message
The client checks a KeyPackage's validity with these steps:
- Verify that the cipher suite and protocol version of the KeyPackage match those in the GroupContext.
- Verify that the
leaf_nodeof the KeyPackage is valid for a KeyPackage according to Section 7.3. - Verify that the signature on the KeyPackage is valid using the public key in
leaf_node.credential. - Verify that the value of
leaf_node.encryption_keyis different from the value of theinit_keyfield.
11. Group Creation ๐ธ
A group always starts out with a single member, the "creator". Everyone else gets added later through the usual Add/Commit mechanism ๐.
The creator is in charge of setting the group ID, cipher suite, and initial extensions for the group. If the creator plans to add other members right at creation time, then it SHOULD fetch KeyPackages for the members to be added, and pick a cipher suite and extensions based on the members' capabilities. To protect against downgrade attacks, the creator MUST use the capabilities information in those KeyPackages to check that the chosen version and cipher suite is the best option supported by all members. Lowkey the most important step here ๐.
Group IDs SHOULD be built so there's a super, super low chance that honest group creators end up generating the same group ID, even without help from the Delivery Service. One way to do this is to make the group ID a freshly generated random value of size KDF.Nh. The Delivery Service MAY try to keep group IDs globally unique by rejecting the creation of new groups that use a previously used ID.
To initialize a group, the creator of the group MUST take the following steps:
- Initialize a one-member group with the following initial values:
- Ratchet tree: A tree with a single node, a leaf node containing an HPKE public key and credential for the creator
- Group ID: A value set by the creator
- Epoch: 0
- Tree hash: The root hash of the above ratchet tree
- Confirmed transcript hash: The zero-length octet string
- Epoch secret: A fresh random value of size KDF.Nh
- Extensions: Any values of the creator's choosing
- Calculate the interim transcript hash:
- Derive the
confirmation_keyfor the epoch as described in Section 8. - Compute a
confirmation_tagover the emptyconfirmed_transcript_hash, using theconfirmation_key, as described in Section 6.1. - Compute the updated
interim_transcript_hashfrom theconfirmed_transcript_hashand theconfirmation_tag, as described in Section 8.2.
- Derive the
At this point, the creator's state represents a one-member group with a fully initialized key schedule, transcript hashes, and so on. Proposals and Commits can be generated for this group state just like for any other state of the group, such as Add proposals and Commits that add other members. A GroupInfo object for this group state can also be published to make external joins easier ๐ฆ.
Members other than the creator join either by being sent a Welcome message (as described in Section 12.4.3.1) or by sending an external Commit (see Section 12.4.3.2).
In principle, the process above could be streamlined by having the creator directly create a tree and choose a random value for the first epoch's epoch secret. We follow the steps above anyway, because they remove unnecessary choices, which is how things like bad randomness could sneak in ๐ โโ๏ธ. The only choices the creator makes here are its own KeyPackage and the leaf secret that the Commit is built from.
11.1. Required Capabilities
A group's configuration puts certain requirements on the clients in it. At a minimum, all members of the group need to support the cipher suite and protocol version in use. Extra requirements can be added by including a required_capabilities extension in the GroupContext.
struct {
ExtensionType extension_types<V>;
ProposalType proposal_types<V>;
CredentialType credential_types<V>;
} RequiredCapabilities;This extension lists the extensions, proposals, and credential types that must be supported by all members of the group. The "default" proposal and extension types defined in this document are assumed to be implemented by all clients, so they don't need to be listed in RequiredCapabilities to be safely used. Note that this is not true for credential types, so don't skip those ๐.
For new members, existing members enforce support for required capabilities while they apply Add commits. Existing members should of course already be in compliance. To make sure this stays true even as the group's extensions get updated, a GroupContextExtensions proposal is deemed invalid if it contains a required_capabilities extension that requires non-default capabilities not supported by all current members ๐จ.
11.2. Reinitialization
A group can be reinitialized by creating a new group with the same membership and different parameters, then linking it to the old group via a resumption PSK ๐. The members of a group reinitialize it with these steps:
- A member of the old group sends a ReInit proposal (see Section 12.1.5).
- A member of the old group sends a Commit covering the ReInit proposal.
- A member of the old group creates an initial Commit that sets up a new group matching the ReInit, and sends a Welcome message:
- The
version,cipher_suite,group_id, andextensionsfields of the GroupContext object in the Welcome message MUST be the same as the corresponding fields in the ReInit proposal. Theepochin the Welcome message MUST be 1. - The Welcome message MUST specify a PreSharedKeyID of type
resumptionwith usagereinit, where thegroup_idfield matches the old group and theepochfield indicates the epoch after the Commit covering the ReInit.
- The
Note that these three steps may be done by the same group member or by different members. For example, if a group member sends a Commit with an inline ReInit proposal (steps 1 and 2) and then goes offline, another group member may recreate the group instead. This flexibility avoids situations where a group gets stuck between steps 2 and 3 ๐ฎโ๐จ.
Resumption PSKs with usagereinitMUST NOT be used in other contexts. A PreSharedKey proposal with typeresumptionand usagereinitMUST be considered invalid. Hard boundary, bestie ๐ซ.
11.3. Subgroup Branching
A new group can be formed from a subset of an existing group's members, using the same parameters as the old group ๐.
A member can create a subgroup by performing these steps:
- Fetch a new KeyPackage for each group member that should be included in the subgroup.
- Create an initial Commit message that sets up the new group and contains a PreSharedKey proposal of type
resumptionwith usagebranch. To avoid key reuse, thepsk_nonceincluded in the PreSharedKeyID object MUST be a randomly sampled nonce of length KDF.Nh ๐ฒ. - Send the corresponding Welcome message to the subgroup members.
A client that receives a Welcome message including a PreSharedKey of type resumption with usage branch MUST verify that the new group reflects a subgroup branched from the referenced group. It checks that:
- The
versionandcipher_suitevalues in the Welcome message are the same as those used by the old group. - The
epochin the Welcome message MUST be 1. - Each LeafNode in a new subgroup MUST match some LeafNode in the original group. In this context, a pair of LeafNodes is said to "match" if the identifiers presented by their respective credentials are considered equivalent by the application.
Resumption PSKs with usagebranchMUST NOT be used in other contexts. A PreSharedKey proposal with typeresumptionand usagebranchMUST be considered invalid. Same energy as before, no exceptions ๐ โโ๏ธ๐.
12. Group Evolution โจ
okay bestie, groups are never static ๐ people join, people leave, and sometimes everyone wants fresh keys so post-compromise security stays strong ๐. In MLS every change happens in a two-step process ๐ฆ:
- A proposal to make the change is broadcast to the group in a Proposal message.
- A member of the group or a new member broadcasts a Commit message that causes one or more proposed changes to enter into effect.
If the same member sends both the Proposal and the Commit, they can squish both steps together by sending the proposals in the commit. So efficient ๐
The group glows up from one cryptographic state to another every time a Commit message is sent and processed โจ. These states are called "epochs", and each one is uniquely identified among the group's states by an eight-octet epoch value ๐. When a brand-new group gets initialized, its starting epoch is 0x0000000000000000. Then every state transition bumps the epoch number up by one ๐ธ.
12.1. Proposals
Proposals ride along inside a FramedContent through a Proposal structure that says what kind of proposal it is ๐:
// See the "MLS Proposal Types" IANA registry for values
uint16 ProposalType;
struct {
ProposalType proposal_type;
select (Proposal.proposal_type) {
case add: Add;
case update: Update;
case remove: Remove;
case psk: PreSharedKey;
case reinit: ReInit;
case external_init: ExternalInit;
case group_context_extensions: GroupContextExtensions;
};
} Proposal;When a client receives a FramedContent containing a Proposal, it MUST verify the signature inside FramedContentAuthData, and it MUST check that the epoch field of the enclosing FramedContent matches the epoch field of the current GroupContext object ๐. If that check passes, the Proposal should be cached so it can be pulled back out by hash (as a ProposalOrRef object) in a later Commit message ๐ง.
12.1.1. Add
An Add proposal asks for a client holding a specific KeyPackage to be added to the group ๐ฅฐ.
struct {
KeyPackage key_package;
} Add;An Add proposal is invalid if its KeyPackage is invalid according to Section 10.1 ๐ซ.
An Add gets applied once it's included in a Commit message ๐. Its position in the list of proposals decides which leaf node the new member lands on. The first Add in the Commit goes into the leftmost empty leaf in the tree, the second Add goes into the next empty leaf to the right, and so on. If there's no empty leaf left, the tree gets extended to the right.
- Identify the leaf L for the new member. If there are empty leaves in the tree, L is the leftmost empty leaf. Otherwise, the tree is extended to the right as described in Section 7.7, and L is assigned the leftmost new blank leaf.
- For each non-blank intermediate node along the path from the leaf L to the root, add L's leaf index to the unmerged_leaves list for the node.
- Set the leaf node L to a new node containing the LeafNode object carried in the leaf_node field of the KeyPackage in the Add.
12.1.2. Update
An Update proposal works a lot like an Add, except it swaps out the sender's LeafNode in the tree instead of adding a brand-new leaf ๐.
struct {
LeafNode leaf_node;
} Update;An Update proposal is invalid if the LeafNode is invalid for an Update proposal according to Section 7.3 โ.
When a member of the group applies an Update, they take these steps:
- Replace the sender's LeafNode with the one contained in the Update proposal.
- Blank the intermediate nodes along the path from the sender's leaf to the root.
12.1.3. Remove
A Remove proposal asks for the member at the removed leaf index to be taken out of the group ๐.
struct {
uint32 removed;
} Remove;A Remove proposal is invalid if the removed field doesn't identify a non-blank leaf node ๐ .
When a member of the group applies a Remove, they follow these steps:
- Identify the leaf node matching removed. Let L be this leaf node.
- Replace the leaf node L with a blank node.
- Blank the intermediate nodes along the path from L to the root.
- Truncate the tree by removing the right subtree until there is at least one non-blank leaf node in the right subtree. If the rightmost non-blank leaf has index L, then this will result in the tree having
2^dleaves, wheredis the smallest value such that2^d > L. Tidy ๐งนโจ
12.1.4. PreSharedKey
A PreSharedKey proposal can ask for a pre-shared key to be injected into the key schedule while the epoch is advancing ๐.
struct {
PreSharedKeyID psk;
} PreSharedKey;A PreSharedKey proposal is invalid if any of the following is true:
- The PreSharedKey proposal is not being processed as part of a reinitialization of the group (see Section 11.2), and the PreSharedKeyID has psktype set to resumption and usage set to reinit.
- The PreSharedKey proposal is not being processed as part of a subgroup branching operation (see Section 11.3), and the PreSharedKeyID has psktype set to resumption and usage set to branch.
- The psk_nonce is not of length
KDF.Nh.
The psk_nonce MUST be randomly sampled ๐ฒ. When a Commit message includes one or more PreSharedKey proposals, group members derive psk_secret as described in Section 8.4, and the order of the PSKs matches the order of the PreSharedKey proposals in the Commit ๐งฉ.
12.1.5. ReInit
A ReInit proposal is a request to reinitialize the group with different parameters, like bumping the version number or switching the cipher suite ๐. The reinit happens by creating a completely new group and shutting the old one down ๐.
struct {
opaque group_id<V>;
ProtocolVersion version;
CipherSuite cipher_suite;
Extension extensions<V>;
} ReInit;A ReInit proposal is invalid if its version field is less than the version for the current group ๐ โโ๏ธ.
When a member of the group applies a ReInit proposal, they wait for the committer to send the Welcome message that matches the ReInit, following the criteria in Section 11.2 ๐ฌ.
12.1.6. ExternalInit
An ExternalInit proposal is for new members who want to join a group through an external commit ๐ช. This proposal can only be used in that context.
struct {
opaque kem_output<V>;
} ExternalInit;When a member of the group applies an ExternalInit, they initialize the next epoch using an init secret computed as described in Section 8.3 โจ. The kem_output field carries the required KEM output.
12.1.7. GroupContextExtensions
A GroupContextExtensions proposal updates the list of extensions in the GroupContext for the group ๐ง.
struct {
Extension extensions<V>;
} GroupContextExtensions;A GroupContextExtensions proposal is invalid if it includes a required_capabilities extension and some members of the group don't support some of the required capabilities (counting capabilities added in the same Commit, and leaving out ones removed) ๐ซ.
When a member of the group applies a GroupContextExtensions proposal, they do this:
- Remove all of the existing extensions from the GroupContext object for the group and replace them with the list of extensions in the proposal. (This is a wholesale replacement, not a merge. An extension is only carried over if the sender of the proposal includes it in the new list.)
Once the GroupContext is updated, its inclusion in the confirmation_tag through the key schedule confirms that all members of the group agree on the extensions in use ๐ค. Main character confirmation energy ๐.
12.1.8. External Proposals
Outsiders can build proposals and send them to the group in two situations ๐. The first one, marked by the external SenderType, lets an entity outside the group submit proposals. For example, an automated service might propose removing a member who's been inactive for a long time, or propose adding a newly hired staff member to a group that represents a real-world team ๐งโ๐ผ. An external sender might also send a ReInit proposal to enforce a changed policy about MLS versions or cipher suites ๐.
The external SenderType needs its signers to be pre-provisioned to the clients within the group, and it can only be used when the external_senders extension is present in the group's GroupContext ๐.
The second case, marked by the new_member_proposal SenderType, is handy when existing members can independently verify that an Add proposal sent by the new joiner themselves (not an existing member) is authorized ๐ฅน. External proposals that aren't authorized are considered invalid ๐ซ.
An external proposal MUST be sent as a PublicMessage object, because the sender won't have the keys needed to construct a PrivateMessage object ๐.
Some proposal types can't come from an external sender ๐ . Among the proposal types defined in this document, only these types may be sent by an external sender:
- add
- remove
- psk
- reinit
- group_context_extensions
Messages from external senders containing proposal types other than the above MUST be rejected as malformed ๐ฅ. New proposal types defined in the future MUST define whether they may be sent by external senders. The "Ext" column in the "MLS Proposal Types" registry (Section 17.4) reflects this property ๐.
12.1.8.1. External Senders Extension
The external_senders extension is a group context extension that holds the credentials and signature keys of the senders who are allowed to send external proposals to the group ๐๏ธ.
struct {
SignaturePublicKey signature_key;
Credential credential;
} ExternalSender;
ExternalSender external_senders<V>;12.2. Proposal List Validation โจ
okay bestie, before a Commit gets to go anywhere, its list of proposals has to pass a vibe check ๐ A group member creating a Commit and a group member processing a Commit MUST verify that the list of committed proposals is valid, using one of the following procedures depending on whether the Commit is external or not. If the list is invalid, the Commit message MUST be rejected as invalid. No exceptions, periodt ๐ โโ๏ธ
For a regular Commit (aka not external) ๐ธ, the list is invalid if any of these things happen:
- It contains an individual proposal that is invalid as specified in Section 12.1. ๐
- It contains an Update proposal generated by the committer. Nope, you can't update yourself in your own Commit ๐
- It contains a Remove proposal that removes the committer. Literally cannot kick yourself out, bestie ๐ญ
- It contains multiple Update and/or Remove proposals that apply to the same leaf. If the committer has received multiple such proposals, they SHOULD prefer any Remove received, or the most recent Update if there are no Removes. Remove is the drama queen here ๐
- It contains multiple Add proposals that contain KeyPackages that represent the same client according to the application (for example, identical signature keys). Double-booking the same person is a no ๐
- It contains an Add proposal with a KeyPackage that represents a client already in the group according to the application, unless there is a Remove proposal in the list removing the matching client from the group. Unless you're swapping them out in the same Commit, you can't add someone who's already here ๐
- It contains multiple PreSharedKey proposals that reference the same PreSharedKeyID. One PSK ID per vibe, please โจ
- It contains multiple GroupContextExtensions proposals. Too many cooks in the group settings ๐
- It contains a ReInit proposal together with any other proposal. If the committer has received other proposals during the epoch, they SHOULD prefer them over the ReInit proposal, which lets the ReInit get resent and applied in a later epoch. ReInit is a solo act, it goes last ๐ฆ
- It contains an ExternalInit proposal. ExternalInit doesn't belong in a regular Commit ๐
- It contains a Proposal with a non-default proposal type that is not supported by some members of the group that will process the Commit. Members being added or removed by the Commit don't need to support the proposal type, though ๐ง
- After processing the Commit, the ratchet tree is invalid. In particular, this happens if it contains any leaf node that is invalid according to Section 7.3. Broken tree = broken vibes ๐
An application may extend the above procedure by additional rules, for example, requiring application-level permissions to add members, or rules concerning non-default proposal types. The app gets to add its own house rules too ๐
For an external Commit, the list is valid if it contains only the following proposals (not necessarily in this order):
- Exactly one ExternalInit
- At most one Remove proposal, with which the joiner removes an old version of themselves. If a Remove proposal is present, then the LeafNode in the path field of the external Commit MUST meet the same criteria as would the LeafNode in an Update for the removed leaf (see Section 12.1.2). In particular, the credential in the LeafNode MUST present a set of identifiers that is acceptable to the application for the removed participant. So you can swap out your old self, but only if your new credential passes the app's check ๐ฆ
- Zero or more PreSharedKey proposals
- No other proposals
Proposal types defined in the future may make updates to the above validation logic to incorporate considerations related to proposals of the new type. Future proposal types get a seat at the table too ๐
12.3. Applying a Proposal List โจ
okay so the sections above explain how each individual proposal gets applied ๐ When creating or processing a Commit, a client applies a whole list of proposals to the ratchet tree and the GroupContext. The client MUST apply the proposals in the list in the following order:
- If there is a GroupContextExtensions proposal, replace the
extensionsfield of theGroupContextfor the group with the contents of the proposal. The new extensions MUST be used when evaluating other proposals in this list. For example, if a GroupContextExtensions proposal adds arequired_capabilitiesextension, then any Add proposals need to indicate support for those capabilities. Settings go first, so everyone else has to match the new vibe โ๏ธ - Apply any Update proposals to the ratchet tree, in any order. ๐
- Apply any Remove proposals to the ratchet tree, in any order. ๐
- Apply any Add proposals to the ratchet tree, in the order they appear in the list. โ
- Look up the PSK secrets for any PreSharedKey proposals, in the order they appear in the list. These secrets are then used to advance the key schedule later in Commit processing. ๐
- If there is an ExternalInit proposal, use it to derive the
init_secretfor use later in Commit processing. ๐งช - If there is a ReInit proposal, note its parameters for application later in Commit processing. ๐
Proposal types defined in the future MUST specify how the above steps are to be adjusted to accommodate the application of proposals of the new type. New kids on the block have to explain where they fit in the line-up ๐
12.4. Commit โจ
okay this is the main event ๐ A Commit message initiates a new epoch for the group, based on a collection of Proposals. It tells group members to update their picture of the group's state by applying the proposals and advancing the key schedule. Main character energy, literally ๐
Each proposal covered by the Commit is included by a ProposalOrRef value, which identifies the proposal to be applied either by value or by reference. Commits that refer to new Proposals from the committer can include them by value. Commits for previously sent proposals, from anyone (including the committer), can be sent by reference. Proposals sent by reference are specified by including the hash of the AuthenticatedContent object in which the proposal was sent (see Section 5.2). So it's either the whole proposal, or a receipt for it ๐งพ
enum {
reserved(0),
proposal(1),
reference(2),
(255)
} ProposalOrRefType;
struct {
ProposalOrRefType type;
select (ProposalOrRef.type) {
case proposal: Proposal proposal;
case reference: ProposalRef reference;
};
} ProposalOrRef;
struct {
ProposalOrRef proposals<V>;
optional<UpdatePath> path;
} Commit;A group member that has observed one or more valid proposals within an epoch MUST send a Commit message before sending application data. This ensures, for example, that any members whose removal was proposed during the epoch are actually removed before any application data is transmitted. Proposals don't just chill forever, they get committed before the party gets going ๐
A sender and a receiver of a Commit MUST verify that the committed list of proposals is valid as specified in Section 12.2. A list is invalid if, for example, it includes an Update and a Remove for the same member, or an Add when the sender does not have the application-level permission to add new users. Both sides run the vibe check, every time ๐
The sender of a Commit SHOULD include all proposals that it has received during the current epoch that are valid according to the rules for their proposal types and according to application policy, as long as this results in a valid proposal list. Bring everyone you've got to the party ๐ฅณ
Due to the asynchronous nature of proposals, receivers of a Commit SHOULD NOT enforce that all valid proposals sent within the current epoch are referenced by the next Commit. In the event that a valid proposal is omitted from the next Commit, and that proposal is still valid in the current epoch, the sender of the proposal MAY resend it after updating it to reflect the current epoch. Left on read? No worries, it can be resent with a fresh epoch ๐ซถ
A member of the group MAY send a Commit that references no proposals at all, which would thus have an empty proposals vector. Such a Commit resets the sender's leaf and the nodes along its direct path, and provides forward secrecy and post-compromise security with regard to the sender of the Commit. An Update proposal can be regarded as a "lazy" version of this operation, where only the leaf changes and intermediate nodes are blanked out. A glow-up with no proposals attached, iconic โจ
By default, the path field of a Commit MUST be populated. The path field MAY be omitted if (a) it covers at least one proposal and (b) none of the proposals covered by the Commit are of "path required" types. A proposal type requires a path if it cannot change the group membership in a way that requires the forward secrecy and post-compromise security guarantees that an UpdatePath provides. The only proposal types defined in this document that do not require a path are:
- add
- psk
- reinit
New proposal types MUST state whether they require a path. If any instance of a proposal type requires a path, then the proposal type requires a path. This attribute of a proposal type is reflected in the "Path Required" field of the "MLS Proposal Types" registry defined in Section 17.4. Each new proposal type has to spill whether it needs a path ๐
Update and Remove proposals are the clearest examples of proposals that require a path. An UpdatePath is required to evict the removed member or the old appearance of the updated member. Basically, if someone's getting booted or re-keyed, the path is non-negotiable ๐
In pseudocode, the logic for validating the path field of a Commit is as follows:
pathRequiredTypes = [
update,
remove,
external_init,
group_context_extensions
]
pathRequired = false
for proposal in commit.proposals:
pathRequired = pathRequired ||
(proposal.msg_type in pathRequiredTypes)
if len(commit.proposals) == 0 || pathRequired:
assert(commit.path != null)To summarize, a Commit can have three different configurations, each with its own use case ๐ง
- An "empty" Commit that references no proposals, which updates the committer's contribution to the group and provides PCS with regard to the committer. Solo glow-up ๐ธ
- A "partial" Commit that references proposals that do not require a path, and where the path is empty. Such a Commit doesn't provide PCS with regard to the committer. Light and breezy ๐ฆ
- A "full" Commit that references proposals of any type, which provides FS with regard to any removed members and PCS for the committer and any updated members. The whole squad, all the way, absolutely iconic ๐
12.4.1. Creating a Commit โจ
okay so bestie, this is where the committer gets to be the main character ๐ when a Commit gets made or processed, the client updates the ratchet tree and the GroupContext, and they go from an "old" state (the current epoch) to a "new" state (the epoch that the Commit kicks off) ๐ฆ when the Commit has an UpdatePath, a "provisional" group context gets built that reflects the proposals and the UpdatePath, but it keeps the old confirmed transcript hash ๐ธ
a member of the group makes a Commit message and its matching Welcome message at the same time, and the steps go like this ๐
- Verify that the list of proposals being committed is valid, as specified in Section 12.2. ๐ซถ
- Build an initial Commit object with the proposals field filled from the Proposals received during the current epoch, and with the path field empty. ๐ง
- Make the new ratchet tree and GroupContext by applying the list of proposals to the old ratchet tree and GroupContext, as defined in Section 12.3. ๐
- Decide whether to fill in the path field. If the proposals in the Commit mean the path field is required (see above), then it MUST be populated. Otherwise, the sender MAY leave the path field out, totally at its discretion. ๐
- If populating the path field:
- If this is an external Commit, give the sender the leftmost blank leaf node in the new ratchet tree. If there are no blank leaf nodes in the new ratchet tree, expand the tree to the right as defined in Section 7.7 and assign the leftmost new blank leaf to the sender. ๐
- Update the sender's direct path in the ratchet tree as described in Section 7.5. Define commit_secret as the value path_secret[n+1], derived from the last path secret value (path_secret[n]) derived for the UpdatePath. ๐
- Build a provisional GroupContext object containing these values:
- group_id: Same as the old GroupContext
- epoch: The epoch number for the new epoch
- tree_hash: The tree hash of the new ratchet tree
- confirmed_transcript_hash: Same as the old GroupContext
- extensions: The new GroupContext extensions (possibly updated by a GroupContextExtensions proposal)
- Encrypt the path secrets from the tree update to the group as described in Section 7.5, using the provisional group context as the context for HPKE encryption. ๐ฅ
- Create an UpdatePath holding the sender's new leaf node and the new public keys and encrypted path secrets along the sender's filtered direct path. Assign this UpdatePath to the path field in the Commit. โจ
- If not populating the path field: set the path field in the Commit to the null optional. Define commit_secret as the all-zero vector of length KDF.Nh (the same length a path_secret value would be). ๐
- Derive the psk_secret as specified in Section 8.4, where the order of PSKs in the derivation matches the order of PreSharedKey proposals in the proposals vector. ๐ซง
- Build a FramedContent object containing the Commit object. Sign the FramedContent using the old GroupContext as context.
- Use the FramedContent to update the confirmed transcript hash and the new GroupContext. ๐ธ
- Use the init_secret from the previous epoch, the commit_secret and psk_secret from the previous steps, and the new GroupContext to compute the new joiner_secret, welcome_secret, epoch_secret, and derived secrets for the new epoch. ๐ฆ
- Use the confirmation_key for the new epoch to compute the confirmation_tag value. ๐
- Calculate the interim transcript hash using the new confirmed transcript hash and the confirmation_tag from the FramedContentAuthData. ๐
- Protect the AuthenticatedContent object using keys from the old epoch:
- If encoding as PublicMessage, compute the membership_tag value using the membership_key. ๐
- If encoding as a PrivateMessage, encrypt the message using the sender_data_secret and the next (key, nonce) pair from the sender's handshake ratchet. ๐ง
- Build a GroupInfo reflecting the new state:
- Set the group_id, epoch, tree, confirmed_transcript_hash, interim_transcript_hash, and group_context_extensions fields to reflect the new state.
- Set the confirmation_tag field to the value of the corresponding field in the FramedContentAuthData object.
- Add any other extensions as defined by the application.
- Optionally derive an external key pair as described in Section 8. (required for external Commits, see Section 12.4.3.2). ๐ท
- Sign the GroupInfo using the member's private signing key. โ๏ธ
- Encrypt the GroupInfo using the key and nonce derived from the joiner_secret. for the new epoch (see Section 12.4.3.1). ๐
- For each new member in the group:
- Identify the lowest common ancestor in the tree of the new member's leaf node and the member sending the Commit. ๐ณ
- If the path field was populated above: compute the path secret corresponding to the common ancestor node. ๐
- Compute an EncryptedGroupSecrets object that encapsulates the init_secret for the current epoch and the path secret (if present). ๐ง
- Build one or more Welcome messages from the encrypted GroupInfo object, the encrypted key packages, and any PSKs for which a proposal was included in the Commit. The order of the psks MUST be the same as the order of PreSharedKey proposals in the proposals vector. As discussed in Section 12.4.3.1, the committer is free to choose how many Welcome messages to construct. However, the set of Welcome messages produced in this step MUST cover every new member added in the Commit. ๐
- If a ReInit proposal was part of the Commit, the committer MUST create a new group with the parameters specified in the ReInit proposal, and with the same members as the original group. The Welcome message MUST include a PreSharedKeyID with these parameters:
- psktype: resumption
- usage: reinit
- group_id: The group ID for the current group
- epoch: The epoch that the group will be in after this Commit
12.4.2. Processing a Commit ๐
okay now the receiving side ๐ a member of the group applies a Commit message by going through these steps ๐
- Verify that the epoch field of the enclosing FramedContent is equal to the epoch field of the current GroupContext object. ๐ฆ
- Unprotect the Commit using the keys from the current epoch:
- If the message is encoded as PublicMessage, verify the membership MAC using the membership_key. ๐
- If the message is encoded as PrivateMessage, decrypt the message using the sender_data_secret and the (key, nonce) pair from the step on the sender's hash ratchet indicated by the generation field. ๐
- Verify the signature on the FramedContent message as described in Section 6.1. โ๏ธ
- Verify that the proposals vector is valid according to the rules in Section 12.2. ๐
- Verify that all PreSharedKey proposals in the proposals vector are available. ๐ธ
- Make the new ratchet tree and GroupContext by applying the list of proposals to the old ratchet tree and GroupContext, as defined in Section 12.3. ๐ง
- Verify that the path value is populated if the proposals vector contains any Update or Remove proposals, or if it's empty. Otherwise, the path value MAY be omitted. ๐
- If the path value is populated, validate it and apply it to the tree:
- If this is an external Commit, give the sender the leftmost blank leaf node in the new ratchet tree. If there are no blank leaf nodes in the new ratchet tree, add a blank leaf to the right side of the new ratchet tree and assign it to the sender. ๐
- Validate the LeafNode as specified in Section 7.3. The leaf_node_source field MUST be set to commit. ๐ซถ
- Verify that the encryption_key value in the LeafNode is different from the committer's current leaf node. ๐
- Verify that none of the public keys in the UpdatePath appear in any node of the new ratchet tree. ๐
- Merge the UpdatePath into the new ratchet tree, as described in Section 7.5. ๐ณ
- Build a provisional GroupContext object containing these values:
- group_id: Same as the old GroupContext
- epoch: The epoch number for the new epoch
- tree_hash: The tree hash of the new ratchet tree
- confirmed_transcript_hash: Same as the old GroupContext
- extensions: The new GroupContext extensions (possibly updated by a GroupContextExtensions proposal)
- Decrypt the path secrets for UpdatePath as described in Section 7.5, using the provisional GroupContext as the context for HPKE decryption. ๐
- Define commit_secret as the value path_secret[n+1], derived from the last path secret value (path_secret[n]) derived for the UpdatePath. ๐ง
- If the path value is not populated, define commit_secret as the all-zero vector of length KDF.Nh (the same length a path_secret value would be). ๐ท
- Update the confirmed and interim transcript hashes using the new Commit, and generate the new GroupContext. ๐ฆ
- Derive the psk_secret as specified in Section 8.4, where the order of PSKs in the derivation matches the order of PreSharedKey proposals in the proposals vector. ๐ซง
- Use the init_secret from the previous epoch, the commit_secret and psk_secret from the previous steps, and the new GroupContext to compute the new joiner_secret, welcome_secret, epoch_secret, and derived secrets for the new epoch. ๐
- Use the confirmation_key for the new epoch to compute the confirmation tag for this message, as described below, and verify that it is the same as the confirmation_tag field in the FramedContentAuthData object. โ
- If the above checks are successful, consider the new GroupContext object as the current state of the group. ๐
- If the Commit included a ReInit proposal, the client MUST NOT use the group to send messages anymore. Instead, it MUST wait for a Welcome message from the committer meeting the requirements of Section 11.2. ๐ญ
Clients need to be prepared to receive a valid Commit message that removes them from the group. In this case, the client cannot send any more messages in the group and SHOULD promptly delete its group state and secret tree. (A client might keep the secret tree for a short time to decrypt late messages in the previous epoch.) ๐
That's the Commit flow, bestie! ๐ธ
12.4.3. Adding Members to the Group ๐ฆ
okay so new members can join the group in two ways ๐: a group member adds them, or they add themselves through an external Commit ๐ซถ. either way, the newbies need some info to bootstrap their local group state โจ
struct {
GroupContext group_context;
Extension extensions<V>;
MAC confirmation_tag;
uint32 signer;
/* SignWithLabel(., "GroupInfoTBS", GroupInfoTBS) */
opaque signature<V>;
} GroupInfo;the group_context field is the current state of the group ๐ธ. the extensions field lets the sender tuck in extra data that might help new joiners ๐. the confirmation_tag is the one from the Commit that kicked off the current epoch, or for epoch 0, it's the one computed when the group was created (see Section 11) ๐ง. (either way, whoever makes a GroupInfo can recompute the confirmation tag as MAC(confirmation_key, confirmed_transcript_hash), so it's not a mystery ๐
)
as we talked about in Section 13, unknown extensions in GroupInfo.extensions MUST be ignored ๐, and the creator of a GroupInfo object SHOULD toss in some random GREASE extensions so other clients learn to ignore unknown stuff ๐. extensions in GroupInfo.group_context.extensions, though, MUST be supported by the new joiner ๐. no skipping those, periodt ๐ญ
new members MUST verify that group_id is unique among the groups they're already participating in ๐. they also MUST verify the signature, using the public key from the leaf node of the ratchet tree at leaf index signer ๐. the signature covers everything in GroupInfo above the signature field, so here's that structure ๐
struct {
GroupContext group_context;
Extension extensions<V>;
MAC confirmation_tag;
uint32 signer;
} GroupInfoTBS;12.4.3.1. Joining via Welcome Message
the committer (the person sending the Commit) is the one in charge of sending a Welcome message to every new member added through Add proposals ๐. the Welcome format lets one message be encrypted for multiple new members at once, which is so smart ๐ง . it's up to the committer how many Welcomes to make for a given Commit. they could make one Welcome encrypted for everyone, a separate one for each person, or Welcomes for batches of people based on whatever batching scheme works for the app ๐ฆ. the process for creating and processing the Welcome is the same in every case, the only difference is which new members the Welcome is encrypted for โจ
the Welcome gives the new members the current state of the group after the Commit gets applied ๐. the new members can't decrypt or verify the Commit itself, but they get the secrets they need to take part in the epoch that the Commit started ๐
so the same Welcome can go to several new members, the group info is encrypted with a symmetric key and nonce derived from the joiner_secret for the new epoch ๐. the joiner_secret is then encrypted to each new member using HPKE ๐. inside that same encrypted package, the committer also sends the path secret for the lowest node (closest to the leaf) that sits in the direct paths of both the committer and the new member ๐ธ. this lets the new member compute private keys for the nodes in its direct path that the Commit is resetting ๐ซถ
if the Welcome sender wants the receiver to bring a PSK into the derivation of the epoch_secret, they can fill in the psks field to say which PSK to use ๐ง
struct {
opaque path_secret<V>;
} PathSecret;
struct {
opaque joiner_secret<V>;
optional<PathSecret> path_secret;
PreSharedKeyID psks<V>;
} GroupSecrets;
struct {
KeyPackageRef new_member;
HPKECiphertext encrypted_group_secrets;
} EncryptedGroupSecrets;
struct {
CipherSuite cipher_suite;
EncryptedGroupSecrets secrets<V>;
opaque encrypted_group_info<V>;
} Welcome;the client processing a Welcome needs a copy of the group's ratchet tree ๐ณ. the tree can ride along in the Welcome message, in an extension of type ratchet_tree ๐. if it comes some other way (like a caching service on the Delivery Service), then the client MUST download the tree before processing the Welcome ๐
when a client gets a Welcome, here's the play-by-play ๐:
- find an entry in the
secretsarray where thenew_membervalue matches one of this client's KeyPackages, using the hash indicated by thecipher_suitefield ๐. if there's no such entry, or the cipher suite in the KeyPackage doesn't match the one in the Welcome, return an error ๐ซ - decrypt the
encrypted_group_secretsvalue with the algorithms from the cipher suite, using the private keyinit_key_privthat goes withinit_keyin the referenced KeyPackage ๐
encrypted_group_secrets =
EncryptWithLabel(init_key, "Welcome",
encrypted_group_info, group_secrets)
group_secrets =
DecryptWithLabel(init_key_priv, "Welcome",
encrypted_group_info, kem_output, ciphertext)- if a PreSharedKeyID is part of the GroupSecrets and the client doesn't have the matching PSK, return an error ๐. also, if a PreSharedKeyID has type resumption with usage reinit or branch, check that it's the only PSK like that ๐
- from the
joiner_secretin the decrypted GroupSecrets object and the PSKs listed in GroupSecrets, derive the welcome_secret, then the welcome_key and welcome_nonce ๐ง. use that key and nonce to decrypt theencrypted_group_infofield ๐
welcome_nonce = ExpandWithLabel(welcome_secret, "nonce", "", AEAD.Nn)
welcome_key = ExpandWithLabel(welcome_secret, "key", "", AEAD.Nk)- verify the signature on the GroupInfo object ๐๏ธ. the signature input is every field in GroupInfo except the
signaturefield ๐. the public key comes from the LeafNode at leaf indexsignerin the ratchet tree. if that node is blank or the signature check fails, return an error โ - verify that the
group_idis unique among the groups this client is currently in ๐ - verify that the
cipher_suitein the GroupInfo matches thecipher_suitein the KeyPackage ๐ซ - verify the integrity of the ratchet tree ๐ณโ
- verify that the tree hash of the ratchet tree matches the
tree_hashfield in GroupInfo ๐งฉ - for each non-empty parent node, verify that it's "parent-hash valid", as described in Section 7.9.2 ๐
- for each non-empty leaf node, validate the LeafNode as described in Section 7.3 ๐ต๏ธ
- for each non-empty parent node and each entry in that node's
unmerged_leavesfield:- verify that the entry is a non-blank leaf node that's a descendant of the parent node ๐ฟ
- verify that every non-blank intermediate node between the leaf node and the parent node also has an entry for that leaf node in its
unmerged_leaves๐ฑ - verify that the encryption key in the parent node doesn't show up in any other node of the tree ๐จ
- verify that the tree hash of the ratchet tree matches the
- find a leaf whose LeafNode is identical to the one in the KeyPackage. if there isn't one, return an error ๐
. call this leaf
my_leaf๐ - build a new group state from the information in the GroupInfo object ๐๏ธ
- initialize the GroupContext from the
group_contextfield of the GroupInfo object ๐ธ - update the leaf
my_leafwith the private key that matches the public key in the node, sincemy_leafis the new member's leaf node in the ratchet tree, as defined above ๐ - if the
path_secretvalue is set in the GroupSecrets object: find the lowest common ancestor of the leaf nodemy_leafand the node of the member at leaf indexGroupInfo.signer. then set the private key for this node to the private key derived from thepath_secret๐๏ธ - for each parent of the common ancestor, up to the root of the tree, derive a new path secret and set the private key for that node to the private key derived from the path secret. the private key MUST be the one that corresponds to the public key in the node ๐
- initialize the GroupContext from the
- use the
joiner_secretfrom the GroupSecrets object to generate the epoch secret and the other derived secrets for the current epoch ๐ง - set the confirmed transcript hash in the new state to the
confirmed_transcript_hashvalue in the GroupInfo โ๏ธ - verify the confirmation tag in the GroupInfo using the derived confirmation key and the
confirmed_transcript_hashfrom the GroupInfo ๐งพ - use the confirmed transcript hash and the confirmation tag to compute the interim transcript hash in the new state ๐ช
- if a PreSharedKeyID was used that has type resumption with usage reinit or branch, verify that the
epochfield in the GroupInfo is equal to 1 ๐ข- for usage reinit, verify that the last Commit to the referenced group contains a ReInit proposal, and that the
group_id,version,cipher_suite, andgroup_context.extensionsfields of the GroupInfo match the ReInit proposal ๐ฏ. also verify that all the members of the old group are also members of the new group, according to the application ๐ฏ - for usage branch, verify that the
versionandcipher_suiteof the new group match those of the old group, and that the members of the new group are a subset of the members of the old group, according to the application ๐
- for usage reinit, verify that the last Commit to the referenced group contains a ReInit proposal, and that the
12.4.3.2. Joining via External Commits โจ
okay so External Commits are how new members (outside parties who want in ๐ซถ) add themselves to a group without an existing member having to come online and issue a Commit that references an Add proposal. it's giving independence, no cap ๐ฆ
Whether existing members accept or reject an external Commit follows the same rules that get applied to other handshake messages ๐
New members can create and issue an external Commit if they have access to the following info for the group's current epoch:
- group ID
- epoch ID
- cipher suite
- public tree hash
- confirmed transcript hash
- confirmation tag of the most recent Commit
- group extensions
- external public key
So, to join via an external Commit, a new member needs a GroupInfo with an external_pub extension sitting in its extensions field ๐
struct {
HPKEPublicKey external_pub;
} ExternalPub;This means a member of the group can let new clients join by making a GroupInfo object available to them ๐ธ Heads up though: a GroupInfo object is specific to an epoch, so it has to get updated as the group advances. Each GroupInfo object can be used for one external join, since that join will cause the epoch to change ๐ญ
The tree_hash field gets used the same way it does in the Welcome message. The full tree can be included via the ratchet_tree extension (see Section 12.4.3.3) ๐ง
The info in a GroupInfo isn't generally public, but applications can choose to make it available to new members so they can do External Commits ๐
In principle, external Commits work like regular Commits. BUT their content has to meet a specific set of requirements, bestie:
- External Commits MUST contain a path field (and is therefore a "full" Commit). The joiner gets added at the leftmost free leaf node (just as if they were added with an Add proposal), and the path is calculated relative to that leaf node.
- The Commit MUST NOT include any proposals by reference, since an external joiner can't determine the validity of proposals sent within the group ๐
- External Commits MUST be signed by the new member. In particular, the signature on the enclosing
AuthenticatedContentMUST verify using the public key for the credential in theleaf_nodeof thepathfield. - When processing a Commit, both existing and new members MUST use the external init secret as described in Section 8.3.
- The sender type for the
AuthenticatedContentencapsulating the external Commit MUST benew_member_commit.
External Commits come in two "flavors" ๐ A "join" Commit adds the sender to the group, or a "resync" Commit replaces a member's prior appearance with a brand new one.
Now the tea โ The "resync" operation lets an attacker who has compromised a member's signature private key introduce themselves into the group and remove the prior, legit member in a single Commit. ๐ Without resync, this can still happen, but it takes two operations: the external Commit to join, and a second Commit to remove the old appearance. Applications for whom this distinction is salient can choose to disallow external commits that contain a Remove. They can also allow resync commits only if they contain a "reinit" PSK proposal that proves the joining member was present in a prior epoch of the group. With that latter approach, the attacker would need to compromise the PSK as well as the signing key. But the application will need to make sure that continuing, non-resynchronizing members have the required PSK ๐
12.4.3.3. Ratchet Tree Extension ๐ณ
By default, a GroupInfo message only gives the joiner a hash of the group's ratchet tree. To process or generate handshake messages, the joiner will need a copy of the ratchet tree from some other source. (For example, the DS might provide a cached copy.) Because the tree hash is included in the GroupInfo message, the source of the ratchet tree doesn't need to be trusted to keep the tree's integrity intact ๐ซง
When the application doesn't want an external source, the whole public state of the ratchet tree can be provided in an extension of type ratchet_tree, which holds a ratchet_tree object of this form:
struct {
NodeType node_type;
select (Node.node_type) {
case leaf: LeafNode leaf_node;
case parent: ParentNode parent_node;
};
} Node;
optional<Node> ratchet_tree<V>;Each entry in the ratchet_tree vector gives the value for one node in the tree, or the null optional for a blank node ๐
The nodes are listed in the order of a left-to-right in-order traversal of the ratchet tree. Each node sits between its left subtree and its right subtree. (This is the same ordering as the array-based trees in Appendix C ๐ง )
If the tree has 2^d leaves, then it has 2^(d+1) - 1 nodes. The ratchet_tree vector logically has that many entries, but the sender MUST NOT include blank nodes after the last non-blank node. The receiver MUST check that the last node in ratchet_tree is non-blank, and then extend the tree to the right until its length is of the form 2^(d+1) - 1, adding the minimum number of blank values possible. (You can totally do this "virtually" by synthesizing blank nodes when needed, instead of actually changing the structure in memory ๐งโโ๏ธ)
The leaves of the tree are stored in the even-numbered entries of the array (the leaf with index L sits in array position 2*L). The root node is at position 2^d - 1 of the array. Intermediate parent nodes can be found by doing the same calculation on the subarrays to the left and right of the root, following something like this algorithm:
# Assuming a class Node that has left and right members
def subtree_root(nodes):
# If there is only one node in the array, return it
if len(nodes) == 1:
return Node(nodes[0])
# Otherwise, the length of the array MUST be odd
if len(nodes) % 2 == 0:
raise Exception("Malformed node array {}", len(nodes))
# Identify the root of the subtree
d = 0
while (2**(d+1)) < len(nodes):
d += 1
R = 2**d - 1
root = Node(nodes[R])
root.left = subtree_root(nodes[:R])
root.right = subtree_root(nodes[(R+1):])
return root(Note that this is the same ordering of nodes as in the array-based tree representation described in Appendix C. The algorithms in that section can be used to simplify decoding this extension into other representations ๐ช)
Here's an example: a tree with six non-blank leaves would be represented as an array of eleven elements, [A, W, B, X, C, _, D, Y, E, Z, F]. The decoding procedure above identifies the subtree roots like so (using R to represent a subtree root):
Y
|
.-----+-----.
/ \
X _
| |
.-+-. .-+-.
/ \ / \
W _ Z _
/ \ / \ / \ / \
A B C D E F _ _
1
0 1 2 3 4 5 6 7 8 9 0
<-----------> R <----------->
<---> R <---> <---> R <--->
- R - - R - - R - - R -
Figure 28: Left-to-Right In-Order Traversal of a Six-Member TreeThe presence of a ratchet_tree extension in a GroupInfo message doesn't change the GroupContext extensions for the group at all ๐
โโ๏ธ The client just stores the ratchet tree it was given and uses it for MLS operations.
If this extension isn't provided in a Welcome message, the client will need to fetch the ratchet tree over some other channel before it can generate or process Commit messages. Applications should ensure that this out-of-band channel has security protections equivalent to the ones afforded to Proposal and Commit messages. For example, an application that encrypts Proposal and Commit messages might distribute ratchet trees encrypted using a key exchanged over the MLS channel ๐
Regardless of how the client gets the tree, the client MUST verify that the root hash of the ratchet tree matches the tree_hash of the GroupContext before using the tree for MLS operations. No skipping this, periodt ๐
13. Extensibility ๐งฉ
The base MLS protocol can be extended in a few ways. New cipher suites can be added to enable new cryptographic algorithms. New types of proposals can perform new actions within an epoch. Extension fields can add extra information to the protocol. In this section we talk about some constraints on these extensibility mechanisms, which are needed to keep broad interoperability intact ๐ธ
13.1. Additional Cipher Suites
As discussed in Section 5.1, MLS lets the participants in a group negotiate the cryptographic algorithms used within the group. This extensibility matters for keeping the protocol secure over time [RFC7696]. It also creates a risk of interoperability failure when clients don't support a common cipher suite ๐ฌ
The cipher suite registry defined in Section 17.1 tries to strike a balance here. On one hand, the base policy for the registry is Specification Required, a pretty low bar meant to avoid needing standards work when different ciphers are needed for niche applications. On the other hand, there's a higher bar (Standards Action) for ciphers to set the Recommended field in the registry. That higher bar exists partly to make sure the interoperability implications of new cipher suites get considered ๐ง
MLS cipher suites are defined independently of MLS versions, so in principle the same cipher suite can be used across versions. Standards work defining new MLS versions should consider whether it's desirable for the new version to be compatible with existing cipher suites, or whether the new version should rule out some cipher suites. For example, a new version could follow the example of HTTP/2, which restricted the set of allowed TLS ciphers (see Section 9.2.2 of [RFC9113]) ๐ฆ
13.2. Proposals
Commit messages don't have an extension field, because the set of proposals is extensible. As discussed in Section 12.4, Proposals with a non-default proposal type MUST NOT be included in a commit unless the proposal type is supported by all the members of the group that will process the Commit. Not the vibe of sneaking in unsupported proposal types ๐ โโ๏ธ๐
13.3. Credential Extensibility ๐
Okay bestie, so MLS only gives you meaningful authentication if every member can authenticate some identity info for every other member ๐ซถ. That identity info lives in Credentials, so the whole trick is making sure everyone uses compatible credential types ๐ . The only types of credential that may be used in a group are the ones all members support, as shown by the capabilities field on each LeafNode in the ratchet tree โจ. An app can introduce a brand-new credential type by grabbing an unallocated identifier from the registry in Section 17.5 and flagging support for it in published LeafNodes ๐. That can happen in Update proposals for existing groups or in KeyPackages that get added to new groups. Once every member in the group has indicated support, members can start using LeafNodes with the new credential ๐ฆ. An app can also lock certain credential types in place by adding a required_capabilities extension to the group's GroupContext ๐. That way nobody can be added to the group unless they support them. Iconic behaviour, honestly ๐.
Looking ahead, future MLS extensions might let a member present more than one credential ๐. Those credentials could show different attributes that different authorities attest to. To stay consistent with the principle from the top of this section, any extension like that would need to make sure each member can still authenticate some identity for each other member ๐. So for every pair of members (Alice, Bob), Alice would need to present at least one credential of a type that Bob supports ๐ง.
13.4. Extensions ๐ธ
This protocol has a way to negotiate extension parameters that's kinda like the one in TLS [RFC8446] ๐. In TLS, negotiation is one-to-one: the client offers extensions in its ClientHello message, and the server shares its choices for the session with extensions in its ServerHello and EncryptedExtensions messages. In MLS, though, extensions show up in four places ๐ญ:
- In KeyPackages, to describe additional information related to the client
- In LeafNodes, to describe additional information about the client or its participation in the group (once in the ratchet tree)
- In the GroupInfo, to tell new members what parameters the group is using, and to provide any additional details needed to join the group
- In the GroupContext object, to make sure all members of the group have the same view of the parameters in use
So basically, an app can use GroupContext extensions to make sure everyone in the group agrees on a set of parameters ๐ค. Clients show their support for parameters in the capabilities field of their LeafNode ๐. New members find out about the group's GroupContext extensions through the extensions field inside the group_context field of the GroupInfo object ๐ฌ. The extensions field of a GroupInfo object (outside of group_context) can carry extra parameters for new joiners to use when they join the group โจ.
This extension mechanism is built for secure and forward-compatible negotiation of extensions ๐ฆ. For that to actually work, implementations MUST correctly handle extensible fields:
- A client that posts a KeyPackage MUST support all parameters advertised in it. Otherwise, another client might fail to interoperate by selecting one of those parameters.
- A client processing a KeyPackage object MUST ignore all unrecognized values in the capabilities field of the LeafNode and all unknown extensions in the extensions and leaf_node.extensions fields. Otherwise, it could fail to interoperate with newer clients.
- A client processing a GroupInfo object MUST ignore all unrecognized extensions in the extensions field.
- Any field containing a list of extensions MUST NOT have more than one extension of any given type.
- A client adding a new member to a group MUST verify that the LeafNode for the new member is compatible with the group's extensions. The capabilities field MUST indicate support for each extension in the GroupContext.
- A client joining a group MUST verify that it supports every extension in the GroupContext for the group. Otherwise, it MUST treat the enclosing GroupInfo message as invalid and not join the group.
Heads up: those last two requirements mean every MLS GroupContext extension is mandatory ๐จ. Any extension the group is using MUST be supported by every member of the group. No exceptions, no cap ๐.
The parameters of a group can change in two ways ๐ . You can send a GroupContextExtensions proposal to turn on additional extensions (Section 12.1.7), or you can reinitialize the group (Section 11.2) ๐.
13.5. GREASE ๐ง
Remember how clients are supposed to ignore unknown values for certain parameters? ๐ To make sure other clients actually do that, a client can follow the "Generate Random Extensions And Sustain Extensibility" approach, or GREASE, from [RFC8701] ๐ซง. In MLS, that means a client generating a KeyPackage, LeafNode, or GroupInfo object throws random values into certain fields. A correctly implemented client just ignores them. A client that wrongly rejects unknown code points will choke on the message, and that's a big flashing sign that it needs fixing ๐ฉ.
When generating the following fields, an MLS client SHOULD include a random selection of values chosen from these GREASE values:
- LeafNode.capabilities.cipher_suites
- LeafNode.capabilities.extensions
- LeafNode.capabilities.proposals
- LeafNode.capabilities.credentials
- LeafNode.extensions
- KeyPackage.extensions
- GroupInfo.extensions
For the KeyPackage and GroupInfo extensions, the extension_data of GREASE extensions MAY have any contents the sender picks, since a correctly implemented receiver will ignore it ๐. For example, a sender could fill these extensions with a randomly sized chunk of random data ๐ฒ.
Heads up: any GREASE values added to LeafNode.extensions need to be mirrored in LeafNode.capabilities.extensions too ๐ช. That's because the LeafNode validation process in Section 7.3 requires those two fields to match.
GREASE values MUST NOT be sent in the following fields ๐ซ. An unsupported value in any of these, GREASE included, will get the whole enclosing message rejected:
- Proposal.proposal_type
- Credential.credential_type
- GroupContext.extensions
- GroupContextExtensions.extensions
GREASE values have been registered across the registries in Section 17, so they can't collide with real future values ๐. These values are reserved in each registry: 0x0A0A, 0x1A1A, 0x2A2A, 0x3A3A, 0x4A4A, 0x5A5A, 0x6A6A, 0x7A7A, 0x8A8A, 0x9A9A, 0xAAAA, 0xBABA, 0xCACA, 0xDADA, and 0xEAEA. (0xFAFA falls in the private use range ๐ธ.) These values MUST only appear in the fields listed above, and never somewhere like the proposal_type field of a Proposal. Clients MUST NOT implement any special processing rules for them when they receive them, because special-casing would wreck their whole purpose of catching extensibility bugs ๐
โโ๏ธ.
GREASE values MUST be handled using the normal logic for processing unsupported values ๐ง . When clients compare capability lists to find what they both support, clients MUST represent their own capabilities with a list that only contains what they actually support, with no GREASE values ๐ช. Basically, lists with GREASE values only get sent to other clients. Representations of a client's own capabilities MUST NOT contain GREASE values ๐ซถ.
14. Sequencing of State Changes โณ
Every Commit message is based on a starting state, which is indicated by the epoch field of the enclosing FramedContent ๐. If you apply the changes from a Commit starting from a different state, the results will be wrong ๐ฌ.
Sequencing wouldn't be a problem at all if every group member sent a Commit based on the most current state of the group ๐. In practice, though, there's a real risk that two members generate Commit messages at the same time, both based on the same state ๐ฏ.
Applications MUST have an established way to resolve conflicting Commit messages for the same epoch ๐ฅ. They can do that by stopping conflicting messages from happening in the first place, or by coming up with rules for deciding which Commit out of several sent in an epoch becomes the canonical one ๐. Whatever approach they pick MUST minimize how long forked or previous group states stay in memory, and it MUST promptly delete them once they're no longer needed for forward secrecy ๐งน.
Generating a Commit message MUST NOT modify a client's state ๐ โโ๏ธ. The client can't know yet whether the Commit's changes will conflict with another Commit. Similarly, the Welcome message for a Commit MUST NOT be delivered to a new joiner until it's clear that the Commit has been accepted ๐.
Even with sequencing sorted, there's a risk that in a busy enough group, a given member never gets to send a Commit because they keep losing to everyone else ๐ญ. How big of a problem that is depends on the app's dynamics ๐.
15. Application Messages ๐ฌ
Handshake messages are mainly there to give clients an authenticated group key exchange ๐. To protect application messages sent among group members, the key schedule's encryption_secret is used to derive a sequence of nonces and keys for encryption ๐๏ธ. Every epoch moves the key schedule forward, which kicks off a new secret tree (see Section 9) along with a fresh set of symmetric ratchets of nonces and keys for each member ๐ณ.
Each client keeps its own local copy of the key schedule for every epoch it's a group member in ๐๏ธ. They derive new keys, nonces, and secrets as needed, and delete the old ones as soon as they've been used ๐งฝ.
The group identifier and epoch let a recipient figure out which group secrets to use and which epoch_secret to start computing other secrets from โจ. The sender identifier and content type tell the recipient which symmetric ratchet to pull from the secret tree ๐ฏ. The generation counter decides how far to iterate along the ratchet to produce the nonce and key needed for encryption or decryption ๐.
15.1. Padding ๐
Okay so, application messages MAY be padded to help resist traffic analysis over encrypted traffic [CLINIC] [HCJ16] ๐ต๏ธโโ๏ธ. MLS might deliver the same payload way less often across a lot of ciphertexts than a traditional web server does, but that still might give an attacker enough info to pull off an attack ๐. Like, if Alice asks Bob "When are we going to the movie?", the answer "Wednesday" could leak to an adversary purely from the ciphertext length. Not okay!! ๐
The length of the padding field in PrivateMessageContent is chosen by the sender at the time of encryption โจ. Senders may use padding to make it harder for attackers outside the group to infer the size of the encrypted content ๐ซถ. Just a heads up though: the transports that carry MLS messages may have maximum message sizes, so padding schemes SHOULD avoid making messages bigger than those limits in a given deployment ๐.
15.2. Restrictions ๐
During each epoch, senders MUST NOT encrypt more data than the security bounds of the AEAD scheme in use allow [CFRG-AEAD-LIMITS] ๐ญ. Bestie, this one is serious.
Also, every change to the group through a handshake message sets a new encryption_secret ๐. So that change MUST be applied before encrypting any new application message. This is required both so that anyone removed from the group can no longer receive messages, and so that confidentiality and authenticity for future messages can (potentially) recover after a past state compromise ๐.
15.3. Delayed and Reordered Application Messages ๐ฆ
Since each application message contains the group identifier, the epoch, and a generation counter, a client can receive messages out of order ๐. When that happens, the client moves the sender ratchet forward to match the received generation counter. Any unused nonce and key pairs from the ratchet are potentially stored, so they can decrypt the messages that got delayed or reordered ๐ง.
Applications SHOULD define a policy on how long to keep unused nonce and key pairs for a sender, and the maximum number to keep. This is on top of making sure those secrets get deleted according to the deletion schedule in Section 9.2 ๐๏ธ. Applications SHOULD also define a policy limiting the maximum number of steps clients will move the ratchet forward in response to a new message. Messages with a generation counter that is too much higher than the last message received would then get rejected. This avoids a denial-of-service attack where the recipient has to do an excessive number of key derivations ๐ค.
For example, a malicious group member could send a message with generation = 0xffffffff at the beginning of a new epoch, forcing recipients to perform billions of key derivations unless they apply limits like the ones discussed above ๐๐.
16. Security Considerations โจ
The security goals of MLS are described in [MLS-ARCH] ๐. Here we describe, at a high level, how the protocol achieves those goals. A complete security analysis is outside the scope of this document. The Security Considerations section of [MLS-ARCH] has some citations to detailed security analyses ๐.
16.1. Transport Security ๐
Because MLS messages are protected at the message level, the confidentiality and integrity of the group state do not depend on those messages being protected in transit ๐ . However, an attacker who can observe those messages in transit will be able to learn about the group state, including potentially the group membership (see Section 16.4.3 below) ๐. Such an attacker might also be able to mount denial-of-service attacks on the group, or exclude new members by selectively removing messages in transit ๐ฌ.
To prevent this form of attack, it is RECOMMENDED that all MLS messages be carried over a secure transport such as TLS [RFC8446] or QUIC [RFC9000] ๐๐ซถ.
16.2. Confidentiality of Group Secrets ๐คซ
Group secrets are partly derived from the output of a ratchet tree ๐ณ. Ratchet trees work by assigning each member of the group to a leaf in the tree, and maintaining this property: the private key of a node in the tree is known only to members of the group that are assigned a leaf in that node's subtree. This is called the _tree invariant_, and it makes it possible to encrypt to all group members except one, with a number of ciphertexts that is logarithmic in the number of group members ๐ง โจ.
The ability to efficiently encrypt to all members except one is what lets members be securely removed from a group ๐ช. It also lets a member rotate their key pair, so the old private key can no longer be used to decrypt new messages ๐๐.
16.3. Confidentiality of Sender Data ๐ถ๏ธ
The PrivateMessage framing encrypts "sender data" that identifies which group member sent an encrypted message, as described in Section 6.3.2 ๐ญ. Just like the QUIC header protection scheme [RFC9001], Section 5.4, this scheme is a variant of the HN1 construction analyzed in [NAN]. A sample of the ciphertext is combined with a sender_data_secret to derive a key and nonce, which are then used for AEAD encryption of the sender data ๐ง.
(key, nonce) = PRF(sender_data_secret, sample)
encrypted_sender_data =
AEAD.Seal(key, nonce, sender_data_aad, sender_data)The only differences between this construction and HN1 as described in [NAN] are that it (1) uses authenticated encryption instead of unauthenticated encryption, and (2) protects information used to derive a nonce instead of the nonce itself ๐ค.
Since the sender_data_secret is distinct from the content encryption key, the sender data encryption scheme achieves AE2 security as defined in [NAN], and therefore guarantees the confidentiality of the sender data ๐ฅฐ.
โ ๏ธ Bestie, listen up! Using the samesender_data_secretand ciphertext sample more than once risks compromising sender data protection, because it reuses an AEAD (key, nonce) pair. For example, in many AEAD schemes, reusing a key and nonce reveals the exclusive OR of the two plaintexts ๐. Assuming the ciphertext output of the AEAD algorithm is indistinguishable from random data (i.e., the AEAD is AE1-secure in the phrasing of [NAN]), the odds of two ciphertext samples being identical are roughly2^(-L/2), i.e., the birthday bound ๐.
The AEAD algorithms for the cipher suites defined in this document all provide this property. The size of the sample depends on the cipher suite's hash function, but in all cases, the probability of collision is no more than 2^-128 ๐ธ. Any future cipher suite MUST use an AE1-secure AEAD algorithm ๐.
16.4. Confidentiality of Group Metadata ๐ซฃ
Okay, so MLS does not give confidentiality protection to some messages and fields within messages:
- KeyPackage messages
- GroupInfo messages
- The unencrypted portion of a Welcome message
- Any Proposal or Commit messages sent as PublicMessage messages
- The unencrypted header fields in PrivateMessage messages
- The lengths of encrypted Welcome and PrivateMessage messages
The only mechanism MLS provides for confidentially distributing a group's ratchet tree to new members is to send it in a Welcome message as a ratchet_tree extension ๐ฒ. If an application distributes the tree some other way, its security will depend on that application mechanism ๐คทโโ๏ธ.
A party observing these fields might be able to infer certain properties of the group:
- Group ID
- Current epoch and frequency of epoch changes
- Frequency of messages within an epoch
- Group extensions
- Group membership
How much metadata is exposed to parties outside the group, and so how much they can infer about the group's properties, depends on several aspects of the DS design, such as:
- How KeyPackages are distributed
- How the ratchet tree is distributed
- How prospective external joiners get a GroupInfo object for the group
- Whether Proposal and Commit messages are sent as PublicMessage or PrivateMessage
In the rest of this section, we note the ways the above properties of the group show up in unprotected group messages, as a guide to understanding how they might be exposed or protected in a given application ๐๐.
16.4.1. GroupID, Epoch, and Message Frequency โฑ๏ธ
MLS provides no mechanism to protect the group ID and epoch of a message from the DS. So the group ID and the frequency of messages and epoch changes are not protected against inspection by the DS ๐๏ธ. However, any modifications to these will cause decryption failure ๐ โโ๏ธ.
16.4.2. Group Extensions ๐งฉ
A group's extensions are first set by the group's creator, and then updated by GroupContextExtensions proposals. A GroupContextExtensions proposal sent as a PublicMessage leaks the group's extensions ๐ข.
A new member learns the group's extensions via a GroupInfo object. When the new member joins via a Welcome message, the Welcome message's encryption protects the GroupInfo message ๐. When the new member joins via an external join, they must be provided with a GroupInfo object. Protecting this GroupInfo object is up to the application. If it is transmitted over a channel that is not confidential to the group and the new joiner, it will leak the group's extensions ๐ซ .
16.4.3. Group Membership ๐ฏโโ๏ธ
The group's membership is represented directly by its ratchet tree, since each member's LeafNode contains the member's cryptographic keys, a credential that holds information about the member's identity, and possibly other identifiers ๐ชช. Applications that expose the group's ratchet tree outside the group also leak the group's membership ๐จ.
Changes to the group's membership are made by means of Add and Remove proposals. If these proposals are sent as PublicMessage, information about the corresponding membership changes will leak. A party that sees all of these changes can reconstruct the group membership ๐งฉโจ.
Welcome messages contain a hash of each KeyPackage the Welcome message is encrypted for. If a party has access to a pool of KeyPackages and observes a Welcome message, they can identify the KeyPackage representing the new member. If the party can also associate the Welcome with a group, they can infer that the identified new member was added to that group ๐ต๏ธ.
These information leaks only reveal the group's membership to the degree that membership is revealed by the contents of a member's LeafNode in the ratchet tree. In some cases this may be pretty direct, e.g., due to credentials attesting to identifiers such as email addresses ๐ง. An application could construct a member's leaf node to be less identifying, e.g., by using a pseudonymous credential and frequently rotating encryption and signature keys ๐ฆ๐ซ.
16.5. Authentication ๐
okay so the first kind of authentication is that group members can check a message came from someone in the group ๐. For encrypted messages this is locked in, because they're encrypted with an AEAD under a key derived from the group secrets. For plaintext messages, the membership_tag does the job. It's a MAC over the message, under a key derived from the group secrets โจ.
The second kind is more specific: group members can check that a message came from a particular member ๐ฏ. That's guaranteed by a digital signature on each message, made with the sender's signature key ๐ซถ.
Okay, the signature keys are honestly the MVP for MLS against active attacks ๐ญ. If a member's signature key gets compromised, an attacker can make LeafNodes and KeyPackages pretending to be that member. Depending on the app, that can let the attacker join the group as the compromised member ๐. Like, if the group lets outside parties join via external commits, an attacker with a stolen signature key could use an external Commit to slide right in. Even a "resync"-style external Commit could swap out the compromised member ๐.
Applications can lower this risk with pre-shared keys (PSKs) ๐. If a group requires joiners to know a PSK on top of authenticating with a credential, then an impersonation attack needs both the relevant PSK and the victim's signature key. The catch? The app needs some outside arrangement that makes sure the legit members actually have the required PSKs ๐ธ.
16.6. Forward Secrecy and Post-Compromise Security ๐ฆ
these two are the big deals for long-lived MLS groups ๐. Forward secrecy means messages sent at a certain point stay secure even if a group member gets compromised later. Post-compromise security means messages stay secure even if a member was compromised at some point in the past.
Compromise
|
|
| V |
------------------|---------|------------------------->
| | Time
<-----------------| |---------------->
Forward Secrecy | | Post-Compromise
| | Security
Figure 29: Forward Secrecy and Post-Compromise SecurityBetween epochs, PCS comes from members regularly updating their leaf key in the ratchet tree ๐. That stops group secrets from still being encrypted to public keys whose private keys were already compromised. Heads up: sending an Update proposal doesn't get you PCS until another member includes it in a Commit ๐. Members can get immediate PCS by sending their own Commit and populating the path field, as described in Section 12.4 ๐. To be clear, in all these cases the PCS guarantees kick in when the members of the group process the relevant Commit, not when the sender creates it ๐ .
Forward secrecy between epochs comes from deleting private keys from past versions of the ratchet tree, which stops old group secrets from being re-derived ๐. Forward secrecy within an epoch comes from deleting message encryption keys once they've been used to encrypt or decrypt a message โจ. Group secrets and message encryption keys are shared by the group, so there's a risk to forward secrecy for as long as any member hasn't deleted them ๐ฌ. That's a particular risk if someone's offline for a long time. Applications SHOULD have mechanisms for evicting group members that are offline for too long (i.e., members who haven't changed their key within some period) โณ.
New groups have their own risk too. They can end up using previously compromised keys (like with PCS) if a member gets added via an old KeyPackage whose private key was compromised ๐ฅฒ. The fix is having clients regularly generate new KeyPackages and upload them to the Delivery Service. That way, the key material used to add someone is more likely to be fresh and less likely to be compromised ๐ง.
16.7. Uniqueness of Ratchet Tree Key Pairs ๐
The encryption and signature keys stored in the encryption_key and signature_key fields of ratchet tree nodes MUST be distinct from one another. If two members' leaf nodes have the same signature key, for example, the data origin authentication properties afforded by signatures within the group get degraded ๐ฉ.
Uniqueness of keys in leaf nodes is assured by explicitly checking each leaf node as it's added to the tree, whether that's in an Add proposal, an Update proposal, or the path field of a Commit ๐. The details live in Sections 7.3, 12.2, and 12.4.2. Uniqueness of encryption keys in parent nodes is assured by checking that the keys in an UpdatePath are not found elsewhere in the tree (see Section 12.4.2) ๐.
16.8. KeyPackage Reuse ๐๏ธ
KeyPackages are meant to be used only once ๐ โโ๏ธ. Once a KeyPackage has introduced the corresponding client to a group, it SHOULD be deleted from the KeyPackage publication system. Reusing KeyPackages can lead to replay attacks ๐ฑ.
An application MAY allow reuse of a "last resort" KeyPackage to prevent denial-of-service attacks ๐. Since a KeyPackage is needed to add a client to a new group, an attacker could stop a client from being added to new groups by exhausting all the available KeyPackages ๐ฅบ. To prevent that denial-of-service attack, the KeyPackage publication system SHOULD rate-limit KeyPackage requests, especially if not authenticated ๐ฆ.
16.9. Delivery Service Compromise ๐ต๏ธโโ๏ธ
MLS is designed to protect the confidentiality and integrity of group data even in the face of a compromised DS ๐ก๏ธ. But a compromised DS can still pull some stunts. It can't forge messages, but it can selectively delay or remove them ๐. Sometimes you can spot this by detecting gaps in the per-sender generation counter, though it's not always possible to tell an attack apart from ordinary message loss. The DS can also permanently block messages to and from a group member, and that won't always be detectable by the other members ๐ถ. If an application uses the DS to resolve conflicts between simultaneous Commits (see Section 14), the DS can also influence which Commit gets applied, even to the point of stopping a member from ever having its Commits applied ๐.
Put together, these abilities could let a DS team up with an attacker who has compromised a member's state to defeat PCS ๐ค. The DS suppresses the valid Update and Commit messages from that member, which would otherwise lock the attacker out and update the member's leaf to a new, uncompromised state. Aside from the SenderData.generation value, MLS leaves loss detection up to the application ๐ซ .
16.10. Authentication Service Compromise ๐จ
AS compromise is way more serious than DS compromise, bestie ๐ญ. A compromised AS can assert a binding for a signature key and identity pair of its choice, which allows impersonation of a given user. That's enough for the AS to join new groups as if it were that user. Depending on the application architecture, it may also be enough for the compromised AS to join the group as an existing user, like as if it were a new device associated with the same user ๐ฑ.
If the application uses a transparency mechanism such as CONIKS [CONIKS] or Key Transparency [KT], end users may be able to detect this kind of misbehavior by the AS ๐. It's also possible to construct schemes where a user's various clients vouch for each other, e.g., by signing each other's keys ๐ค.
16.11. Additional Policy Enforcement ๐
The DS and AS may also apply additional policies to MLS operations to get additional security properties โจ. For example, MLS enables any participant to add or remove members of a group, but a DS could enforce a policy that only certain members are allowed to do that ๐. MLS authenticates all members of a group, and a DS could help ensure that only clients with certain types of credentials are admitted ๐ชช. MLS provides no inherent protection against denial of service, so a DS could also enforce rate limits to mitigate those risks ๐ง.
16.12. Group Fragmentation by Malicious Insiders ๐ช
It's possible for a malicious member of a group to "fragment" the group by crafting an invalid UpdatePath ๐. Recall that an UpdatePath encrypts a sequence of path secrets to different subtrees of the group's ratchet trees. Those path secrets should be derived in a sequence, as described in Section 7.4, but the UpdatePath syntax lets the sender encrypt arbitrary, unrelated secrets. The syntax also doesn't guarantee that the encrypted path secret for a given node corresponds to the public key provided for that node ๐.
Both of these types of corruption will make processing of a Commit fail for some members of the group. If the public key for a node doesn't match the path secret, the members who decrypt that path secret will reject the Commit based on this mismatch ๐ . If the path secret sequence is incorrect at some point, members who can decrypt nodes before that point will compute a different public key for the mismatched node than the one in the UpdatePath, which also makes the Commit fail ๐. Applications SHOULD provide mechanisms for failed commits to be reported, so that group members who weren't able to recognize the error themselves can reinitialize the group if necessary ๐ฃ.
Even with an error reporting mechanism in place, though, members can still get locked out of the group by a malformed Commit ๐ฉ. Malformed Commits can only be recognized by certain members of the group. So in an asynchronous application, it may be the case that all the members who could detect a fault in a Commit are offline. In that case, the Commit will be accepted by the group, and the resulting state may become the basis for further Commits. When the affected members come back online, they'll reject the first Commit and be unable to catch up with the group ๐ฅ. They'll need to either add themselves back with an external Commit or reinitialize the group from scratch.
Applications can address this risk by requiring certain members of the group to acknowledge successful processing of a Commit before the group regards the Commit as accepted โ . The minimum set of acknowledgements needed to verify that a Commit is well-formed is one acknowledgement from one member per node in the UpdatePath. That means one member from each subtree rooted in the copath node corresponding to the node in the UpdatePath ๐งฉ. MLS does not provide a built-in mechanism for such acknowledgements, but they can be added at the application layer ๐.
17. IANA Considerations โจ
okay so IANA has set up a bunch of registries ๐ all of them live under the "Messaging Layer Security" group registry heading ๐ and new entries get added through the Specification Required policy [RFC8126]. here's the lineup:
- MLS Cipher Suites (Section 17.1)
- MLS Wire Formats (Section 17.2)
- MLS Extension Types (Section 17.3)
- MLS Proposal Types (Section 17.4)
- MLS Credential Types (Section 17.5)
- MLS Signature Labels (Section 17.6)
- MLS Public Key Encryption Labels (Section 17.7)
- MLS Exporter Labels (Section 17.8)
the MLS Designated Experts (DEs) get their own spotlight in Section 17.9 ๐ฆ so check there for the deets on them.
17.1. MLS Cipher Suites ๐
okay bestie, a cipher suite is basically a combo of a protocol version and the set of crypto algorithms you're supposed to use together ๐ it's giving "pick your whole outfit at once" energy.
the name follows this naming convention:
CipherSuite MLS_LVL_KEM_AEAD_HASH_SIG = VALUE;and VALUE is a 16-bit integer:
uint16 CipherSuite;each part of the name tells you something different ๐
+===========+==================================+
| Component | Contents |
+===========+==================================+
| LVL | The security level (in bits) |
+-----------+----------------------------------+
| KEM | The KEM algorithm used for HPKE |
| | in ratchet tree operations |
+-----------+----------------------------------+
| AEAD | The AEAD algorithm used for HPKE |
| | and message protection |
+-----------+----------------------------------+
| HASH | The hash algorithm used for HPKE |
| | and the MLS transcript hash |
+-----------+----------------------------------+
| SIG | The signature algorithm used for |
| | message authentication |
+-----------+----------------------------------+Table 5
the registry has four columns, and here's the tea on each one ๐
- Value: the numeric value of the cipher suite
- Name: the name of the cipher suite
- Recommended: whether the IETF recommends supporting this cipher suite. the valid values are "Y", "N", and "D", as explained below. the default value for this column is "N". setting the Recommended item to "Y" or "D", or changing an item that's currently "Y" or "D", requires Standards Action [RFC8126].
- Y: the IETF has consensus that the item is RECOMMENDED. ๐ this only means the mechanism is fit for the purpose it was defined for. you still need to read the docs carefully to figure out where it applies. the IETF could recommend stuff with limited applicability, but they'll also write applicability statements that spell out any limitations or constraints on its use.
- N: the item hasn't been evaluated by the IETF, and the IETF hasn't said anything about whether the mechanism is suitable. this doesn't mean it's flawed, just that there's no consensus yet ๐ the IETF might keep something marked "N" because it has limited applicability or usage constraints.
- D: the item is discouraged and SHOULD NOT or MUST NOT be used ๐ this marking can flag mechanisms that cause problems if you use them, like a weak crypto algorithm or something that could cause interoperability headaches in deployment.
- Reference: the document where this cipher suite is defined
here are the initial contents of the registry ๐
+========+===================================================+=+====+
| Value |Name |R|Ref |
+========+===================================================+=+====+
| 0x0000 |RESERVED |-|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0001 |MLS_128_DHKEMX25519_AES128GCM_SHA256_Ed25519 |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0002 |MLS_128_DHKEMP256_AES128GCM_SHA256_P256 |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0003 |MLS_128_DHKEMX25519_CHACHA20POLY1305_SHA256_Ed25519|Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0004 |MLS_256_DHKEMX448_AES256GCM_SHA512_Ed448 |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0005 |MLS_256_DHKEMP521_AES256GCM_SHA512_P521 |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0006 |MLS_256_DHKEMX448_CHACHA20POLY1305_SHA512_Ed448 |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0007 |MLS_256_DHKEMP384_AES256GCM_SHA384_P384 |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x0A0A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x1A1A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x2A2A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x3A3A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x4A4A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x5A5A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x6A6A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x7A7A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x8A8A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0x9A9A |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0xAAAA |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0xBABA |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0xCACA |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0xDADA |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0xEAEA |GREASE |Y|RFC |
| | | |9420|
+--------+---------------------------------------------------+-+----+
| 0xF000 |Reserved for Private Use |-|RFC |
| - | | |9420|
| 0xFFFF | | | |
+--------+---------------------------------------------------+-+----+Table 6: MLS Extension Types Registry
all the non-GREASE cipher suites use HMAC [RFC2104] as their MAC function, with a different hash for each suite ๐ฆ here's how the cipher suites map onto the HPKE primitives [RFC9180], the HMAC hash functions, and the TLS signature schemes [RFC8446] ๐
+======+======+========+========+========+========================+
|Value |KEM | KDF | AEAD | Hash | Signature |
+======+======+========+========+========+========================+
|0x0001|0x0020| 0x0001 | 0x0001 | SHA256 | ed25519 |
+------+------+--------+--------+--------+------------------------+
|0x0002|0x0010| 0x0001 | 0x0001 | SHA256 | ecdsa_secp256r1_sha256 |
+------+------+--------+--------+--------+------------------------+
|0x0003|0x0020| 0x0001 | 0x0003 | SHA256 | ed25519 |
+------+------+--------+--------+--------+------------------------+
|0x0004|0x0021| 0x0003 | 0x0002 | SHA512 | ed448 |
+------+------+--------+--------+--------+------------------------+
|0x0005|0x0012| 0x0003 | 0x0002 | SHA512 | ecdsa_secp521r1_sha512 |
+------+------+--------+--------+--------+------------------------+
|0x0006|0x0021| 0x0003 | 0x0003 | SHA512 | ed448 |
+------+------+--------+--------+--------+------------------------+
|0x0007|0x0011| 0x0002 | 0x0002 | SHA384 | ecdsa_secp384r1_sha384 |
+------+------+--------+--------+--------+------------------------+Table 7
the transcript hash used for the MLS transcript hash is whichever one is referenced in the cipher suite name ๐ง for the suites defined above, "SHA256", "SHA384", and "SHA512" mean the SHA-256, SHA-384, and SHA-512 functions defined in [SHS] โจ
and one last thing, bestie ๐ซถ: in addition to the general requirements of Section 13.1, future cipher suites MUST meet the requirements of Section 16.3. no skipping that!! ๐ญ
It's advisable to keep the number of cipher suites low, so clients are more likely to interoperate across a federated setup. โจ That's why the suites only include modern algorithms that are also well-established. ๐ Clients can pick between two security levels, roughly 128-bit and 256-bit. Within each level, they can choose between the faster X25519/X448 curves or curves that comply with FIPS 140-2 for Diffie-Hellman key negotiation. ๐ฆ Clients can also go with ChaCha20Poly1305 or AES-GCM, for example if they care about performance. ๐ ChaCha20Poly1305 isn't listed by FIPS 140-2, so it doesn't get paired with the FIPS-compliant curves. The security level of the symmetric encryption and hash functions always matches the security level of the curve. ๐ธ
The mandatory-to-implement cipher suite for MLS 1.0 is MLS_128_DHKEMX25519_AES128GCM_SHA256_Ed25519. ๐ It uses Curve25519 for key exchange, AES-128-GCM for HPKE, HKDF over SHA2-256, and Ed25519 for signatures. MLS clients MUST implement this cipher suite. ๐ซถ
17.2. MLS Wire Formats
The "MLS Wire Formats" registry is where you'll find the identifiers for the types of messages that can be sent in MLS. ๐ฎ The wire format field is two bytes wide, so the valid wire format values run from 0x0000 to 0xFFFF. ๐ฅ
Template:
- Value: The numeric value of the wire format
- Name: The name of the wire format
- Recommended: Same as in Section 17.1
- Reference: The document where this wire format is defined
Initial contents:
+=================+==========================+===+==========+
| Value | Name | R | Ref |
+=================+==========================+===+==========+
| 0x0000 | RESERVED | - | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0001 | mls_public_message | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0002 | mls_private_message | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0003 | mls_welcome | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0004 | mls_group_info | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0005 | mls_key_package | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0xF000 - 0xFFFF | Reserved for Private Use | - | RFC 9420 |
+-----------------+--------------------------+---+----------+Table 8: MLS Wire Formats Registry
17.3. MLS Extension Types
The "MLS Extension Types" registry is the home base for identifiers of extensions to the MLS protocol. ๐ง The extension type field is two bytes wide, so valid extension type values fall in the range 0x0000 to 0xFFFF. ๐
Template:
- Value: The numeric value of the extension type
- Name: The name of the extension type
- Message(s): The messages in which the extension may appear, drawn from the following list:
- KP: KeyPackage objects
- LN: LeafNode objects
- GC: GroupContext objects
- GI: GroupInfo objects
- Recommended: Same as in Section 17.1
- Reference: The document where this extension is defined
Initial contents:
+==========+=======================+============+===+==========+
| Value | Name | Message(s) | R | Ref |
+==========+=======================+============+===+==========+
| 0x0000 | RESERVED | N/A | - | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x0001 | application_id | LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x0002 | ratchet_tree | GI | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x0003 | required_capabilities | GC | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x0004 | external_pub | GI | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x0005 | external_senders | GC | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x0A0A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x1A1A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x2A2A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x3A3A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x4A4A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x5A5A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x6A6A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x7A7A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x8A8A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0x9A9A | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0xAAAA | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0xBABA | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0xCACA | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0xDADA | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0xEAEA | GREASE | KP, GI, LN | Y | RFC 9420 |
+----------+-----------------------+------------+---+----------+
| 0xF000 - | Reserved for Private | N/A | - | RFC 9420 |
| 0xFFFF | Use | | | |
+----------+-----------------------+------------+---+----------+Table 9: MLS Extension Types Registry
17.4. MLS Proposal Types
The "MLS Proposal Types" registry holds identifiers for the kinds of proposals that can be made to change an MLS group. ๐ The extension type field is two bytes wide here too, so valid extension type values sit in the range 0x0000 to 0xFFFF. ๐
Template:
- Value: The numeric value of the proposal type
- Name: The name of the proposal type
- Recommended: Same as in Section 17.1
- External: Whether a proposal of this type may be sent by an external sender (see Section 12.1.8)
- Path Required: Whether a Commit covering a proposal of this type is required to have its path field populated (see Section 12.4)
- Reference: The document where this extension is defined
Initial contents:
+==========+==========================+===+=====+======+==========+
| Value | Name | R | Ext | Path | Ref |
+==========+==========================+===+=====+======+==========+
| 0x0000 | RESERVED | - | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0001 | add | Y | Y | N | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0002 | update | Y | N | Y | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0003 | remove | Y | Y | Y | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0004 | psk | Y | Y | N | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0005 | reinit | Y | Y | N | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0006 | external_init | Y | N | Y | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0007 | group_context_extensions | Y | Y | Y | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x0A0A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x1A1A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x2A2A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x3A3A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x4A4A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x5A5A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x6A6A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x7A7A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x8A8A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0x9A9A | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0xAAAA | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0xBABA | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0xCACA | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0xDADA | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0xEAEA | GREASE | Y | - | - | RFC 9420 |
+----------+--------------------------+---+-----+------+----------+
| 0xF000 - | Reserved for Private Use | - | - | - | RFC 9420 |
| 0xFFFF | | | | | |
+----------+--------------------------+---+-----+------+----------+Table 10: MLS Proposal Types Registry
17.5. MLS Credential Types ๐
okay so the "MLS Credential Types" registry is where we keep the list of credential types that MLS can use for authentication ๐ชชโจ the credential type field is two bytes wide, so valid values run from 0x0000 all the way up to 0xFFFF. big range, bestie ๐ญ
Template:
Value: the numeric value of the credential typeName: the name of the credential typeRecommended: same as in Section 17.1Reference: the document where this credential is defined
Initial contents (it's giving spreadsheet energy ๐ ):
+=================+==========================+===+==========+
| Value | Name | R | Ref |
+=================+==========================+===+==========+
| 0x0000 | RESERVED | - | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0001 | basic | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0002 | x509 | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x0A0A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x1A1A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x2A2A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x3A3A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x4A4A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x5A5A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x6A6A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x7A7A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x8A8A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0x9A9A | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0xAAAA | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0xBABA | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0xCACA | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0xDADA | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0xEAEA | GREASE | Y | RFC 9420 |
+-----------------+--------------------------+---+----------+
| 0xF000 - 0xFFFF | Reserved for Private Use | - | RFC 9420 |
+-----------------+--------------------------+---+----------+
Table 11: MLS Credential Types Registry17.6. MLS Signature Labels โ๏ธ
so the SignWithLabel function from Section 5.1.2 is there to stop signatures from different contexts getting mixed up ๐ โโ๏ธ every context gets its own distinct label that gets baked into the signature. the "MLS Signature Labels" registry records the labels defined in this document, and it lets extra labels be registered too, in case extensions add other kinds of signatures using the same signature keys that MLS already uses elsewhere ๐
Template:
Label: the string to be used as the Label parameter to SignWithLabelRecommended: same as in Section 17.1Reference: the document where this label is defined
Initial contents:
+====================+===+==========+
| Label | R | Ref |
+====================+===+==========+
| "FramedContentTBS" | Y | RFC 9420 |
+--------------------+---+----------+
| "LeafNodeTBS" | Y | RFC 9420 |
+--------------------+---+----------+
| "KeyPackageTBS" | Y | RFC 9420 |
+--------------------+---+----------+
| "GroupInfoTBS" | Y | RFC 9420 |
+--------------------+---+----------+
Table 12: MLS Signature Labels
Registry17.7. MLS Public Key Encryption Labels ๐
same energy as the signature labels, but for encryption ๐ซถ the EncryptWithLabel function from Section 5.1.3 avoids mixing up ciphertexts that were made for different purposes in different contexts. each context gets a distinct label that is incorporated into the signature. the "MLS Public Key Encryption Labels" registry records the labels defined in this document and allows additional labels to be registered in case extensions add other types of public key encryption using the same HPKE keys used elsewhere in MLS ๐ฆ
Template:
Label: the string to be used as the Label parameter to EncryptWithLabelRecommended: same as in Section 17.1Reference: the document where this label is defined
Initial contents:
+==================+===+==========+
| Label | R | Ref |
+==================+===+==========+
| "UpdatePathNode" | Y | RFC 9420 |
+------------------+---+----------+
| "Welcome" | Y | RFC 9420 |
+------------------+---+----------+
Table 13: MLS Public Key
Encryption Labels Registry17.8. MLS Exporter Labels ๐ธ
the exporter function from Section 8.5 lets applications pull key material out of the MLS key schedule ๐ just like the TLS exporter [RFC8446], the MLS exporter uses a label to keep different applications' uses of it separate. the "MLS Exporter Labels" registry lets applications register their usage so nobody collides ๐
Template:
Label: the string to be used as the Label parameter to MLS-ExporterRecommended: same as in Section 17.1Reference: the document where this label is defined
This registry has no initial contents, since it's meant for applications to use, not the core protocol ๐ the table below only shows the column layout:
+=======+=============+===========+
| Label | Recommended | Reference |
+=======+=============+===========+
| (N/A) | (N/A) | (N/A) |
+-------+-------------+-----------+
Table 14: MLS Exporter Labels
Registry17.9. MLS Designated Expert Pool ๐
okay this is the review squad ๐ง Specification Required [RFC8126] registry requests get registered after a three-week review period on the MLS Designated Expert (DE) mailing list <mailto:mls-reg-review@ietf.org>, based on the advice of one or more of the MLS DEs. BUT, to allow values to be allocated before publication, the MLS DEs may approve registration once they're satisfied that such a specification will be published โจ
Registration requests sent to the MLS DEs' mailing list for review SHOULD use an appropriate subject (for example, "Request to register value in MLS Bar registry") ๐
Within the review period, the MLS DEs will either approve or deny the registration request, and they'll tell the MLS DEs' mailing list and IANA what they decided. Denials SHOULD include an explanation and, if it applies, suggestions for how to make the request work ๐ If a request sits undetermined for longer than 21 days, it can be brought to the IESG's attention for resolution using the <mailto:iesg@ietf.org> mailing list ๐
The criteria that SHOULD be applied by the MLS DEs include checking whether the proposed registration duplicates existing functionality, whether it's likely to be of general applicability or only useful for a single application, and whether the registration description is clear ๐ง For example, for cipher suite registrations, the MLS DEs will apply the advisory found in Section 17.1.
IANA MUST only accept registry updates from the MLS DEs, and IANA SHOULD direct all requests for registration to the MLS DEs' mailing list ๐ซ
It's suggested that multiple MLS DEs who can represent the perspectives of different applications using this specification be appointed, so the review is broadly informed ๐ซถ And if a registration decision could look like a conflict of interest for a particular MLS DE, that MLS DE SHOULD defer to the judgment of the other MLS DEs ๐ฆ
17.10. The "message/mls" Media Type ๐
this document registers the "message/mls" media type in the "message" registry so other protocols (for example, HTTP [RFC9113]) can carry MLS messages ๐จ here's the full registration, verbatim:
Type name: message
Subtype name: mls
Required parameters: none
Optional parameters: version
version: The MLS protocol version expressed as
a string <major>.<minor>. If omitted, the version is "1.0",
which corresponds to MLS ProtocolVersion mls10. If for some
reason the version number in the media type parameter differs
from the ProtocolVersion embedded in the protocol, the protocol
takes precedence.
Encoding considerations: MLS messages are represented using the TLS
presentation language [RFC8446]. Therefore, MLS messages need to
be treated as binary data.
Security considerations: MLS is an encrypted messaging layer
designed to be transmitted over arbitrary lower-layer protocols.
The security considerations in this document (RFC 9420) also
apply.
Interoperability considerations: N/A
Published specification: RFC 9420
Applications that use this media type: MLS-based messaging
applications
Fragment identifier considerations: N/A
Additional information:
Deprecated alias names for this type: N/A
Magic number(s): N/A
File extension(s): N/A
Macintosh file type code(s): N/A
Person & email address to contact for further information: IETF MLS
Working Group <mailto:mls@ietf.org>
Intended usage: COMMON
Restrictions on usage: N/A
Author: IETF MLS Working Group
Change controller: IETF18. References โจ
18.1. Normative References
okay so these are the references you need to read if you want to implement this, no cap ๐๐ the spec leans on them for real, so they're not optional vibes.
[RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
Hashing for Message Authentication", RFC 2104,
DOI 10.17487/RFC2104, February 1997,
<https://www.rfc-editor.org/info/rfc2104>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for
Writing an IANA Considerations Section in RFCs", BCP 26,
RFC 8126, DOI 10.17487/RFC8126, June 2017,
<https://www.rfc-editor.org/info/rfc8126>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
<https://www.rfc-editor.org/info/rfc8446>.
[RFC9180] Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid
Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180,
February 2022, <https://www.rfc-editor.org/info/rfc9180>.18.2. Informative References
these ones are the extra reading, the deep-dive stuff that's super worth a look if you're obsessed with how this all works ๐๐ธ they're not required to implement it, but they're giving context and I love that for us ๐ซถ
[ART] Cohn-Gordon, K., Cremers, C., Garratt, L., Millican, J.,
and K. Milner, "On Ends-to-Ends Encryption: Asynchronous
Group Messaging with Strong Security Guarantees", Version
2.3, DOI 10.1145/3243734.3243747, March 2020,
<https://eprint.iacr.org/2017/666.pdf>.
[CFRG-AEAD-LIMITS]
Gรผnther, F., Thomson, M., and C. A. Wood, "Usage Limits on
AEAD Algorithms", Work in Progress, Internet-Draft, draft-
irtf-cfrg-aead-limits-07, 31 May 2023,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
aead-limits-07>.
[CLINIC] Miller, B., Huang, L., Joseph, A., and J. Tygar, "I Know
Why You Went to the Clinic: Risks and Realization of HTTPS
Traffic Analysis", Privacy Enhancing Technologies, pp.
143-163, DOI 10.1007/978-3-319-08506-7_8, 2014,
<https://doi.org/10.1007/978-3-319-08506-7_8>.
[CONIKS] Melara, M. S., Blankstein, A., Bonneau, J., Felten, E. W.,
and M. J. Freedman, "CONIKS: Bringing Key Transparency to
End Users", Proceedings of the 24th USENIX Security
Symposium, ISBN 978-1-939133-11-3, August 2015,
<https://www.usenix.org/system/files/conference/
usenixsecurity15/sec15-paper-melara.pdf>.
[DoubleRatchet]
Cohn-Gordon, K., Cremers, C., Dowling, B., Garratt, L.,
and D. Stebila, "A Formal Security Analysis of the Signal
Messaging Protocol", 2017 IEEE European Symposium on
Security and Privacy (EuroS&P),
DOI 10.1109/eurosp.2017.27, April 2017,
<https://doi.org/10.1109/eurosp.2017.27>.
[HCJ16] Husรกk, M., ฤermรกk, M., Jirsรญk, T., and P. ฤeleda, "HTTPS
traffic analysis and client identification using passive
SSL/TLS fingerprinting", EURASIP Journal on Information
Security, Vol. 2016, Issue 1,
DOI 10.1186/s13635-016-0030-7, February 2016,
<https://doi.org/10.1186/s13635-016-0030-7>.
[KT] "Key Transparency Design Doc", commit fb0f87f, June 2020,
<https://github.com/google/keytransparency/blob/master/
docs/design.md>.
[MLS-ARCH] Beurdouche, B., Rescorla, E., Omara, E., Inguva, S., and
A. Duric, "The Messaging Layer Security (MLS)
Architecture", Work in Progress, Internet-Draft, draft-
ietf-mls-architecture-10, 16 December 2022,
<https://datatracker.ietf.org/doc/html/draft-ietf-mls-
architecture-10>.
[NAN] Bellare, M., Ng, R., and B. Tackmann, "Nonces Are Noticed:
AEAD Revisited", Advances in Cryptology - CRYPTO 2019, pp.
235-265, DOI 10.1007/978-3-030-26948-7_9, August 2019,
<https://doi.org/10.1007/978-3-030-26948-7_9>.
[RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated
Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008,
<https://www.rfc-editor.org/info/rfc5116>.
[RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch,
"Network Time Protocol Version 4: Protocol and Algorithms
Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010,
<https://www.rfc-editor.org/info/rfc5905>.
[RFC6125] Saint-Andre, P. and J. Hodges, "Representation and
Verification of Domain-Based Application Service Identity
within Internet Public Key Infrastructure Using X.509
(PKIX) Certificates in the Context of Transport Layer
Security (TLS)", RFC 6125, DOI 10.17487/RFC6125, March
2011, <https://www.rfc-editor.org/info/rfc6125>.
[RFC7696] Housley, R., "Guidelines for Cryptographic Algorithm
Agility and Selecting Mandatory-to-Implement Algorithms",
BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015,
<https://www.rfc-editor.org/info/rfc7696>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>.
[RFC8701] Benjamin, D., "Applying Generate Random Extensions And
Sustain Extensibility (GREASE) to TLS Extensibility",
RFC 8701, DOI 10.17487/RFC8701, January 2020,
<https://www.rfc-editor.org/info/rfc8701>.
[RFC9000] Iyengar, J., Ed. and M. Thomson, Ed., "QUIC: A UDP-Based
Multiplexed and Secure Transport", RFC 9000,
DOI 10.17487/RFC9000, May 2021,
<https://www.rfc-editor.org/info/rfc9000>.
[RFC9001] Thomson, M., Ed. and S. Turner, Ed., "Using TLS to Secure
QUIC", RFC 9001, DOI 10.17487/RFC9001, May 2021,
<https://www.rfc-editor.org/info/rfc9001>.
[RFC9113] Thomson, M., Ed. and C. Benfield, Ed., "HTTP/2", RFC 9113,
DOI 10.17487/RFC9113, June 2022,
<https://www.rfc-editor.org/info/rfc9113>.
[SHS] National Institute of Standards and Technology (NIST),
"Secure Hash Standard (SHS)", FIPS PUB 180-4,
DOI 10.6028/NIST.FIPS.180-4, August 2015,
<https://doi.org/10.6028/NIST.FIPS.180-4>.
[Signal] Perrin(ed), T. and M. Marlinspike, "The Double Ratchet
Algorithm", Revision 1, November 2016,
<https://www.signal.org/docs/specifications/
doubleratchet/>.Appendix A. Protocol Origins of Example Trees ๐
okay this appendix is a little treasure map ๐บ๏ธโจ MLS operations are what create the specific ratchet tree shapes you see in the examples, and they usually touch a whole direct path at once ๐ this section walks through which operations could have produced each example tree in the document, so you can literally trace the drama step by step ๐
To construct the tree in Figure 11:
- A creates a group with B, ..., G
- F sends an empty Commit, setting X, Y, and W
- G removes C and D, blanking V, U, and setting Y and W
- B sends an empty Commit, setting T and W
To construct the tree in Figure 10:
- A creates a group with B, ..., H, as well as some members outside this subtree
- F sends an empty Commit, setting Y and its ancestors
- D removes B and C, with the following effects:
- Blank the direct paths of B and C
- Set X, the top node, and any further nodes in the direct path of D
- Someone outside this subtree removes G, blanking the direct path of G
- A adds a new member at B with a partial Commit, adding B as unmerged at X
To construct the tree in Figure 13:
- A creates a group with B, C, and D
- B sends a full Commit, setting X and Y
- D removes C, setting Z and Y
- B adds a new member at C with a full Commit
- The Add proposal adds C as unmerged at Z and Y
- The path in the Commit resets X and Y, clearing Y's unmerged leaves
To construct the tree in Figure 21:
- A creates a group with B, ..., G
- A removes F in a full Commit, setting T, U, and W
- E sends an empty Commit, setting Y and W
- A adds a new member at F in a partial Commit, adding F as unmerged at Y and W
Appendix B. Evolution of Parent Hashes โจ
okay bestie, let's watch parent hashes glow up in a small group ๐ธ we'll follow this sequence of operations:
- A initializes a new group
- A adds B to the group with a full Commit
- B adds C and D to the group with a full Commit
- C sends an empty Commit
Y Y'
| |
.-+-. .-+-.
==> ==> / \ ==> / \
X X' _=Z X' Z'
/ \ / \ / \ / \ / \
A A B A B C D A B C DFigure 30: Building a Four-Member Tree to Illustrate Parent Hashes
Now the parent hashes on the nodes update like this ๐ (we're using ph for parent hash, th for tree hash, and osth for original sibling tree hash):
- A adds B: set X
- A.parent_hash = ph(X) =
H(X, ph="", osth=th(B))
- A.parent_hash = ph(X) =
- B adds C, D: set B', X', and Y
- X'.parent_hash = ph(Y) =
H(Y, ph="", osth=th(Z)), where th(Z) covers (C, _, D) - B'.parent_hash = ph(X') =
H(X', ph=X'.parent_hash, osth=th(A))
- X'.parent_hash = ph(Y) =
- C sends empty Commit: set C', Z', Y'
- Z'.parent_hash = ph(Y') =
H(Y', ph="", osth=th(X')), where th(X') covers (A, X', B') - C'.parent_hash = ph(Z') =
H(Z', ph=Z'.parent_hash, osth=th(D))
- Z'.parent_hash = ph(Y') =
When a new member joins, they get a tree with these parent hash values and check the validity relationships below ๐ง
+======+======================================+=====================+
| Node | Parent Hash Value | Valid? |
+======+======================================+=====================+
| A | H(X, ph="", osth=th(B)) | No, B changed |
+------+--------------------------------------+---------------------+
| B' | H(X', ph=X'.parent_hash, osth=th(A)) | Yes |
+------+--------------------------------------+---------------------+
| C' | H(Z', ph=Z'.parent_hash, osth=th(D)) | Yes |
+------+--------------------------------------+---------------------+
| D | (none, never sent an UpdatePath) | N/A |
+------+--------------------------------------+---------------------+
| X' | H(Y, ph="", osth=th(Z)) | No, Y and Z |
| | | changed |
+------+--------------------------------------+---------------------+
| Z' | H(Y', ph="", osth=th(X')) | Yes |
+------+--------------------------------------+---------------------+Table 15
So the joiner ends up with these path-hash links in the tree:
Y'
|
+-.
\
X' Z'
\ /
A B' C' DFigure 31: Parent-hash links connect all non-empty parent nodes to leaves
These chains together cover every non-blank parent node in the tree, so the tree is parent-hash valid ๐
Here's the tea though: this tree is valid, but it still has invalid parent-hash links ๐ If a client checks parent hashes top-down from Y', they'd find that X' has an invalid parent hash relative to Y', but that Z' has a valid one. If the client checks bottom-up instead, the chain from B' ends in an invalid link from X' to Y'. These invalid links are just the natural result of multiple clients having committed ๐
Also, look at how the tree hash and the parent hash interact ๐ฆ The parent hash of node C' includes the tree hash of node D. The parent hash of node Z' includes the tree hash of X', which covers nodes A and B' (including the parent hash of B'). Even though the tree hash and the parent hash depend on each other, the dependencies are structured so there's never a circular dependency. iconic, honestly.
In the special case where a new member first receives the tree for a group (for example, in a ratchet tree GroupInfo extension Section 12.4.3.3), the parent hashes are expressed in the tree representation, but the tree hash doesn't have to be. Instead, the new member recomputes the tree hashes for all the nodes in the tree and checks that they match the tree hash in the GroupInfo object. If the tree is valid, the subtree hashes computed this way line up with the inputs needed for parent hash validation, except where recomputation is needed to account for unmerged leaves โจ
Appendix C. Array-Based Trees ๐
One benefit of complete balanced trees is that they admit a simple flat array representation, and it's so clean ๐ญ In this representation, leaf nodes are even-numbered nodes, with the n-th leaf at 2*n. Intermediate nodes live in the odd-numbered nodes. For example, the tree with 8 leaves looks like this:
X
|
.---------+---------.
/ \
X X
| |
.---+---. .---+---.
/ \ / \
X X X X
/ \ / \ / \ / \
/ \ / \ / \ / \
X X X X X X X X
Node: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Leaf: 0 1 2 3 4 5 6 7Figure 32: An Eight-Member Tree Represented as an Array
This lets us compute relationships between tree nodes just by manipulating indices, instead of maintaining complicated structures in memory ๐ง The basic rule is that the high-order bits of parent and child node indices have the following relation (where x is an arbitrary bit string):
parent=01x => left=00x, right=10xSince node relationships are implicit, the algorithms for adding and removing nodes at the right edge of the tree are super simple. If there are N nodes in the array:
- Add: Append N + 1 blank values to the end of the array.
- Remove: Truncate the array to its first (N-1) / 2 entries.
The Python code below shows the tree computations needed to use an array-based tree for MLS. Let's go, bestie ๐ซถ
# The exponent of the largest power of 2 less than x. Equivalent to:
# int(math.floor(math.log(x, 2)))
def log2(x):
if x == 0:
return 0
k = 0
while (x >> k) > 0:
k += 1
return k-1
# The level of a node in the tree. Leaves are level 0, their parents
# are level 1, etc. If a node's children are at different levels,
# then its level is the max level of its children plus one.
def level(x):
if x & 0x01 == 0:
return 0
k = 0
while ((x >> k) & 0x01) == 1:
k += 1
return k
# The number of nodes needed to represent a tree with n leaves.
def node_width(n):
if n == 0:
return 0
else:
return 2*(n - 1) + 1
# The index of the root node of a tree with n leaves.
def root(n):
w = node_width(n)
return (1 << log2(w)) - 1
# The left child of an intermediate node.
def left(x):
k = level(x)
if k == 0:
raise Exception('leaf node has no children')
return x ^ (0x01 << (k - 1))
# The right child of an intermediate node.
def right(x):
k = level(x)
if k == 0:
raise Exception('leaf node has no children')
return x ^ (0x03 << (k - 1))
# The parent of a node.
def parent(x, n):
if x == root(n):
raise Exception('root node has no parent')
k = level(x)
b = (x >> (k + 1)) & 0x01
return (x | (1 << k)) ^ (b << (k + 1))
# The other child of the node's parent.
def sibling(x, n):
p = parent(x, n)
if x < p:
return right(p)
else:
return left(p)
# The direct path of a node, ordered from leaf to root.
def direct_path(x, n):
r = root(n)
if x == r:
return []
d = []
while x != r:
x = parent(x, n)
d.append(x)
return d
# The copath of a node, ordered from leaf to root.
def copath(x, n):
if x == root(n):
return []
d = direct_path(x, n)
d.insert(0, x)
d.pop()
return [sibling(y, n) for y in d]
# The common ancestor of two nodes is the lowest node that is in the
# direct paths of both leaves.
def common_ancestor_semantic(x, y, n):
dx = set([x]) | set(direct_path(x, n))
dy = set([y]) | set(direct_path(y, n))
dxy = dx & dy
if len(dxy) == 0:
raise Exception('failed to find common ancestor')
return min(dxy, key=level)
# The common ancestor of two nodes is the lowest node that is in the
# direct paths of both leaves.
def common_ancestor_direct(x, y, _):
# Handle cases where one is an ancestor of the other
lx, ly = level(x)+1, level(y)+1
if (lx <= ly) and (x>>ly == y>>ly):
return y
elif (ly <= lx) and (x>>lx == y>>lx):
return x
# Handle other cases
xn, yn = x, y
k = 0
while xn != yn:
xn, yn = xn >> 1, yn >> 1
k += 1
return (xn << k) + (1 << (k-1)) - 1Appendix D. Link-Based Trees ๐ฆ
An implementation can choose to store ratchet trees in a "link-based" representation, where each node stores references to its parents and/or children. This is different from the array-based representation above, where those relationships get computed from the relationships between nodes' indices in the array. An implementation like this needs to update those links to keep the tree balanced as it gets extended to add new members or truncated when members are removed ๐ธ
The code snippet below shows how these algorithms could be implemented in Python:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value # Value of the node
self.left = left # Left child node
self.right = right # Right child node
@staticmethod
def blank_subtree(depth):
if depth == 1:
return Node(None)
L = Node.blank_subtree(depth-1)
R = Node.blank_subtree(depth-1)
return Node(None, left=L, right=R)
def empty(self):
L_empty = (self.left == None) or self.left.empty()
R_empty = (self.right == None) or self.right.empty()
return (self.value == None) and L_empty and R_empty
class Tree:
def __init__(self):
self.depth = 0 # Depth of the tree
self.root = None # Root node of the tree, initially empty
# Add a blank subtree to the right
def extend(self):
if self.depth == 0:
self.depth = 1
self.root = Node(None)
L = self.root
R = Node.blank_subtree(self.depth)
self.root = Node(None, left=L, right=R)
self.depth += 1
# Truncate the right subtree
def truncate(self):
if self.root == None:
return
if not self.root.right.empty():
raise Exception("Cannot truncate non-blank subtree")
self.depth -= 1
self.root = self.root.leftContributors ๐ธ
okay bestie, these are the amazing humans who helped cook this spec and deserve all the flowers ๐๐ซถ
- Joel Alwen, Amazon, Email:
alwenjo@amazon.com - Karthikeyan Bhargavan, Inria, Email:
karthikeyan.bhargavan@inria.fr - Cas Cremers, CISPA, Email:
cremers@cispa.de - Alan Duric, Wire, Email:
alan@wire.com - Britta Hale, Naval Postgraduate School, Email:
britta.hale@nps.edu - Srinivas Inguva, Email:
singuva@yahoo.com - Konrad Kohbrok, Phoenix R&D, Email:
konrad.kohbrok@datashrine.de - Albert Kwon, MIT, Email:
kwonal@mit.edu - Tom Leavy, Amazon, Email:
tomleavy@amazon.com - Brendan McMillion, Email:
brendanmcmillion@gmail.com - Marta Mularczyk, Amazon, Email:
mulmarta@amazon.com - Eric Rescorla, Mozilla, Email:
ekr@rtfm.com - Michael Rosenberg, Trail of Bits, Email:
michael.rosenberg@trailofbits.com - Thรฉophile Wallez, Inria, Email:
theophile.wallez@inria.fr - Thyla van der Merwe, Royal Holloway, University of London, Email:
tjvdmerwe@gmail.com
Authors' Addresses ๐ฆ
and these are the authors, the main characters who brought the whole thing to life ๐โจ
- Richard Barnes, Cisco, Email:
rlb@ipv.sx - Benjamin Beurdouche, Inria & Mozilla, Email:
ietf@beurdouche.com - Raphael Robert, Phoenix R&D, Email:
ietf@raphaelrobert.com - Jon Millican, Meta Platforms, Email:
jmillican@meta.com - Emad Omara, Email:
emad.omara@gmail.com - Katriel Cohn-Gordon, University of Oxford, Email:
me@katriel.co.uk
that's the whole spec, babe, we did it ๐๐
๐ฆ where this page comes from
- ietf: rfc9420 2023-07
- ๐ girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms