idnits 2.17.1 draft-ietf-mls-protocol-12.txt: -(4198): 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 : ---------------------------------------------------------------------------- ** There are 29 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 (11 October 2021) is 921 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 929, but not defined == Missing Reference: 'CD' is mentioned on line 822, but not defined == Missing Reference: 'A' is mentioned on line 822, but not defined -- Looks like a reference, but probably isn't: '0' on line 1122 -- Looks like a reference, but probably isn't: '1' on line 1012 == Missing Reference: 'X' is mentioned on line 1019, but not defined -- Looks like a reference, but probably isn't: '4' on line 2263 == Outdated reference: A later version (-13) exists of draft-ietf-mls-architecture-07 Summary: 1 error (**), 0 flaws (~~), 7 warnings (==), 5 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: 14 April 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 11 October 2021 16 The Messaging Layer Security (MLS) Protocol 17 draft-ietf-mls-protocol-12 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 14 April 2022. 57 Copyright Notice 59 Copyright (c) 2021 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 Simplified BSD License text 68 as described in Section 4.e of the Trust Legal Provisions and are 69 provided without warranty as described in the Simplified BSD License. 71 Table of Contents 73 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 74 1.1. Change Log . . . . . . . . . . . . . . . . . . . . . . . 5 75 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 10 76 3. Basic Assumptions . . . . . . . . . . . . . . . . . . . . . . 11 77 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 11 78 5. Ratchet Trees . . . . . . . . . . . . . . . . . . . . . . . . 14 79 5.1. Tree Computation Terminology . . . . . . . . . . . . . . 15 80 5.2. Ratchet Tree Nodes . . . . . . . . . . . . . . . . . . . 17 81 5.3. Views of a Ratchet Tree . . . . . . . . . . . . . . . . . 18 82 5.4. Ratchet Tree Evolution . . . . . . . . . . . . . . . . . 19 83 5.5. Synchronizing Views of the Tree . . . . . . . . . . . . . 21 84 6. Cryptographic Objects . . . . . . . . . . . . . . . . . . . . 22 85 6.1. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . 22 86 6.2. Credentials . . . . . . . . . . . . . . . . . . . . . . . 23 87 7. Key Packages . . . . . . . . . . . . . . . . . . . . . . . . 25 88 7.1. Key Package IDs . . . . . . . . . . . . . . . . . . . . . 26 89 7.2. Client Capabilities . . . . . . . . . . . . . . . . . . . 27 90 7.3. Lifetime . . . . . . . . . . . . . . . . . . . . . . . . 27 91 7.4. KeyPackage Identifiers . . . . . . . . . . . . . . . . . 27 92 7.5. Parent Hash . . . . . . . . . . . . . . . . . . . . . . . 28 93 7.5.1. Using Parent Hashes . . . . . . . . . . . . . . . . . 28 94 7.5.2. Verifying Parent Hashes . . . . . . . . . . . . . . . 29 95 7.6. Tree Hashes . . . . . . . . . . . . . . . . . . . . . . . 30 96 7.7. Group State . . . . . . . . . . . . . . . . . . . . . . . 31 97 7.8. Update Paths . . . . . . . . . . . . . . . . . . . . . . 32 99 8. Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . 33 100 8.1. External Initialization . . . . . . . . . . . . . . . . . 36 101 8.2. Pre-Shared Keys . . . . . . . . . . . . . . . . . . . . . 37 102 8.3. Secret Tree . . . . . . . . . . . . . . . . . . . . . . . 40 103 8.4. Encryption Keys . . . . . . . . . . . . . . . . . . . . . 41 104 8.5. Deletion Schedule . . . . . . . . . . . . . . . . . . . . 42 105 8.6. Exporters . . . . . . . . . . . . . . . . . . . . . . . . 43 106 8.7. Resumption Secret . . . . . . . . . . . . . . . . . . . . 44 107 8.8. State Authentication Keys . . . . . . . . . . . . . . . . 44 108 9. Message Framing . . . . . . . . . . . . . . . . . . . . . . . 44 109 9.1. Content Authentication . . . . . . . . . . . . . . . . . 47 110 9.2. Content Encryption . . . . . . . . . . . . . . . . . . . 49 111 9.3. Sender Data Encryption . . . . . . . . . . . . . . . . . 50 112 10. Group Creation . . . . . . . . . . . . . . . . . . . . . . . 51 113 10.1. Required Capabilities . . . . . . . . . . . . . . . . . 52 114 10.2. Linking a New Group to an Existing Group . . . . . . . . 53 115 10.2.1. Sub-group Branching . . . . . . . . . . . . . . . . 53 116 11. Group Evolution . . . . . . . . . . . . . . . . . . . . . . . 53 117 11.1. Proposals . . . . . . . . . . . . . . . . . . . . . . . 54 118 11.1.1. Add . . . . . . . . . . . . . . . . . . . . . . . . 54 119 11.1.2. Update . . . . . . . . . . . . . . . . . . . . . . . 56 120 11.1.3. Remove . . . . . . . . . . . . . . . . . . . . . . . 56 121 11.1.4. PreSharedKey . . . . . . . . . . . . . . . . . . . . 57 122 11.1.5. ReInit . . . . . . . . . . . . . . . . . . . . . . . 57 123 11.1.6. ExternalInit . . . . . . . . . . . . . . . . . . . . 58 124 11.1.7. AppAck . . . . . . . . . . . . . . . . . . . . . . . 58 125 11.1.8. GroupContextExtensions . . . . . . . . . . . . . . . 59 126 11.1.9. External Proposals . . . . . . . . . . . . . . . . . 60 127 11.2. Commit . . . . . . . . . . . . . . . . . . . . . . . . . 61 128 11.2.1. External Commits . . . . . . . . . . . . . . . . . . 68 129 11.2.2. Welcoming New Members . . . . . . . . . . . . . . . 71 130 11.3. Ratchet Tree Extension . . . . . . . . . . . . . . . . . 74 131 12. Extensibility . . . . . . . . . . . . . . . . . . . . . . . . 75 132 13. Sequencing of State Changes . . . . . . . . . . . . . . . . . 77 133 13.1. Server-Enforced Ordering . . . . . . . . . . . . . . . . 78 134 13.2. Client-Enforced Ordering . . . . . . . . . . . . . . . . 78 135 14. Application Messages . . . . . . . . . . . . . . . . . . . . 78 136 14.1. Message Encryption and Decryption . . . . . . . . . . . 79 137 14.2. Restrictions . . . . . . . . . . . . . . . . . . . . . . 80 138 14.3. Delayed and Reordered Application messages . . . . . . . 80 139 15. Security Considerations . . . . . . . . . . . . . . . . . . . 80 140 15.1. Confidentiality of the Group Secrets . . . . . . . . . . 80 141 15.2. Authentication . . . . . . . . . . . . . . . . . . . . . 81 142 15.3. Forward Secrecy and Post-Compromise Security . . . . . . 81 143 15.4. InitKey Reuse . . . . . . . . . . . . . . . . . . . . . 82 144 15.5. Group Fragmentation by Malicious Insiders . . . . . . . 82 145 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 83 146 16.1. MLS Ciphersuites . . . . . . . . . . . . . . . . . . . . 83 147 16.2. MLS Extension Types . . . . . . . . . . . . . . . . . . 86 148 16.3. MLS Proposal Types . . . . . . . . . . . . . . . . . . . 87 149 16.4. MLS Credential Types . . . . . . . . . . . . . . . . . . 88 150 16.5. MLS Designated Expert Pool . . . . . . . . . . . . . . . 89 151 17. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 90 152 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 91 153 18.1. Normative References . . . . . . . . . . . . . . . . . . 91 154 18.2. Informative References . . . . . . . . . . . . . . . . . 92 155 Appendix A. Tree Math . . . . . . . . . . . . . . . . . . . . . 93 156 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 96 158 1. Introduction 160 DISCLAIMER: This is a work-in-progress draft of MLS and has not yet 161 seen significant security analysis. It should not be used as a basis 162 for building production systems. 164 RFC EDITOR: PLEASE REMOVE THE FOLLOWING PARAGRAPH The source for this 165 draft is maintained in GitHub. Suggested changes should be submitted 166 as pull requests at https://github.com/mlswg/mls-protocol. 167 Instructions are on that page as well. Editorial changes can be 168 managed in GitHub, but any substantive change should be discussed on 169 the MLS mailing list. 171 A group of users who want to send each other encrypted messages needs 172 a way to derive shared symmetric encryption keys. For two parties, 173 this problem has been studied thoroughly, with the Double Ratchet 174 emerging as a common solution [doubleratchet] [signal]. Channels 175 implementing the Double Ratchet enjoy fine-grained forward secrecy as 176 well as post-compromise security, but are nonetheless efficient 177 enough for heavy use over low-bandwidth networks. 179 For a group of size greater than two, a common strategy is to 180 unilaterally broadcast symmetric "sender" keys over existing shared 181 symmetric channels, and then for each member to send messages to the 182 group encrypted with their own sender key. Unfortunately, while this 183 improves efficiency over pairwise broadcast of individual messages 184 and provides forward secrecy (with the addition of a hash ratchet), 185 it is difficult to achieve post-compromise security with sender keys. 186 An adversary who learns a sender key can often indefinitely and 187 passively eavesdrop on that member's messages. Generating and 188 distributing a new sender key provides a form of post-compromise 189 security with regard to that sender. However, it requires 190 computation and communications resources that scale linearly with the 191 size of the group. 193 In this document, we describe a protocol based on tree structures 194 that enable asynchronous group keying with forward secrecy and post- 195 compromise security. Based on earlier work on "asynchronous 196 ratcheting trees" [art], the protocol presented here uses an 197 asynchronous key-encapsulation mechanism for tree structures. This 198 mechanism allows the members of the group to derive and update shared 199 keys with costs that scale as the log of the group size. 201 1.1. Change Log 203 RFC EDITOR PLEASE DELETE THIS SECTION. 205 draft-12 207 * Use the GroupContext to derive the joiner_secret (*) 209 * Make PreSharedKeys non optional in GroupSecrets (*) 211 * Update name for this particular key (*) 213 * Truncate tree size on removal (*) 215 * Use HPKE draft-08 (*) 217 * Clarify requirements around identity in MLS groups (*) 219 * Signal the intended wire format for MLS messages (*) 221 * Inject GroupContext as HPKE info instead of AAD (*) 223 * Clarify extension handling and make extension updatable (*) 225 * Improve extensibility of Proposals (*) 227 * Constrain proposal in External Commit (*) 229 * Remove the notion of a 'leaf index' (*) 231 * Add group_context_extensions proposal ID (*) 233 * Add RequiredCapabilities extension (*) 235 * Use cascaded KDF instead of concatenation to consolidate PSKs (*) 237 * Use key package hash to index clients in message structs (*) 239 * Don't require PublicGroupState for external init (*) 240 * Make ratchet tree section clearer. 242 * Handle non-member sender cases in MLSPlaintextTBS 244 * Clarify encoding of signatures with NIST curves 246 * Remove OPEN ISSUEs and TODOs 248 * Normalize the description of the zero vector 250 draft-11 252 * Include subtree keys in parent hash (*) 254 * Pin HPKE to draft-07 (*) 256 * Move joiner secret to the end of the first key schedule epoch (*) 258 * Add an AppAck proposal 260 * Make initializations of transcript hashes consistent 262 draft-10 264 * Allow new members to join via an external Commit (*) 266 * Enable proposals to be sent inline in a Commit (*) 268 * Re-enable constant-time Add (*) 270 * Change expiration extension to lifetime extension (*) 272 * Make the tree in the Welcome optional (*) 274 * PSK injection, re-init, sub-group branching (*) 276 * Require the initial init_secret to be a random value (*) 278 * Remove explicit sender data nonce (*) 280 * Do not encrypt to joiners in UpdatePath generation (*) 282 * Move MLSPlaintext signature under the confirmation tag (*) 284 * Explicitly authenticate group membership with MLSPLaintext (*) 286 * Clarify X509Credential structure (*) 287 * Remove uneeded interim transcript hash from GroupInfo (*) 289 * IANA considerations 291 * Derive an authentication secret 293 * Use Extract/Expand from HPKE KDF 295 * Clarify that application messages MUST be encrypted 297 draft-09 299 * Remove blanking of nodes on Add (*) 301 * Change epoch numbers to uint64 (*) 303 * Add PSK inputs (*) 305 * Add key schedule exporter (*) 307 * Sign the updated direct path on Commit, using "parent hashes" and 308 one signature per leaf (*) 310 * Use structured types for external senders (*) 312 * Redesign Welcome to include confirmation and use derived keys (*) 314 * Remove ignored proposals (*) 316 * Always include an Update with a Commit (*) 318 * Add per-message entropy to guard against nonce reuse (*) 320 * Use the same hash ratchet construct for both application and 321 handshake keys (*) 323 * Add more ciphersuites 325 * Use HKDF to derive key pairs (*) 327 * Mandate expiration of ClientInitKeys (*) 329 * Add extensions to GroupContext and flesh out the extensibility 330 story (*) 332 * Rename ClientInitKey to KeyPackage 334 draft-08 335 * Change ClientInitKeys so that they only refer to one ciphersuite 336 (*) 338 * Decompose group operations into Proposals and Commits (*) 340 * Enable Add and Remove proposals from outside the group (*) 342 * Replace Init messages with multi-recipient Welcome message (*) 344 * Add extensions to ClientInitKeys for expiration and downgrade 345 resistance (*) 347 * Allow multiple Proposals and a single Commit in one MLSPlaintext 348 (*) 350 draft-07 352 * Initial version of the Tree based Application Key Schedule (*) 354 * Initial definition of the Init message for group creation (*) 356 * Fix issue with the transcript used for newcomers (*) 358 * Clarifications on message framing and HPKE contexts (*) 360 draft-06 362 * Reorder blanking and update in the Remove operation (*) 364 * Rename the GroupState structure to GroupContext (*) 366 * Rename UserInitKey to ClientInitKey 368 * Resolve the circular dependency that draft-05 introduced in the 369 confirmation MAC calculation (*) 371 * Cover the entire MLSPlaintext in the transcript hash (*) 373 draft-05 375 * Common framing for handshake and application messages (*) 377 * Handshake message encryption (*) 379 * Convert from literal state to a commitment via the "tree hash" (*) 381 * Add credentials to the tree and remove the "roster" concept (*) 382 * Remove the secret field from tree node values 384 draft-04 386 * Updating the language to be similar to the Architecture document 388 * ECIES is now renamed in favor of HPKE (*) 390 * Using a KDF instead of a Hash in TreeKEM (*) 392 draft-03 394 * Added ciphersuites and signature schemes (*) 396 * Re-ordered fields in UserInitKey to make parsing easier (*) 398 * Fixed inconsistencies between Welcome and GroupState (*) 400 * Added encryption of the Welcome message (*) 402 draft-02 404 * Removed ART (*) 406 * Allowed partial trees to avoid double-joins (*) 408 * Added explicit key confirmation (*) 410 draft-01 412 * Initial description of the Message Protection mechanism. (*) 414 * Initial specification proposal for the Application Key Schedule 415 using the per-participant chaining of the Application Secret 416 design. (*) 418 * Initial specification proposal for an encryption mechanism to 419 protect Application Messages using an AEAD scheme. (*) 421 * Initial specification proposal for an authentication mechanism of 422 Application Messages using signatures. (*) 424 * Initial specification proposal for a padding mechanism to 425 improving protection of Application Messages against traffic 426 analysis. (*) 428 * Inversion of the Group Init Add and Application Secret derivations 429 in the Handshake Key Schedule to be ease chaining in case we 430 switch design. (*) 432 * Removal of the UserAdd construct and split of GroupAdd into Add 433 and Welcome messages (*) 435 * Initial proposal for authenticating handshake messages by signing 436 over group state and including group state in the key schedule (*) 438 * Added an appendix with example code for tree math 440 * Changed the ECIES mechanism used by TreeKEM so that it uses nonces 441 generated from the shared secret 443 draft-00 445 * Initial adoption of draft-barnes-mls-protocol-01 as a WG item. 447 2. Terminology 449 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 450 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 451 "OPTIONAL" in this document are to be interpreted as described in BCP 452 14 [RFC2119] [RFC8174] when, and only when, they appear in all 453 capitals, as shown here. 455 Client: An agent that uses this protocol to establish shared 456 cryptographic state with other clients. A client is defined by 457 the cryptographic keys it holds. 459 Group: A collection of clients with shared cryptographic state. 461 Member: A client that is included in the shared state of a group, 462 hence has access to the group's secrets. 464 Key Package: A signed object describing a client's identity and 465 capabilities, and including a hybrid public-key encryption (HPKE 466 [I-D.irtf-cfrg-hpke]) public key that can be used to encrypt to 467 that client. 469 Initialization Key (InitKey): A key package that is prepublished by 470 a client, which other clients can use to introduce the client to a 471 new group. 473 Signature Key: A signing key pair used to authenticate the sender of 474 a message. 476 Terminology specific to tree computations is described in Section 5. 478 We use the TLS presentation language [RFC8446] to describe the 479 structure of protocol messages. 481 3. Basic Assumptions 483 This protocol is designed to execute in the context of a Service 484 Provider (SP) as described in [I-D.ietf-mls-architecture]. In 485 particular, we assume the SP provides the following services: 487 * A signature key provider which allows clients to authenticate 488 protocol messages in a group. 490 * A broadcast channel, for each group, which will relay a message to 491 all members of a group. For the most part, we assume that this 492 channel delivers messages in the same order to all participants. 493 (See Section 13 for further considerations.) 495 * A directory to which clients can publish key packages and download 496 key packages for other participants. 498 4. Protocol Overview 500 The goal of this protocol is to allow a group of clients to exchange 501 confidential and authenticated messages. It does so by deriving a 502 sequence of secrets and keys known only to members. Those should be 503 secret against an active network adversary and should have both 504 forward secrecy and post-compromise security with respect to 505 compromise of any members. 507 We describe the information stored by each client as _state_, which 508 includes both public and private data. An initial state is set up by 509 a group creator, which is a group containing only itself. The 510 creator then sends _Add_ proposals for each client in the initial set 511 of members, followed by a _Commit_ message which incorporates all of 512 the _Adds_ into the group state. Finally, the group creator 513 generates a _Welcome_ message corresponding to the Commit and sends 514 this directly to all the new members, who can use the information it 515 contains to set up their own group state and derive a shared secret. 516 Members exchange Commit messages for post-compromise security, to add 517 new members, and to remove existing members. These messages produce 518 new shared secrets which are causally linked to their predecessors, 519 forming a logical Directed Acyclic Graph (DAG) of states. 521 The protocol algorithms we specify here follow. Each algorithm 522 specifies both (i) how a client performs the operation and (ii) how 523 other clients update their state based on it. 525 There are three major operations in the lifecycle of a group: 527 * Adding a member, initiated by a current member; 529 * Updating the leaf secret of a member; 531 * Removing a member. 533 Each of these operations is "proposed" by sending a message of the 534 corresponding type (Add / Update / Remove). The state of the group 535 is not changed, however, until a Commit message is sent to provide 536 the group with fresh entropy. In this section, we show each proposal 537 being committed immediately, but in more advanced deployment cases an 538 application might gather several proposals before committing them all 539 at once. 541 Before the initialization of a group, clients publish InitKeys (as 542 KeyPackage objects) to a directory provided by the Service Provider. 544 Group 545 A B C Directory Channel 546 | | | | | 547 | KeyPackageA | | | | 548 |------------------------------------------------->| | 549 | | | | | 550 | | KeyPackageB | | | 551 | |-------------------------------->| | 552 | | | | | 553 | | | KeyPackageC | | 554 | | |--------------->| | 555 | | | | | 557 When a client A wants to establish a group with B and C, it first 558 initializes a group state containing only itself and downloads 559 KeyPackages for B and C. For each member, A generates an Add and 560 Commit message adding that member, and broadcasts them to the group. 561 It also generates a Welcome message and sends this directly to the 562 new member (there's no need to send it to the group). Only after A 563 has received its Commit message back from the server does it update 564 its state to reflect the new member's addition. 566 Upon receiving the Welcome message, the new member will be able to 567 read and send new messages to the group. Messages received before 568 the client has joined the group are ignored. 570 Group 571 A B C Directory Channel 572 | | | | | 573 | KeyPackageB, KeyPackageC | | 574 |<-------------------------------------------| | 575 |state.init() | | | | 576 | | | | | 577 | | | | Add(A->AB) | 578 | | | | Commit(Add) | 579 |--------------------------------------------------------------->| 580 | | | | | 581 | Welcome(B) | | | | 582 |------------->|state.join() | | | 583 | | | | | 584 | | | | Add(A->AB) | 585 | | | | Commit(Add) | 586 |<---------------------------------------------------------------| 587 |state.add(B) | | | | 588 | | | | | 589 | | | | | 590 | | | | Add(AB->ABC) | 591 | | | | Commit(Add) | 592 |--------------------------------------------------------------->| 593 | | | | | 594 | | Welcome(C) | | | 595 |---------------------------->|state.join() | | 596 | | | | | 597 | | | | Add(AB->ABC) | 598 | | | | Commit(Add) | 599 |<---------------------------------------------------------------| 600 |state.add(C) |<------------------------------------------------| 601 | |state.add(C) | | | 602 | | | | | 604 Subsequent additions of group members proceed in the same way. Any 605 member of the group can download a KeyPackage for a new client and 606 broadcast an Add message that the current group can use to update 607 their state, and a Welcome message that the new client can use to 608 initialize its state and join the group. 610 To enforce the forward secrecy and post-compromise security of 611 messages, each member periodically updates their leaf secret. Any 612 member can update this information at any time by generating a fresh 613 KeyPackage and sending an Update message followed by a Commit 614 message. Once all members have processed both, the group's secrets 615 will be unknown to an attacker that had compromised the sender's 616 prior leaf secret. 618 Update messages should be sent at regular intervals of time as long 619 as the group is active, and members that don't update should 620 eventually be removed from the group. It's left to the application 621 to determine an appropriate amount of time between Updates. 623 Group 624 A B ... Z Directory Channel 625 | | | | | 626 | | Update(B) | | | 627 | |------------------------------------------->| 628 | Commit(Upd) | | | | 629 |---------------------------------------------------------->| 630 | | | | | 631 | | | | Update(B) | 632 | | | | Commit(Upd) | 633 |<----------------------------------------------------------| 634 |state.upd(B) |<-------------------------------------------| 635 | |state.upd(B) |<----------------------------| 636 | | |state.upd(B) | | 637 | | | | | 639 Members are removed from the group in a similar way. Any member of 640 the group can send a Remove proposal followed by a Commit message, 641 which adds new entropy to the group state that's known to all except 642 the removed member. Note that this does not necessarily imply that 643 any member is actually allowed to evict other members; groups can 644 enforce access control policies on top of these basic mechanism. 646 Group 647 A B ... Z Directory Channel 648 | | | | | 649 | | | Remove(B) | | 650 | | | Commit(Rem) | | 651 | | |---------------------------->| 652 | | | | | 653 | | | | Remove(B) | 654 | | | | Commit(Rem) | 655 |<----------------------------------------------------------| 656 |state.rem(B) | |<----------------------------| 657 | | |state.rem(B) | | 658 | | | | | 659 | | | | | 661 5. Ratchet Trees 663 The protocol uses "ratchet trees" for deriving shared secrets among a 664 group of clients. 666 5.1. Tree Computation Terminology 668 Trees consist of _nodes_. A node is a _leaf_ if it has no children, 669 and a _parent_ otherwise; note that all parents in our trees have 670 precisely two children, a _left_ child and a _right_ child. A node 671 is the _root_ of a tree if it has no parents, and _intermediate_ if 672 it has both children and parents. The _descendants_ of a node are 673 that node, its children, and the descendants of its children, and we 674 say a tree _contains_ a node if that node is a descendant of the root 675 of the tree. Nodes are _siblings_ if they share the same parent. 677 A _subtree_ of a tree is the tree given by the descendants of any 678 node, the _head_ of the subtree. The _size_ of a tree or subtree is 679 the number of leaf nodes it contains. For a given parent node, its 680 _left subtree_ is the subtree with its left child as head 681 (respectively _right subtree_). 683 All trees used in this protocol are left-balanced binary trees. A 684 binary tree is _full_ (and _balanced_) if its size is a power of two 685 and for any parent node in the tree, its left and right subtrees have 686 the same size. 688 A binary tree is _left-balanced_ if for every parent, either the 689 parent is balanced, or the left subtree of that parent is the largest 690 full subtree that could be constructed from the leaves present in the 691 parent's own subtree. Given a list of n items, there is a unique 692 left-balanced binary tree structure with these elements as leaves. 694 (Note that left-balanced binary trees are the same structure that is 695 used for the Merkle trees in the Certificate Transparency protocol 696 [I-D.ietf-trans-rfc6962-bis].) 698 The _direct path_ of a root is the empty list, and of any other node 699 is the concatenation of that node's parent along with the parent's 700 direct path. The _copath_ of a node is the node's sibling 701 concatenated with the list of siblings of all the nodes in its direct 702 path, excluding the root. 704 For example, in the below tree: 706 * The direct path of C is (CD, ABCD, ABCDEFG) 708 * The copath of C is (D, AB, EFG) 709 7 = root 710 ______|______ 711 / \ 712 3 11 713 __|__ __| 714 / \ / \ 715 1 5 9 | 716 / \ / \ / \ | 717 A B C D E F G 719 1 1 1 720 0 1 2 3 4 5 6 7 8 9 0 1 2 722 Each node in the tree is assigned an _index_, starting at zero and 723 running from left to right. A node is a leaf node if and only if it 724 has an even index. The node indices for the nodes in the above tree 725 are as follows: 727 * 0 = A 729 * 1 = AB 731 * 2 = B 733 * 3 = ABCD 735 * 4 = C 737 * 5 = CD 739 * 6 = D 741 * 7 = ABCDEFG 743 * 8 = E 745 * 9 = EF 747 * 10 = F 749 * 11 = EFG 751 * 12 = G 753 A tree with n leaves has 2*n - 1 nodes. For example, the above tree 754 has 7 leaves (A, B, C, D, E, F, G) and 13 nodes. The root of a tree 755 with n leaves is always the node with index 2^k - 1, where k is the 756 largest number such that 2^k < n. 758 5.2. Ratchet Tree Nodes 760 A particular instance of a ratchet tree is defined by the same 761 parameters that define an instance of HPKE, namely: 763 * A Key Encapsulation Mechanism (KEM), including a DeriveKeyPair 764 function that creates a key pair for the KEM from a symmetric 765 secret 767 * A Key Derivation Function (KDF), including Extract and Expand 768 functions 770 * An AEAD encryption scheme 772 Each node in a ratchet tree contains up to five values: 774 * A private key (only within the member's direct path, see below) 776 * A public key 778 * An ordered list of node indices for "unmerged" leaves (see 779 Section 5.3) 781 * A credential (only for leaf nodes) 783 * A hash of certain information about the node's parent, as of the 784 last time the node was changed (see Section 7.5). 786 The conditions under which each of these values must or must not be 787 present are laid out in Section 5.3. 789 A node in the tree may also be _blank_, indicating that no value is 790 present at that node. The _resolution_ of a node is an ordered list 791 of non-blank nodes that collectively cover all non-blank descendants 792 of the node. 794 * The resolution of a non-blank node comprises the node itself, 795 followed by its list of unmerged leaves, if any 797 * The resolution of a blank leaf node is the empty list 799 * The resolution of a blank intermediate node is the result of 800 concatenating the resolution of its left child with the resolution 801 of its right child, in that order 803 For example, consider the following tree, where the "_" character 804 represents a blank node and unmerged leaves are indicated in square 805 brackets: 807 _ 808 __|__ 809 / \ 810 _ 5[C] 811 / \ / \ 812 A _ C D 814 0 1 2 3 4 5 6 816 In this tree, we can see all of the above rules in play: 818 * The resolution of node 5 is the list [CD, C] 820 * The resolution of node 2 is the empty list [] 822 * The resolution of node 3 is the list [A, CD, C] 824 Every node, regardless of whether the node is blank or populated, has 825 a corresponding _hash_ that summarizes the contents of the subtree 826 below that node. The rules for computing these hashes are described 827 in Section 7.6. 829 5.3. Views of a Ratchet Tree 831 We generally assume that each participant maintains a complete and 832 up-to-date view of the public state of the group's ratchet tree, 833 including the public keys for all nodes and the credentials 834 associated with the leaf nodes. 836 No participant in an MLS group knows the private key associated with 837 every node in the tree. Instead, each member is assigned to a leaf 838 of the tree, which determines the subset of private keys it knows. 839 The credential stored at that leaf is one provided by the member. 841 In particular, MLS maintains the members' views of the tree in such a 842 way as to maintain the _tree invariant_: 844 The private key for a node in the tree is known to a member of 845 the group only if that member's leaf is a descendant of 846 the node. 848 In other words, if a node is not blank, then it holds a public key. 849 The corresponding private key is known only to members occupying 850 leaves below that node. 852 The reverse implication is not true: A member may not know the 853 private keys of all the intermediate nodes they're below. Such a 854 member has an _unmerged_ leaf. Encrypting to an intermediate node 855 requires encrypting to the node's public key, as well as the public 856 keys of all the unmerged leaves below it. A leaf is unmerged when it 857 is first added, because the process of adding the leaf does not give 858 it access to all of the nodes above it in the tree. Leaves are 859 "merged" as they receive the private keys for nodes, as described in 860 Section 5.4. 862 5.4. Ratchet Tree Evolution 864 A member of an MLS group advances the key schedule to provide forward 865 secrecy and post-compromise security by providing the group with 866 fresh key material to be added into the group's shared secret. To do 867 so, one member of the group generates fresh key material, applies it 868 to their local tree state, and then sends this key material to other 869 members in the group via an UpdatePath message (see Section 7.8) . 870 All other group members then apply the key material in the UpdatePath 871 to their own local tree state to derive the group's now-updated 872 shared secret. 874 To begin, the generator of the UpdatePath updates its leaf KeyPackage 875 and its direct path to the root with new secret values. The HPKE 876 leaf public key within the KeyPackage MUST be derived from a freshly 877 generated HPKE secret key to provide post-compromise security. 879 The generator of the UpdatePath starts by sampling a fresh random 880 value called "leaf_secret", and uses the leaf_secret to generate 881 their leaf HPKE key pair (see Section 7) and to seed a sequence of 882 "path secrets", one for each ancestor of its leaf. In this setting, 883 path_secret[0] refers to the node directly above the leaf, 884 path_secret[1] for its parent, and so on. At each step, the path 885 secret is used to derive a new secret value for the corresponding 886 node, from which the node's key pair is derived. 888 leaf_node_secret = DeriveSecret(leaf_secret, "node") 889 path_secret[0] = DeriveSecret(leaf_secret, "path") 891 path_secret[n] = DeriveSecret(path_secret[n-1], "path") 892 node_secret[n] = DeriveSecret(path_secret[n], "node") 894 leaf_priv, leaf_pub = KEM.DeriveKeyPair(leaf_node_secret) 895 node_priv[n], node_pub[n] = KEM.DeriveKeyPair(node_secret[n]) 897 For example, suppose there is a group with four members, with C an 898 unmerged leaf at node 5: 900 3 901 __|__ 902 / \ 903 1 5[C] 904 / \ / \ 905 A B C D 907 0 1 2 3 4 5 6 909 If member B subsequently generates an UpdatePath based on a secret 910 "leaf_secret", then it would generate the following sequence of path 911 secrets: 913 path_secret[1] --> node_secret[1] --> node_priv[1], node_pub[1] 914 ^ 915 | 916 path_secret[0] --> node_secret[0] --> node_priv[0], node_pub[0] 917 ^ 918 | 919 leaf_secret --> leaf_node_secret --> leaf_priv, leaf_pub 920 ~> leaf_key_package 922 After applying the UpdatePath, the tree will have the following 923 structure, where lp and np[i] represent the leaf_priv and node_priv 924 values generated as described above: 926 np[1] -> 3 927 __|__ 928 / \ 929 np[0] -> 1 5[C] 930 / \ / \ 931 A B C D 932 ^ 933 | 934 lp 936 0 1 2 3 4 5 6 938 After performing these operations, the generator of the UpdatePath 939 MUST delete the leaf_secret. 941 5.5. Synchronizing Views of the Tree 943 After generating fresh key material and applying it to ratchet 944 forward their local tree state as described in the prior section, the 945 generator must broadcast this update to other members of the group in 946 a Commit message, who apply it to keep their local views of the tree 947 in sync with the sender's. More specifically, when a member commits 948 a change to the tree (e.g., to add or remove a member), it transmits 949 an UpdatePath containing a set of public keys and encrypted path 950 secrets for intermediate nodes in the direct path of its leaf. The 951 other members of the group use these values to update their view of 952 the tree, aligning their copy of the tree to the sender's. 954 An UpdatePath contains the following information for each node in the 955 direct path of the sender's leaf, including the root: 957 * The public key for the node 959 * Zero or more encrypted copies of the path secret corresponding to 960 the node 962 The path secret value for a given node is encrypted for the subtree 963 corresponding to the parent's non-updated child, that is, the child 964 on the copath of the sender's leaf node. There is one encryption of 965 the path secret to each public key in the resolution of the non- 966 updated child. 968 The recipient of an UpdatePath processes it with the following steps: 970 1. Compute the updated path secrets. 972 * Identify a node in the direct path for which the local member 973 is in the subtree of the non-updated child. 975 * Identify a node in the resolution of the copath node for which 976 this node has a private key. 978 * Decrypt the path secret for the parent of the copath node 979 using the private key from the resolution node. 981 * Derive path secrets for ancestors of that node using the 982 algorithm described above. 984 * The recipient SHOULD verify that the received public keys 985 agree with the public keys derived from the new path_secret 986 values. 988 2. Merge the updated path secrets into the tree. 990 * For all updated nodes, 992 - Replace the public key for each node with the received 993 public key. 995 - Set the list of unmerged leaves to the empty list. 997 - Store the updated hash of the node's parent (represented as 998 a ParentNode struct), going from root to leaf, so that each 999 hash incorporates all the nodes above it. The root node 1000 always has a zero-length hash for this value. 1002 * For nodes where an updated path secret was computed in step 1, 1003 compute the corresponding node key pair and replace the values 1004 stored at the node with the computed values. 1006 For example, in order to communicate the example update described in 1007 the previous section, the sender would transmit the following values: 1009 +=============+====================================================+ 1010 | Public Key | Ciphertext(s) | 1011 +=============+====================================================+ 1012 | node_pub[1] | E(pk(5), path_secret[1]), E(pk(C), path_secret[1]) | 1013 +-------------+----------------------------------------------------+ 1014 | node_pub[0] | E(pk(A), path_secret[0]) | 1015 +-------------+----------------------------------------------------+ 1017 Table 1 1019 In this table, the value pk(ns[X]) represents the public key derived 1020 from the node secret X, whereas pk(X) represents the public leaf key 1021 for user X. The value E(K, S) represents the public-key encryption 1022 of the path secret S to the public key K (using HPKE). 1024 After processing the update, each recipient MUST delete outdated key 1025 material, specifically: 1027 * The path secrets used to derive each updated node key pair. 1029 * Each outdated node key pair that was replaced by the update. 1031 6. Cryptographic Objects 1033 6.1. Ciphersuites 1035 Each MLS session uses a single ciphersuite that specifies the 1036 following primitives to be used in group key computations: 1038 * HPKE parameters: 1040 - A Key Encapsulation Mechanism (KEM) 1042 - A Key Derivation Function (KDF) 1044 - An AEAD encryption algorithm 1046 * A hash algorithm 1048 * A signature algorithm 1050 MLS uses draft-08 of HPKE [I-D.irtf-cfrg-hpke] for public-key 1051 encryption. The DeriveKeyPair function associated to the KEM for the 1052 ciphersuite maps octet strings to HPKE key pairs. 1054 Ciphersuites are represented with the CipherSuite type. HPKE public 1055 keys are opaque values in a format defined by the underlying protocol 1056 (see the Cryptographic Dependencies section of the HPKE specification 1057 for more information). 1059 opaque HPKEPublicKey<1..2^16-1>; 1061 The signature algorithm specified in the ciphersuite is the mandatory 1062 algorithm to be used for signatures in MLSPlaintext and the tree 1063 signatures. It MUST be the same as the signature algorithm specified 1064 in the credential field of the KeyPackage objects in the leaves of 1065 the tree (including the InitKeys used to add new members). 1067 The ciphersuites are defined in section Section 16.1. 1069 6.2. Credentials 1071 A member of a group authenticates the identities of other 1072 participants by means of credentials issued by some authentication 1073 system, like a PKI. Each type of credential MUST express the 1074 following data in the context of the group it is used with: 1076 * The public key of a signature key pair matching the 1077 SignatureScheme specified by the CipherSuite of the group 1079 * The identity of the holder of the private key 1081 Credentials MAY also include information that allows a relying party 1082 to verify the identity / signing key binding. 1084 Additionally, Credentials SHOULD specify the signature scheme 1085 corresponding to each contained public key. 1087 // See RFC 8446 and the IANA TLS SignatureScheme registry 1088 uint16 SignatureScheme; 1090 // See IANA registry for registered values 1091 uint16 CredentialType; 1093 struct { 1094 opaque identity<0..2^16-1>; 1095 SignatureScheme signature_scheme; 1096 opaque signature_key<0..2^16-1>; 1097 } BasicCredential; 1099 struct { 1100 opaque cert_data<0..2^16-1>; 1101 } Certificate; 1103 struct { 1104 CredentialType credential_type; 1105 select (Credential.credential_type) { 1106 case basic: 1107 BasicCredential; 1109 case x509: 1110 Certificate chain<1..2^32-1>; 1111 }; 1112 } Credential; 1114 A BasicCredential is a raw, unauthenticated assertion of an identity/ 1115 key binding. The format of the key in the public_key field is 1116 defined by the relevant ciphersuite: the group ciphersuite for a 1117 credential in a ratchet tree, the KeyPackage ciphersuite for a 1118 credential in a KeyPackage object. 1120 For X509Credential, each entry in the chain represents a single DER- 1121 encoded X509 certificate. The chain is ordered such that the first 1122 entry (chain[0]) is the end-entity certificate and each subsequent 1123 certificate in the chain MUST be the issuer of the previous 1124 certificate. The algorithm for the public_key in the end-entity 1125 certificate MUST match the relevant ciphersuite. 1127 For ciphersuites using Ed25519 or Ed448 signature schemes, the public 1128 key is in the format specified [RFC8032]. For ciphersuites using 1129 ECDSA with the NIST curves P-256 or P-521, the public key is the 1130 output of the uncompressed Elliptic-Curve-Point-to-Octet-String 1131 conversion according to [SECG]. 1133 The signatures used throughout this document are encoded as specified 1134 in [RFC8446]. In particular, ECDSA signatures are DER-encoded and 1135 EdDSA signatures are defined as the concatenation of r and s as 1136 specified in [RFC8032]. 1138 Note that each new credential that has not already been validated by 1139 the application MUST be validated against the Authentication Service. 1141 7. Key Packages 1143 In order to facilitate asynchronous addition of clients to a group, 1144 it is possible to pre-publish key packages that provide some public 1145 information about a user. KeyPackage structures provide information 1146 about a client that any existing member can use to add this client to 1147 the group asynchronously. 1149 A KeyPackage object specifies a ciphersuite that the client supports, 1150 as well as providing a public key that others can use for key 1151 agreement. 1153 The identity arising from the credential, together with the 1154 endpoint_id in the KeyPackage serve to uniquely identify a client in 1155 a group. 1157 When used as InitKeys, KeyPackages are intended to be used only once 1158 and SHOULD NOT be reused except in case of last resort. (See 1159 Section 15.4). Clients MAY generate and publish multiple InitKeys to 1160 support multiple ciphersuites. 1162 KeyPackages contain a public key chosen by the client, which the 1163 client MUST ensure uniquely identifies a given KeyPackage object 1164 among the set of KeyPackages created by this client. 1166 The value for hpke_init_key MUST be a public key for the asymmetric 1167 encryption scheme defined by cipher_suite. The whole structure is 1168 signed using the client's signature key. A KeyPackage object with an 1169 invalid signature field MUST be considered malformed. The input to 1170 the signature computation comprises all of the fields except for the 1171 signature field. 1173 enum { 1174 reserved(0), 1175 mls10(1), 1176 (255) 1177 } ProtocolVersion; 1179 // See IANA registry for registered values 1180 uint16 ExtensionType; 1182 struct { 1183 ExtensionType extension_type; 1184 opaque extension_data<0..2^32-1>; 1185 } Extension; 1187 struct { 1188 ProtocolVersion version; 1189 CipherSuite cipher_suite; 1190 HPKEPublicKey hpke_init_key; 1191 opaque endpoint_id<0..255>; 1192 Credential credential; 1193 Extension extensions<8..2^32-1>; 1194 opaque signature<0..2^16-1>; 1195 } KeyPackage; 1197 KeyPackage objects MUST contain at least two extensions, one of type 1198 capabilities, and one of type lifetime. The capabilities extension 1199 allow MLS session establishment to be safe from downgrade attacks on 1200 the parameters described (as discussed in Section 10), while still 1201 only advertising one version / ciphersuite per KeyPackage. 1203 As the KeyPackage is a structure which is stored in the Ratchet Tree 1204 and updated depending on the evolution of this tree, each 1205 modification of its content MUST be reflected by a change of its 1206 signature. This allow other members to control the validity of the 1207 KeyPackage at any time and in particular in the case of a newcomer 1208 joining the group. 1210 7.1. Key Package IDs 1212 When it is necessary to refer to a specific KeyPackage, protocol 1213 messages incorporate a KeyPackageID: 1215 struct { opaque key_package_hash<0..255>; } KeyPackageID 1217 This value is the hash of the KeyPackage, using the hash indicated by 1218 the cipher_suite field. KeyPackage hashes are used in a Welcome 1219 message to indicate which KeyPackage is being used to include the new 1220 member. Since members of a group are uniquely identified by their 1221 leaf KeyPackages, messages within a group use the hash of this key 1222 package to refer to group members, e.g., to specify the target of a 1223 Remove proposal or the signer of an MLSPlaintext. 1225 7.2. Client Capabilities 1227 The capabilities extension indicates what protocol versions, 1228 ciphersuites, protocol extensions, and non-default proposal types are 1229 supported by a client. Proposal types defined in this document are 1230 considered "default" and thus need not be listed. 1232 struct { 1233 ProtocolVersion versions<0..255>; 1234 CipherSuite ciphersuites<0..255>; 1235 ExtensionType extensions<0..255>; 1236 ProposalType proposals<0..255>; 1237 } Capabilities; 1239 This extension MUST be always present in a KeyPackage. Extensions 1240 that appear in the extensions field of a KeyPackage MUST be included 1241 in the extensions field of the capabilities extension. 1243 7.3. Lifetime 1245 The lifetime extension represents the times between which clients 1246 will consider a KeyPackage valid. This time is represented as an 1247 absolute time, measured in seconds since the Unix epoch 1248 (1970-01-01T00:00:00Z). A client MUST NOT use the data in a 1249 KeyPackage for any processing before the not_before date, or after 1250 the not_after date. 1252 uint64 not_before; 1253 uint64 not_after; 1255 Applications MUST define a maximum total lifetime that is acceptable 1256 for a KeyPackage, and reject any KeyPackage where the total lifetime 1257 is longer than this duration. 1259 This extension MUST always be present in a KeyPackage. 1261 7.4. KeyPackage Identifiers 1263 Within MLS, a KeyPackage is identified by its hash (see, e.g., 1264 Section 11.2.2). The external_key_id extension allows applications 1265 to add an explicit, application-defined identifier to a KeyPackage. 1267 opaque external_key_id<0..2^16-1>; 1269 7.5. Parent Hash 1271 The parent_hash extension carries information to authenticate the 1272 structure of the tree, as described below. 1274 opaque parent_hash<0..255>; 1276 Consider a ratchet tree with a parent node P and children V and S. 1277 The parent hash of P changes whenever an UpdatePath object is applied 1278 to the ratchet tree along a path traversing node V (and hence also 1279 P). The new "Parent Hash of P (with Co-Path Child S)" is obtained by 1280 hashing P's ParentHashInput struct using the resolution of S to 1281 populate the original_child_resolution field. This way, P's Parent 1282 Hash fixes the new HPKE public keys of all nodes on the path from P 1283 to the root. Furthermore, for each such key PK the hash also binds 1284 the set of HPKE public keys to which PK's secret key was encrypted in 1285 the commit packet that anounced the UpdatePath object. 1287 struct { 1288 HPKEPublicKey public_key; 1289 opaque parent_hash<0..255>; 1290 HPKEPublicKey original_child_resolution<0..2^32-1>; 1291 } ParentHashInput; 1293 The Parent Hash of P with Co-Path Child S is the hash of a 1294 ParentHashInput object populated as follows. The field public_key 1295 contains the HPKE public key of P. If P is the root, then 1296 parent_hash is set to a zero-length octet string. Otherwise 1297 parent_hash is the Parent Hash of P's parent with P's sibling as the 1298 co-path child. 1300 Finally, original_child_resolution is the array of HPKEPublicKey 1301 values of the nodes in the resolution of S but with the 1302 unmerged_leaves of P omitted. For example, in the ratchet tree 1303 depicted in Section 5.2 the ParentHashInput of node 5 with co-path 1304 child 4 would contain an empty original_child_resolution since 4's 1305 resolution includes only itself but 4 is also an unmerged leaf of 5. 1306 Meanwhile, the ParentHashInput of node 5 with co-path child 6 has an 1307 array with one element in it: the HPKE public key of 6. 1309 7.5.1. Using Parent Hashes 1311 The Parent Hash of P appears in three types of structs. If V is 1312 itself a parent node then P's Parent Hash is stored in the 1313 parent_hash fields of both V's ParentHashInput struct and V's 1314 ParentNode struct. (The ParentNode struct is used to encapsulate all 1315 public information about V that must be conveyed to a new member 1316 joining the group as well as to define the Tree Hash of node V.) 1317 If, on the other hand, V is a leaf and its KeyPackage contains the 1318 parent_hash extension then the Parent Hash of P (with V's sibling as 1319 co-path child) is stored in that field. In particular, the extension 1320 MUST be present in the leaf_key_package field of an UpdatePath 1321 object. (This way, the signature of such a KeyPackage also serves to 1322 attest to which keys the group member introduced into the ratchet 1323 tree and to whom the corresponding secret keys were sent. This helps 1324 prevent malicious insiders from constructing artificial ratchet trees 1325 with a node V whose HPKE secret key is known to the insider yet where 1326 the insider isn't assigned a leaf in the subtree rooted at V. 1327 Indeed, such a ratchet tree would violate the tree invariant.) 1329 7.5.2. Verifying Parent Hashes 1331 To this end, when processing a Commit message clients MUST recompute 1332 the expected value of parent_hash for the committer's new leaf and 1333 verify that it matches the parent_hash value in the supplied 1334 leaf_key_package. Moreover, when joining a group, new members MUST 1335 authenticate each non-blank parent node P. A parent node P is 1336 authenticated by performing the following check: 1338 * Let L and R be the left and right children of P, respectively 1340 * If L.parent_hash is equal to the Parent Hash of P with Co-Path 1341 Child R, the check passes 1343 * If R is blank, replace R with its left child until R is either 1344 non-blank or a leaf node 1346 * If R is a blank leaf node, the check fails 1348 * If R.parent_hash is equal to the Parent Hash of P with Co-Path 1349 Child L, the check passes 1351 * Otherwise, the check fails 1353 The left-child recursion under the right child of P is necessary 1354 because the expansion of the tree to the right due to Add proposals 1355 can cause blank nodes to be interposed between a parent node and its 1356 right child. 1358 7.6. Tree Hashes 1360 To allow group members to verify that they agree on the public 1361 cryptographic state of the group, this section defines a scheme for 1362 generating a hash value (called the "tree hash") that represents the 1363 contents of the group's ratchet tree and the members' KeyPackages. 1364 The tree hash of a tree is the tree hash of its root node, which we 1365 define recursively, starting with the leaves. 1367 As some nodes may be blank while others contain data we use the 1368 following struct to include data if present. 1370 struct { 1371 uint8 present; 1372 select (present) { 1373 case 0: struct{}; 1374 case 1: T value; 1375 } 1376 } optional; 1378 The tree hash of a leaf node is the hash of leaf's LeafNodeHashInput 1379 object which might include a Key Package depending on whether or not 1380 it is blank. 1382 struct { 1383 uint32 node_index; 1384 optional key_package; 1385 } LeafNodeHashInput; 1387 Now the tree hash of any non-leaf node is recursively defined to be 1388 the hash of its ParentNodeTreeHashInput. This includes an optional 1389 ParentNode object depending on whether the node is blank or not. 1391 struct { 1392 HPKEPublicKey public_key; 1393 opaque parent_hash<0..255>; 1394 uint32 unmerged_leaves<0..2^32-1>; 1395 } ParentNode; 1397 struct { 1398 uint32 node_index; 1399 optional parent_node; 1400 opaque left_hash<0..255>; 1401 opaque right_hash<0..255>; 1402 } ParentNodeTreeHashInput; 1404 The left_hash and right_hash fields hold the tree hashes of the 1405 node's left and right children, respectively. 1407 7.7. Group State 1409 Each member of the group maintains a GroupContext object that 1410 summarizes the state of the group: 1412 struct { 1413 opaque group_id<0..255>; 1414 uint64 epoch; 1415 opaque tree_hash<0..255>; 1416 opaque confirmed_transcript_hash<0..255>; 1417 Extension extensions<0..2^32-1>; 1418 } GroupContext; 1420 The fields in this state have the following semantics: 1422 * The group_id field is an application-defined identifier for the 1423 group. 1425 * The epoch field represents the current version of the group key. 1427 * The tree_hash field contains a commitment to the contents of the 1428 group's ratchet tree and the credentials for the members of the 1429 group, as described in Section 7.6. 1431 * The confirmed_transcript_hash field contains a running hash over 1432 the messages that led to this state. 1434 When a new member is added to the group, an existing member of the 1435 group provides the new member with a Welcome message. The Welcome 1436 message provides the information the new member needs to initialize 1437 its GroupContext. 1439 Different changes to the group will have different effects on the 1440 group state. These effects are described in their respective 1441 subsections of Section 11.1. The following general rules apply: 1443 * The group_id field is constant 1445 * The epoch field increments by one for each Commit message that is 1446 processed 1448 * The tree_hash is updated to represent the current tree and 1449 credentials 1451 * The confirmed_transcript_hash is updated with the data for an 1452 MLSPlaintext message encoding a Commit message in two parts: 1454 struct { 1455 WireFormat wire_format; 1456 opaque group_id<0..255>; 1457 uint64 epoch; 1458 Sender sender; 1459 opaque authenticated_data<0..2^32-1>; 1460 ContentType content_type = commit; 1461 Commit commit; 1462 opaque signature<0..2^16-1>; 1463 } MLSPlaintextCommitContent; 1465 struct { 1466 optional confirmation_tag; 1467 } MLSPlaintextCommitAuthData; 1469 interim_transcript_hash_[0] = ""; // zero-length octet string 1471 confirmed_transcript_hash_[n] = 1472 Hash(interim_transcript_hash_[n] || 1473 MLSPlaintextCommitContent_[n]); 1475 interim_transcript_hash_[n+1] = 1476 Hash(confirmed_transcript_hash_[n] || 1477 MLSPlaintextCommitAuthData_[n]); 1479 Thus the confirmed_transcript_hash field in a GroupContext object 1480 represents a transcript over the whole history of MLSPlaintext Commit 1481 messages, up to the confirmation tag field in the current 1482 MLSPlaintext message. The confirmation tag is then included in the 1483 transcript for the next epoch. The interim transcript hash is 1484 computed by new members using the confirmation tag in the GroupInfo 1485 struct, and enables existing members to incorporate a Commit message 1486 into the transcript without having to store the whole 1487 MLSPlaintextCommitAuthData structure. 1489 As shown above, when a new group is created, the 1490 interim_transcript_hash field is set to the zero-length octet string. 1492 7.8. Update Paths 1494 As described in Section 11.2, each MLS Commit message may optionally 1495 transmit a KeyPackage leaf and node values along its direct path. 1496 The path contains a public key and encrypted secret value for all 1497 intermediate nodes in the path above the leaf. The path is ordered 1498 from the closest node to the leaf to the root; each node MUST be the 1499 parent of its predecessor. 1501 struct { 1502 opaque kem_output<0..2^16-1>; 1503 opaque ciphertext<0..2^16-1>; 1504 } HPKECiphertext; 1506 struct { 1507 HPKEPublicKey public_key; 1508 HPKECiphertext encrypted_path_secret<0..2^32-1>; 1509 } UpdatePathNode; 1511 struct { 1512 KeyPackage leaf_key_package; 1513 UpdatePathNode nodes<0..2^32-1>; 1514 } UpdatePath; 1516 For each UpdatePathNode, the resolution of the corresponding copath 1517 node MUST be filtered by removing all new leaf nodes added as part of 1518 this MLS Commit message. The number of ciphertexts in the 1519 encrypted_path_secret vector MUST be equal to the length of the 1520 filtered resolution, with each ciphertext being the encryption to the 1521 respective resolution node. 1523 The HPKECiphertext values are computed as 1525 kem_output, context = SetupBaseS(node_public_key, group_context) 1526 ciphertext = context.Seal("", path_secret) 1528 where node_public_key is the public key of the node that the path 1529 secret is being encrypted for, group_context is the current 1530 GroupContext object for the group, and the functions SetupBaseS and 1531 Seal are defined according to [I-D.irtf-cfrg-hpke]. 1533 Decryption is performed in the corresponding way, using the private 1534 key of the resolution node and the ephemeral public key transmitted 1535 in the message. 1537 8. Key Schedule 1539 Group keys are derived using the Extract and Expand functions from 1540 the KDF for the group's ciphersuite, as well as the functions defined 1541 below: 1543 ExpandWithLabel(Secret, Label, Context, Length) = 1544 KDF.Expand(Secret, KDFLabel, Length) 1546 Where KDFLabel is specified as: 1548 struct { 1549 uint16 length = Length; 1550 opaque label<7..255> = "mls10 " + Label; 1551 opaque context<0..2^32-1> = Context; 1552 } KDFLabel; 1554 DeriveSecret(Secret, Label) = 1555 ExpandWithLabel(Secret, Label, "", KDF.Nh) 1557 The value KDF.Nh is the size of an output from KDF.Extract, in bytes. 1558 In the below diagram: 1560 * KDF.Extract takes its salt argument from the top and its IKM 1561 argument from the left 1563 * DeriveSecret takes its Secret argument from the incoming arrow 1565 * 0 represents an all-zero byte string of length KDF.Nh. 1567 When processing a handshake message, a client combines the following 1568 information to derive new epoch secrets: 1570 * The init secret from the previous epoch 1572 * The commit secret for the current epoch 1574 * The GroupContext object for current epoch 1576 Given these inputs, the derivation of secrets for an epoch proceeds 1577 as shown in the following diagram: 1579 init_secret_[n-1] 1580 | 1581 V 1582 commit_secret -> KDF.Extract 1583 | 1584 V 1585 ExpandWithLabel(., "joiner", GroupContext_[n], KDF.Nh) 1586 | 1587 V 1588 joiner_secret 1589 | 1590 V 1591 psk_secret (or 0) -> KDF.Extract 1592 | 1593 +--> DeriveSecret(., "welcome") 1594 | = welcome_secret 1595 | 1596 V 1597 ExpandWithLabel(., "epoch", GroupContext_[n], KDF.Nh) 1598 | 1599 V 1600 epoch_secret 1601 | 1602 +--> DeriveSecret(.,