idnits 2.17.1 draft-ietf-mls-protocol-11.txt: 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: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 3 instances of too long lines in the document, the longest one being 20 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 22, 2020) is 1221 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 771, but not defined == Missing Reference: 'CD' is mentioned on line 771, but not defined == Missing Reference: 'A' is mentioned on line 771, but not defined -- Looks like a reference, but probably isn't: '0' on line 1061 -- Looks like a reference, but probably isn't: '1' on line 3855 == Missing Reference: 'X' is mentioned on line 958, but not defined -- Looks like a reference, but probably isn't: '4' on line 2121 -- Looks like a reference, but probably isn't: '2' on line 3857 == Outdated reference: A later version (-12) exists of draft-irtf-cfrg-hpke-07 == Outdated reference: A later version (-13) exists of draft-ietf-mls-architecture-05 == Outdated reference: A later version (-42) exists of draft-ietf-trans-rfc6962-bis-34 Summary: 1 error (**), 0 flaws (~~), 8 warnings (==), 6 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: June 25, 2021 Inria 6 J. Millican 7 Facebook 8 E. Omara 9 Google 10 K. Cohn-Gordon 11 University of Oxford 12 R. Robert 13 Wire 14 December 22, 2020 16 The Messaging Layer Security (MLS) Protocol 17 draft-ietf-mls-protocol-11 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 Status of This Memo 34 This Internet-Draft is submitted in full conformance with the 35 provisions of BCP 78 and BCP 79. 37 Internet-Drafts are working documents of the Internet Engineering 38 Task Force (IETF). Note that other groups may also distribute 39 working documents as Internet-Drafts. The list of current Internet- 40 Drafts is at https://datatracker.ietf.org/drafts/current/. 42 Internet-Drafts are draft documents valid for a maximum of six months 43 and may be updated, replaced, or obsoleted by other documents at any 44 time. It is inappropriate to use Internet-Drafts as reference 45 material or to cite them other than as "work in progress." 47 This Internet-Draft will expire on June 25, 2021. 49 Copyright Notice 51 Copyright (c) 2020 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (https://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 67 1.1. Change Log . . . . . . . . . . . . . . . . . . . . . . . 5 68 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 9 69 3. Basic Assumptions . . . . . . . . . . . . . . . . . . . . . . 9 70 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 10 71 5. Ratchet Trees . . . . . . . . . . . . . . . . . . . . . . . . 13 72 5.1. Tree Computation Terminology . . . . . . . . . . . . . . 14 73 5.2. Ratchet Tree Nodes . . . . . . . . . . . . . . . . . . . 16 74 5.3. Views of a Ratchet Tree . . . . . . . . . . . . . . . . . 17 75 5.4. Ratchet Tree Evolution . . . . . . . . . . . . . . . . . 18 76 5.5. Synchronizing Views of the Tree . . . . . . . . . . . . . 20 77 6. Cryptographic Objects . . . . . . . . . . . . . . . . . . . . 21 78 6.1. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . 21 79 6.2. Credentials . . . . . . . . . . . . . . . . . . . . . . . 22 80 7. Key Packages . . . . . . . . . . . . . . . . . . . . . . . . 24 81 7.1. Client Capabilities . . . . . . . . . . . . . . . . . . . 25 82 7.2. Lifetime . . . . . . . . . . . . . . . . . . . . . . . . 26 83 7.3. KeyPackage Identifiers . . . . . . . . . . . . . . . . . 26 84 7.4. Parent Hash . . . . . . . . . . . . . . . . . . . . . . . 26 85 7.4.1. Using Parent Hashes . . . . . . . . . . . . . . . . . 27 86 7.4.2. Verifying Parent Hashes . . . . . . . . . . . . . . . 27 87 7.5. Tree Hashes . . . . . . . . . . . . . . . . . . . . . . . 28 88 7.6. Group State . . . . . . . . . . . . . . . . . . . . . . . 29 89 7.7. Update Paths . . . . . . . . . . . . . . . . . . . . . . 31 90 8. Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . 32 91 8.1. External Initialization . . . . . . . . . . . . . . . . . 34 92 8.2. Pre-Shared Keys . . . . . . . . . . . . . . . . . . . . . 35 93 8.3. Secret Tree . . . . . . . . . . . . . . . . . . . . . . . 37 94 8.4. Encryption Keys . . . . . . . . . . . . . . . . . . . . . 38 95 8.5. Deletion Schedule . . . . . . . . . . . . . . . . . . . . 39 96 8.6. Exporters . . . . . . . . . . . . . . . . . . . . . . . . 40 97 8.7. Resumption Secret . . . . . . . . . . . . . . . . . . . . 41 98 8.8. State Authentication Keys . . . . . . . . . . . . . . . . 41 99 9. Message Framing . . . . . . . . . . . . . . . . . . . . . . . 41 100 9.1. Content Authentication . . . . . . . . . . . . . . . . . 43 101 9.2. Content Encryption . . . . . . . . . . . . . . . . . . . 45 102 9.3. Sender Data Encryption . . . . . . . . . . . . . . . . . 46 103 10. Group Creation . . . . . . . . . . . . . . . . . . . . . . . 47 104 10.1. Linking a New Group to an Existing Group . . . . . . . . 48 105 10.1.1. Sub-group Branching . . . . . . . . . . . . . . . . 49 106 11. Group Evolution . . . . . . . . . . . . . . . . . . . . . . . 49 107 11.1. Proposals . . . . . . . . . . . . . . . . . . . . . . . 49 108 11.1.1. Add . . . . . . . . . . . . . . . . . . . . . . . . 50 109 11.1.2. Update . . . . . . . . . . . . . . . . . . . . . . . 51 110 11.1.3. Remove . . . . . . . . . . . . . . . . . . . . . . . 51 111 11.1.4. PreSharedKey . . . . . . . . . . . . . . . . . . . . 52 112 11.1.5. ReInit . . . . . . . . . . . . . . . . . . . . . . . 52 113 11.1.6. ExternalInit . . . . . . . . . . . . . . . . . . . . 53 114 11.1.7. AppAck . . . . . . . . . . . . . . . . . . . . . . . 53 115 11.1.8. External Proposals . . . . . . . . . . . . . . . . . 54 116 11.2. Commit . . . . . . . . . . . . . . . . . . . . . . . . . 55 117 11.2.1. External Commits . . . . . . . . . . . . . . . . . . 61 118 11.2.2. Welcoming New Members . . . . . . . . . . . . . . . 63 119 11.3. Ratchet Tree Extension . . . . . . . . . . . . . . . . . 66 120 12. Extensibility . . . . . . . . . . . . . . . . . . . . . . . . 67 121 13. Sequencing of State Changes . . . . . . . . . . . . . . . . . 69 122 13.1. Server-Enforced Ordering . . . . . . . . . . . . . . . . 70 123 13.2. Client-Enforced Ordering . . . . . . . . . . . . . . . . 70 124 14. Application Messages . . . . . . . . . . . . . . . . . . . . 70 125 14.1. Message Encryption and Decryption . . . . . . . . . . . 71 126 14.2. Restrictions . . . . . . . . . . . . . . . . . . . . . . 72 127 14.3. Delayed and Reordered Application messages . . . . . . . 72 128 15. Security Considerations . . . . . . . . . . . . . . . . . . . 72 129 15.1. Confidentiality of the Group Secrets . . . . . . . . . . 72 130 15.2. Authentication . . . . . . . . . . . . . . . . . . . . . 73 131 15.3. Forward Secrecy and Post-Compromise Security . . . . . . 73 132 15.4. InitKey Reuse . . . . . . . . . . . . . . . . . . . . . 73 133 15.5. Group Fragmentation by Malicious Insiders . . . . . . . 74 134 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 74 135 16.1. MLS Ciphersuites . . . . . . . . . . . . . . . . . . . . 75 136 16.2. MLS Extension Types . . . . . . . . . . . . . . . . . . 78 137 16.3. MLS Credential Types . . . . . . . . . . . . . . . . . . 79 138 16.4. MLS Designated Expert Pool . . . . . . . . . . . . . . . 80 139 17. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 81 140 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 82 141 18.1. Normative References . . . . . . . . . . . . . . . . . . 82 142 18.2. Informative References . . . . . . . . . . . . . . . . . 82 143 18.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 83 144 Appendix A. Tree Math . . . . . . . . . . . . . . . . . . . . . 84 145 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 87 147 1. Introduction 149 DISCLAIMER: This is a work-in-progress draft of MLS and has not yet 150 seen significant security analysis. It should not be used as a basis 151 for building production systems. 153 RFC EDITOR: PLEASE REMOVE THE FOLLOWING PARAGRAPH The source for this 154 draft is maintained in GitHub. Suggested changes should be submitted 155 as pull requests at https://github.com/mlswg/mls-protocol. 156 Instructions are on that page as well. Editorial changes can be 157 managed in GitHub, but any substantive change should be discussed on 158 the MLS mailing list. 160 A group of users who want to send each other encrypted messages needs 161 a way to derive shared symmetric encryption keys. For two parties, 162 this problem has been studied thoroughly, with the Double Ratchet 163 emerging as a common solution [doubleratchet] [signal]. Channels 164 implementing the Double Ratchet enjoy fine-grained forward secrecy as 165 well as post-compromise security, but are nonetheless efficient 166 enough for heavy use over low-bandwidth networks. 168 For a group of size greater than two, a common strategy is to 169 unilaterally broadcast symmetric "sender" keys over existing shared 170 symmetric channels, and then for each member to send messages to the 171 group encrypted with their own sender key. Unfortunately, while this 172 improves efficiency over pairwise broadcast of individual messages 173 and provides forward secrecy (with the addition of a hash ratchet), 174 it is difficult to achieve post-compromise security with sender keys. 175 An adversary who learns a sender key can often indefinitely and 176 passively eavesdrop on that member's messages. Generating and 177 distributing a new sender key provides a form of post-compromise 178 security with regard to that sender. However, it requires 179 computation and communications resources that scale linearly with the 180 size of the group. 182 In this document, we describe a protocol based on tree structures 183 that enable asynchronous group keying with forward secrecy and post- 184 compromise security. Based on earlier work on "asynchronous 185 ratcheting trees" [art], the protocol presented here uses an 186 asynchronous key-encapsulation mechanism for tree structures. This 187 mechanism allows the members of the group to derive and update shared 188 keys with costs that scale as the log of the group size. 190 1.1. Change Log 192 RFC EDITOR PLEASE DELETE THIS SECTION. 194 draft-10 196 o Allow new members to join via an external Commit (*) 198 o Enable proposals to be sent inline in a Commit (*) 200 o Re-enable constant-time Add (*) 202 o Change expiration extension to lifetime extension (*) 204 o Make the tree in the Welcome optional (*) 206 o PSK injection, re-init, sub-group branching (*) 208 o Require the initial init_secret to be a random value (*) 210 o Remove explicit sender data nonce (*) 212 o Do not encrypt to joiners in UpdatePath generation (*) 214 o Move MLSPlaintext signature under the confirmation tag (*) 216 o Explicitly authenticate group membership with MLSPLaintext (*) 218 o Clarify X509Credential structure (*) 220 o Remove uneeded interim transcript hash from GroupInfo (*) 222 o IANA considerations 224 o Derive an authentication secret 226 o Use Extract/Expand from HPKE KDF 228 o Clarify that application messages MUST be encrypted 230 draft-09 232 o Remove blanking of nodes on Add (*) 234 o Change epoch numbers to uint64 (*) 236 o Add PSK inputs (*) 237 o Add key schedule exporter (*) 239 o Sign the updated direct path on Commit, using "parent hashes" and 240 one signature per leaf (*) 242 o Use structured types for external senders (*) 244 o Redesign Welcome to include confirmation and use derived keys (*) 246 o Remove ignored proposals (*) 248 o Always include an Update with a Commit (*) 250 o Add per-message entropy to guard against nonce reuse (*) 252 o Use the same hash ratchet construct for both application and 253 handshake keys (*) 255 o Add more ciphersuites 257 o Use HKDF to derive key pairs (*) 259 o Mandate expiration of ClientInitKeys (*) 261 o Add extensions to GroupContext and flesh out the extensibility 262 story (*) 264 o Rename ClientInitKey to KeyPackage 266 draft-08 268 o Change ClientInitKeys so that they only refer to one ciphersuite 269 (*) 271 o Decompose group operations into Proposals and Commits (*) 273 o Enable Add and Remove proposals from outside the group (*) 275 o Replace Init messages with multi-recipient Welcome message (*) 277 o Add extensions to ClientInitKeys for expiration and downgrade 278 resistance (*) 280 o Allow multiple Proposals and a single Commit in one MLSPlaintext 281 (*) 283 draft-07 284 o Initial version of the Tree based Application Key Schedule (*) 286 o Initial definition of the Init message for group creation (*) 288 o Fix issue with the transcript used for newcomers (*) 290 o Clarifications on message framing and HPKE contexts (*) 292 draft-06 294 o Reorder blanking and update in the Remove operation (*) 296 o Rename the GroupState structure to GroupContext (*) 298 o Rename UserInitKey to ClientInitKey 300 o Resolve the circular dependency that draft-05 introduced in the 301 confirmation MAC calculation (*) 303 o Cover the entire MLSPlaintext in the transcript hash (*) 305 draft-05 307 o Common framing for handshake and application messages (*) 309 o Handshake message encryption (*) 311 o Convert from literal state to a commitment via the "tree hash" (*) 313 o Add credentials to the tree and remove the "roster" concept (*) 315 o Remove the secret field from tree node values 317 draft-04 319 o Updating the language to be similar to the Architecture document 321 o ECIES is now renamed in favor of HPKE (*) 323 o Using a KDF instead of a Hash in TreeKEM (*) 325 draft-03 327 o Added ciphersuites and signature schemes (*) 329 o Re-ordered fields in UserInitKey to make parsing easier (*) 331 o Fixed inconsistencies between Welcome and GroupState (*) 332 o Added encryption of the Welcome message (*) 334 draft-02 336 o Removed ART (*) 338 o Allowed partial trees to avoid double-joins (*) 340 o Added explicit key confirmation (*) 342 draft-01 344 o Initial description of the Message Protection mechanism. (*) 346 o Initial specification proposal for the Application Key Schedule 347 using the per-participant chaining of the Application Secret 348 design. (*) 350 o Initial specification proposal for an encryption mechanism to 351 protect Application Messages using an AEAD scheme. (*) 353 o Initial specification proposal for an authentication mechanism of 354 Application Messages using signatures. (*) 356 o Initial specification proposal for a padding mechanism to 357 improving protection of Application Messages against traffic 358 analysis. (*) 360 o Inversion of the Group Init Add and Application Secret derivations 361 in the Handshake Key Schedule to be ease chaining in case we 362 switch design. (*) 364 o Removal of the UserAdd construct and split of GroupAdd into Add 365 and Welcome messages (*) 367 o Initial proposal for authenticating handshake messages by signing 368 over group state and including group state in the key schedule (*) 370 o Added an appendix with example code for tree math 372 o Changed the ECIES mechanism used by TreeKEM so that it uses nonces 373 generated from the shared secret 375 draft-00 377 o Initial adoption of draft-barnes-mls-protocol-01 as a WG item. 379 2. Terminology 381 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 382 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 383 "OPTIONAL" in this document are to be interpreted as described in BCP 384 14 [RFC2119] [RFC8174] when, and only when, they appear in all 385 capitals, as shown here. 387 Client: An agent that uses this protocol to establish shared 388 cryptographic state with other clients. A client is defined by 389 the cryptographic keys it holds. 391 Group: A collection of clients with shared cryptographic state. 393 Member: A client that is included in the shared state of a group, 394 hence has access to the group's secrets. 396 Key Package: A signed object describing a client's identity and 397 capabilities, and including a hybrid public-key encryption (HPKE 398 [I-D.irtf-cfrg-hpke]) public key that can be used to encrypt to 399 that client. 401 Initialization Key (InitKey): A key package that is prepublished by 402 a client, which other clients can use to introduce the client to a 403 new group. 405 Signature Key: A signing key pair used to authenticate the sender of 406 a message. 408 Terminology specific to tree computations is described in Section 5. 410 We use the TLS presentation language [RFC8446] to describe the 411 structure of protocol messages. 413 3. Basic Assumptions 415 This protocol is designed to execute in the context of a Service 416 Provider (SP) as described in [I-D.ietf-mls-architecture]. In 417 particular, we assume the SP provides the following services: 419 o A signature key provider which allows clients to authenticate 420 protocol messages in a group. 422 o A broadcast channel, for each group, which will relay a message to 423 all members of a group. For the most part, we assume that this 424 channel delivers messages in the same order to all participants. 425 (See Section 13 for further considerations.) 427 o A directory to which clients can publish key packages and download 428 key packages for other participants. 430 4. Protocol Overview 432 The goal of this protocol is to allow a group of clients to exchange 433 confidential and authenticated messages. It does so by deriving a 434 sequence of secrets and keys known only to members. Those should be 435 secret against an active network adversary and should have both 436 forward secrecy and post-compromise security with respect to 437 compromise of any members. 439 We describe the information stored by each client as _state_, which 440 includes both public and private data. An initial state is set up by 441 a group creator, which is a group containing only itself. The 442 creator then sends _Add_ proposals for each client in the initial set 443 of members, followed by a _Commit_ message which incorporates all of 444 the _Adds_ into the group state. Finally, the group creator 445 generates a _Welcome_ message corresponding to the Commit and sends 446 this directly to all the new members, who can use the information it 447 contains to set up their own group state and derive a shared secret. 448 Members exchange Commit messages for post-compromise security, to add 449 new members, and to remove existing members. These messages produce 450 new shared secrets which are causally linked to their predecessors, 451 forming a logical Directed Acyclic Graph (DAG) of states. 453 The protocol algorithms we specify here follow. Each algorithm 454 specifies both (i) how a client performs the operation and (ii) how 455 other clients update their state based on it. 457 There are three major operations in the lifecycle of a group: 459 o Adding a member, initiated by a current member; 461 o Updating the leaf secret of a member; 463 o Removing a member. 465 Each of these operations is "proposed" by sending a message of the 466 corresponding type (Add / Update / Remove). The state of the group 467 is not changed, however, until a Commit message is sent to provide 468 the group with fresh entropy. In this section, we show each proposal 469 being committed immediately, but in more advanced deployment cases an 470 application might gather several proposals before committing them all 471 at once. 473 Before the initialization of a group, clients publish InitKeys (as 474 KeyPackage objects) to a directory provided by the Service Provider. 476 Group 477 A B C Directory Channel 478 | | | | | 479 | KeyPackageA | | | | 480 |------------------------------------------------->| | 481 | | | | | 482 | | KeyPackageB | | | 483 | |-------------------------------->| | 484 | | | | | 485 | | | KeyPackageC | | 486 | | |--------------->| | 487 | | | | | 489 When a client A wants to establish a group with B and C, it first 490 initializes a group state containing only itself and downloads 491 KeyPackages for B and C. For each member, A generates an Add and 492 Commit message adding that member, and broadcasts them to the group. 493 It also generates a Welcome message and sends this directly to the 494 new member (there's no need to send it to the group). Only after A 495 has received its Commit message back from the server does it update 496 its state to reflect the new member's addition. 498 Upon receiving the Welcome message and the corresponding Commit, the 499 new member will be able to read and send new messages to the group. 500 Messages received before the client has joined the group are ignored. 502 Group 503 A B C Directory Channel 504 | | | | | 505 | KeyPackageB, KeyPackageC | | 506 |<-------------------------------------------| | 507 |state.init() | | | | 508 | | | | | 509 | | | | Add(A->AB) | 510 | | | | Commit(Add) | 511 |--------------------------------------------------------------->| 512 | | | | | 513 | Welcome(B) | | | | 514 |------------->|state.init() | | | 515 | | | | | 516 | | | | Add(A->AB) | 517 | | | | Commit(Add) | 518 |<---------------------------------------------------------------| 519 |state.add(B) |<------------------------------------------------| 520 | |state.join() | | | 521 | | | | | 522 | | | | Add(AB->ABC) | 523 | | | | Commit(Add) | 524 |--------------------------------------------------------------->| 525 | | | | | 526 | | Welcome(C) | | | 527 |---------------------------->|state.init() | | 528 | | | | | 529 | | | | Add(AB->ABC) | 530 | | | | Commit(Add) | 531 |<---------------------------------------------------------------| 532 |state.add(C) |<------------------------------------------------| 533 | |state.add(C) |<---------------------------------| 534 | | |state.join() | | 536 Subsequent additions of group members proceed in the same way. Any 537 member of the group can download a KeyPackage for a new client and 538 broadcast an Add message that the current group can use to update 539 their state, and a Welcome message that the new client can use to 540 initialize its state. 542 To enforce the forward secrecy and post-compromise security of 543 messages, each member periodically updates their leaf secret. Any 544 member can update this information at any time by generating a fresh 545 KeyPackage and sending an Update message followed by a Commit 546 message. Once all members have processed both, the group's secrets 547 will be unknown to an attacker that had compromised the sender's 548 prior leaf secret. 550 Update messages should be sent at regular intervals of time as long 551 as the group is active, and members that don't update should 552 eventually be removed from the group. It's left to the application 553 to determine an appropriate amount of time between Updates. 555 Group 556 A B ... Z Directory Channel 557 | | | | | 558 | | Update(B) | | | 559 | |------------------------------------------->| 560 | Commit(Upd) | | | | 561 |---------------------------------------------------------->| 562 | | | | | 563 | | | | Update(B) | 564 | | | | Commit(Upd) | 565 |<----------------------------------------------------------| 566 |state.upd(B) |<-------------------------------------------| 567 | |state.upd(B) |<----------------------------| 568 | | |state.upd(B) | | 569 | | | | | 571 Members are removed from the group in a similar way. Any member of 572 the group can send a Remove proposal followed by a Commit message, 573 which adds new entropy to the group state that's known to all except 574 the removed member. Note that this does not necessarily imply that 575 any member is actually allowed to evict other members; groups can 576 enforce access control policies on top of these basic mechanism. 578 Group 579 A B ... Z Directory Channel 580 | | | | | 581 | | | Remove(B) | | 582 | | | Commit(Rem) | | 583 | | |---------------------------->| 584 | | | | | 585 | | | | Remove(B) | 586 | | | | Commit(Rem) | 587 |<----------------------------------------------------------| 588 |state.rem(B) | |<----------------------------| 589 | | |state.rem(B) | | 590 | | | | | 591 | | | | | 593 5. Ratchet Trees 595 The protocol uses "ratchet trees" for deriving shared secrets among a 596 group of clients. 598 5.1. Tree Computation Terminology 600 Trees consist of _nodes_. A node is a _leaf_ if it has no children, 601 and a _parent_ otherwise; note that all parents in our trees have 602 precisely two children, a _left_ child and a _right_ child. A node 603 is the _root_ of a tree if it has no parents, and _intermediate_ if 604 it has both children and parents. The _descendants_ of a node are 605 that node, its children, and the descendants of its children, and we 606 say a tree _contains_ a node if that node is a descendant of the root 607 of the tree. Nodes are _siblings_ if they share the same parent. 609 A _subtree_ of a tree is the tree given by the descendants of any 610 node, the _head_ of the subtree. The _size_ of a tree or subtree is 611 the number of leaf nodes it contains. For a given parent node, its 612 _left subtree_ is the subtree with its left child as head 613 (respectively _right subtree_). 615 All trees used in this protocol are left-balanced binary trees. A 616 binary tree is _full_ (and _balanced_) if its size is a power of two 617 and for any parent node in the tree, its left and right subtrees have 618 the same size. 620 A binary tree is _left-balanced_ if for every parent, either the 621 parent is balanced, or the left subtree of that parent is the largest 622 full subtree that could be constructed from the leaves present in the 623 parent's own subtree. Given a list of "n" items, there is a unique 624 left-balanced binary tree structure with these elements as leaves. 626 (Note that left-balanced binary trees are the same structure that is 627 used for the Merkle trees in the Certificate Transparency protocol 628 [I-D.ietf-trans-rfc6962-bis].) 630 The _direct path_ of a root is the empty list, and of any other node 631 is the concatenation of that node's parent along with the parent's 632 direct path. The _copath_ of a node is the node's sibling 633 concatenated with the list of siblings of all the nodes in its direct 634 path, excluding the root. 636 For example, in the below tree: 638 o The direct path of C is (CD, ABCD, ABCDEFG) 640 o The copath of C is (D, AB, EFG) 641 ABCDEFG 642 / \ 643 / \ 644 / \ 645 ABCD EFG 646 / \ / \ 647 / \ / \ 648 AB CD EF | 649 / \ / \ / \ | 650 A B C D E F G 652 1 1 1 653 0 1 2 3 4 5 6 7 8 9 0 1 2 655 Each node in the tree is assigned a _node index_, starting at zero 656 and running from left to right. A node is a leaf node if and only if 657 it has an even index. The node indices for the nodes in the above 658 tree are as follows: 660 o 0 = A 662 o 1 = AB 664 o 2 = B 666 o 3 = ABCD 668 o 4 = C 670 o 5 = CD 672 o 6 = D 674 o 7 = ABCDEFG 676 o 8 = E 678 o 9 = EF 680 o 10 = F 682 o 11 = EFG 684 o 12 = G 686 The leaves of the tree are indexed separately, using a _leaf index_, 687 since the protocol messages only need to refer to leaves in the tree. 688 Like nodes, leaves are numbered left to right. The node with leaf 689 index "k" is also called the "k-th" leaf. Note that given the above 690 numbering, a node is a leaf node if and only if it has an even node 691 index, and a leaf node's leaf index is half its node index. The leaf 692 indices in the above tree are as follows: 694 o 0 = A 696 o 1 = B 698 o 2 = C 700 o 3 = D 702 o 4 = E 704 o 5 = F 706 o 6 = G 708 5.2. Ratchet Tree Nodes 710 A particular instance of a ratchet tree is defined by the same 711 parameters that define an instance of HPKE, namely: 713 o A Key Encapsulation Mechanism (KEM), including a "DeriveKeyPair" 714 function that creates a key pair for the KEM from a symmetric 715 secret 717 o A Key Derivation Function (KDF), including "Extract" and "Expand" 718 functions 720 o An AEAD encryption scheme 722 Each node in a ratchet tree contains up to five values: 724 o A private key (only within the member's direct path, see below) 726 o A public key 728 o An ordered list of leaf indices for "unmerged" leaves (see 729 Section 5.3) 731 o A credential (only for leaf nodes) 733 o A hash of certain information about the node's parent, as of the 734 last time the node was changed (see Section 7.4). 736 The conditions under which each of these values must or must not be 737 present are laid out in Section 5.3. 739 A node in the tree may also be _blank_, indicating that no value is 740 present at that node. The _resolution_ of a node is an ordered list 741 of non-blank nodes that collectively cover all non-blank descendants 742 of the node. 744 o The resolution of a non-blank node comprises the node itself, 745 followed by its list of unmerged leaves, if any 747 o The resolution of a blank leaf node is the empty list 749 o The resolution of a blank intermediate node is the result of 750 concatenating the resolution of its left child with the resolution 751 of its right child, in that order 753 For example, consider the following tree, where the "_" character 754 represents a blank node: 756 _ 757 / \ 758 / \ 759 _ CD[C] 760 / \ / \ 761 A _ C D 763 0 1 2 3 4 5 6 765 In this tree, we can see all of the above rules in play: 767 o The resolution of node 5 is the list [CD, C] 769 o The resolution of node 2 is the empty list [] 771 o The resolution of node 3 is the list [A, CD, C] 773 Every node, regardless of whether the node is blank or populated, has 774 a corresponding _hash_ that summarizes the contents of the subtree 775 below that node. The rules for computing these hashes are described 776 in Section 7.5. 778 5.3. Views of a Ratchet Tree 780 We generally assume that each participant maintains a complete and 781 up-to-date view of the public state of the group's ratchet tree, 782 including the public keys for all nodes and the credentials 783 associated with the leaf nodes. 785 No participant in an MLS group knows the private key associated with 786 every node in the tree. Instead, each member is assigned to a leaf 787 of the tree, which determines the subset of private keys it knows. 788 The credential stored at that leaf is one provided by the member. 790 In particular, MLS maintains the members' views of the tree in such a 791 way as to maintain the _tree invariant_: 793 The private key for a node in the tree is known to a member of 794 the group only if that member's leaf is a descendant of 795 the node. 797 In other words, if a node is not blank, then it holds a public key. 798 The corresponding private key is known only to members occupying 799 leaves below that node. 801 The reverse implication is not true: A member may not know the 802 private keys of all the intermediate nodes they're below. Such a 803 member has an _unmerged_ leaf. Encrypting to an intermediate node 804 requires encrypting to the node's public key, as well as the public 805 keys of all the unmerged leaves below it. A leaf is unmerged when it 806 is first added, because the process of adding the leaf does not give 807 it access to all of the nodes above it in the tree. Leaves are 808 "merged" as they receive the private keys for nodes, as described in 809 Section 5.4. 811 5.4. Ratchet Tree Evolution 813 A member of an MLS group advances the key schedule to provide forward 814 secrecy and post-compromise security by providing the group with 815 fresh key material to be added into the group's shared secret. To do 816 so, one member of the group generates fresh key material, applies it 817 to their local tree state, and then sends this key material to other 818 members in the group via an UpdatePath message (see Section 7.7) . 819 All other group members then apply the key material in the UpdatePath 820 to their own local tree state to derive the group's now-updated 821 shared secret. 823 To begin, the generator of the UpdatePath updates its leaf KeyPackage 824 and its direct path to the root with new secret values. The HPKE 825 leaf public key within the KeyPackage MUST be derived from a freshly 826 generated HPKE secret key to provide post-compromise security. 828 The generator of the UpdatePath starts by sampling a fresh random 829 value called "leaf_secret", and uses the leaf_secret to generate 830 their leaf HPKE key pair (see Section 7) and to seed a sequence of 831 "path secrets", one for each ancestor of its leaf. In this setting, 832 path_secret[0] refers to the node directly above the leaf, 833 path_secret[1] for its parent, and so on. At each step, the path 834 secret is used to derive a new secret value for the corresponding 835 node, from which the node's key pair is derived. 837 leaf_node_secret = DeriveSecret(leaf_secret, "node") 838 path_secret[0] = DeriveSecret(leaf_secret, "path") 840 path_secret[n] = DeriveSecret(path_secret[n-1], "path") 841 node_secret[n] = DeriveSecret(path_secret[n], "node") 843 leaf_priv, leaf_pub = KEM.DeriveKeyPair(leaf_node_secret) 844 node_priv[n], node_pub[n] = KEM.DeriveKeyPair(node_secret[n]) 846 For example, suppose there is a group with four members: 848 G 849 / \ 850 / \ 851 / \ 852 E _ 853 / \ / \ 854 A B C D 856 If member B subsequently generates an UpdatePath based on a secret 857 "leaf_secret", then it would generate the following sequence of path 858 secrets: 860 path_secret[1] --> node_secret[1] --> node_priv[1], node_pub[1] 861 ^ 862 | 863 path_secret[0] --> node_secret[0] --> node_priv[0], node_pub[0] 864 ^ 865 | 866 leaf_secret --> leaf_node_secret --> leaf_priv, leaf_pub 867 ~> leaf_key_package 869 After applying the UpdatePath, the tree will have the following 870 structure, where "np[i]" represents the node_priv values generated as 871 described above: 873 np[1] 874 / \ 875 np[0] _ 876 / \ / \ 877 A B C D 879 After performing these operations, the generator of the UpdatePath 880 MUST delete the leaf_secret. 882 5.5. Synchronizing Views of the Tree 884 After generating fresh key material and applying it to ratchet 885 forward their local tree state as described in the prior section, the 886 generator must broadcast this update to other members of the group in 887 a Commit message, who apply it to keep their local views of the tree 888 in sync with the sender's. More specifically, when a member commits 889 a change to the tree (e.g., to add or remove a member), it transmits 890 an UpdatePath message containing a set of public and encrypted 891 private values for intermediate nodes in the direct path of a leaf. 892 The other members of the group use these values to update their view 893 of the tree, aligning their copy of the tree to the sender's. 895 To transmit this update, the sender broadcasts to the group the 896 following information for each node in the direct path of the leaf, 897 including the root: 899 o The public key for the node 901 o Zero or more encrypted copies of the path secret corresponding to 902 the node 904 The path secret value for a given node is encrypted for the subtree 905 corresponding to the parent's non-updated child, that is, the child 906 on the copath of the leaf node. There is one encrypted path secret 907 for each public key in the resolution of the non-updated child. 909 The recipient of a path update processes it with the following steps: 911 1. Compute the updated path secrets. 913 * Identify a node in the direct path for which the local member 914 is in the subtree of the non-updated child. 916 * Identify a node in the resolution of the copath node for which 917 this node has a private key. 919 * Decrypt the path secret for the parent of the copath node 920 using the private key from the resolution node. 922 * Derive path secrets for ancestors of that node using the 923 algorithm described above. 925 * The recipient SHOULD verify that the received public keys 926 agree with the public keys derived from the new path_secret 927 values. 929 2. Merge the updated path secrets into the tree. 931 * For all updated nodes, 933 + Replace the public key for each node with the received 934 public key. 936 + Set the list of unmerged leaves to the empty list. 938 + Store the updated hash of the node's parent (represented as 939 a ParentNode struct), going from root to leaf, so that each 940 hash incorporates all the nodes above it. The root node 941 always has a zero-length hash for this value. 943 * For nodes where an updated path secret was computed in step 1, 944 compute the corresponding node key pair and replace the values 945 stored at the node with the computed values. 947 For example, in order to communicate the example update described in 948 the previous section, the sender would transmit the following values: 950 +------------+----------------------------------+ 951 | Public Key | Ciphertext(s) | 952 +------------+----------------------------------+ 953 | pk(ns[1]) | E(pk(C), ps[1]), E(pk(D), ps[1]) | 954 | | | 955 | pk(ns[0]) | E(pk(A), ps[0]) | 956 +------------+----------------------------------+ 958 In this table, the value pk(ns[X]) represents the public key derived 959 from the node secret X, whereas pk(X) represents the public leaf key 960 for user X. The value E(K, S) represents the public-key encryption 961 of the path secret S to the public key K. 963 After processing the update, each recipient MUST delete outdated key 964 material, specifically: 966 o The path secrets used to derive each updated node key pair. 968 o Each outdated node key pair that was replaced by the update. 970 6. Cryptographic Objects 972 6.1. Ciphersuites 974 Each MLS session uses a single ciphersuite that specifies the 975 following primitives to be used in group key computations: 977 o HPKE parameters: 979 * A Key Encapsulation Mechanism (KEM) 981 * A Key Derivation Function (KDF) 983 * An AEAD encryption algorithm 985 o A hash algorithm 987 o A signature algorithm 989 MLS uses draft-07 of HPKE [I-D.irtf-cfrg-hpke] for public-key 990 encryption. The "DeriveKeyPair" function associated to the KEM for 991 the ciphersuite maps octet strings to HPKE key pairs. 993 Ciphersuites are represented with the CipherSuite type. HPKE public 994 keys are opaque values in a format defined by the underlying protocol 995 (see the Cryptographic Dependencies section of the HPKE specification 996 for more information). 998 opaque HPKEPublicKey<1..2^16-1>; 1000 The signature algorithm specified in the ciphersuite is the mandatory 1001 algorithm to be used for signatures in MLSPlaintext and the tree 1002 signatures. It MUST be the same as the signature algorithm specified 1003 in the credential field of the KeyPackage objects in the leaves of 1004 the tree (including the InitKeys used to add new members). 1006 The ciphersuites are defined in section Section 16.1. 1008 6.2. Credentials 1010 A member of a group authenticates the identities of other 1011 participants by means of credentials issued by some authentication 1012 system, like a PKI. Each type of credential MUST express the 1013 following data in the context of the group it is used with: 1015 o The public key of a signature key pair matching the 1016 SignatureScheme specified by the CipherSuite of the group 1018 o The identity of the holder of the private key 1020 Credentials MAY also include information that allows a relying party 1021 to verify the identity / signing key binding. 1023 Additionally, Credentials SHOULD specify the signature scheme 1024 corresponding to each contained public key. 1026 // See RFC 8446 and the IANA TLS SignatureScheme registry 1027 uint16 SignatureScheme; 1029 // See IANA registry for registered values 1030 uint16 CredentialType; 1032 struct { 1033 opaque identity<0..2^16-1>; 1034 SignatureScheme signature_scheme; 1035 opaque signature_key<0..2^16-1>; 1036 } BasicCredential; 1038 struct { 1039 opaque cert_data<0..2^16-1>; 1040 } Certificate; 1042 struct { 1043 CredentialType credential_type; 1044 select (Credential.credential_type) { 1045 case basic: 1046 BasicCredential; 1048 case x509: 1049 Certificate chain<1..2^32-1>; 1050 }; 1051 } Credential; 1053 A BasicCredential is a raw, unauthenticated assertion of an identity/ 1054 key binding. The format of the key in the "public_key" field is 1055 defined by the relevant ciphersuite: the group ciphersuite for a 1056 credential in a ratchet tree, the KeyPackage ciphersuite for a 1057 credential in a KeyPackage object. 1059 For X509Credential, each entry in the chain represents a single DER- 1060 encoded X509 certificate. The chain is ordered such that the first 1061 entry (chain[0]) is the end-entity certificate and each subsequent 1062 certificate in the chain MUST be the issuer of the previous 1063 certificate. The algorithm for the "public_key" in the end-entity 1064 certificate MUST match the relevant ciphersuite. 1066 For ciphersuites using Ed25519 or Ed448 signature schemes, the public 1067 key is in the format specified [RFC8032]. For ciphersuites using 1068 ECDSA with the NIST curves P-256 or P-521, the public key is the 1069 output of the uncompressed Elliptic-Curve-Point-to-Octet-String 1070 conversion according to [SECG]. 1072 Note that each new credential that has not already been validated by 1073 the application MUST be validated against the Authentication Service. 1075 7. Key Packages 1077 In order to facilitate asynchronous addition of clients to a group, 1078 it is possible to pre-publish key packages that provide some public 1079 information about a user. KeyPackage structures provide information 1080 about a client that any existing member can use to add this client to 1081 the group asynchronously. 1083 A KeyPackage object specifies a ciphersuite that the client supports, 1084 as well as providing a public key that others can use for key 1085 agreement. The client's signature key can be updated throughout the 1086 lifetime of the group by sending a new KeyPackage with a new 1087 Credential. However, the identity MUST be the same in both 1088 Credentials and the new Credential MUST be validated by the 1089 authentication service. 1091 When used as InitKeys, KeyPackages are intended to be used only once 1092 and SHOULD NOT be reused except in case of last resort. (See 1093 Section 15.4). Clients MAY generate and publish multiple InitKeys to 1094 support multiple ciphersuites. 1096 KeyPackages contain a public key chosen by the client, which the 1097 client MUST ensure uniquely identifies a given KeyPackage object 1098 among the set of KeyPackages created by this client. 1100 The value for hpke_init_key MUST be a public key for the asymmetric 1101 encryption scheme defined by cipher_suite. The whole structure is 1102 signed using the client's signature key. A KeyPackage object with an 1103 invalid signature field MUST be considered malformed. The input to 1104 the signature computation comprises all of the fields except for the 1105 signature field. 1107 enum { 1108 reserved(0), 1109 mls10(1), 1110 (255) 1111 } ProtocolVersion; 1113 // See IANA registry for registered values 1114 uint16 ExtensionType; 1116 struct { 1117 ExtensionType extension_type; 1118 opaque extension_data<0..2^16-1>; 1119 } Extension; 1121 struct { 1122 ProtocolVersion version; 1123 CipherSuite cipher_suite; 1124 HPKEPublicKey hpke_init_key; 1125 Credential credential; 1126 Extension extensions<8..2^32-1>; 1127 opaque signature<0..2^16-1>; 1128 } KeyPackage; 1130 KeyPackage objects MUST contain at least two extensions, one of type 1131 "capabilities", and one of type "lifetime". The "capabilities" 1132 extension allow MLS session establishment to be safe from downgrade 1133 attacks on the parameters described (as discussed in Section 10), 1134 while still only advertising one version / ciphersuite per 1135 KeyPackage. 1137 As the "KeyPackage" is a structure which is stored in the Ratchet 1138 Tree and updated depending on the evolution of this tree, each 1139 modification of its content MUST be reflected by a change of its 1140 signature. This allow other members to control the validity of the 1141 KeyPackage at any time and in particular in the case of a newcomer 1142 joining the group. 1144 7.1. Client Capabilities 1146 The "capabilities" extension indicates what protocol versions, 1147 ciphersuites, and protocol extensions are supported by a client. 1149 struct { 1150 ProtocolVersion versions<0..255>; 1151 CipherSuite ciphersuites<0..255>; 1152 ExtensionType extensions<0..255>; 1153 } Capabilities; 1154 This extension MUST be always present in a KeyPackage. Extensions 1155 that appear in the "extensions" field of a KeyPackage MUST be 1156 included in the "extensions" field of the "capabilities" extension. 1158 7.2. Lifetime 1160 The "lifetime" extension represents the times between which clients 1161 will consider a KeyPackage valid. This time is represented as an 1162 absolute time, measured in seconds since the Unix epoch 1163 (1970-01-01T00:00:00Z). A client MUST NOT use the data in a 1164 KeyPackage for any processing before the "not_before" date, or after 1165 the "not_after" date. 1167 uint64 not_before; 1168 uint64 not_after; 1170 Applications MUST define a maximum total lifetime that is acceptable 1171 for a KeyPackage, and reject any KeyPackage where the total lifetime 1172 is longer than this duration. 1174 This extension MUST always be present in a KeyPackage. 1176 7.3. KeyPackage Identifiers 1178 Within MLS, a KeyPackage is identified by its hash (see, e.g., 1179 Section 11.2.2). The "key_id" extension allows applications to add 1180 an explicit, application-defined identifier to a KeyPackage. 1182 opaque key_id<0..2^16-1>; 1184 7.4. Parent Hash 1186 Consider a ratchet tree with a parent node P and children V and S. 1187 The parent hash of P changes whenever an "UpdatePath" object is 1188 applied to the ratchet tree along a path traversing node V (and hence 1189 also P). The new "Parent Hash of P (with Co-Path Child S)" is 1190 obtained by hashing P's "ParentHashInput" struct using the resolution 1191 of S to populate the "original_child_resolution" field. This way, 1192 P's Parent Hash fixes the new HPKE public keys of all nodes on the 1193 path from P to the root. Furthermore, for each such key PK the hash 1194 also binds the set of HPKE public keys to which PK's secret key was 1195 encrypted in the commit packet that anounced the "UpdatePath" object. 1197 struct { 1198 HPKEPublicKey public_key; 1199 opaque parent_hash<0..255>; 1200 HPKEPublicKey original_child_resolution<0..2^32-1>; 1201 } ParentHashInput; 1202 The Parent Hash of P with Co-Path Child S is the hash of a 1203 "ParentHashInput" object populated as follows. The field 1204 "public_key" contains the HPKE public key of P. If P is the root, 1205 then "parent_hash" is set to a zero-length octet string. Otherwise 1206 "parent_hash" is the Parent Hash of P's parent with P's sibling as 1207 the co-path child. 1209 Finally, "original_child_resolution" is the array of "HPKEPublicKey" 1210 values of the nodes in the resolution of S but with the 1211 "unmerged_leaves" of P omitted. For example, in the ratchet tree 1212 depicted in Section 5.2 the "ParentHashInput" of node 5 with co-path 1213 child 4 would contain an empty "original_child_resolution" since 4's 1214 resolution includes only itself but 4 is also an unmerged leaf of 5. 1215 Meanwhile, the "ParentHashInput" of node 5 with co-path child 6 has 1216 an array with one element in it: the HPKE public key of 6. 1218 7.4.1. Using Parent Hashes 1220 The Parent Hash of P appears in three types of structs. If V is 1221 itself a parent node then P's Parent Hash is stored in the 1222 "parent_hash" fields of both V's "ParentHashInput" struct and V's 1223 "ParentNode" struct. (The "ParentNode" struct is used to encapsulate 1224 all public information about V that must be conveyed to a new member 1225 joining the group as well as to define the Tree Hash of node V.) 1227 If, on the other hand, V is a leaf and its KeyPackage contains the 1228 "parent_hash" extension then the Parent Hash of P (with V's sibling 1229 as co-path child) is stored in that field. In particular, the 1230 extension MUST be present in the "leaf_key_package" field of an 1231 "UpdatePath" object. (This way, the signature of such a KeyPackage 1232 also serves to attest to which keys the group member introduced into 1233 the ratchet tree and to whom the corresponding secret keys were sent. 1234 This helps prevent malicious insiders from constructing artificial 1235 ratchet trees with a node V whose HPKE secret key is known to the 1236 insider yet where the insider isn't assigned a leaf in the subtree 1237 rooted at V. Indeed, such a ratchet tree would violate the tree 1238 invariant.) 1240 7.4.2. Verifying Parent Hashes 1242 To this end, when processing a Commit message clients MUST recompute 1243 the expected value of "parent_hash" for the committer's new leaf and 1244 verify that it matches the "parent_hash" value in the supplied 1245 "leaf_key_package". Moreover, when joining a group, new members MUST 1246 authenticate each non-blank parent node P. A parent node P is 1247 authenticated by performing the following check: 1249 o Let L and R be the left and right children of P, respectively 1250 o If L.parent_hash is equal to the Parent Hash of P with Co-Path 1251 Child R, the check passes 1253 o If R is blank, replace R with its left child until R is either 1254 non-blank or a leaf node 1256 o If R is a leaf node, the check fails 1258 o If R.parent_hash is equal to the Parent Hash of P with Co-Path 1259 Child L, the check passes 1261 o Otherwise, the check fails 1263 The left-child recursion under the right child of P is necessary 1264 because the expansion of the tree to the right due to Add proposals 1265 can cause blank nodes to be interposed between a parent node and its 1266 right child. 1268 7.5. Tree Hashes 1270 To allow group members to verify that they agree on the public 1271 cryptographic state of the group, this section defines a scheme for 1272 generating a hash value (called the "tree hash") that represents the 1273 contents of the group's ratchet tree and the members' KeyPackages. 1274 The tree hash of a tree is the tree hash of its root node, which we 1275 define recursively, starting with the leaves. 1277 As some nodes may be blank while others contain data we use the 1278 following struct to include data if present. 1280 struct { 1281 uint8 present; 1282 select (present) { 1283 case 0: struct{}; 1284 case 1: T value; 1285 } 1286 } optional; 1288 The tree hash of a leaf node is the hash of leaf's 1289 "LeafNodeHashInput" object which might include a Key Package 1290 depending on whether or not it is blank. 1292 struct { 1293 uint32 node_index; 1294 optional key_package; 1295 } LeafNodeHashInput; 1296 Note that the "node_index" field contains the index of the leaf among 1297 the nodes in the tree, not its index among the leaves; "node_index = 1298 2 * leaf_index". 1300 Now the tree hash of any non-leaf node is recursively defined to be 1301 the hash of its "ParentNodeTreeHashInput". This includes an optional 1302 "ParentNode" object depending on if the node is blank or not. 1304 struct { 1305 HPKEPublicKey public_key; 1306 opaque parent_hash<0..255>; 1307 uint32 unmerged_leaves<0..2^32-1>; 1308 } ParentNode; 1310 struct { 1311 uint32 node_index; 1312 optional parent_node; 1313 opaque left_hash<0..255>; 1314 opaque right_hash<0..255>; 1315 } ParentNodeTreeHashInput; 1317 The "left_hash" and "right_hash" fields hold the tree hashes of the 1318 node's left and right children, respectively. 1320 7.6. Group State 1322 Each member of the group maintains a GroupContext object that 1323 summarizes the state of the group: 1325 struct { 1326 opaque group_id<0..255>; 1327 uint64 epoch; 1328 opaque tree_hash<0..255>; 1329 opaque confirmed_transcript_hash<0..255>; 1330 Extension extensions<0..2^32-1>; 1331 } GroupContext; 1333 The fields in this state have the following semantics: 1335 o The "group_id" field is an application-defined identifier for the 1336 group. 1338 o The "epoch" field represents the current version of the group key. 1340 o The "tree_hash" field contains a commitment to the contents of the 1341 group's ratchet tree and the credentials for the members of the 1342 group, as described in Section 7.5. 1344 o The "confirmed_transcript_hash" field contains a running hash over 1345 the messages that led to this state. 1347 When a new member is added to the group, an existing member of the 1348 group provides the new member with a Welcome message. The Welcome 1349 message provides the information the new member needs to initialize 1350 its GroupContext. 1352 Different changes to the group will have different effects on the 1353 group state. These effects are described in their respective 1354 subsections of Section 11.1. The following general rules apply: 1356 o The "group_id" field is constant 1358 o The "epoch" field increments by one for each Commit message that 1359 is processed 1361 o The "tree_hash" is updated to represent the current tree and 1362 credentials 1364 o The "confirmed_transcript_hash" is updated with the data for an 1365 MLSPlaintext message encoding a Commit message in two parts: 1367 struct { 1368 opaque group_id<0..255>; 1369 uint64 epoch; 1370 Sender sender; 1371 ContentType content_type = commit; 1372 Commit commit; 1373 opaque signature<0..2^16-1>; 1374 } MLSPlaintextCommitContent; 1376 struct { 1377 MAC confirmation_tag; 1378 } MLSPlaintextCommitAuthData; 1380 interim_transcript_hash_[0] = ""; // zero-length octet string 1382 confirmed_transcript_hash_[n] = 1383 Hash(interim_transcript_hash_[n] || 1384 MLSPlaintextCommitContent_[n]); 1386 interim_transcript_hash_[n+1] = 1387 Hash(confirmed_transcript_hash_[n] || 1388 MLSPlaintextCommitAuthData_[n]); 1390 Thus the "confirmed_transcript_hash" field in a GroupContext object 1391 represents a transcript over the whole history of MLSPlaintext Commit 1392 messages, up to the confirmation tag field in the current 1393 MLSPlaintext message. The confirmation tag is then included in the 1394 transcript for the next epoch. The interim transcript hash is passed 1395 to new members in the GroupInfo struct, and enables existing members 1396 to incorporate a Commit message into the transcript without having to 1397 store the whole MLSPlaintextCommitAuthData structure. 1399 As shown above, when a new group is created, the 1400 "interim_transcript_hash" field is set to the zero-length octet 1401 string. 1403 7.7. Update Paths 1405 As described in Section 11.2, each MLS Commit message may optionally 1406 transmit a KeyPackage leaf and node values along its direct path. 1407 The path contains a public key and encrypted secret value for all 1408 intermediate nodes in the path above the leaf. The path is ordered 1409 from the closest node to the leaf to the root; each node MUST be the 1410 parent of its predecessor. 1412 struct { 1413 opaque kem_output<0..2^16-1>; 1414 opaque ciphertext<0..2^16-1>; 1415 } HPKECiphertext; 1417 struct { 1418 HPKEPublicKey public_key; 1419 HPKECiphertext encrypted_path_secret<0..2^32-1>; 1420 } UpdatePathNode; 1422 struct { 1423 KeyPackage leaf_key_package; 1424 UpdatePathNode nodes<0..2^32-1>; 1425 } UpdatePath; 1427 For each "UpdatePathNode", the resolution of the corresponding copath 1428 node MUST be filtered by removing all new leaf nodes added as part of 1429 this MLS Commit message. The number of ciphertexts in the 1430 "encrypted_path_secret" vector MUST be equal to the length of the 1431 filtered resolution, with each ciphertext being the encryption to the 1432 respective resolution node. 1434 The HPKECiphertext values are computed as 1436 kem_output, context = SetupBaseS(node_public_key, "") 1437 ciphertext = context.Seal(group_context, path_secret) 1438 where "node_public_key" is the public key of the node that the path 1439 secret is being encrypted for, group_context is the current 1440 GroupContext object for the group, and the functions "SetupBaseS" and 1441 "Seal" are defined according to [I-D.irtf-cfrg-hpke]. 1443 Decryption is performed in the corresponding way, using the private 1444 key of the resolution node and the ephemeral public key transmitted 1445 in the message. 1447 8. Key Schedule 1449 Group keys are derived using the "Extract" and "Expand" functions 1450 from the KDF for the group's ciphersuite, as well as the functions 1451 defined below: 1453 ExpandWithLabel(Secret, Label, Context, Length) = 1454 KDF.Expand(Secret, KDFLabel, Length) 1456 Where KDFLabel is specified as: 1458 struct { 1459 uint16 length = Length; 1460 opaque label<7..255> = "mls10 " + Label; 1461 opaque context<0..2^32-1> = Context; 1462 } KDFLabel; 1464 DeriveSecret(Secret, Label) = 1465 ExpandWithLabel(Secret, Label, "", KDF.Nh) 1467 The value "KDF.Nh" is the size of an output from "KDF.Extract", in 1468 bytes. In the below diagram: 1470 o KDF.Extract takes its salt argument from the top and its IKM 1471 argument from the left 1473 o DeriveSecret takes its Secret argument from the incoming arrow 1475 When processing a handshake message, a client combines the following 1476 information to derive new epoch secrets: 1478 o The init secret from the previous epoch 1480 o The commit secret for the current epoch 1482 o The GroupContext object for current epoch 1484 Given these inputs, the derivation of secrets for an epoch proceeds 1485 as shown in the following diagram: 1487 init_secret_[n-1] 1488 | 1489 V 1490 commit_secret -> KDF.Extract 1491 | 1492 V 1493 DeriveSecret(., "joiner") 1494 | 1495 V 1496 joiner_secret 1497 | 1498 V 1499 psk_secret (or 0) -> KDF.Extract 1500 | 1501 +--> DeriveSecret(., "welcome") 1502 | = welcome_secret 1503 | 1504 V 1505 ExpandWithLabel(., "epoch", GroupContext_[n], KDF.Nh) 1506 | 1507 V 1508 epoch_secret 1509 | 1510 +--> DeriveSecret(.,