idnits 2.17.1 draft-ietf-mls-protocol-14.txt: -(5379): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There is 1 instance of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (3 May 2022) is 717 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'C' is mentioned on line 2142, but not defined == Missing Reference: 'Z' is mentioned on line 1261, but not defined == Missing Reference: 'A' is mentioned on line 1261, but not defined -- Looks like a reference, but probably isn't: '16' on line 1347 -- Looks like a reference, but probably isn't: '0' on line 4401 -- Looks like a reference, but probably isn't: '4' on line 1778 -- Looks like a reference, but probably isn't: '1' on line 2278 == Missing Reference: 'F' is mentioned on line 2387, but not defined == Missing Reference: 'R' is mentioned on line 4412, but not defined ** Obsolete normative reference: RFC 7540 (Obsoleted by RFC 9113) == Outdated reference: A later version (-13) exists of draft-ietf-mls-architecture-07 -- Obsolete informational reference (is this intentional?): RFC 6125 (Obsoleted by RFC 9525) Summary: 1 error (**), 0 flaws (~~), 8 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group R. Barnes 3 Internet-Draft Cisco 4 Intended status: Informational B. Beurdouche 5 Expires: 4 November 2022 Inria & Mozilla 6 R. Robert 8 J. Millican 9 Facebook 10 E. Omara 11 Google 12 K. Cohn-Gordon 13 University of Oxford 14 3 May 2022 16 The Messaging Layer Security (MLS) Protocol 17 draft-ietf-mls-protocol-14 19 Abstract 21 Messaging applications are increasingly making use of end-to-end 22 security mechanisms to ensure that messages are only accessible to 23 the communicating endpoints, and not to any servers involved in 24 delivering messages. Establishing keys to provide such protections 25 is challenging for group chat settings, in which more than two 26 clients need to agree on a key but may not be online at the same 27 time. In this document, we specify a key establishment protocol that 28 provides efficient asynchronous group key establishment with forward 29 secrecy and post-compromise security for groups in size ranging from 30 two to thousands. 32 Discussion Venues 34 This note is to be removed before publishing as an RFC. 36 Source for this draft and an issue tracker can be found at 37 https://github.com/mlswg/mls-protocol (https://github.com/mlswg/mls- 38 protocol). 40 Status of This Memo 42 This Internet-Draft is submitted in full conformance with the 43 provisions of BCP 78 and BCP 79. 45 Internet-Drafts are working documents of the Internet Engineering 46 Task Force (IETF). Note that other groups may also distribute 47 working documents as Internet-Drafts. The list of current Internet- 48 Drafts is at https://datatracker.ietf.org/drafts/current/. 50 Internet-Drafts are draft documents valid for a maximum of six months 51 and may be updated, replaced, or obsoleted by other documents at any 52 time. It is inappropriate to use Internet-Drafts as reference 53 material or to cite them other than as "work in progress." 55 This Internet-Draft will expire on 4 November 2022. 57 Copyright Notice 59 Copyright (c) 2022 IETF Trust and the persons identified as the 60 document authors. All rights reserved. 62 This document is subject to BCP 78 and the IETF Trust's Legal 63 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 64 license-info) in effect on the date of publication of this document. 65 Please review these documents carefully, as they describe your rights 66 and restrictions with respect to this document. Code Components 67 extracted from this document must include Revised BSD License text as 68 described in Section 4.e of the Trust Legal Provisions and are 69 provided without warranty as described in the Revised BSD License. 71 Table of Contents 73 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 74 1.1. Change Log . . . . . . . . . . . . . . . . . . . . . . . 5 75 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 11 76 2.1. Presentation Langauge . . . . . . . . . . . . . . . . . . 12 77 2.1.1. Optional Value . . . . . . . . . . . . . . . . . . . 12 78 2.1.2. Variable-size Vector Headers . . . . . . . . . . . . 13 79 3. Operating Context . . . . . . . . . . . . . . . . . . . . . . 15 80 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 15 81 4.1. Cryptographic State and Evolution . . . . . . . . . . . . 16 82 4.2. Example Protocol Execution . . . . . . . . . . . . . . . 18 83 4.3. Relationships Between Epochs . . . . . . . . . . . . . . 22 84 5. Ratchet Tree Concepts . . . . . . . . . . . . . . . . . . . . 23 85 5.1. Ratchet Tree Terminology . . . . . . . . . . . . . . . . 24 86 5.2. Views of a Ratchet Tree . . . . . . . . . . . . . . . . . 25 87 5.3. Ratchet Tree Nodes . . . . . . . . . . . . . . . . . . . 27 88 6. Cryptographic Objects . . . . . . . . . . . . . . . . . . . . 29 89 6.1. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . 29 90 6.2. Hash-Based Identifiers . . . . . . . . . . . . . . . . . 30 91 6.3. Credentials . . . . . . . . . . . . . . . . . . . . . . . 31 92 6.3.1. Uniquely Identifying Clients . . . . . . . . . . . . 32 93 7. Message Framing . . . . . . . . . . . . . . . . . . . . . . . 33 94 7.1. Content Authentication . . . . . . . . . . . . . . . . . 35 95 7.2. Encoding and Decoding a Plaintext . . . . . . . . . . . . 37 96 7.3. Encoding and Decoding a Ciphertext . . . . . . . . . . . 37 97 7.3.1. Content Encryption . . . . . . . . . . . . . . . . . 38 98 7.3.2. Sender Data Encryption . . . . . . . . . . . . . . . 39 99 8. Ratchet Tree Operations . . . . . . . . . . . . . . . . . . . 40 100 8.1. Parent Node Contents . . . . . . . . . . . . . . . . . . 40 101 8.2. Leaf Node Contents . . . . . . . . . . . . . . . . . . . 41 102 8.3. Leaf Node Validation . . . . . . . . . . . . . . . . . . 44 103 8.4. Ratchet Tree Evolution . . . . . . . . . . . . . . . . . 45 104 8.5. Adding and Removing Leaves . . . . . . . . . . . . . . . 47 105 8.6. Synchronizing Views of the Tree . . . . . . . . . . . . . 49 106 8.7. Tree Hashes . . . . . . . . . . . . . . . . . . . . . . . 51 107 8.8. Parent Hash . . . . . . . . . . . . . . . . . . . . . . . 51 108 8.8.1. Using Parent Hashes . . . . . . . . . . . . . . . . . 54 109 8.8.2. Verifying Parent Hashes . . . . . . . . . . . . . . . 54 110 8.9. Update Paths . . . . . . . . . . . . . . . . . . . . . . 55 111 9. Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . 56 112 9.1. Group Context . . . . . . . . . . . . . . . . . . . . . . 58 113 9.2. Transcript Hashes . . . . . . . . . . . . . . . . . . . . 60 114 9.3. External Initialization . . . . . . . . . . . . . . . . . 61 115 9.4. Pre-Shared Keys . . . . . . . . . . . . . . . . . . . . . 61 116 9.5. Exporters . . . . . . . . . . . . . . . . . . . . . . . . 64 117 9.6. Resumption PSK . . . . . . . . . . . . . . . . . . . . . 65 118 9.7. Epoch Authenticators . . . . . . . . . . . . . . . . . . 65 119 10. Secret Tree . . . . . . . . . . . . . . . . . . . . . . . . . 66 120 10.1. Encryption Keys . . . . . . . . . . . . . . . . . . . . 66 121 10.2. Deletion Schedule . . . . . . . . . . . . . . . . . . . 67 122 11. Key Packages . . . . . . . . . . . . . . . . . . . . . . . . 69 123 11.1. KeyPackage Validation . . . . . . . . . . . . . . . . . 71 124 11.2. KeyPackage Identifiers . . . . . . . . . . . . . . . . . 71 125 12. Group Creation . . . . . . . . . . . . . . . . . . . . . . . 71 126 12.1. Required Capabilities . . . . . . . . . . . . . . . . . 73 127 12.2. Reinitialization . . . . . . . . . . . . . . . . . . . . 73 128 12.3. Sub-group Branching . . . . . . . . . . . . . . . . . . 74 129 13. Group Evolution . . . . . . . . . . . . . . . . . . . . . . . 75 130 13.1. Proposals . . . . . . . . . . . . . . . . . . . . . . . 76 131 13.1.1. Add . . . . . . . . . . . . . . . . . . . . . . . . 76 132 13.1.2. Update . . . . . . . . . . . . . . . . . . . . . . . 77 133 13.1.3. Remove . . . . . . . . . . . . . . . . . . . . . . . 77 134 13.1.4. PreSharedKey . . . . . . . . . . . . . . . . . . . . 78 135 13.1.5. ReInit . . . . . . . . . . . . . . . . . . . . . . . 78 136 13.1.6. ExternalInit . . . . . . . . . . . . . . . . . . . . 79 137 13.1.7. AppAck . . . . . . . . . . . . . . . . . . . . . . . 79 138 13.1.8. GroupContextExtensions . . . . . . . . . . . . . . . 80 139 13.1.9. External Proposals . . . . . . . . . . . . . . . . . 81 140 13.2. Commit . . . . . . . . . . . . . . . . . . . . . . . . . 82 141 13.2.1. Creating a Commit . . . . . . . . . . . . . . . . . 85 142 13.2.2. Processing a Commit . . . . . . . . . . . . . . . . 88 143 13.2.3. Adding Members to the Group . . . . . . . . . . . . 90 144 13.3. Ratchet Tree Extension . . . . . . . . . . . . . . . . . 96 145 14. Extensibility . . . . . . . . . . . . . . . . . . . . . . . . 99 146 14.1. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . 99 147 14.2. Proposals . . . . . . . . . . . . . . . . . . . . . . . 100 148 14.3. Credential Extensibility . . . . . . . . . . . . . . . . 100 149 15. Sequencing of State Changes . . . . . . . . . . . . . . . . . 102 150 15.1. Server-Enforced Ordering . . . . . . . . . . . . . . . . 103 151 15.2. Client-Enforced Ordering . . . . . . . . . . . . . . . . 103 152 16. Application Messages . . . . . . . . . . . . . . . . . . . . 104 153 16.1. Message Encryption and Decryption . . . . . . . . . . . 104 154 16.2. Restrictions . . . . . . . . . . . . . . . . . . . . . . 105 155 16.3. Delayed and Reordered Application messages . . . . . . . 105 156 17. Security Considerations . . . . . . . . . . . . . . . . . . . 105 157 17.1. Confidentiality of the Group Secrets . . . . . . . . . . 106 158 17.2. Authentication . . . . . . . . . . . . . . . . . . . . . 106 159 17.3. Forward Secrecy and Post-Compromise Security . . . . . . 107 160 17.4. KeyPackage Reuse . . . . . . . . . . . . . . . . . . . . 107 161 17.5. Group Fragmentation by Malicious Insiders . . . . . . . 108 162 18. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 108 163 18.1. MLS Ciphersuites . . . . . . . . . . . . . . . . . . . . 109 164 18.2. MLS Extension Types . . . . . . . . . . . . . . . . . . 113 165 18.3. MLS Proposal Types . . . . . . . . . . . . . . . . . . . 114 166 18.4. MLS Credential Types . . . . . . . . . . . . . . . . . . 115 167 18.5. MLS Designated Expert Pool . . . . . . . . . . . . . . . 116 168 18.6. The "message/mls" MIME Type . . . . . . . . . . . . . . 117 169 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 117 170 20. References . . . . . . . . . . . . . . . . . . . . . . . . . 118 171 20.1. Normative References . . . . . . . . . . . . . . . . . . 118 172 20.2. Informative References . . . . . . . . . . . . . . . . . 119 173 Appendix A. Protocol Origins of Example Trees . . . . . . . . . 121 174 Appendix B. Array-Based Trees . . . . . . . . . . . . . . . . . 122 175 Appendix C. Link-Based Trees . . . . . . . . . . . . . . . . . . 126 176 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 128 178 1. Introduction 180 DISCLAIMER: This is a work-in-progress draft of MLS and has not yet 181 seen significant security analysis. It should not be used as a basis 182 for building production systems. 184 RFC EDITOR: PLEASE REMOVE THE FOLLOWING PARAGRAPH The source for this 185 draft is maintained in GitHub. Suggested changes should be submitted 186 as pull requests at https://github.com/mlswg/mls-protocol. 187 Instructions are on that page as well. Editorial changes can be 188 managed in GitHub, but any substantive change should be discussed on 189 the MLS mailing list. 191 A group of users who want to send each other encrypted messages needs 192 a way to derive shared symmetric encryption keys. For two parties, 193 this problem has been studied thoroughly, with the Double Ratchet 194 emerging as a common solution [doubleratchet] [signal]. Channels 195 implementing the Double Ratchet enjoy fine-grained forward secrecy as 196 well as post-compromise security, but are nonetheless efficient 197 enough for heavy use over low-bandwidth networks. 199 For a group of size greater than two, a common strategy is to 200 unilaterally broadcast symmetric "sender" keys over existing shared 201 symmetric channels, and then for each member to send messages to the 202 group encrypted with their own sender key. Unfortunately, while this 203 improves efficiency over pairwise broadcast of individual messages 204 and provides forward secrecy (with the addition of a hash ratchet), 205 it is difficult to achieve post-compromise security with sender keys. 206 An adversary who learns a sender key can often indefinitely and 207 passively eavesdrop on that member's messages. Generating and 208 distributing a new sender key provides a form of post-compromise 209 security with regard to that sender. However, it requires 210 computation and communications resources that scale linearly with the 211 size of the group. 213 In this document, we describe a protocol based on tree structures 214 that enable asynchronous group keying with forward secrecy and post- 215 compromise security. Based on earlier work on "asynchronous 216 ratcheting trees" [art], the protocol presented here uses an 217 asynchronous key-encapsulation mechanism for tree structures. This 218 mechanism allows the members of the group to derive and update shared 219 keys with costs that scale as the log of the group size. 221 1.1. Change Log 223 RFC EDITOR PLEASE DELETE THIS SECTION. 225 draft-13 227 * TLS syntax updates (including variable-header-length vectors) (*) 229 * Stop generating redundant PKE key pairs. (*) 231 * Move validation of identity change to the AS 233 * Add message/mls MIME type registration 235 * Split LeafNode from KeyPackage (*) 237 * Remove endpoint_id (*) 239 * Reorganize to make section layout more sane 241 * Forbid proposals by reference in external commits (*) 242 * Domain separation for KeyPackage and Proposal references (*) 244 * Downgrade MUST to SHOULD for commit senders including all valid 245 commits 247 * Stronger parent hashes for authenticated identities (*) 249 * Move wire_format to a separate tagged-union structure MLSMessage 251 * Generalize tree extend/truncate algorithms 253 * Add algorithms for link-based trees 255 * Forbid self-Update entirely (*) 257 * Consolidate resumption PSK cases (*) 259 * 384 Ciphersuite Addition 261 * Remove explicit version pin on HPKE (*) 263 * Remove the requirement for Add in external commit (*) 265 * Use smaller, fixed-size hash-based identifiers (*) 267 * Be explicit that Credentials can attest to multiple identities (*) 269 draft-12 271 * Use the GroupContext to derive the joiner_secret (*) 273 * Make PreSharedKeys non optional in GroupSecrets (*) 275 * Update name for this particular key (*) 277 * Truncate tree size on removal (*) 279 * Use HPKE draft-08 (*) 281 * Clarify requirements around identity in MLS groups (*) 283 * Signal the intended wire format for MLS messages (*) 285 * Inject GroupContext as HPKE info instead of AAD (*) 287 * Clarify extension handling and make extension updatable (*) 289 * Improve extensibility of Proposals (*) 290 * Constrain proposal in External Commit (*) 292 * Remove the notion of a 'leaf index' (*) 294 * Add group_context_extensions proposal ID (*) 296 * Add RequiredCapabilities extension (*) 298 * Use cascaded KDF instead of concatenation to consolidate PSKs (*) 300 * Use key package hash to index clients in message structs (*) 302 * Don't require PublicGroupState for external init (*) 304 * Make ratchet tree section clearer. 306 * Handle non-member sender cases in MLSPlaintextTBS 308 * Clarify encoding of signatures with NIST curves 310 * Remove OPEN ISSUEs and TODOs 312 * Normalize the description of the zero vector 314 draft-11 316 * Include subtree keys in parent hash (*) 318 * Pin HPKE to draft-07 (*) 320 * Move joiner secret to the end of the first key schedule epoch (*) 322 * Add an AppAck proposal 324 * Make initializations of transcript hashes consistent 326 draft-10 328 * Allow new members to join via an external Commit (*) 330 * Enable proposals to be sent inline in a Commit (*) 332 * Re-enable constant-time Add (*) 334 * Change expiration extension to lifetime extension (*) 336 * Make the tree in the Welcome optional (*) 337 * PSK injection, re-init, sub-group branching (*) 339 * Require the initial init_secret to be a random value (*) 341 * Remove explicit sender data nonce (*) 343 * Do not encrypt to joiners in UpdatePath generation (*) 345 * Move MLSPlaintext signature under the confirmation tag (*) 347 * Explicitly authenticate group membership with MLSPLaintext (*) 349 * Clarify X509Credential structure (*) 351 * Remove unneeded interim transcript hash from GroupInfo (*) 353 * IANA considerations 355 * Derive an authentication secret 357 * Use Extract/Expand from HPKE KDF 359 * Clarify that application messages MUST be encrypted 361 draft-09 363 * Remove blanking of nodes on Add (*) 365 * Change epoch numbers to uint64 (*) 367 * Add PSK inputs (*) 369 * Add key schedule exporter (*) 371 * Sign the updated direct path on Commit, using "parent hashes" and 372 one signature per leaf (*) 374 * Use structured types for external senders (*) 376 * Redesign Welcome to include confirmation and use derived keys (*) 378 * Remove ignored proposals (*) 380 * Always include an Update with a Commit (*) 382 * Add per-message entropy to guard against nonce reuse (*) 383 * Use the same hash ratchet construct for both application and 384 handshake keys (*) 386 * Add more ciphersuites 388 * Use HKDF to derive key pairs (*) 390 * Mandate expiration of ClientInitKeys (*) 392 * Add extensions to GroupContext and flesh out the extensibility 393 story (*) 395 * Rename ClientInitKey to KeyPackage 397 draft-08 399 * Change ClientInitKeys so that they only refer to one ciphersuite 400 (*) 402 * Decompose group operations into Proposals and Commits (*) 404 * Enable Add and Remove proposals from outside the group (*) 406 * Replace Init messages with multi-recipient Welcome message (*) 408 * Add extensions to ClientInitKeys for expiration and downgrade 409 resistance (*) 411 * Allow multiple Proposals and a single Commit in one MLSPlaintext 412 (*) 414 draft-07 416 * Initial version of the Tree based Application Key Schedule (*) 418 * Initial definition of the Init message for group creation (*) 420 * Fix issue with the transcript used for newcomers (*) 422 * Clarifications on message framing and HPKE contexts (*) 424 draft-06 426 * Reorder blanking and update in the Remove operation (*) 428 * Rename the GroupState structure to GroupContext (*) 430 * Rename UserInitKey to ClientInitKey 431 * Resolve the circular dependency that draft-05 introduced in the 432 confirmation MAC calculation (*) 434 * Cover the entire MLSPlaintext in the transcript hash (*) 436 draft-05 438 * Common framing for handshake and application messages (*) 440 * Handshake message encryption (*) 442 * Convert from literal state to a commitment via the "tree hash" (*) 444 * Add credentials to the tree and remove the "roster" concept (*) 446 * Remove the secret field from tree node values 448 draft-04 450 * Updating the language to be similar to the Architecture document 452 * ECIES is now renamed in favor of HPKE (*) 454 * Using a KDF instead of a Hash in TreeKEM (*) 456 draft-03 458 * Added ciphersuites and signature schemes (*) 460 * Re-ordered fields in UserInitKey to make parsing easier (*) 462 * Fixed inconsistencies between Welcome and GroupState (*) 464 * Added encryption of the Welcome message (*) 466 draft-02 468 * Removed ART (*) 470 * Allowed partial trees to avoid double-joins (*) 472 * Added explicit key confirmation (*) 474 draft-01 476 * Initial description of the Message Protection mechanism. (*) 477 * Initial specification proposal for the Application Key Schedule 478 using the per-participant chaining of the Application Secret 479 design. (*) 481 * Initial specification proposal for an encryption mechanism to 482 protect Application Messages using an AEAD scheme. (*) 484 * Initial specification proposal for an authentication mechanism of 485 Application Messages using signatures. (*) 487 * Initial specification proposal for a padding mechanism to 488 improving protection of Application Messages against traffic 489 analysis. (*) 491 * Inversion of the Group Init Add and Application Secret derivations 492 in the Handshake Key Schedule to be ease chaining in case we 493 switch design. (*) 495 * Removal of the UserAdd construct and split of GroupAdd into Add 496 and Welcome messages (*) 498 * Initial proposal for authenticating handshake messages by signing 499 over group state and including group state in the key schedule (*) 501 * Added an appendix with example code for tree math 503 * Changed the ECIES mechanism used by TreeKEM so that it uses nonces 504 generated from the shared secret 506 draft-00 508 * Initial adoption of draft-barnes-mls-protocol-01 as a WG item. 510 2. Terminology 512 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 513 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 514 "OPTIONAL" in this document are to be interpreted as described in BCP 515 14 [RFC2119] [RFC8174] when, and only when, they appear in all 516 capitals, as shown here. 518 Client: An agent that uses this protocol to establish shared 519 cryptographic state with other clients. A client is defined by 520 the cryptographic keys it holds. 522 Group: A group represents a logical collection of clents that share 523 a common secret value at any given time. Its state is represented 524 as a linear sequence of epochs in which each epoch depends on its 525 predecessor. 527 Epoch: A state of a group in which a specific set of authenticated 528 clients hold shared cryptographic state. 530 Member: A client that is included in the shared state of a group, 531 hence has access to the group's secrets. 533 Key Package: A signed object describing a client's identity and 534 capabilities, and including a hybrid public-key encryption (HPKE 535 [RFC9180]) public key that can be used to encrypt to that client, 536 and which other clients can use to introduce the client to a new 537 group. 539 Signature Key: A signing key pair used to authenticate the sender of 540 a message. 542 Handshake Message: An MLSPlaintext or MLSCiphertext message carrying 543 an MLS Proposal or Commit object, as opposed to application data. 545 Application Message: An MLSCiphertext message carrying application 546 data. 548 Terminology specific to tree computations is described in 549 Section 5.1. 551 In general, symmetric values are referred to as "keys" or "secrets" 552 interchangeably. Either term denotes a value that MUST be kept 553 confidential to a Client. When labelling individual values, we 554 typically use "secret" to refer to a value that is used derive 555 further secret values, and "key" to refer to a value that is used 556 with an algorithm such as HMAC or an AEAD algorithm. 558 2.1. Presentation Langauge 560 We use the TLS presentation language [RFC8446] to describe the 561 structure of protocol messages. In addition to the base syntax, we 562 add two additional features, the ability for fields to be optional 563 and the ability for vectors to have variable-size length headers. 565 2.1.1. Optional Value 567 An optional value is encoded with a presence-signaling octet, 568 followed by the value itself if present. When decoding, a presence 569 octet with a value other than 0 or 1 MUST be rejected as malformed. 571 struct { 572 uint8 present; 573 select (present) { 574 case 0: struct{}; 575 case 1: T value; 576 } 577 } optional; 579 2.1.2. Variable-size Vector Headers 581 In the TLS presentation language, vectors are encoded as a sequence 582 of encoded elements prefixed with a length. The length field has a 583 fixed size set by specifying the minimum and maximum lengths of the 584 encoded sequence of elements. 586 In MLS, there are several vectors whose sizes vary over significant 587 ranges. So instead of using a fixed-size length field, we use a 588 variable-size length using a variable-length integer encoding based 589 on the one in Section 16 of [RFC9000]. (They differ only in that the 590 one here requires a minimum-size encoding.) Instead of presenting 591 min and max values, the vector description simply includes a V. For 592 example: 594 struct { 595 uint32 fixed<0..255>; 596 opaque variable; 597 } StructWithVectors; 599 Such a vector can represent values with length from 0 bytes to 2^30 600 bytes. The variable-length integer encoding reserves the two most 601 significant bits of the first byte to encode the base 2 logarithm of 602 the integer encoding length in bytes. The integer value is encoded 603 on the remaining bits, in network byte order. The encoded value MUST 604 use the smallest number of bits required to represent the value. 605 When decoding, values using more bits than necessary MUST be treated 606 as malformed. 608 This means that integers are encoded on 1, 2, or 4 bytes and can 609 encode 6-, 14-, or 30-bit values respectively. 611 +========+=========+=============+=======+============+ 612 | Prefix | Length | Usable Bits | Min | Max | 613 +========+=========+=============+=======+============+ 614 | 00 | 1 | 6 | 0 | 63 | 615 +--------+---------+-------------+-------+------------+ 616 | 01 | 2 | 14 | 64 | 16383 | 617 +--------+---------+-------------+-------+------------+ 618 | 10 | 4 | 30 | 16384 | 1073741823 | 619 +--------+---------+-------------+-------+------------+ 620 | 11 | invalid | - | - | - | 621 +--------+---------+-------------+-------+------------+ 623 Table 1: Summary of Integer Encodings 625 Vectors that start with "11" prefix are invalid and MUST be rejected. 627 For example, the four byte sequence 0x9d7f3e7d decodes to 494878333; 628 the two byte sequence 0x7bbd decodes to 15293; and the single byte 629 0x25 decodes to 37. 631 The following figure adapts the pseudocode provided in [RFC9000] to 632 add a check for minimum-length encoding: 634 ReadVarint(data): 635 // The length of variable-length integers is encoded in the 636 // first two bits of the first byte. 637 v = data.next_byte() 638 prefix = v >> 6 639 length = 1 << prefix 641 // Once the length is known, remove these bits and read any 642 // remaining bytes. 643 v = v & 0x3f 644 repeat length-1 times: 645 v = (v << 8) + data.next_byte() 646 return v 648 // Check that the encoder used the minimum bits required 649 if length > 1 && v < (1 << (length - 1)): 650 raise an exception 652 The use of variable-size integers for vector lengths allows vectors 653 to grow very large, up to 2^30 bytes. Implementations should take 654 care not to allow vectors to overflow available storage. To 655 facilitate debugging of potential interoperatbility problems, 656 implementations should provide a clear error when such an overflow 657 condition occurs. 659 3. Operating Context 661 MLS is designed to operate in the context described in 662 [I-D.ietf-mls-architecture]. In particular, we assume that the 663 following services are provided: 665 * A Delivery Service that routes MLS messages among the participants 666 in the protocol. The following types of delivery are typically 667 required: 669 - Pre-publication of KeyPackage objects for clients 671 - Broadcast delivery of Proposal and Commit messages to members 672 of a group 674 - Unicast delivery of Welcome messages to new members of a group 676 * An Authentication Service that enables group members to 677 authenticate the credentials presented by other group members. 679 4. Protocol Overview 681 The core functionality of MLS is continuous group authenticated key 682 exchange (AKE). As with other authenticated key exchange protocols 683 (such as TLS), the participants in the protocol agree on a common 684 secret value, and each participant can verify the identity of the 685 other participants. MLS provides group AKE in the sense that there 686 can be more than two participants in the protocol, and continuous 687 group AKE in the sense that the set of participants in the protocol 688 can change over time. 690 The core organizing principles of MLS are _groups_ and _epochs_. A 691 group represents a logical collection of clients that share a common 692 secret value at any given time. The history of a group is divided 693 into a linear sequence of epochs. In each epoch, a set of 694 authenticated _members_ agree on an _epoch secret_ that is known only 695 to the members of the group in that epoch. The set of members 696 involved in the group can change from one epoch to the next, and MLS 697 ensures that only the members in the current epoch have access to the 698 epoch secret. From the epoch secret, members derive further shared 699 secrets for message encryption, group membership authentication, etc. 701 The creator of an MLS group creates the group's first epoch 702 unilaterally, with no protocol interactions. Thereafter, the members 703 of the group advance their shared cryptographic state from one epoch 704 to another by exchanging MLS messages: 706 * A _KeyPackage_ object describes a client's capabilities and 707 provides keys that can be used to add the client to a group. 709 * A _Proposal_ message proposes a change to be made in the next 710 epoch, such as adding or removing a member 712 * A _Commit_ message initiates a new epoch by instructing members of 713 the group to implement a collection of proposals 715 * A _Welcome_ message provides a new member to the group with the 716 information to initialize their state for the epoch in which they 717 were added or in which they want to add themselves to the group 719 KeyPackage and Welcome messages are used to initiate a group or 720 introduce new members, so they are exchanged between group members 721 and clients not yet in the group. 723 Proposal and Commit messages are sent from one member of a group to 724 the others. MLS provides a common framing layer for sending messages 725 within a group: An _MLSPlaintext_ message provides sender 726 authentication for unencrypted Proposal and Commit messages. An 727 _MLSCiphertext_ message provides encryption and authentication for 728 both Proposal/Commit messages as well as any application data. 730 4.1. Cryptographic State and Evolution 732 The cryptographic state at the core of MLS is divided into three 733 areas of responsibility: 735 .- ... -. 736 | | 737 | | | 738 | | | Key Schedule 739 | V | 740 | epoch_secret | 741 . | | | . 742 |\ Ratchet | | | Secret /| 743 | \ Tree | | | Tree / | 744 | \ | | | / | 745 | \ | V | / | 746 | +--> commit_secret --> epoch_secret --> encryption_secret -->+ | 747 | / | | | \ | 748 | / | | | \ | 749 | / | | | \ | 750 |/ | | | \| 751 ' | V | ' 752 | epoch_secret | 753 | | | 754 | | | 755 | V | 756 | | 757 '- ... -' 759 Figure 1: Overview of MLS group evolution 761 * A _ratchet tree_ that represents the membership of the group, 762 providing group members a way to authenticate each other and 763 efficiently encrypt messages to subsets of the group. Each epoch 764 has a distinct ratchet tree. It seeds the _key schedule_. 766 * A _key schedule_ that describes the chain of key derivations used 767 to progress from epoch to epoch (mainly using the _init_secret_ 768 and _epoch_secret_); and to derive a variety of other secrets (see 769 Table 3) used during the current epoch. One of these (the 770 _encryption_secret_) is the root of _secret_tree_. 772 * A _secret tree_ derived from the key schedule that represents 773 shared secrets used by the members of the group to provide 774 confidentiality and forward secrecy for MLS messages. Each epoch 775 has a distinct secret tree. 777 Each member of the group maintains a view of these facets of the 778 group's state. MLS messages are used to initialize these views and 779 keep them in sync as the group transitions between epochs. 781 Each new epoch is initiated with a Commit message. The Commit 782 instructs existing members of the group to update their views of the 783 ratchet tree by applying a set of Proposals, and uses the updated 784 ratchet tree to distribute fresh entropy to the group. This fresh 785 entropy is provided only to members in the new epoch, not to members 786 who have been removed, so it maintains the confidentiality of the 787 epoch secret (in other words, it provides post-compromise security 788 with respect to those members). 790 For each Commit that adds member(s) to the group, there is a single 791 corresponding Welcome message. The Welcome message provides all the 792 new members with the information they need to initialize their views 793 of the key schedule and ratchet tree, so that these views are 794 equivalent to the views held by other members of the group in this 795 epoch. 797 In addition to defining how one epoch secret leads to the next, the 798 key schedule also defines a collection of secrets that are derived 799 from the epoch secret. For example: 801 * An _encryption secret_ that is used to initialize the secret tree 802 for the epoch. 804 * A _confirmation key_ that is used to confirm that all members 805 agree on the shared state of the group. 807 * A _resumption secret_ that members can use to prove their 808 membership in the group, e.g., in the case of branching a 809 subgroup. 811 Finally, an _init secret_ is derived that is used to initialize the 812 next epoch. 814 4.2. Example Protocol Execution 816 There are three major operations in the lifecycle of a group: 818 * Adding a member, initiated by a current member; 820 * Updating the leaf secret of a member; 822 * Removing a member. 824 Each of these operations is "proposed" by sending a message of the 825 corresponding type (Add / Update / Remove). The state of the group 826 is not changed, however, until a Commit message is sent to provide 827 the group with fresh entropy. In this section, we show each proposal 828 being committed immediately, but in more advanced deployment cases an 829 application might gather several proposals before committing them all 830 at once. In the illustrations below, we show the Proposal and Commit 831 messages directly, while in reality they would be sent encapsulated 832 in MLSPlaintext or MLSCiphertext objects. 834 Before the initialization of a group, clients publish KeyPackages to 835 a directory provided by the Service Provider. 837 Group 838 A B C Directory Channel 839 | | | | | 840 | KeyPackageA | | | | 841 +------------------------------------------------->| | 842 | | | | | 843 | | KeyPackageB | | | 844 | +-------------------------------->| | 845 | | | | | 846 | | | KeyPackageC | | 847 | | +--------------->| | 848 | | | | | 850 Figure 2: Clients A, B, and C publish KeyPackages to the directory 852 When a client A wants to establish a group with B and C, it first 853 initializes a group state containing only itself and downloads 854 KeyPackages for B and C. For each member, A generates an Add and 855 Commit message adding that member, and broadcasts them to the group. 856 It also generates a Welcome message and sends this directly to the 857 new member (there's no need to send it to the group). Only after A 858 has received its Commit message back from the server does it update 859 its state to reflect the new member's addition. 861 Upon receiving the Welcome message, the new member will be able to 862 read and send new messages to the group. However, messages sent 863 before they were added to the group will not be accessible. 865 Group 866 A B C Directory Channel 867 | | | | | 868 | KeyPackageB, KeyPackageC | | 869 |<-------------------------------------------+ | 870 | | | | | 871 | | | | Add(A->AB) | 872 | | | | Commit(Add) | 873 +--------------------------------------------------------------->| 874 | | | | | 875 | Welcome(B) | | | | 876 +------------->| | | | 877 | | | | | 878 | | | | Add(A->AB) | 879 | | | | Commit(Add) | 880 |<---------------------------------------------------------------+ 881 | | | | | 882 | | | | | 883 | | | | Add(AB->ABC) | 884 | | | | Commit(Add) | 885 +--------------------------------------------------------------->| 886 | | | | | 887 | | Welcome(C) | | | 888 +---------------------------->| | | 889 | | | | | 890 | | | | Add(AB->ABC) | 891 | | | | Commit(Add) | 892 |<---------------------------------------------------------------+ 893 | |<------------------------------------------------+ 894 | | | | | 896 Figure 3: Client A creates a group with clients B and C 898 Subsequent additions of group members proceed in the same way. Any 899 member of the group can download a KeyPackage for a new client and 900 broadcast Add and Commit messages that the current group will use to 901 update their state, and a Welcome message that the new client can use 902 to initialize its state and join the group. 904 To enforce the forward secrecy and post-compromise security of 905 messages, each member periodically updates the keys that represent 906 them to the group. A member does this by sending a Commit (possibly 907 with no proposals), or by sending an Update message that is committed 908 by another member. Once the other members of the group have 909 processed these messages, the group's secrets will be unknown to an 910 attacker that had compromised the sender's prior leaf secret. 912 Update messages should be sent at regular intervals of time as long 913 as the group is active, and members that don't update should 914 eventually be removed from the group. It's left to the application 915 to determine an appropriate amount of time between Updates. 917 Group 918 A B ... Z Directory Channel 919 | | | | | 920 | | Update(B) | | | 921 | +------------------------------------------->| 922 | Commit(Upd) | | | | 923 +---------------------------------------------------------->| 924 | | | | | 925 | | | | Update(B) | 926 | | | | Commit(Upd) | 927 |<----------------------------------------------------------+ 928 | |<-------------------------------------------+ 929 | | |<----------------------------+ 930 | | | | | 932 Figure 4: Client B proposes to update its key, and client A 933 commits the proposal. As a result, the keys for both B and A 934 updated, so the group has post-compromise security with respect 935 to both of them. 937 Members are removed from the group in a similar way. Any member of 938 the group can send a Remove proposal followed by a Commit message. 939 The Commit message provides new entropy to all members of the group 940 except the removed member. This new entropy is added to the epoch 941 secret for the new epoch, so that it is not known to the removed 942 member. Note that this does not necessarily imply that any member is 943 actually allowed to evict other members; groups can enforce access 944 control policies on top of these basic mechanism. 946 Group 947 A B ... Z Directory Channel 948 | | | | | 949 | | | Remove(B) | | 950 | | | Commit(Rem) | | 951 | | +---------------------------->| 952 | | | | | 953 | | | | Remove(B) | 954 | | | | Commit(Rem) | 955 |<----------------------------------------------------------+ 956 | | |<----------------------------+ 957 | | | | | 959 Figure 5: Client Z removes client B from the group 961 4.3. Relationships Between Epochs 963 A group has a single linear sequence of epochs. Groups and epochs 964 are generally independent of one-another. However, it can sometimes 965 be useful to link epochs cryptographically, either within a group or 966 across groups. MLS derives a resumption pre-shared key (PSK) from 967 each epoch to allow entropy extracted from one epoch to be injected 968 into a future epoch. This link guarantees that members entering the 969 new epoch agree on a key if and only if they were members of the 970 group during the epoch from which the resumption key was extracted. 972 MLS supports two ways to tie a new group to an existing group. Re- 973 initialization closes one group and creates a new group comprising 974 the same members with different parameters. Branching starts a new 975 group with a subset of the original group's participants (with no 976 effect on the original group). In both cases, the new group is 977 linked to the old group via a resumption PSK. 979 epoch_A_[n-1] 980 | 981 | 982 |<-- ReInit 983 | 984 V 985 epoch_A_[n] epoch_B_[0] 986 . | 987 . PSK(usage=reinit) | 988 .....................>| 989 | 990 V 991 epoch_B_[1] 993 Figure 6: Reinitializing a group 995 epoch_A_[n] epoch_B_[0] 996 | | 997 | PSK(usage=branch) | 998 |....................>| 999 | | 1000 V V 1001 epoch_A_[n+1] epoch_B_[1] 1003 Figure 7: Branching a group 1005 Applications may also choose to use resumption PSKs to link epochs in 1006 other ways. For example, the following figure shows a case where a 1007 resumption PSK from epoch n is injected into epoch n+k. This 1008 demonstrates that the members of the group at epoch n+k were also 1009 members at epoch n, irrespective of any changes to these members' 1010 keys due to Updates or Commits. 1012 epoch_A_[n] 1013 | 1014 | PSK(usage=application) 1015 |..................... 1016 | . 1017 | . 1018 ... ... 1019 | . 1020 | . 1021 V . 1022 epoch_A_[n+k-1] . 1023 | . 1024 | . 1025 |<.................... 1026 | 1027 V 1028 epoch_A_[n+k] 1030 Figure 8: Reinjecting entropy from an earlier epoch 1032 5. Ratchet Tree Concepts 1034 The protocol uses "ratchet trees" for deriving shared secrets among a 1035 group of clients. A ratchet tree is an arrangement of secrets and 1036 key pairs among the members of a group in a way that allows for 1037 secrets to be efficiently updated to reflect changes in the group. 1039 Ratchet trees allow a group to efficiently remove any member by 1040 encrypting new entropy to a subset of the group. A ratchet tree 1041 assigns shared keys to subgroups of the overall group, so that, for 1042 example, encrypting to all but one member of the group requires only 1043 log(N) encryptions, instead of the N-1 encryptions that would be 1044 needed to encrypt to each participant individually (where N is the 1045 number of members in the group). 1047 This remove operation allows MLS to efficiently achieve post- 1048 compromise security. In an Update proposal or a full Commit message, 1049 an old (possibly compromised) representation of a member is 1050 efficiently removed from the group and replaced with a freshly 1051 generated instance. 1053 5.1. Ratchet Tree Terminology 1055 Trees consist of _nodes_. A node is a _leaf_ if it has no children, 1056 and a _parent_ otherwise; note that all parents in our trees have 1057 precisely two children, a _left_ child and a _right_ child. A node 1058 is the _root_ of a tree if it has no parents, and _intermediate_ if 1059 it has both children and parents. The _descendants_ of a node are 1060 that node's children, and the descendants of its children, and we say 1061 a tree _contains_ a node if that node is a descendant of the root of 1062 the tree, or if the node itself is the root of the tree. Nodes are 1063 _siblings_ if they share the same parent. 1065 A _subtree_ of a tree is the tree given by any node (the _head_ of 1066 the subtree) and its descendants. The _size_ of a tree or subtree is 1067 the number of leaf nodes it contains. For a given parent node, its 1068 _left subtree_ is the subtree with its left child as head 1069 (respectively _right subtree_). 1071 All trees used in this protocol are left-balanced binary trees. A 1072 binary tree is _full_ (and _balanced_) if its size is a power of two 1073 and for any parent node in the tree, its left and right subtrees have 1074 the same size. 1076 A binary tree is _left-balanced_ if for every parent, either the 1077 parent is balanced, or the left subtree of that parent is the largest 1078 full subtree that could be constructed from the leaves present in the 1079 parent's own subtree. Given a list of n items, there is a unique 1080 left-balanced binary tree structure with these elements as leaves. 1082 (Note that left-balanced binary trees are the same structure that is 1083 used for the Merkle trees in the Certificate Transparency protocol 1084 [I-D.ietf-trans-rfc6962-bis].) 1086 The _direct path_ of a root is the empty list, and of any other node 1087 is the concatenation of that node's parent along with the parent's 1088 direct path. The _copath_ of a node is the node's sibling 1089 concatenated with the list of siblings of all the nodes in its direct 1090 path, excluding the root. 1092 For example, in the below tree: 1094 * The direct path of C is (W, V, X) 1096 * The copath of C is (D, U, Z) 1097 X = root 1098 | 1099 .-----+-----. 1100 / \ 1101 V Z 1102 | | 1103 .-+-. .-+ 1104 / \ / \ 1105 U W Y + 1106 / \ / \ / \ | 1107 A B C D E F G 1109 0 1 2 3 4 5 6 1111 Figure 9: A complete tree with seven members 1113 A tree with n leaves has 2*n - 1 nodes. For example, the above tree 1114 has 7 leaves (A, B, C, D, E, F, G) and 13 nodes. 1116 Each leaf is given an _index_ (or _leaf index_), starting at 0 from 1117 the left to n-1 at the right. 1119 Finally, a node in the tree may also be _blank_, indicating that no 1120 value is present at that node (i.e. no keying material). This is 1121 often the case when a leaf was recently removed from the tree. 1123 There are multiple ways that an implementation might represent a 1124 ratchet tree in memory. For example, left-balanced binary trees can 1125 be represented as an array of nodes, with node relationships computed 1126 based on nodes' indices in the array. Or a more traditional 1127 representation of linked node objects may be used. Appendix B and 1128 Appendix C provide some details on how to implement the tree 1129 operations required for MLS in these representations. MLS places no 1130 requirements on implementations' internal representations of ratchet 1131 trees. An implementation MAY use any tree representation and 1132 associated algorithms, as long as they produce correct protocol 1133 messages. 1135 5.2. Views of a Ratchet Tree 1137 We generally assume that each participant maintains a complete and 1138 up-to-date view of the public state of the group's ratchet tree, 1139 including the public keys for all nodes and the credentials 1140 associated with the leaf nodes. 1142 No participant in an MLS group knows the private key associated with 1143 every node in the tree. Instead, each member is assigned to a leaf 1144 of the tree, which determines the subset of private keys it knows. 1145 The credential stored at that leaf is one provided by the member. 1147 In particular, MLS maintains the members' views of the tree in such a 1148 way as to maintain the _tree invariant_: 1150 The private key for a node in the tree is known to a member of 1151 the group only if the node's subtree contains that member's leaf. 1153 In other words, if a node is not blank, then it holds a public key. 1154 The corresponding private key is known only to members occupying 1155 leaves below that node. 1157 The reverse implication is not true: A member may not know the 1158 private keys of all the intermediate nodes they're below. Such a 1159 member has an _unmerged_ leaf. Encrypting to an intermediate node 1160 requires encrypting to the node's public key, as well as the public 1161 keys of all the unmerged leaves below it. A leaf is unmerged when it 1162 is first added, because the process of adding the leaf does not give 1163 it access to all of the nodes above it in the tree. Leaves are 1164 "merged" as they receive the private keys for nodes, as described in 1165 Section 8.4. 1167 For example, consider a four-member group (A, B, C, D) where the node 1168 above the right two members is blank. (This is what it would look 1169 like if A created a group with B, C, and D.) Then the public state 1170 of the tree and the views of the private keys of the tree held by 1171 each participant would be as follows, where _ represents a blank 1172 node, ? represents an unknown private key, and pk(X) represents the 1173 public key corresponding to the private key X: 1175 Public Tree 1176 ============================ 1177 pk(ABCD) 1178 / \ 1179 pk(AB) _ 1180 / \ / \ 1181 pk(A) pk(B) pk(C) pk(D) 1183 Private @ A Private @ B Private @ C Private @ D 1184 ============= ============= ============= ============= 1185 ABCD ABCD ABCD ABCD 1186 / \ / \ / \ / \ 1187 AB _ AB _ ? _ ? _ 1188 / \ / \ / \ / \ / \ / \ / \ / \ 1189 A ? ? ? ? B ? ? ? ? C ? ? ? ? D 1191 Note how the tree invariant applies: Each member knows only their own 1192 leaf, and the private key AB is known only to A and B. 1194 5.3. Ratchet Tree Nodes 1196 A particular instance of a ratchet tree includes the same parameters 1197 that define an instance of HPKE, namely: 1199 * A Key Encapsulation Mechanism (KEM), including a DeriveKeyPair 1200 function that creates a key pair for the KEM from a symmetric 1201 secret 1203 * A Key Derivation Function (KDF), including Extract and Expand 1204 functions 1206 * An AEAD encryption scheme 1208 Each non-blank node in a ratchet tree contains up to five values: 1210 * A public key 1212 * A private key (only within the member's direct path, see below) 1214 * A credential (only for leaf nodes) 1216 * An ordered list of "unmerged" leaves (see Section 5.2) 1218 * A hash of certain information about the node's parent, as of the 1219 last time the node was changed (see Section 8.8). 1221 The _resolution_ of a node is an ordered list of non-blank nodes that 1222 collectively cover all non-blank descendants of the node. The 1223 resolution of a non-blank node with no unmerged leaves is just the 1224 node itself. More generally, the resolution of a node is effectively 1225 a depth-first, left-first enumeration of the nearest non-blank nodes 1226 below the node: 1228 * The resolution of a non-blank node comprises the node itself, 1229 followed by its list of unmerged leaves, if any 1231 * The resolution of a blank leaf node is the empty list 1233 * The resolution of a blank intermediate node is the result of 1234 concatenating the resolution of its left child with the resolution 1235 of its right child, in that order 1237 For example, consider the following subtree, where the _ character 1238 represents a blank node and unmerged leaves are indicated in square 1239 brackets: 1241 ... 1242 / 1243 _ 1244 | 1245 .-+-. 1246 / \ 1247 _ Z[C] 1248 / \ / \ 1249 A _ C D 1251 0 1 2 3 1253 Figure 10: A tree with blanks and unmerged leaves 1255 In this tree, we can see all of the above rules in play: 1257 * The resolution of node Z is the list [Z, C] 1259 * The resolution of leaf 1 is the empty list [] 1261 * The resolution of top node is the list [A, Z, C] 1263 Every node, regardless of whether the node is blank or populated, has 1264 a corresponding _hash_ that summarizes the contents of the subtree 1265 below that node. The rules for computing these hashes are described 1266 in Section 8.7. 1268 6. Cryptographic Objects 1270 6.1. Ciphersuites 1272 Each MLS session uses a single ciphersuite that specifies the 1273 following primitives to be used in group key computations: 1275 * HPKE parameters: 1277 - A Key Encapsulation Mechanism (KEM) 1279 - A Key Derivation Function (KDF) 1281 - An AEAD encryption algorithm 1283 * A hash algorithm 1285 * A MAC algorithm 1287 * A signature algorithm 1289 MLS uses HPKE for public-key encryption [RFC9180]. The DeriveKeyPair 1290 function associated to the KEM for the ciphersuite maps octet strings 1291 to HPKE key pairs. As in HPKE, MLS assumes that an AEAD algorithm 1292 produces a single ciphertext output from AEAD encryption (aligning 1293 with [RFC5116]), as opposed to a separate ciphertext and tag. 1295 Ciphersuites are represented with the CipherSuite type. HPKE public 1296 keys are opaque values in a format defined by the underlying protocol 1297 (see the Cryptographic Dependencies section of the HPKE specification 1298 for more information). 1300 opaque HPKEPublicKey; 1302 The signature algorithm specified in the ciphersuite is the mandatory 1303 algorithm to be used for signatures in MLSMessageAuth and the tree 1304 signatures. It MUST be the same as the signature algorithm specified 1305 in the credentials in the leaves of the tree (including the leaf node 1306 information in KeyPackages used to add new members). 1308 Like HPKE public keys, signature public keys are represented as 1309 opaque values in a format defined by the cipher suite's signature 1310 scheme. 1312 opaque SignaturePublicKey; 1313 For ciphersuites using Ed25519 or Ed448 signature schemes, the public 1314 key is in the format specified in [RFC8032]. For ciphersuites using 1315 ECDSA with the NIST curves (P-256, P-384, or P-521), the public key 1316 is the output of the uncompressed Elliptic-Curve-Point-to-Octet- 1317 String conversion according to [SECG]. 1319 To disambiguate different signatures used in MLS, each signed value 1320 is prefixed by a label as shown below: 1322 SignWithLabel(SignatureKey, Label, Content) = 1323 Signature.Sign(SignatureKey, SignContent) 1325 VerifyWithLabel(VerificationKey, Label, Content) = 1326 Signature.Verify(VerificationKey, SignContent) 1328 Where SignContent is specified as: 1330 struct { 1331 opaque label = "MLS 1.0 " + Label; 1332 opaque content = Content; 1333 } SignContent; 1335 Here, the functions Signature.Sign and Signature.Verify are defined 1336 by the signature algorithm. 1338 The ciphersuites are defined in section Section 18.1. 1340 6.2. Hash-Based Identifiers 1342 Some MLS messages refer to other MLS objects by hash. For example, 1343 Welcome messages refer to KeyPackages for the members being welcomed, 1344 and Commits refer to Proposals they cover. These identifiers are 1345 computed as follows: 1347 opaque HashReference[16]; 1349 HashReference KeyPackageRef; 1350 HashReference LeafNodeRef; 1351 HashReference ProposalRef; 1353 MakeKeyPackageRef(value) = KDF.expand( 1354 KDF.extract("", value), "MLS 1.0 KeyPackage Reference", 16) 1356 MakeLeafNodeRef(value) = KDF.expand( 1357 KDF.extract("", value), "MLS 1.0 Leaf Node Reference", 16) 1359 MakeProposalRef(value) = KDF.expand( 1360 KDF.extract("", value), "MLS 1.0 Proposal Reference", 16) 1362 For a KeyPackageRef, the value input is the encoded KeyPackage, and 1363 the ciphersuite specified in the KeyPackage determines the KDF used. 1364 For a LeafNodeRef, the value input is the LeafNode object for the 1365 leaf node in question. For a ProposalRef, the value input is the 1366 MLSMessageContentAuth carrying the proposal. In the latter two 1367 cases, the KDF is determined by the group's ciphersuite. 1369 6.3. Credentials 1371 Each member of a group presents a credential that associates an 1372 identity with the member's key material. This information is 1373 verified according to the Authentication Service in use for a group. 1375 A Credential can provide multiple identifiers for the client. It is 1376 up to the application to decide which identifier or identifiers to 1377 use at the application level. For example, a certificate in an 1378 X509Credential may attest to several domain names or email addresses 1379 in its subjectAltName extension. An application may decide to 1380 present all of these to a user, or if it knows a "desired" domain 1381 name or email address, it can check that the desired identifier is 1382 among those attested. Using the terminology from [RFC6125], a 1383 Credential provides "presented identifiers", and it is up to the 1384 application to supply a "reference identifier" for the authenticated 1385 client, if any. 1387 Credentials MAY also include information that allows a relying party 1388 to verify the identity / signing key binding, such as a signature 1389 from a trusted authority. 1391 // See IANA registry for registered values 1392 uint16 CredentialType; 1394 struct { 1395 opaque cert_data; 1396 } Certificate; 1398 struct { 1399 CredentialType credential_type; 1400 select (credential_type) { 1401 case basic: 1402 opaque identity; 1404 case x509: 1405 Certificate chain; 1406 }; 1407 } Credential; 1408 A BasicCredential is a bare assertion of an identity, without any 1409 additional information. The format of the encoded identity is 1410 defined by the application. 1412 For an X.509 credential, each entry in the chain represents a single 1413 DER-encoded X.509 certificate. The chain is ordered such that the 1414 first entry (chain[0]) is the end-entity certificate and each 1415 subsequent certificate in the chain MUST be the issuer of the 1416 previous certificate. The public key encoded in the 1417 subjectPublicKeyInfo of the end-entity certificate MUST be identical 1418 to the signature_key in the LeafNode containing this credential. 1420 The signatures used in this document are encoded as specified in 1421 [RFC8446]. In particular, ECDSA signatures are DER-encoded and EdDSA 1422 signatures are defined as the concatenation of r and s as specified 1423 in [RFC8032]. 1425 Each new credential that has not already been validated by the 1426 application MUST be validated against the Authentication Service. 1427 Applications SHOULD require that a client present the same set of 1428 identifiers throughout its presence in the group, even if its 1429 Credential is changed in a Commit or Update. If an application 1430 allows clients to change identifiers over time, then each time the 1431 client presents a new credential, the application MUST verify that 1432 the set of identifiers in the credential is acceptable to the 1433 application for this client. 1435 6.3.1. Uniquely Identifying Clients 1437 MLS implementations will presumably provide applications with a way 1438 to request protocol operations with regard to other clients (e.g., 1439 removing clients). Such functions will need to refer to the other 1440 clients using some identifier. MLS clients have a few types of 1441 identifiers, with different operational properties. 1443 The Credentials presented by the clients in a group authenticate 1444 application-level identifiers for the clients. These identifiers may 1445 not uniquely identify clients. For example, if a user has multiple 1446 devices that are all present in an MLS group, then those devices' 1447 clients could all present the user's application-layer identifiers. 1449 Internally to the protocol, group members are uniquely identified by 1450 their leaves, expressed as LeafNodeRef objects. These identifiers 1451 are unstable: They change whenever the member sends a Commit, or 1452 whenever an Update proposal from the member is committed. 1454 MLS provides two unique client identifiers that are stable across 1455 epochs: 1457 * The index of a client among the leaves of the tree 1459 * The epoch_id field in the key package 1461 The application may also provide application-specific unique 1462 identifiers in the extensions field of KeyPackage or LeafNode 1463 objects. 1465 7. Message Framing 1467 Handshake and application messages use a common framing structure. 1468 This framing provides encryption to ensure confidentiality within the 1469 group, as well as signing to authenticate the sender within the 1470 group. 1472 The main structure is MLSMessageContent, which contains the content 1473 of the message. This structure is authenticated using MLSMessageAuth 1474 (see Section 7.1). The two structures are combined in 1475 MLSMessageContentAuth, which can then be encoded/decoded from/to 1476 MLSPlaintext or MLSCiphertext, which are then included in the 1477 MLSMessage structure. 1479 MLSCiphertext represents a signed and encrypted message, with 1480 protections for both the content of the message and related metadata. 1481 MLSPlaintext represents a message that is only signed, and not 1482 encrypted. Applications MUST use MLSCiphertext to encrypt 1483 application messages and SHOULD use MLSCiphertext to encode handshake 1484 messages, but MAY transmit handshake messages encoded as MLSPlaintext 1485 objects in cases where it is necessary for the Delivery Service to 1486 examine such messages. 1488 enum { 1489 reserved(0), 1490 mls10(1), 1491 (255) 1492 } ProtocolVersion; 1494 enum { 1495 reserved(0), 1496 application(1), 1497 proposal(2), 1498 commit(3), 1499 (255) 1500 } ContentType; 1502 enum { 1503 reserved(0), 1504 member(1), 1505 external(2), 1506 new_member(3), 1507 (255) 1508 } SenderType; 1510 struct { 1511 SenderType sender_type; 1512 switch (sender_type) { 1513 case member: 1514 LeafNodeRef member_ref; 1515 case external: 1516 uint32 sender_index; 1517 case new_member: 1518 struct{}; 1519 } 1520 } Sender; 1522 enum { 1523 reserved(0), 1524 mls_plaintext(1), 1525 mls_ciphertext(2), 1526 mls_welcome(3), 1527 mls_group_info(4), 1528 mls_key_package(5), 1529 (255) 1530 } WireFormat; 1532 struct { 1533 opaque group_id; 1534 uint64 epoch; 1535 Sender sender; 1536 opaque authenticated_data; 1538 ContentType content_type; 1539 select (MLSMessageContent.content_type) { 1540 case application: 1541 opaque application_data; 1542 case proposal: 1543 Proposal proposal; 1544 case commit: 1545 Commit commit; 1546 } 1547 } MLSMessageContent; 1549 struct { 1550 ProtocolVersion version = mls10; 1551 WireFormat wire_format; 1552 select (MLSMessage.wire_format) { 1553 case mls_plaintext: 1554 MLSPlaintext plaintext; 1555 case mls_ciphertext: 1556 MLSCiphertext ciphertext; 1557 case mls_welcome: 1558 Welcome welcome; 1559 case mls_group_info: 1560 GroupInfo group_info; 1561 case mls_key_package: 1562 KeyPackage key_package; 1563 } 1564 } MLSMessage; 1566 External sender types are sent as MLSPlaintext, see Section 13.1.9 1567 for their use. 1569 The following structure is used to fully describe the data 1570 transmitted in plaintexts or ciphertexts. 1572 struct { 1573 WireFormat wire_format; 1574 MLSMessageContent content; 1575 MLSMessageAuth auth; 1576 } MLSMessageContentAuth; 1578 7.1. Content Authentication 1580 MLSMessageContent is authenticated using the MLSMessageAuth 1581 structure. 1583 struct { 1584 opaque mac_value; 1585 } MAC; 1587 struct { 1588 // SignWithLabel(., "MLSMessageContentTBS", MLSMessageContentTBS) 1589 opaque signature; 1590 select (MLSMessageContent.content_type) { 1591 case commit: 1592 // MAC(confirmation_key, 1593 // GroupContext.confirmed_transcript_hash) 1594 MAC confirmation_tag; 1595 case application: 1596 case proposal: 1597 struct{}; 1598 } 1599 } MLSMessageAuth; 1600 The signature is computed using SignWithLabel with label 1601 "MLSMessageContentTBS" and with a content that covers the message 1602 content and the wire format that will be used for this message. If 1603 the sender's sender_type is Member, the content also covers the 1604 GroupContext for the current epoch, so that signatures are specific 1605 to a given group and epoch. 1607 The sender MUST use the private key corresponding to the following 1608 signature key depending on the sender's sender_type: 1610 * member: The signature key contained in the Credential at the leaf 1611 with the sender's LeafNodeRef 1613 * external: The signature key contained in the Credential at the 1614 index indicated by the sender_index in the external_senders group 1615 context extension (see Section Section 13.1.9.1). In this case, 1616 the content_type of the message MUST NOT be commit, since only 1617 members of the group or new joiners can send Commit messages. 1619 * new_member: The signature key depends on the content_type: 1621 - proposal: The signature key in the credential contained in 1622 KeyPackage in the Add proposal (see Section Section 13.1.9). 1624 - commit: The signature key in the credential contained in the 1625 KeyPackage in the Commit's path (see Section Section 9.3). 1627 struct { 1628 ProtocolVersion version = mls10; 1629 WireFormat wire_format; 1630 MLSMessageContent content; 1631 select (MLSMessageContentTBS.content.sender.sender_type) { 1632 case member: 1633 case new_member: 1634 GroupContext context; 1636 case external: 1637 struct{}; 1638 } 1639 } MLSMessageContentTBS; 1641 Recipients of an MLSMessage MUST verify the signature with the key 1642 depending on the sender_type of the sender as described above. 1644 The confirmation tag value confirms that the members of the group 1645 have arrived at the same state of the group. 1647 A MLSMessageAuth is said to be valid when both the signature and 1648 confirmation_tag fields are valid. 1650 7.2. Encoding and Decoding a Plaintext 1652 Plaintexts are encoded using the MLSPlaintext structure. 1654 struct { 1655 MLSMessageContent content; 1656 MLSMessageAuth auth; 1657 select(MLSPlaintext.content.sender.sender_type) { 1658 case member: 1659 MAC membership_tag; 1660 case external: 1661 case new_member: 1662 struct{}; 1663 } 1664 } MLSPlaintext; 1666 The membership_tag field in the MLSPlaintext object authenticates the 1667 sender's membership in the group. For messages sent by members, it 1668 MUST be set to the following value: 1670 struct { 1671 MLSMessageContentTBS content_tbs; 1672 MLSMessageAuth auth; 1673 } MLSMessageContentTBM; 1675 membership_tag = MAC(membership_key, MLSMessageContentTBM) 1677 When decoding a MLSPlaintext into a MLSMessageContentAuth, the 1678 application MUST check membership_tag, and MUST check that the 1679 MLSMessageAuth is valid. 1681 7.3. Encoding and Decoding a Ciphertext 1683 Ciphertexts are encoded using the MLSCiphertext structure. 1685 struct { 1686 opaque group_id; 1687 uint64 epoch; 1688 ContentType content_type; 1689 opaque authenticated_data; 1690 opaque encrypted_sender_data; 1691 opaque ciphertext; 1692 } MLSCiphertext; 1693 encrypted_sender_data and ciphertext are encrypted using the AEAD 1694 function specified by the ciphersuite in use, using as input the 1695 structures MLSSenderData and MLSCiphertextContent. 1697 7.3.1. Content Encryption 1699 The ciphertext content is encoded using the MLSCiphertextContent 1700 structure. 1702 struct { 1703 select (MLSCiphertext.content_type) { 1704 case application: 1705 opaque application_data; 1707 case proposal: 1708 Proposal proposal; 1710 case commit: 1711 Commit commit; 1712 } 1714 MLSMessageAuth auth; 1715 opaque padding; 1716 } MLSCiphertextContent; 1718 In the MLS key schedule, the sender creates two distinct key ratchets 1719 for handshake and application messages for each member of the group. 1720 When encrypting a message, the sender looks at the ratchets it 1721 derived for its own member and chooses an unused generation from 1722 either the handshake or application ratchet depending on the content 1723 type of the message. This generation of the ratchet is used to 1724 derive a provisional nonce and key. 1726 Before use in the encryption operation, the nonce is XORed with a 1727 fresh random value to guard against reuse. Because the key schedule 1728 generates nonces deterministically, a client must keep persistent 1729 state as to where in the key schedule it is; if this persistent state 1730 is lost or corrupted, a client might reuse a generation that has 1731 already been used, causing reuse of a key/nonce pair. 1733 To avoid this situation, the sender of a message MUST generate a 1734 fresh random 4-byte "reuse guard" value and XOR it with the first 1735 four bytes of the nonce from the key schedule before using the nonce 1736 for encryption. The sender MUST include the reuse guard in the 1737 reuse_guard field of the sender data object, so that the recipient of 1738 the message can use it to compute the nonce to be used for 1739 decryption. 1741 +-+-+-+-+---------...---+ 1742 | Key Schedule Nonce | 1743 +-+-+-+-+---------...---+ 1744 XOR 1745 +-+-+-+-+---------...---+ 1746 | Guard | 0 | 1747 +-+-+-+-+---------...---+ 1748 === 1749 +-+-+-+-+---------...---+ 1750 | Encrypt/Decrypt Nonce | 1751 +-+-+-+-+---------...---+ 1753 The Additional Authenticated Data (AAD) input to the encryption 1754 contains an object of the following form, with the values used to 1755 identify the key and nonce: 1757 struct { 1758 opaque group_id; 1759 uint64 epoch; 1760 ContentType content_type; 1761 opaque authenticated_data; 1762 } MLSCiphertextContentAAD; 1764 When decoding a MLSCiphertextContent, the application MUST check that 1765 the MLSMessageAuth is valid. 1767 7.3.2. Sender Data Encryption 1769 The "sender data" used to look up the key for the content encryption 1770 is encrypted with the ciphersuite's AEAD with a key and nonce derived 1771 from both the sender_data_secret and a sample of the encrypted 1772 content. Before being encrypted, the sender data is encoded as an 1773 object of the following form: 1775 struct { 1776 LeafNodeRef sender; 1777 uint32 generation; 1778 opaque reuse_guard[4]; 1779 } MLSSenderData; 1781 MLSSenderData.sender is assumed to be a member sender type. When 1782 constructing an MLSSenderData from a Sender object, the sender MUST 1783 verify Sender.sender_type is member and use Sender.sender for 1784 MLSSenderData.sender. 1786 The reuse_guard field contains a fresh random value used to avoid 1787 nonce reuse in the case of state loss or corruption, as described in 1788 Section 7.3.1. 1790 The key and nonce provided to the AEAD are computed as the KDF of the 1791 first KDF.Nh bytes of the ciphertext generated in the previous 1792 section. If the length of the ciphertext is less than KDF.Nh, the 1793 whole ciphertext is used without padding. In pseudocode, the key and 1794 nonce are derived as: 1796 ciphertext_sample = ciphertext[0..KDF.Nh-1] 1798 sender_data_key = ExpandWithLabel(sender_data_secret, "key", 1799 ciphertext_sample, AEAD.Nk) 1800 sender_data_nonce = ExpandWithLabel(sender_data_secret, "nonce", 1801 ciphertext_sample, AEAD.Nn) 1803 The Additional Authenticated Data (AAD) for the SenderData ciphertext 1804 is the first three fields of MLSCiphertext: 1806 struct { 1807 opaque group_id; 1808 uint64 epoch; 1809 ContentType content_type; 1810 } MLSSenderDataAAD; 1812 When parsing a SenderData struct as part of message decryption, the 1813 recipient MUST verify that the LeafNodeRef indicated in the sender 1814 field identifies a member of the group. 1816 8. Ratchet Tree Operations 1818 The ratchet tree for an epoch describes the membership of a group in 1819 that epoch, providing public-key encryption (HPKE) keys that can be 1820 used to encrypt to subsets of the group as well as information to 1821 authenticate the members. In order to reflect changes to the 1822 membership of the group from one epoch to the next, corresponding 1823 changes are made to the ratchet tree. In this section, we describe 1824 the content of the tree and the required operations. 1826 8.1. Parent Node Contents 1828 As discussed in Section 5.3, the nodes of a ratchet tree contain 1829 several types of data describing individual members (for leaf nodes) 1830 or subgroups of the group (for parent nodes). Parent nodes are 1831 simpler: 1833 struct { 1834 HPKEPublicKey encryption_key; 1835 opaque parent_hash; 1836 uint32 unmerged_leaves; 1837 } ParentNode; 1838 The encryption_key field contains an HPKE public key whose private 1839 key is held only by the members at the leaves among its descendants. 1840 The parent_hash field contains a hash of this node's parent node, as 1841 described in Section 8.8. The unmerged_leaves field lists the leaves 1842 under this parent node that are unmerged, according to their indices 1843 among all the leaves in the tree. 1845 8.2. Leaf Node Contents 1847 A leaf node in the tree describes all the details of an individual 1848 client's appearance in the group, signed by that client. It is also 1849 used in client KeyPackage objects to store the information that will 1850 be needed to add a client to a group. 1852 enum { 1853 reserved(0), 1854 key_package(1), 1855 update(2), 1856 commit(3), 1857 (255) 1858 } LeafNodeSource; 1860 struct { 1861 ProtocolVersion versions; 1862 CipherSuite ciphersuites; 1863 ExtensionType extensions; 1864 ProposalType proposals; 1865 CredentialType credentials; 1866 } Capabilities; 1868 struct { 1869 uint64 not_before; 1870 uint64 not_after; 1871 } Lifetime; 1873 // See IANA registry for registered values 1874 uint16 ExtensionType; 1876 struct { 1877 ExtensionType extension_type; 1878 opaque extension_data; 1879 } Extension; 1881 struct { 1882 HPKEPublicKey encryption_key; 1883 SignaturePublicKey signature_key; 1884 Credential credential; 1885 Capabilities capabilities; 1886 LeafNodeSource leaf_node_source; 1887 select (leaf_node_source) { 1888 case key_package: 1889 Lifetime lifetime; 1891 case update: 1892 struct {} 1894 case commit: 1895 opaque parent_hash; 1896 } 1898 Extension extensions; 1899 // SignWithLabel(., "LeafNodeTBS", LeafNodeTBS) 1900 opaque signature; 1901 } LeafNode; 1903 struct { 1904 HPKEPublicKey encryption_key; 1905 SignaturePublicKey signature_key; 1906 Credential credential; 1907 Capabilities capabilities; 1909 LeafNodeSource leaf_node_source; 1910 select (leaf_node_source) { 1911 case key_package: 1912 Lifetime lifetime; 1914 case update: 1915 struct{}; 1917 case commit: 1918 opaque parent_hash; 1919 } 1921 Extension extensions; 1923 select (leaf_node_source) { 1924 case key_package: 1925 struct{}; 1927 case update: 1928 opaque group_id; 1930 case commit: 1931 opaque group_id; 1932 } 1933 } LeafNodeTBS; 1934 The encryption_key field conains an HPKE public key whose private key 1935 is held only by the member occupying this leaf (or in the case of a 1936 LeafNode in a KeyPackage object, the issuer of the KeyPackage). The 1937 credential contains authentication information for this member, as 1938 described in Section 6.3. 1940 The capabilities field indicates what protocol versions, 1941 ciphersuites, extensions, credential types, and non-default proposal 1942 types are supported by a client. Proposal and extension types 1943 defined in this document are considered "default" and thus need not 1944 be listed, while any credential types the application wishes to use 1945 MUST be listed. Extensions that appear in the extensions field of a 1946 LeafNode MUST be included in the extensions field of the capabilities 1947 field, and the credential type used in the LeafNode MUST be included 1948 in the credentials field of the capabilities field. 1950 The leaf_node_source field indicates how this LeafNode came to be 1951 added to the tree. This signal tells other members of the group 1952 whether the leaf node is required to have a lifetime or parent_hash, 1953 and whether the group_id is added as context to the signature. 1954 Whether these fields can be computed by the client represented by the 1955 LeafNode depends on when the LeafNode was created. For example, a 1956 KeyPackage is created before the client knows which group it will be 1957 used with, so its signature can't bind to a group_id. 1959 In the case where the leaf was added to the tree based on a pre- 1960 published KeyPackage, the lifetime field represents the times between 1961 which clients will consider a LeafNode valid. These times are 1962 represented as absolute times, measured in seconds since the Unix 1963 epoch (1970-01-01T00:00:00Z). Applications MUST define a maximum 1964 total lifetime that is acceptable for a LeafNode, and reject any 1965 LeafNode where the total lifetime is longer than this duration. 1967 In the case where the leaf node was inserted into the tree via a 1968 Commit message, the parent_hash field contains the parent hash for 1969 this leaf node (see Section 8.8). 1971 The LeafNodeTBS structure covers the fields above the signature in 1972 the LeafNode. In addition, when the leaf node was created in the 1973 context of a group (the update and commit cases), the group ID of the 1974 group is added as context to the signature. 1976 LeafNode objects stored in the group's ratchet tree are updated 1977 according to the evolution of the tree. Each modification of 1978 LeafNode content MUST be reflected by a change in its signature. 1979 This allows other members to verify the validity of the LeafNode at 1980 any time, particularly in the case of a newcomer joining the group. 1982 8.3. Leaf Node Validation 1984 The validity of a LeafNode needs to be verified at a few stages: 1986 * When a LeafNode is downloaded in a KeyPackage, before it is used 1987 to add the client to the group 1989 * When a LeafNode is received by a group member in an Add, Update, 1990 or Commit message 1992 * When a client joining a group receives LeafNode objects for the 1993 other members of the group in the group's ratchet tree 1995 The client verifies the validity of a LeafNode using the following 1996 steps: 1998 * Verify that the credential in the LeafNode is valid according to 1999 the authentication service and the client's local policy. These 2000 actions MUST be the same regardless of at what point in the 2001 protocol the LeafNode is being verified with the following 2002 exception: If the LeafNode is an update to another LeafNode, the 2003 authentication service MUST additionally validate that the set of 2004 identities attested by the credential in the new LeafNode is 2005 acceptable relative to the identities attested by the old 2006 credential. 2008 * Verify that the signature on the LeafNode is valid using the 2009 public key in the LeafNode's credential 2011 * Verify that the LeafNode is compatible with the group's 2012 parameters. If the GroupContext has a required_capabilities 2013 extension, then the required extensions, proposals, and credential 2014 types MUST be listed in the LeafNode's capabilities field. 2016 * Verify that the credential type is supported by all members of the 2017 group, as specified by the capabilities field of each member's 2018 LeafNode, and that the capabilities field of this LeafNode 2019 indicates support for all the credential types currently in use by 2020 other members. 2022 * Verify the lifetime field: 2024 - When validating a LeafNode in a KeyPackage before sending an 2025 Add proposal, the current time MUST be within the lifetime 2026 range. A KeyPackage containing a LeafNode that is expired or 2027 not yet valid MUST NOT be sent in an Add proposal. 2029 - When receiving an Add or validating a tree, checking the 2030 lifetime is RECOMMENDED, if it is feasible in a given 2031 application context. Because of the asynchronous nature of 2032 MLS, the lifetime may have been valid when the leaf node was 2033 proposed for addition, even if it is expired at these later 2034 points in the protocol. 2036 * Verify that the leaf_node_source field has the appropriate value 2037 for the context in which the LeafNode is being validated (as 2038 defined in Section 8.2). 2040 * Verify that the following fields in the LeafNode are unique among 2041 the members of the group (including any other members added in the 2042 same Commit): 2044 - encryption_key 2046 - signature_key 2048 * Verify that the extensions in the leaf node are supported. The ID 2049 for each extension in the extensions field MUST be listed in the 2050 field capabilities.extensions of the LeafNode. 2052 8.4. Ratchet Tree Evolution 2054 In order to provide forward secrecy and post-compromise security, 2055 whenever a member initiates an epoch change (i.e., commits; see 2056 Section 13.2), they refresh the key pairs of their leaf and of all 2057 nodes on their leaf's direct path (all nodes for which they know the 2058 secret key). 2060 The member initiating the epoch change generates the fresh key pairs 2061 using the following procedure. The procedure is designed in a way 2062 that allows group members to efficiently communicate the fresh secret 2063 keys to other group members, as described in Section 8.9. 2065 Recall the definition of resolution from Section 5.3. To begin with, 2066 the generator of the UpdatePath updates its leaf and its leaf's 2067 _filtered direct path_ with new key pairs. The filtered direct path 2068 of a node is obtained from the node's direct path by removing all 2069 nodes whose child on the nodes's copath has an empty resolution (any 2070 unmerged leaves of the copath child count towards its resolution). 2071 Such a removed node does not need a key pair, since after blanking 2072 it, its resolution consists of a single node on the filtered direct 2073 path. Using the key pair of the node in the resolution is equivalent 2074 to using the key pair of the removed node. 2076 * Blank all the nodes on the direct path from the leaf to the root. 2078 * Generate a fresh HPKE key pair for the leaf. 2080 * Generate a sequence of path secrets, one for each node on the 2081 leaf's filtered direct path, as follows. In this setting, 2082 path_secret[0] refers to the first parent node in the filtered 2083 direct path, path_secret[1] to the second parent node, and so on. 2085 path_secret[0] is sampled at random 2086 path_secret[n] = DeriveSecret(path_secret[n-1], "path") 2088 * Compute the sequence of HPKE key pairs (node_priv,node_pub), one 2089 for each node on the leaf's direct path, as follows. 2091 node_secret[n] = DeriveSecret(path_secret[n], "node") 2092 node_priv[n], node_pub[n] = KEM.DeriveKeyPair(node_secret[n]) 2094 The node secret is derived as a temporary intermediate secret so that 2095 each secret is only used with one algorithm: The path secret is used 2096 as an input to DeriveSecret and the node secret is used as an input 2097 to DeriveKeyPair. 2099 For example, suppose there is a group with four members, with C an 2100 unmerged leaf at Z: 2102 Y 2103 | 2104 .-+-. 2105 / \ 2106 X Z[C] 2107 / \ / \ 2108 A B C D 2110 0 1 2 3 2112 Figure 11: A full tree with one unmerged leaf 2114 If member B subsequently generates an UpdatePath based on a secret 2115 "leaf_secret", then it would generate the following sequence of path 2116 secrets: 2118 path_secret[1] ---> node_secret[1] -------> node_priv[1], node_pub[1] 2120 ^ 2121 | 2122 | 2123 path_secret[0] ---> node_secret[0] -------> node_priv[0], node_pub[0] 2125 ^ 2126 | 2127 | 2128 leaf_secret ------> leaf_node_secret --+--> leaf_priv, leaf_pub 2129 | | 2130 '-------. .-------' 2131 | 2132 leaf_node 2134 After applying the UpdatePath, the tree will have the following 2135 structure, where lp and np[i] represent the leaf_priv and node_priv 2136 values generated as described above: 2138 node_priv[1] --------> Y' 2139 | 2140 .-+-. 2141 / \ 2142 node_priv[0] ----> X' Z[C] 2143 / \ / \ 2144 A B C D 2145 ^ 2146 leaf_priv -----------+ 2147 0 1 2 3 2149 8.5. Adding and Removing Leaves 2151 In addition to the path-based updates to the tree described above, it 2152 is also necessary to add and remove leaves of the tree in order to 2153 reflect changes to the membership of the group (see Section 13.1.1 2154 and Section 13.1.3). Leaves are always added and removed at the 2155 right edge of the tree: Either a new rightmost leaf is added, or the 2156 rightmost leaf is removed. Nodes' parent/child node relationships 2157 are then updated to maintain the tree's left-balanced structure. 2158 These operations are also known as _extending_ and _truncating_ the 2159 tree. 2161 To add a new leaf: Add leaf L as the new rightmost leaf of the tree. 2162 Add a blank parent node P whose right child is L. P is attached to 2163 the tree as the right child of the only appropriate node to make the 2164 updated tree left-balanced (or set it as a new root). The former 2165 right child of P's parent becomes P's left child (or the old root 2166 becomes P's left child if P is the new root). 2168 _ <-- new parent _ 2169 __|_ __|__ 2170 / \ / \ 2171 X ===> X | ===> X _ <-- new parent 2172 / \ / \ | / \ / \ 2173 A B A B C <-- new leaf A B C D <-- new leaf 2175 To remove the rightmost leaf: Remove the rightmost leaf node L and 2176 its parent node P. If P was the root of the tree, P's left child is 2177 now the root of the tree. Otherwise, set the right child of P's 2178 parent to be P's left child. 2180 Y Y 2181 __|__ __|_ 2182 / \ / \ 2183 X Z <-- remove parent ===> X | <-- reassign child 2184 / \ / \ / \ | 2185 A B C D <-- remove leaf A B C 2187 Y <-- remove parent 2188 __|_ 2189 / \ 2190 X | ===> X <-- reassign root 2191 / \ | / \ 2192 A B C <-- remove leaf A B 2194 Note that in the rest of the protocol, the rightmost leaf will only 2195 be removed when it is blank. 2197 Concrete algorithms for these operations on array-based and link- 2198 based trees are provided in Appendix B and Appendix C. The concrete 2199 algorithms are non-normative. An implementation MAY use any 2200 algorithm that produces the correct tree in its internal 2201 representation. 2203 8.6. Synchronizing Views of the Tree 2205 After generating fresh key material and applying it to ratchet 2206 forward their local tree state as described in the Section 8.4, the 2207 generator must broadcast this update to other members of the group in 2208 a Commit message, who apply it to keep their local views of the tree 2209 in sync with the sender's. More specifically, when a member commits 2210 a change to the tree (e.g., to add or remove a member), it transmits 2211 an UpdatePath containing a set of public keys and encrypted path 2212 secrets for intermediate nodes in the filtered direct path of its 2213 leaf. The other members of the group use these values to update 2214 their view of the tree, aligning their copy of the tree to the 2215 sender's. 2217 An UpdatePath contains the following information for each node in the 2218 filtered direct path of the sender's leaf, including the root: 2220 * The public key for the node 2222 * Zero or more encrypted copies of the path secret corresponding to 2223 the node 2225 The path secret value for a given node is encrypted for the subtree 2226 corresponding to the parent's non-updated child, that is, the child 2227 on the copath of the sender's leaf node. There is one encryption of 2228 the path secret to each public key in the resolution of the non- 2229 updated child. 2231 The recipient of an UpdatePath processes it with the following steps: 2233 1. Compute the updated path secrets. 2235 * Identify a node in the filtered direct path for which the 2236 recipient is in the subtree of the non-updated child. 2238 * Identify a node in the resolution of the copath node for which 2239 the recipient has a private key. 2241 * Decrypt the path secret for the parent of the copath node 2242 using the private key from the resolution node. 2244 * Derive path secrets for ancestors of that node using the 2245 algorithm described above. 2247 * The recipient SHOULD verify that the received public keys 2248 agree with the public keys derived from the new path_secret 2249 values. 2251 2. Merge the updated path secrets into the tree. 2253 * Blank all nodes on the direct path of the sender's leaf. 2255 * For all nodes on the filtered direct path of the sender's 2256 leaf, 2258 - Set the public key to the received public key. 2260 - Set the list of unmerged leaves to the empty list. 2262 - Store the updated hash of the next node on the filtered 2263 direct path (represented as a ParentNode struct), going 2264 from root to leaf, so that each hash incorporates all the 2265 non-blank nodes above it. The root node always has a zero- 2266 length hash for this value. 2268 * For nodes where a path secret was recovered in step 1 2269 ("Compute the updated path secrets"), compute and store the 2270 node's updated private key. 2272 For example, in order to communicate the example update described in 2273 the previous section, the sender would transmit the following values: 2275 +=============+====================================================+ 2276 | Public Key | Ciphertext(s) | 2277 +=============+====================================================+ 2278 | node_pub[1] | E(pk(Z), path_secret[1]), E(pk(C), path_secret[1]) | 2279 +-------------+----------------------------------------------------+ 2280 | node_pub[0] | E(pk(A), path_secret[0]) | 2281 +-------------+----------------------------------------------------+ 2283 Table 2 2285 In this table, the value node_pub[i] represents the public key 2286 derived from node_secret[i], pk(X) represents the current public key 2287 of node X, and E(K, S) represents the public-key encryption of the 2288 path secret S to the public key K (using HPKE). 2290 After processing the update, each recipient MUST delete outdated key 2291 material, specifically: 2293 * The path secrets used to derive each updated node key pair. 2295 * Each outdated node key pair that was replaced by the update. 2297 8.7. Tree Hashes 2299 To allow group members to verify that they agree on the public 2300 cryptographic state of the group, this section defines a scheme for 2301 generating a hash value (called the "tree hash") that represents the 2302 contents of the group's ratchet tree and the members' leaf nodes. 2303 The tree hash of a tree is the tree hash of its root node, which we 2304 define recursively, starting with the leaves. 2306 The tree hash of a leaf node is the hash of leaf's LeafNodeHashInput 2307 object which might include a LeafNode object depending on whether or 2308 not it is blank. 2310 struct { 2311 uint32 leaf_index; 2312 optional leaf_node; 2313 } LeafNodeHashInput; 2315 Now the tree hash of any non-leaf node is recursively defined to be 2316 the hash of its ParentNodeHashInput. This includes an optional 2317 ParentNode object depending on whether the node is blank or not. 2319 struct { 2320 optional parent_node; 2321 opaque left_hash; 2322 opaque right_hash; 2323 } ParentNodeHashInput; 2325 The left_hash and right_hash fields hold the tree hashes of the 2326 node's left and right children, respectively. 2328 8.8. Parent Hash 2330 The parent_hash field in ratchet tree nodes carries information to 2331 authenticate the information in the ratchet tree. Parent hashes 2332 chain together so that the signature on a leaf node, by covering the 2333 leaf node's parent hash, indirectly includes information about the 2334 structure of the tree at the time the leaf node was last updated. 2336 Consider a ratchet tree with a non-blank parent node P and children V 2337 and S. 2339 ... 2340 / 2341 P 2342 __|__ 2343 / \ 2344 V S 2345 / \ / \ 2346 ... ... ... ... 2348 The parent hash of P changes whenever an UpdatePath object is applied 2349 to the ratchet tree along a path from a leaf U traversing node V (and 2350 hence also P). The new "Parent hash of P (with copath child S)" is 2351 obtained by hashing P's ParentHashInput struct. 2353 struct { 2354 HPKEPublicKey encryption_key; 2355 opaque parent_hash; 2356 opaque original_sibling_tree_hash; 2357 } ParentHashInput; 2359 The field encryption_key contains the HPKE public key of P. If P is 2360 the root, then the parent_hash field is set to a zero-length octet 2361 string. Otherwise, parent_hash is the Parent Hash of the next node 2362 after P on the filtered direct path of U. This way, P's Parent Hash 2363 fixes the new HPKE public key of each node V on the path from P to 2364 the root. Note that the path from P to the root may contain some 2365 blank nodes that are not fixed by P's Parent Hash. However, for each 2366 node that has an HPKE key, this key is fixed by P's Parent Hash. 2368 Finally, original_sibling_tree_hash is the tree hash of S in the 2369 ratchet tree modified as follows: 2371 * Extend the subtree of S by adding blank leaves until it is full, 2372 i.e., until its number of leaves is a power of 2 (see 2373 Section 8.5). 2375 * For each leaf L in P.unmerged_leaves, blank L and remove it from 2376 the unmerged_leaves sets of all parent nodes. 2378 Observe that original_sibling_tree_hash does not change between 2379 updates of P. This property is crucial for the correctness of the 2380 protocol. 2382 For example, in the following tree: 2384 W [F] 2385 ______|_____ 2386 / \ 2387 U Y [F] 2388 __|__ __|__ 2389 / \ / \ 2390 T _ _ | 2391 / \ / \ / \ | 2392 A B C D E F G 2394 Figure 12: A tree illustrating parent hash computations. 2396 With P = W and S = Y, original_sibling_tree_hash is the tree hash of 2397 the following tree: 2399 Y 2400 __|__ 2401 / \ 2402 _ _ 2403 / \ / \ 2404 E _ G _ 2406 Because W.unmerged_leaves includes F, F is blanked and removed from 2407 Y.unmerged_leaves. 2409 Note that no recomputation is needed if the tree hash of S is 2410 unchanged since the last time P was updated. This is the case for 2411 computing or processing a Commit whose UpdatePath traverses P, since 2412 the Commit itself resets P. (In other words, it is only necessary to 2413 recompute the original sibling tree hash when validating group's tree 2414 on joining.) More generally, if none of the entries in 2415 P.unmerged_leaves is in the subtree under S (and thus no nodes were 2416 truncated), then the original tree hash at S is the tree hash of S in 2417 the current tree. 2419 If it is necessary to recompute the original tree hash of a node, the 2420 efficiency of recomputation can be improved by caching intermediate 2421 tree hashes, to avoid recomputing over the subtree when the subtree 2422 is included in multiple parent hashes. A subtree hash can be reused 2423 as long as the intersection of the parent's unmerged leaves with the 2424 subtree is the same as in the earlier computation. 2426 8.8.1. Using Parent Hashes 2428 The Parent Hash of P appears in three types of structs. If V is 2429 itself a parent node then P's Parent Hash is stored in the 2430 parent_hash field of the structs ParentHashInput and ParentNode of 2431 the node before P on the filtered direct path of U. (The ParentNode 2432 struct is used to encapsulate all public information about that node 2433 that must be conveyed to a new member joining the group as well as to 2434 define its Tree Hash.) 2436 If, on the other hand, V is the leaf U and its LeafNode has 2437 leaf_node_source set to commit, then the Parent Hash of P (with V's 2438 sibling as copath child) is stored in the parent_hash field. This is 2439 true in particular of the LeafNode object sent in the leaf_node field 2440 of an UpdatePath. The signature of such a LeafNode thus also attests 2441 to which keys the group member introduced into the ratchet tree and 2442 to whom the corresponding secret keys were sent. This helps prevent 2443 malicious insiders from constructing artificial ratchet trees with a 2444 node V whose HPKE secret key is known to the insider yet where the 2445 insider isn't assigned a leaf in the subtree rooted at V. Indeed, 2446 such a ratchet tree would violate the tree invariant. 2448 8.8.2. Verifying Parent Hashes 2450 Parent hashes are verified at two points in the protocol: When 2451 joining a group and when processing a Commit. 2453 The parent hash in a node U is valid with respect to a parent node P 2454 if the following criteria hold: 2456 * U is a descendant of P in the tree 2458 * The nodes between U and P in the tree are all blank 2460 * The parent_hash field of U is equal to the parent hash of P with 2461 copath child S, where S is the child of P that is not on the path 2462 from U to P. 2464 A parent node P is "parent-hash valid" if it can be chained back to a 2465 leaf node in this way. That is, if there is leaf node L and a 2466 sequence of parent nodes P_1, ..., P_N such that P_N = P and each 2467 step in the chain is authenticated by a parent hash: L's parent hash 2468 is valid with respect to P_1, P_1's parent hash is valid with respect 2469 to P_2, and so on. 2471 When joining a group, the new member MUST authenticate that each non- 2472 blank parent node P is parent-hash valid. This can be done "bottom 2473 up" by building chains up from leaves and verifying that all non- 2474 blank parent nodes are covered by exactly one such chain, or "top 2475 down" by verifying that there is exactly one descendant of each non- 2476 blank parent node for which the parent node is parent-hash valid. 2478 When processing a Commit message that includes an UpdatePath, clients 2479 MUST recompute the expected value of parent_hash for the committer's 2480 new leaf and verify that it matches the parent_hash value in the 2481 supplied leaf_node. After being merged into the tree, the nodes in 2482 the UpdatePath form a parent-hash chain from the committer's leaf to 2483 the root. 2485 8.9. Update Paths 2487 As described in Section 13.2, each MLS Commit message may optionally 2488 transmit a LeafNode and parent node values along its direct path. 2489 The path contains a public key and encrypted secret value for all 2490 intermediate nodes in the filtered direct path from the leaf to the 2491 root. The path is ordered from the closest node to the leaf to the 2492 root; each node MUST be the parent of its predecessor. 2494 struct { 2495 opaque kem_output; 2496 opaque ciphertext; 2497 } HPKECiphertext; 2499 struct { 2500 HPKEPublicKey encryption_key; 2501 HPKECiphertext encrypted_path_secret; 2502 } UpdatePathNode; 2504 struct { 2505 LeafNode leaf_node; 2506 UpdatePathNode nodes; 2507 } UpdatePath; 2509 For each UpdatePathNode, the resolution of the corresponding copath 2510 node MUST be filtered by removing all new leaf nodes added as part of 2511 this MLS Commit message. The number of ciphertexts in the 2512 encrypted_path_secret vector MUST be equal to the length of the 2513 filtered resolution, with each ciphertext being the encryption to the 2514 respective resolution node. 2516 The HPKECiphertext values are computed as 2518 kem_output, context = SetupBaseS(node_public_key, group_context) 2519 ciphertext = context.Seal("", path_secret) 2520 where node_public_key is the public key of the node that the path 2521 secret is being encrypted for, group_context is the current 2522 GroupContext object for the group, and the functions SetupBaseS and 2523 Seal are defined according to [RFC9180]. 2525 Decryption is performed in the corresponding way, using the private 2526 key of the resolution node. 2528 9. Key Schedule 2530 Group keys are derived using the Extract and Expand functions from 2531 the KDF for the group's ciphersuite, as well as the functions defined 2532 below: 2534 ExpandWithLabel(Secret, Label, Context, Length) = 2535 KDF.Expand(Secret, KDFLabel, Length) 2537 DeriveSecret(Secret, Label) = 2538 ExpandWithLabel(Secret, Label, "", KDF.Nh) 2540 Where KDFLabel is specified as: 2542 struct { 2543 uint16 length = Length; 2544 opaque label = "MLS 1.0 " + Label; 2545 opaque context = Context; 2546 } KDFLabel; 2548 The value KDF.Nh is the size of an output from KDF.Extract, in bytes. 2549 In the below diagram: 2551 * KDF.Extract takes its salt argument from the top and its Input Key 2552 Material (IKM) argument from the left 2554 * DeriveSecret takes its Secret argument from the incoming arrow 2556 * 0 represents an all-zero byte string of length KDF.Nh. 2558 When processing a handshake message, a client combines the following 2559 information to derive new epoch secrets: 2561 * The init secret from the previous epoch 2563 * The commit secret for the current epoch 2565 * The GroupContext object for current epoch 2566 Given these inputs, the derivation of secrets for an epoch proceeds 2567 as shown in the following diagram: 2569 init_secret_[n-1] 2570 | 2571 | 2572 V 2573 commit_secret --> KDF.Extract 2574 | 2575 | 2576 V 2577 ExpandWithLabel(., "joiner", GroupContext_[n], KDF.Nh) 2578 | 2579 | 2580 V 2581 joiner_secret 2582 | 2583 | 2584 V 2585 psk_secret (or 0) --> KDF.Extract 2586 | 2587 | 2588 +--> DeriveSecret(., "welcome") 2589 | = welcome_secret 2590 | 2591 V 2592 ExpandWithLabel(., "epoch", GroupContext_[n], KDF.Nh) 2593 | 2594 | 2595 V 2596 epoch_secret 2597 | 2598 | 2599 +--> DeriveSecret(.,