idnits 2.17.1 draft-barnes-mls-protocol-01.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 02, 2018) is 2118 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'I-D.omara-mls-architecture' is mentioned on line 199, but not defined == Outdated reference: A later version (-42) exists of draft-ietf-trans-rfc6962-bis-28 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). 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 J. Millican 5 Expires: January 3, 2019 Facebook 6 E. Omara 7 Google 8 K. Cohn-Gordon 9 University of Oxford 10 R. Robert 11 Wire 12 July 02, 2018 14 The Messaging Layer Security (MLS) Protocol 15 draft-barnes-mls-protocol-01 17 Abstract 19 Messaging applications are increasingly making use of end-to-end 20 security mechanisms to ensure that messages are only accessible to 21 the communicating endpoints, and not to any servers involved in 22 delivering messages. Establishing keys to provide such protections 23 is challenging for group chat settings, in which more than two 24 participants need to agree on a key but may not be online at the same 25 time. In this document, we specify a key establishment protocol that 26 provides efficient asynchronous group key establishment with forward 27 secrecy and post-compromise security for groups in size ranging from 28 two to thousands. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at https://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on January 3, 2019. 47 Copyright Notice 49 Copyright (c) 2018 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (https://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 66 3. Basic Assumptions . . . . . . . . . . . . . . . . . . . . . . 5 67 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 5 68 5. Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . 9 69 5.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 9 70 5.2. Merkle Trees . . . . . . . . . . . . . . . . . . . . . . 11 71 5.2.1. Merkle Proofs . . . . . . . . . . . . . . . . . . . . 12 72 5.3. Ratchet Trees . . . . . . . . . . . . . . . . . . . . . . 12 73 5.3.1. Ratchet Trees for ART . . . . . . . . . . . . . . . . 13 74 5.3.2. Ratchet Trees for TreeKEM . . . . . . . . . . . . . . 13 75 5.3.3. Ratchet Tree Updates . . . . . . . . . . . . . . . . 14 76 5.3.4. Blank Ratchet Tree Nodes . . . . . . . . . . . . . . 15 77 6. Group State . . . . . . . . . . . . . . . . . . . . . . . . . 16 78 6.1. Cryptographic Objects . . . . . . . . . . . . . . . . . . 17 79 6.1.1. ART with Curve25519 and SHA-256 . . . . . . . . . . . 18 80 6.1.2. ART with P-256 and SHA-256 . . . . . . . . . . . . . 18 81 6.1.3. TreeKEM with Curve25519, SHA-256, and AES-128-GCM . . 19 82 6.1.4. TreeKEM with P-256, SHA-256, and AES-128-GCM . . . . 19 83 6.2. Direct Paths . . . . . . . . . . . . . . . . . . . . . . 20 84 6.3. Key Schedule . . . . . . . . . . . . . . . . . . . . . . 21 85 7. Initialization Keys . . . . . . . . . . . . . . . . . . . . . 22 86 7.1. UserInitKey . . . . . . . . . . . . . . . . . . . . . . . 23 87 7.2. GroupInitKey . . . . . . . . . . . . . . . . . . . . . . 23 88 8. Handshake Messages . . . . . . . . . . . . . . . . . . . . . 24 89 8.1. Init . . . . . . . . . . . . . . . . . . . . . . . . . . 26 90 8.2. GroupAdd . . . . . . . . . . . . . . . . . . . . . . . . 26 91 8.3. UserAdd . . . . . . . . . . . . . . . . . . . . . . . . . 27 92 8.4. Update . . . . . . . . . . . . . . . . . . . . . . . . . 28 93 8.5. Remove . . . . . . . . . . . . . . . . . . . . . . . . . 29 94 9. Sequencing of State Changes . . . . . . . . . . . . . . . . . 29 95 9.1. Server-Enforced Ordering . . . . . . . . . . . . . . . . 30 96 9.2. Client-Enforced Ordering . . . . . . . . . . . . . . . . 31 97 9.3. Merging Updates . . . . . . . . . . . . . . . . . . . . . 31 98 10. Message Protection . . . . . . . . . . . . . . . . . . . . . 32 99 11. Security Considerations . . . . . . . . . . . . . . . . . . . 33 100 11.1. Confidentiality of the Group Secrets . . . . . . . . . . 33 101 11.2. Authentication . . . . . . . . . . . . . . . . . . . . . 34 102 11.3. Forward and post-compromise security . . . . . . . . . . 34 103 11.4. Init Key Reuse . . . . . . . . . . . . . . . . . . . . . 34 104 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35 105 13. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 35 106 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 35 107 14.1. Normative References . . . . . . . . . . . . . . . . . . 35 108 14.2. Informative References . . . . . . . . . . . . . . . . . 36 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 37 111 1. Introduction 113 DISCLAIMER: This is a work-in-progress draft of MLS and has not yet 114 seen significant security analysis. It should not be used as a basis 115 for building production systems. 117 RFC EDITOR: PLEASE REMOVE THE FOLLOWING PARAGRAPH The source for this 118 draft is maintained in GitHub. Suggested changes should be submitted 119 as pull requests at https://github.com/ekr/mls-protocol. 120 Instructions are on that page as well. Editorial changes can be 121 managed in GitHub, but any substantive change should be discussed on 122 the MLS mailing list. 124 A group of agents who want to send each other encrypted messages 125 needs a way to derive shared symmetric encryption keys. For two 126 parties, this problem has been studied thoroughly, with the Double 127 Ratchet emerging as a common solution [doubleratchet] [signal]. 128 Channels implementing the Double Ratchet enjoy fine-grained forward 129 secrecy as well as post-compromise security, but are nonetheless 130 efficient enough for heavy use over low-bandwidth networks. 132 For a group of size greater than two, a common strategy is to 133 unilaterally broadcast symmetric "sender" keys over existing shared 134 symmetric channels, and then for each agent to send messages to the 135 group encrypted with their own sender key. Unfortunately, while this 136 improves efficiency over pairwise broadcast of individual messages 137 and (with the addition of a hash ratchet) provides forward secrecy, 138 it is difficult to achieve post-compromise security with sender keys. 139 An adversary who learns a sender key can often indefinitely and 140 passively eavesdrop on that sender's messages. Generating and 141 distributing a new sender key provides a form of post-compromise 142 security with regard to that sender. However, it requires 143 computation and communications resources that scale linearly as the 144 size of the group. 146 In this document, we describe a protocol based on tree structures 147 that enable asynchronous group keying with forward secrecy and post- 148 compromise security. This document describes two candidate 149 approaches, one using "asynchronous ratcheting trees" [art], the 150 other using an asynchronous key-encapsulation mechanism for tree 151 structures called TreeKEM. Both mechanisms allow the members of the 152 group to derive and update shared keys with costs that scale as the 153 log of the group size. The use of Merkle trees to store identity 154 information allows strong authentication of group membership, again 155 with logarithmic cost. 157 2. Terminology 159 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 160 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 161 document are to be interpreted as described in [RFC2119]. 163 [TODO: The architecture document uses "Client" instead of 164 "Participant". Harmonize terminology.] 166 Participant: An agent that uses this protocol to establish shared 167 cryptographic state with other participants. A participant is 168 defined by the cryptographic keys it holds. An application may 169 use one participant per device (keeping keys local to each device) 170 or sync keys among a user's devices so that each user appears as a 171 single participant. 173 Group: A collection of participants with shared cryptographic state. 175 Member: A participant that is included in the shared state of a 176 group, and has access to the group's secrets. 178 Initialization Key: A short-lived Diffie-Hellman key pair used to 179 introduce a new member to a group. Initialization keys can be 180 published for both individual participants (UserInitKey) and 181 groups (GroupInitKey). 183 Leaf Key: A short-lived Diffie-Hellman key pair that represents a 184 group member's contribution to the group secret, so called because 185 the participants leaf keys are the leaves in the group's ratchet 186 tree. 188 Identity Key: A long-lived signing key pair used to authenticate the 189 sender of a message. 191 Terminology specific to tree computations is described in Section 5. 193 We use the TLS presentation language [I-D.ietf-tls-tls13] to describe 194 the structure of protocol messages. 196 3. Basic Assumptions 198 This protocol is designed to execute in the context of a Messaging 199 Service (MS) as described in [I-D.omara-mls-architecture]. In 200 particular, we assume the MS provides the following services: 202 o A long-term identity key provider which allows participants to 203 authenticate protocol messages in a group. These keys MUST be 204 kept for the lifetime of the group as there is no mechanism in the 205 protocol for changing a participant's identity key. 207 o A broadcast channel, for each group, which will relay a message to 208 all members of a group. For the most part, we assume that this 209 channel delivers messages in the same order to all participants. 210 (See Section 9 for further considerations.) 212 o A directory to which participants can publish initialization keys, 213 and from which participant can download initialization keys for 214 other participants. 216 4. Protocol Overview 218 The goal of this protocol is to allow a group of participants to 219 exchange confidential and authenticated messages. It does so by 220 deriving a sequence of keys known only to group members. Keys should 221 be secret against an active network adversary and should have both 222 forward and post-compromise secrecy with respect to compromise of a 223 participant. 225 We describe the information stored by each participant as a _state_, 226 which includes both public and private data. An initial state, 227 including an initial set of participants, is set up by a group 228 creator using the _Init_ algorithm and based on information pre- 229 published by the initial members. The creator sends the _GroupInit_ 230 message to the participants, who can then set up their own group 231 state and derive the same shared key. Participants then exchange 232 messages to produce new shared states which are causally linked to 233 their predecessors, forming a logical Directed Acyclic Graph (DAG) of 234 states. Participants can send _Update_ messages for post-compromise 235 secrecy and new participants can be added or existing participants 236 removed from the group. 238 The protocol algorithms we specify here follow. Each algorithm 239 specifies both (i) how a participant performs the operation and (ii) 240 how other participants update their state based on it. 242 There are four major operations in the lifecycle of a group: 244 o Adding a member, initiated by a current member 246 o Adding a member, initiated by the new member 248 o Key update 250 o Removal of a member 252 Before the initialization of a group, participants publish 253 UserInitKey objects to a directory provided to the Messaging Service. 255 Group 256 A B C Directory Channel 257 | | | | | 258 | UserInitKeyA | | | | 259 |------------------------------------------->| | 260 | | | | | 261 | | UserInitKeyB | | | 262 | |---------------------------->| | 263 | | | | | 264 | | | UserInitKeyC | | 265 | | |------------->| | 266 | | | | | 268 When a participant A wants to establish a group with B and C, it 269 first downloads InitKeys for B and C. It then initializes a group 270 state containing only itself and uses the InitKeys to compute 271 GroupAdd messages to add B and C, in a sequence chosen by A. These 272 messages are broadcasted to the Group, and processed in sequence by B 273 and C. Messages received before a participant has joined the group 274 are ignored. Only after A has received its GroupAdd messages back 275 from the server does it update its state to reflect their addition. 277 Group 278 A B C Directory Channel 279 | | | | | 280 | UserInitKeyB, UserInitKeyC | | 281 |<-------------------------------------------| | 282 | | | | | 283 | | | | GroupAdd(A->AB) | 284 |--------------------------------------------------------------->| 285 | | | | | 286 | | | | GroupAdd(AB->ABC) | 287 |--------------------------------------------------------------->| 288 | | | | | 289 | | | | GroupAdd(A->AB) | 290 |<---------------------------------------------------------------| 291 |state.add(B) |<------------------------------------------------| 292 | |state.init() |x---------------------------------| 293 | | | | | 294 | | | | GroupAdd(AB->ABC) | 295 |<---------------------------------------------------------------| 296 |state.add(C) |<------------------------------------------------| 297 | |state.add(C) |<---------------------------------| 298 | | |state.init() | | 299 | | | | | 301 Subsequent additions of group members proceed in the same way. Any 302 member of the group can download an InitKey for a new participant and 303 broadcast a GroupAdd which the current group can use to update their 304 state and the new participant can use to initialize its state. 306 It is sometimes necessary for a new participant to join without an 307 explicit invitation from a current member. For example, if a user 308 that is authorized to be in the group logs in on a new device, that 309 device will need to join the group as a new participant, but will not 310 have been invited. 312 In these "user-initiated join" cases, the "InitKey + Add message" 313 flow is reversed. We assume that at some previous point, a group 314 member has published a GroupInitKey reflecting the current state of 315 the group (A, B, C). The new participant Z downloads that 316 GroupInitKey from the directory, generates a UserAdd message, and 317 broadcasts it to the group. Once current members process this 318 message, they will have a shared state that also includes Z. 320 Group 321 A B ... Z Directory Channel 322 | GroupInitKey | | | | 323 |------------------------------------------->| | 324 | | | | | 325 ~ ~ ~ ~ ~ 326 | | | | | 327 | | | GroupInitKey | | 328 | | |<-------------| | 329 | | | | | 330 | | | UserAdd(.->D)| | 331 | | |---------------------------->| 332 | | | | | 333 | | | | UserAdd(.->D)| 334 |<----------------------------------------------------------| 335 |state.add(D) |<-------------------------------------------| 336 | |state.add(D) |<----------------------------| 337 | | |state.init() | | 338 | | | | | 340 To enforce forward secrecy and post-compromise security of messages, 341 each participant periodically updates its leaf key, the DH key pair 342 that represents its contribution to the group key. Any member of the 343 group can send an Update at any time by generating a fresh leaf key 344 pair and sending an Update message that describes how to update the 345 group key with that new key pair. Once all participants have 346 processed this message, the group's secrets will be unknown to an 347 attacker that had compromised the sender's prior leaf private key. 349 It is left to the application to determine the interval of time 350 between Update messages. This policy could require a change for each 351 message, or it could require sending an update every week or more. 353 Group 354 A B ... Z Directory Channel 355 | | | | | 356 | Update(A) | | | | 357 |---------------------------------------------------------->| 358 | | | | | 359 | | | | Update(A) | 360 |<----------------------------------------------------------| 361 |state.upd(D) |<-------------------------------------------| 362 | |state.upd(D) |<----------------------------| 363 | | |state.upd(A) | | 364 | | | | | 366 Users are deleted from the group in a similar way, as a key update is 367 effectively removing the old leaf from the group. Any member of the 368 group can generate a Delete message that adds new entropy to the 369 group state that is known to all members except the deleted member. 370 After other participants have processed this message, the group's 371 secrets will be unknown to the deleted participant. Note that this 372 does not necessarily imply that any member is actually allowed to 373 evict other members; groups can layer authentication-based access 374 control policies on top of these basic mechanism. 376 Group 377 A B ... Z Directory Channel 378 | | | | | 379 | | | Delete(B) | | 380 | | |---------------------------->| 381 | | | | | 382 | | | | Delete(B) | 383 |<----------------------------------------------------------| 384 |state.del(B) | |<----------------------------| 385 | | |state.del(B) | | 386 | | | | | 387 | | | | | 389 5. Binary Trees 391 The protocol uses two types of binary tree structures: 393 o Merkle trees for efficiently committing to a set of group 394 participants. 396 o Ratchet trees for deriving shared secrets among this group of 397 participants. 399 The two trees in the protocol share a common structure, allowing us 400 to maintain a direct mapping between their nodes when manipulating 401 group membership. The "nth" leaf in each tree is owned by the "nth" 402 group participant. 404 5.1. Terminology 406 We use a common set of terminology to refer to both types of binary 407 tree. 409 Trees consist of various different types of _nodes_. A node is a 410 _leaf_ if it has no children, and a _parent_ otherwise; note that all 411 parents in our Merkle or ratchet trees have precisely two children, a 412 _left_ child and a _right_ child. A node is the _root_ of a tree if 413 it has no parents, and _intermediate_ if it has both children and 414 parents. The _descendants_ of a node are that node, its children, 415 and the descendants of its children, and we say a tree _contains_ a 416 node if that node is a descendant of the root of the tree. Nodes are 417 _siblings_ if they share the same parent. 419 A _subtree_ of a tree is the tree given by the descendants of any 420 node, the _head_ of the subtree The _size_ of a tree or subtree is 421 the number of leaf nodes it contains. For a given parent node, its 422 _left subtree_ is the subtree with its left child as head 423 (respectively _right subtree_). 425 All trees used in this protocol are left-balanced binary trees. A 426 binary tree is _full_ (and _balanced_) if it its size is a power of 427 two and for any parent node in the tree, its left and right subtrees 428 have the same size. If a subtree is full and it is not a subset of 429 any other full subtree, then it is _maximal_. 431 A binary tree is _left-balanced_ if for every parent, either the 432 parent is balanced, or the left subtree of that parent is the largest 433 full subtree that could be constructed from the leaves present in the 434 parent's own subtree. Note that given a list of "n" items, there is 435 a unique left-balanced binary tree structure with these elements as 436 leaves. In such a left-balanced tree, the "k-th" leaf node refers to 437 the "k-th" leaf node in the tree when counting from the left, 438 starting from 0. 440 The _direct path_ of a root is the empty list, and of any other node 441 is the concatenation of that node with the direct path of its parent. 442 The _copath_ of a node is the list of siblings of nodes in its direct 443 path, excluding the root, which has no sibling. The _frontier_ of a 444 tree is the list of heads of the maximal full subtrees of the tree, 445 ordered from left to right. 447 For example, in the below tree: 449 o The direct path of C is (C, CD, ABCD) 451 o The copath of C is (D, AB, EFG) 453 o The frontier of the tree is (ABCD, EF, G) 454 ABCDEFG 455 / \ 456 / \ 457 / \ 458 ABCD EFG 459 / \ / \ 460 / \ / \ 461 AB CD EF \ 462 / \ / \ / \ \ 463 A B C D E F G 465 We extend both types of tree to include a concept of "blank" nodes; 466 which are used to replace group members who have been removed. We 467 expand on how these are used and implemented in the sections below. 469 (Note that left-balanced binary trees are the same structure that is 470 used for the Merkle trees in the Certificate Transparency protocol 471 [I-D.ietf-trans-rfc6962-bis].) 473 5.2. Merkle Trees 475 Merkle trees are used to efficiently commit to a collection of group 476 members. We require a hash function, denoted H, to construct this 477 tree. 479 Each node in a Merkle tree is the output of the hash function, 480 computed as follows: 482 o Leaf nodes: "H( 0x01 || leaf-value )" 484 o Parent nodes: "H( 0x02 || left-value || right-value)" 486 o Blank leaf nodes: "H( 0x00 )" 488 The below tree provides an example of a size 2 tree, containing 489 identity keys "A" and "B". 491 * H(2 || H(1 || A) || H(1 || B)) 492 / \ 493 / \ 494 H(1 || A) * * H(1 || B) 496 In Merkle trees, blank nodes appear only at the leaves. In 497 computation of intermediate nodes, they are treated in the same way 498 as other nodes. 500 5.2.1. Merkle Proofs 502 A proof of a given leaf being a member of the Merkle tree consists of 503 the value of the leaf node, as well as the values of each node in its 504 copath. From these values, its path to the root can be verified; 505 proving the inclusion of the leaf in the Merkle tree. 507 In the below tree, we denote with a star the Merkle proof of 508 membership for leaf node "A". For brevity, we notate "Hash(0x02 || 509 A || B)" as "AB". 511 ABCD 512 / \ 513 AB CD* 514 / \ / \ 515 A B* C D 517 5.3. Ratchet Trees 519 Ratchet trees are used for generating shared group secrets. In this 520 section, we describe the structure of a ratchet tree, along with two 521 ways to manage a ratchet tree, called ART and TreeKEM. 523 To construct these trees, we require: 525 o A Diffie-Hellman finite-field group or elliptic curve 527 o A Derive-Key-Pair function that produces a key pair from an octet 528 string 530 o A hash function (TreeKEM only) 532 A ratchet tree is a left-balanced binary tree, in which each node 533 contains up to three values: 535 o A secret octet string (optional) 537 o An asymmetric private key (optional) 539 o An asymmetric public key 541 The private key and public key for a node are derived from its secret 542 value using the Derive-Key-Pair operation. 544 The relationships between nodes are different for ART and TreeKEM. 545 In either case, the ratchet tree structure ensures the following 546 property: A party can compute the secret value for the root of the 547 tree if and only if that party holds the secret value for another 548 node lower in the tree (together with public information). Each 549 participant holds one leaf secret; each participant can update the 550 root secret by changing their leaf secret. 552 5.3.1. Ratchet Trees for ART 554 In ART the contents of a parent node are computed from its children 555 as follows: 557 o parent_secret = DH(left_child, right_child) 559 o parent_private, parent_public = Derive-Key-Pair(parent_secret) 561 Ratchet trees are constructed as left-balanced trees, defined such 562 that each parent node's key pair is derived from the Diffie-Hellman 563 shared secret of its two child nodes. To compute the root secret and 564 private key, a participant must know the public keys of nodes in its 565 copath, as well as its own leaf private key. 567 For example, the ratchet tree consisting of the private keys (A, B, 568 C, D) is constructed as follows: 570 DH(DH(AB), DH(CD)) 571 / \ 572 DH(AB) DH(CD) 573 / \ / \ 574 A B C D 576 5.3.2. Ratchet Trees for TreeKEM 578 In TreeKEM, the contents of a parent node are computed from one of 579 its children as follows: 581 o parent_secret = Hash(child_secret) 583 o parent_private, parent_public = Derive-Key-Pair(parent_secret) 585 The contents of the parent are based on the latest-updated child. 586 For example, if participants with leaf secrets A, B, C, and D join a 587 group in that order, then the resulting tree will have the following 588 structure: 590 H(H(D)) 591 / \ 592 H(B) H(D) 593 / \ / \ 594 A B C D 595 If the first participant subsequently changes its leaf secret to be 596 X, then the tree will have the following structure. 598 H(H(X)) 599 / \ 600 H(X) H(D) 601 / \ / \ 602 X B C D 604 5.3.3. Ratchet Tree Updates 606 In order to update the state of the group such as adding and removing 607 participants, MLS messages are used to make changes to the group's 608 ratchet tree. While the details of update processing differ between 609 ART and TreeKEM (as described below), in both cases the participant 610 proposing an update to the tree transmits a representation of a set 611 of tree nodes along the direct path from a leaf to the root. Other 612 participants in the group can use these nodes to update their view of 613 the tree, aligning their copy of the tree to the sender's. 615 In ART, the transmitted nodes are represented by their public keys. 616 Receivers process an update with the following steps: 618 1. Replace the public keys in the cached tree with the received 619 values 621 2. Whenever a public key is updated for a node whose sibling has a 622 private key populated: 624 * Perform a DH operation and update the node's parent 626 * Repeat the prior step until reaching the root 628 In TreeKEM, the sender transmits a node by sending the public key for 629 the node and an encrypted version of the secret value for the node. 630 The secret value is encrypted in such a way that it can be decrypted 631 only by holders of the private key for one of its children, namely 632 the child that is not in the direct path being transmitted. (That 633 is, each node in the direct path is encrypted for holders of the 634 private key for a node in the corresponding copath.) For leaf nodes, 635 no encrypted secret is transmitted. 637 A TreeKEM update is processed with the following steps: 639 1. Compute the updated secret values * Identify a node in the direct 640 path for which the local participant has the private key * 641 Decrypt the secret value for that node * Compute secret values 642 for ancestors of that node by hashing the decrypted secret 644 2. Merge the updated secrets into the tree * Replace the public keys 645 for nodes on the direct path with the received public keys * For 646 nodes where an updated secret was computed in step 1, replace the 647 secret value for the node with the updated value 649 For example, suppose we had the following tree: 651 G 652 / \ 653 / \ 654 E F 655 / \ / \ 656 A B C D 658 If an update is made along the direct path B-E-G, then the following 659 values will be transmitted (using pk(X) to represent the public key 660 corresponding to the secret value X and E(K, S) to represent public- 661 key encryption to the public key K of the secret value S): 663 +------------+-------------+ 664 | Public Key | Ciphertext | 665 +------------+-------------+ 666 | pk(G) | E(pk(F), G) | 667 | | | 668 | pk(E) | E(pk(A), E) | 669 | | | 670 | pk(B) | | 671 +------------+-------------+ 673 5.3.4. Blank Ratchet Tree Nodes 675 Nodes in a ratchet tree can have a special value "_", used to 676 indicate that the node should be ignored during path computations. 677 Such nodes are used to replace leaves when participants are deleted 678 from the group. 680 If any node in the copath of a leaf is _, it should be ignored during 681 the computation of the path. For example, the tree consisting of the 682 private keys (A, _, C, D) is constructed as follows for ART: 684 DH(A, DH(CD)) 685 / \ 686 A DH(CD) 687 / \ / \ 688 A _ C D 690 Replacing a node by _ in TreeKEM, means performing an update on any 691 leaf without sending the new key to the the blanked leaf. In the 692 following example, participant A update its key to A' and derive the 693 new sequence of keys up-to the path. Here A only send H(H(A')) to 694 the parent node of C and D but does not send H(A') to B which evicts 695 it from the Group. ~~~~~ H(H(A')) / \ H(A') H(C) / \ / \ A' _ C D 696 ~~~~~ 698 If two sibling nodes are both _, their parent value also becomes _. 700 Blank nodes effectively result in an unbalanced tree, but allow the 701 tree management to behave as for a balanced tree for programming 702 simplicity. 704 6. Group State 706 The state of an MLS group at a given time comprises: 708 o A group identifier (GID) 710 o A ciphersuite used for cryptographic computations 712 o A Merkle tree over the participants' identity keys 714 o A ratchet tree over the participants' leaf key pairs 716 o A message master secret (known only to participants) 718 o An add key pair (private key known only to participants) 720 o An init secret (known only to participants) 722 Since a group can evolve over time, a session logically comprises a 723 sequence of states. The time in which each individual state is used 724 is called an "epoch", and each state is assigned an epoch number that 725 increments when the state changes. 727 MLS handshake messages provide each node with enough information 728 about the trees to authenticate messages within the group and compute 729 the group secrets. 731 Thus, each participant will need to store the following information 732 about each state of the group: 734 1. The participant's index in the identity/ratchet trees 736 2. The private key associated with the participant's leaf public 737 key 739 3. The private key associated with the participant's identity 740 public key 742 4. The current epoch number 744 5. The group identifier (GID) 746 6. A subset of the identity tree comprising at least the copath for 747 the participant's leaf 749 7. A subset of the ratchet tree comprising at least the copath for 750 the participant's leaf 752 8. The current message encryption shared secret, called the master 753 secret 755 9. The current add key pair 757 10. The current init secret 759 6.1. Cryptographic Objects 761 Each MLS session uses a single ciphersuite that specifies the 762 following primitives to be used in group key computations: 764 o A hash function 766 o A Diffie-Hellman finite-field group or elliptic curve 768 o An AEAD encryption algorithm (TreeKEM only) [RFC5116] 770 The ciphersuite must also specify an algorithm "Derive-Key-Pair" that 771 maps octet strings with the same length as the output of the hash 772 function to key pairs for the asymmetric encryption scheme. 774 Public keys and Merkle tree nodes used in the protocol are opaque 775 values in a format defined by the ciphersuite, using the following 776 four types: 778 uint16 CipherSuite; 779 opaque DHPublicKey<1..2^16-1>; 780 opaque SignaturePublicKey<1..2^16-1>; 781 opaque MerkleNode<1..255> 783 [[OPEN ISSUE: In some cases we will want to include a raw key when we 784 sign and in others we may want to include an identity or a 785 certificate containing the key. This type needs to be extended to 786 accommodate that.]] 788 6.1.1. ART with Curve25519 and SHA-256 790 This ciphersuite uses the following primitives: 792 o Hash function: SHA-256 794 o Diffie-Hellman group: Curve25519 [RFC7748] 796 o AEAD: N/A 798 Given an octet string X, the private key produced by the Derive-Key- 799 Pair operation is SHA-256(X). (Recall that any 32-octet string is a 800 valid Curve25519 private key.) The corresponding public key is 801 X25519(SHA-256(X), 9). 803 Implementations SHOULD use the approach specified in [RFC7748] to 804 calculate the Diffie-Hellman shared secret. Implementations MUST 805 check whether the computed Diffie-Hellman shared secret is the all- 806 zero value and abort if so, as described in Section 6 of [RFC7748]. 807 If implementers use an alternative implementation of these elliptic 808 curves, they SHOULD perform the additional checks specified in 809 Section 7 of [RFC7748] 811 6.1.2. ART with P-256 and SHA-256 813 This ciphersuite uses the following primitives: 815 o Hash function: SHA-256 817 o Diffie-Hellman group: secp256r1 (NIST P-256) 819 o AEAD: N/A 821 Given an octet string X, the private key produced by the Derive-Key- 822 Pair operation is SHA-256(X), interpreted as a big-endian integer. 823 The corresponding public key is the result of multiplying the 824 standard P-256 base point by this integer. 826 P-256 ECDH calculations (including parameter and key generation as 827 well as the shared secret calculation) are performed according to 828 [IEEE1363] using the ECKAS-DH1 scheme with the identity map as key 829 derivation function (KDF), so that the shared secret is the 830 x-coordinate of the ECDH shared secret elliptic curve point 831 represented as an octet string. Note that this octet string (Z in 832 IEEE 1363 terminology) as output by FE2OSP, the Field Element to 833 Octet String Conversion Primitive, has constant length for any given 834 field; leading zeros found in this octet string MUST NOT be 835 truncated. 837 (Note that this use of the identity KDF is a technicality. The 838 complete picture is that ECDH is employed with a non-trivial KDF 839 because MLS does not directly use this secret for anything other than 840 for computing other secrets.) 842 Clients MUST validate remote public values by ensuring that the point 843 is a valid point on the elliptic curve. The appropriate validation 844 procedures are defined in Section 4.3.7 of [X962] and alternatively 845 in Section 5.6.2.3 of [keyagreement]. This process consists of three 846 steps: (1) verify that the value is not the point at infinity (O), 847 (2) verify that for Y = (x, y) both integers are in the correct 848 interval, (3) ensure that (x, y) is a correct solution to the 849 elliptic curve equation. For these curves, implementers do not need 850 to verify membership in the correct subgroup. 852 6.1.3. TreeKEM with Curve25519, SHA-256, and AES-128-GCM 854 This ciphersuite uses the following primities: 856 o Hash function: SHA-256 858 o Diffie-Hellman group: Curve25519 [RFC7748] 860 o AEAD: AES-128-GCM 862 DH and Derive-Key-Pair operations are performed in the same way as 863 the corresponding ART ciphersuite. 865 Encryption keys are derived from shared secrets by taking the first 866 16 bytes of H(Z), where Z is the shared secret and H is SHA-256. 868 6.1.4. TreeKEM with P-256, SHA-256, and AES-128-GCM 870 This ciphersuite uses the following primities: 872 o Hash function: P-256 874 o Diffie-Hellman group: secp256r1 (NIST P-256) 876 o AEAD: AES-128-GCM 878 DH and Derive-Key-Pair operations are performed in the same way as 879 the corresponding ART ciphersuite. 881 Encryption keys are derived from shared secrets by taking the first 882 16 bytes of H(Z), where Z is the shared secret and H is SHA-256. 884 6.2. Direct Paths 886 As described in Section 5.3.3, each MLS message needs to transmit 887 node values along the direct path from a leaf to the root. In ART, 888 this simply entails sending the public key for each node. In 889 TreeKEM, the path contains a public key for the leaf node, and a 890 public key and encrypted secret value for intermediate nodes in the 891 path. In both cases, the path is ordered from the leaf to the root; 892 each node MUST be the parent of its predecessor. 894 DHPublicKey ARTPath<0..2^16-1>; 896 struct { 897 DHPublicKey ephemeral_key; 898 opaque nonce<0..255>; 899 opaque ciphertext<0..255>; 900 } ECIESCiphertext; 902 struct { 903 DHPublicKey public_key; 904 ECIESCiphertext ciphertext; 905 } TreeKEMNode; 907 struct { 908 DHPublicKey leaf; 909 TreeKEMNode intermediates<0..2^16-1>; 910 } TreeKEMPath; 912 struct { 913 select (mode) { 914 case ART: ARTPath; 915 case TreeKEM: TreeKEMPath; 916 }; 917 } DirectPath; 919 When using TreeKEM, the ECIESCiphertext values encoding the encrypted 920 secret values are computed as follows: 922 o Generate an ephemeral DH key pair (x, x*G) in the DH group 923 specified by the ciphersuite in use 925 o Compute the shared secret Z with the node's other child 927 o Generate a fresh nonce N 929 o Encrypt the node's secret value using the AEAD algorithm specified 930 by the ciphersuite in use, with the following inputs: 932 * Key: A key derived from Z as specified by the ciphersuite 934 * Nonce: A random nonce N of the size required by the algorithm 936 * Additional Authenticated Data: The empty octet string 938 * Plaintext: The secret value, without any further formatting 940 o Encode the ECIESCiphertext with the following values: 942 * ephemeral_key: The ephemeral public key x*G 944 * nonce: The random nonce N 946 * ciphertext: The AEAD output 948 Decryption is performed in the corresponding way, using the private 949 key of the non-updated child and the ephemeral public key transmitted 950 in the message. 952 6.3. Key Schedule 954 Group keys are derived using the HKDF-Extract and HKDF-Expand 955 functions as defined in [RFC5869], as well as the functions defined 956 below: 958 Derive-Secret(Secret, Label, ID, Epoch, Msg) = 959 HKDF-Expand(Secret, HkdfLabel, Length) 961 Where HkdfLabel is specified as: 963 struct { 964 uint16 length = Length; 965 opaque label<7..255> = "mls10 " + Label; 966 opaque group_id<0..2^16-1> = ID; 967 uint32 epoch = Epoch; 968 opaque message<1..2^16-1> = Msg 969 } HkdfLabel; 971 The Hash function used by HKDF is the ciphersuite hash algorithm. 972 Hash.length is its output length in bytes. In the below diagram: 974 o HKDF-Extract takes its Salt argument from the top and its IKM 975 argument from the left 977 o Derive-Secret takes its Secret argument from the incoming arrow 978 When processing a handshake message, a participant combines the 979 following information to derive new epoch secrets: 981 o The init secret from the previous epoch 983 o The update secret for the current epoch 985 o The handshake message that caused the epoch change 987 o The current group identifier (GID) and epoch 989 The derivation of the update secret depends on the change being made, 990 as described below. 992 For UserAdd or GroupAdd, the new user does not know the prior epoch 993 init secret. Instead, entropy from the prior epoch is added via the 994 update secret, and an all-zero vector with the same length as a hash 995 output is used in the place of the init secret. 997 Given these inputs, the derivation of secrets for an epoch proceeds 998 as shown in the following diagram: 1000 Init Secret [n-1] (or 0) 1001 | 1002 V 1003 Update Secret -> HKDF-Extract = Epoch Secret 1004 | 1005 | 1006 +--> Derive-Secret(., "msg", ID, Epoch, Msg) 1007 | = message_master_secret 1008 | 1009 +--> Derive-Secret(., "add", ID, Epoch, Msg) 1010 | | 1011 | V 1012 | Derive-Key-Pair(.) = Add Key Pair 1013 | 1014 V 1015 Derive-Secret(., "init", ID, Epoch, Msg) 1016 | 1017 V 1018 Init Secret [n] 1020 7. Initialization Keys 1022 In order to facilitate asynchronous addition of participants to a 1023 group, it is possible to pre-publish initialization keys that provide 1024 some public information about a user or group. UserInitKey messages 1025 provide information about a potential group member, that a group 1026 member can use to add this user to a group asynchronously. 1027 GroupInitKey messages provide information about a group that a new 1028 user can use to join the group without any of the existing members of 1029 the group being online. 1031 7.1. UserInitKey 1033 A UserInitKey object specifies what ciphersuites a client supports, 1034 as well as providing public keys that the client can use for key 1035 derivation and signing. The client's identity key is intended to be 1036 stable throughout the lifetime of the group; there is no mechanism to 1037 change it. Init keys are intended to be used a very limited number 1038 of times, potentially once. (see Section 11.4). 1040 The init_keys array MUST have the same length as the cipher_suites 1041 array, and each entry in the init_keys array MUST be a public key for 1042 the DH group or KEM defined by the corresponding entry in the 1043 cipher_suites array. 1045 The whole structure is signed using the client's identity key. A 1046 UserInitKey object with an invalid signature field MUST be considered 1047 malformed. The input to the signature computation comprises all of 1048 the fields except for the signature field. 1050 struct { 1051 CipherSuite cipher_suites<0..255>; 1052 DHPublicKey init_keys<1..2^16-1>; 1053 SignaturePublicKey identity_key; 1054 SignatureScheme algorithm; 1055 opaque signature<0..2^16-1>; 1056 } UserInitKey; 1058 7.2. GroupInitKey 1060 A GroupInitKey object specifies the aspects of a group's state that a 1061 new member needs to initialize its state (together with an identity 1062 key and a fresh leaf key pair). 1064 o The current epoch number 1066 o The number of participants currently in the group 1068 o The group ID 1070 o The cipher suite used by the group 1072 o The public key of the current update key pair for the group 1073 o The frontier of the identity tree, as a sequence of hash values 1075 o The frontier of the ratchet tree, as a sequence of public keys 1077 GroupInitKey messages are not themselves signed. A GroupInitKey 1078 should not be published "bare"; instead, it should be published by 1079 constructing a handshake message with type "none", which will include 1080 a signature by a member of the group and a proof of membership in the 1081 group. 1083 struct { 1084 uint32 epoch; 1085 uint32 group_size; 1086 opaque group_id<0..2^16-1>; 1087 CipherSuite cipher_suite; 1088 DHPublicKey add_key; 1089 MerkleNode identity_frontier<0..2^16-1>; 1090 TreeNode ratchet_frontier<0..2^16-1>; 1091 } GroupInitKey; 1093 8. Handshake Messages 1095 Over the lifetime of a group, its state will change for: 1097 o Group initialization 1099 o A current member adding a new participant 1101 o A new participant adding themselves 1103 o A current participant updating its leaf key 1105 o A current member deleting another current member 1107 In MLS, these changes are accomplished by broadcasting "handshake" 1108 messages to the group. Note that unlike TLS and DTLS, there is not a 1109 consolidated handshake phase to the protocol. Rather, handshake 1110 messages are exchanged throughout the lifetime of a group, whenever a 1111 change is made to the group state. This means an unbounded number of 1112 interleaved application and handshake messages. 1114 An MLS handshake message encapsulates a specific message that 1115 accomplishes a change to the group state. It also includes two other 1116 important features: 1118 o A GroupInitKey so that a new participant can observe the latest 1119 state of the handshake and initialize itself 1121 o A signature by a member of the group, together with a Merkle 1122 inclusion proof that demonstrates that the signer is a legitimate 1123 member of the group. 1125 Before considering a handshake message valid, the recipient MUST 1126 verify both that the signature is valid, the Merkle inclusion proof 1127 is valid, and the sender is authorized to make the change according 1128 to group policy. The input to the signature computations comprises 1129 the entire handshake message except for the signature field. 1131 The Merkle tree head to be used for validating the inclusion proof 1132 MUST be one that the recipient trusts to represent the current list 1133 of participant identity keys. 1135 enum { 1136 none(0), 1137 init(1), 1138 user_add(2), 1139 group_add(3), 1140 update(4), 1141 delete(5), 1142 (255) 1143 } HandshakeType; 1145 struct { 1146 HandshakeType msg_type; 1147 uint24 inner_length; 1148 select (Handshake.msg_type) { 1149 case none: struct{}; 1150 case init: Init; 1151 case user_add: UserAdd; 1152 case group_add: GroupAdd; 1153 case update: Update; 1154 case delete: Delete; 1155 }; 1157 uint32 prior_epoch; 1158 GroupInitKey init_key; 1160 uint32 signer_index; 1161 MerkleNode identity_proof<1..2^16-1>; 1162 SignaturePublicKey identity_key; 1164 SignatureScheme algorithm; 1165 opaque signature<1..2^16-1>; 1166 } Handshake; 1168 [[ OPEN ISSUE: There will be a need to integrate credentials from an 1169 authentication service that associate identities to the identity keys 1170 used to sign messages. This integration will enable meaningful 1171 authentication (of identities, rather than keys), and will need to be 1172 done in such a way as to prevent unknown key share attacks. ]] 1174 [[ OPEN ISSUE: The GroupAdd and Delete operations create a "double- 1175 join" situation, where a participants leaf key is also known to 1176 another participant. When a participant A is double-joined to 1177 another B, deleting A will not remove them from the conversation, 1178 since they will still hold the leaf key for B. These situations are 1179 resolved by updates, but since operations are asynchronous and 1180 participants may be offline for a long time, the group will need to 1181 be able to maintain security in the presence of double-joins. ]] 1183 [[ OPEN ISSUE: It is not possible for the recipient of a handshake 1184 message to verify that ratchet tree information in the message is 1185 accurate, because each node can only compute the secret and private 1186 key for nodes in its direct path. This creates the possibility that 1187 a malicious participant could cause a denial of service by sending a 1188 handshake message with invalid values for public keys in the ratchet 1189 tree. ]] 1191 8.1. Init 1193 [[ OPEN ISSUE: Direct initialization is currently undefined. A 1194 participant can create a group by initializing its own state to 1195 reflect a group including only itself, then adding the initial 1196 participants. This has computation and communication complexity O(N 1197 log N) instead of the O(N) complexity of direct initialization. ]] 1199 8.2. GroupAdd 1201 A GroupAdd message is sent by a group member to add a new participant 1202 to the group. 1204 struct { 1205 PublicKey ephemeral; 1206 DirectPath add_path<1..2^16-1>; 1207 } GroupAdd; 1209 A group member generates this message using the following steps: 1211 o Requesting from the directory a UserInitKey for the user to be 1212 added 1214 o Generate a fresh ephemeral DH key pair 1215 o Generate the leaf secret for the new node as the output of a DH 1216 operation between the ephemeral key pair and the public key in the 1217 UserInitKey 1219 o Use the ratchet frontier and the new leaf secret to compute the 1220 direct path between the new leaf and the new root 1222 The public key of the ephemeral key pair is placed in the "ephemeral" 1223 field of the GroupAdd message. The computed direct path is placed in 1224 the "add_path" field. 1226 The new participant processes the message and the private key 1227 corresponding to the UserInitKey to initialize his state as follows: 1229 o Compute the participant's leaf secret by combining the init key in 1230 the UserInitKey with the prior epoch's add key pair 1232 o Use the frontiers in the GroupInitKey of the Handshake message to 1233 add its keys to the trees 1235 An existing participant receiving a GroupAdd message first verifies 1236 the signature on the message, then verifies its identity proof 1237 against the identity tree held by the participant. The participant 1238 then updates its state as follows: 1240 o Compute the new participant's leaf key pair by combining the leaf 1241 key in the UserInitKey with the prior epoch add key pair 1243 o Update the group's identity tree and ratchet tree with the new 1244 participant's information 1246 The update secret resulting from this change is the output of a DH 1247 computation between the private key for the root of the ratchet tree 1248 and the add public key from the previous epoch. 1250 8.3. UserAdd 1252 A UserAdd message is sent by a new group participant to add themself 1253 to the group, based on having already had access to a GroupInitKey 1254 for the group. 1256 struct { 1257 DirectPath add_path; 1258 } UserAdd; 1260 A new participant generates this message using the following steps: 1262 o Fetch a GroupInitKey for the group 1263 o Use the frontiers in the GroupInitKey to add its keys to the trees 1265 o Compute the direct path from the new participant's leaf in the new 1266 ratchet tree (the add_path). 1268 An existing participant receiving a UserAdd first verifies the 1269 signature on the message, then verifies its identity inclusion proof 1270 against the updated identity tree expressed in the GroupInitKey of 1271 the Handshake message (since the signer is not included in the prior 1272 group state held by the existing participant). The participant then 1273 updates its state as follows: 1275 o Update trees with the descriptions in the new GroupInitKey 1277 o Update the local ratchet tree with the information in the UserAdd 1278 message, replacing any common nodes with the values in the add 1279 path 1281 The update secret resulting from this change is the output of a DH 1282 computation between the private key for the root of the ratchet tree 1283 and the add public key from the previous epoch. 1285 8.4. Update 1287 An Update message is sent by a group participant to update its leaf 1288 key pair. This operation provides post-compromise security with 1289 regard to the participant's prior leaf private key. 1291 struct { 1292 DirectPath update_path; 1293 } Update; 1295 The sender of an Update message creates it in the following way: 1297 o Generate a fresh leaf key pair 1299 o Compute its direct path in the current ratchet tree 1301 An existing participant receiving a Update message first verifies the 1302 signature on the message, then verifies its identity proof against 1303 the identity tree held by the participant. The participant then 1304 updates its state as follows: 1306 o Update the cached ratchet tree by replacing nodes in the direct 1307 path from the updated leaf using the information contained in the 1308 Update message 1310 The update secret resulting from this change is the secret for the 1311 root node of the ratchet tree. 1313 8.5. Remove 1315 A Remove message is sent by a group member to remove one or more 1316 participants from the group. 1318 struct { 1319 uint32 deleted; 1320 DirectPath path; 1321 } Remove; 1323 The sender of a Remove message generates it as as follows: 1325 o Generate a fresh leaf key pair 1327 o Compute its direct path in the current ratchet tree, starting from 1328 the deleted leaf (Note: In ART, this requires knowing the deleted 1329 node's copath) 1331 An existing participant receiving a Delete message first verifies the 1332 signature on the message, then verifies its identity proof against 1333 the identity tree held by the participant. The participant then 1334 updates its state as follows: 1336 o Update the cached ratchet tree by replacing nodes in the direct 1337 path from the deleted leaf using the information in the Delete 1338 message 1340 o Update the cached ratchet tree and identity tree by replacing the 1341 deleted node's leaves with blank nodes 1343 The update secret resulting from this change is the secret for the 1344 root node of the ratchet tree after both updates. 1346 9. Sequencing of State Changes 1348 [[ OPEN ISSUE: This section has an initial set of considerations 1349 regarding sequencing. It would be good to have some more detailed 1350 discussion, and hopefully have a mechanism to deal with this issue. 1351 ]] 1353 Each handshake message is premised on a given starting state, 1354 indicated in its "prior_epoch" field. If the changes implied by a 1355 handshake messages are made starting from a different state, the 1356 results will be incorrect. 1358 This need for sequencing is not a problem as long as each time a 1359 group member sends a handshake message, it is based on the most 1360 current state of the group. In practice, however, there is a risk 1361 that two members will generate handshake messages simultaneously, 1362 based on the same state. 1364 When this happens, there is a need for the members of the group to 1365 deconflict the simultaneous handshake messages. There are two 1366 general approaches: 1368 o Have the delivery service enforce a total order 1370 o Have a signal in the message that clients can use to break ties 1372 In ART, in either case, there is a risk of starvation. In a 1373 sufficiently busy group, a given member may never be able to send a 1374 handshake message, because he always loses to other members. The 1375 degree to which this is a practical problem will depend on the 1376 dynamics of the application. 1378 In TreeKEM, because of the non-contributivity of intermediate nodes 1379 update messages can be applied one after the other without the 1380 Delivery Service having to reject any handshake message which makes 1381 TreeKEM more resilient regarding the concurrency of handshake 1382 messages. The Messaging system can decide to choose the order for 1383 applying the state changes. Note that there are certain cases (if no 1384 total ordering is applied by the Delivery Service) where the ordering 1385 is important for security, ie. all updates must be executed before 1386 deletes. 1388 Regardless of how messages are kept in sequence, implementations MUST 1389 only update their cryptographic state when valid handshake messages 1390 are received. Generation of handshake messages MUST be stateless, 1391 since the endpoint cannot know at that time whether the change 1392 implied by the handshake message will succeed or not. 1394 9.1. Server-Enforced Ordering 1396 With this approach, the delivery service ensures that incoming 1397 messages are added to an ordered queue and outgoing messages are 1398 dispatched in the same order. The server is trusted to resolve 1399 conflicts during race-conditions (when two members send a message at 1400 the same time), as the server doesn't have any additional knowledge 1401 thanks to the confidentiality of the messages. 1403 Messages should have a counter field sent in clear-text that can be 1404 checked by the server and used for tie-breaking. The counter starts 1405 at 0 and is incremented for every new incoming message. In ART, if 1406 two group members send a message with the same counter, the first 1407 message to arrive will be accepted by the server and the second one 1408 will be rejected. The rejected message needs to be sent again with 1409 the correct counter number. In TreeKEM, the message does not 1410 necessarily need to be resent. 1412 To prevent counter manipulation by the server, the counter's 1413 integrity can be ensured by including the counter in a signed message 1414 envelope. 1416 This applies to all messages, not only state changing messages. 1418 9.2. Client-Enforced Ordering 1420 Order enforcement can be implemented on the client as well, one way 1421 to achieve it is to use a two step update protocol: the first client 1422 sends a proposal to update and the proposal is accepted when it gets 1423 50%+ approval from the rest of the group, then it sends the approved 1424 update. Clients which didn't get their proposal accepted, will wait 1425 for the winner to send their update before retrying new proposals. 1427 While this seems safer as it doesn't rely on the server, it is more 1428 complex and harder to implement. It also could cause starvation for 1429 some clients if they keep failing to get their proposal accepted. 1431 9.3. Merging Updates 1433 When TreeKEM is in use, it is possible to partly address the problem 1434 of concurrent changes by having the recipients of the changes merge 1435 them, rather than having the senders retry. Because the value of 1436 intermediate node is determined by its last updated child (as opposed 1437 to both its children in ART), TreeKEM updates can be merged by 1438 recipients as long as the recipients agree on an order - the only 1439 question is which node was last updated. 1441 Recall that the processing of a TreeKEM update proceeds in two steps: 1443 1. Compute updated secret values by hashing up the tree 1445 2. Update the tree with the new secret and public values 1447 To merge an ordered list of updates, a recipient simply performs 1448 these updates in the specified order. 1450 For example, suppose we have a tree in the following configuration: 1452 H(H(D)) 1453 / \ 1454 H(B) H(D) 1455 / \ / \ 1456 A B C D 1458 Now suppose B and C simultaneously decide to update to X and Y, 1459 respectively. They will send out updates of the following form: 1461 Update from B Update from C 1462 ============= ============= 1463 H(H(X)) H(H(Y)) 1464 / \ 1465 H(X) H(Y) 1466 \ / 1467 X Y 1469 Assuming that the ordering agreed by the group says that B's update 1470 should be processed before C's, the other participants in the group 1471 will overwrite the root value for B with the root value from C, and 1472 all arrive at the following state: 1474 H(H(Y)) 1475 / \ 1476 H(X) H(Y) 1477 / \ / \ 1478 A X Y D 1480 10. Message Protection 1482 [[ OPEN ISSUE: This section has initial considerations about message 1483 protection. This issue clearly needs more specific recommendations, 1484 possibly a protocol specification in this document or a separate one. 1485 ]] 1487 The primary purpose of this protocol is to enable an authenticated 1488 group key exchange among participants. In order to protect messages 1489 sent among those participants, an application will need to specify 1490 how messages are protected. 1492 For every epoch, the root key of the ratcheting tree can be used to 1493 derive key material for symmetric operations such as encryption/AEAD 1494 and MAC; AEAD or MAC MUST be used to ensure that the message 1495 originated from a member of the group. 1497 In addition, asymmetric signatures SHOULD be used to authenticate the 1498 sender of a message. 1500 In combination with server-side enforced ordering, data from previous 1501 messages is used (as a salt when hashing) to: 1503 o add freshness to derived symmetric keys 1505 o cryptographically bind the transcript of all previous messages 1506 with the current group shared secret 1508 Possible candidates for that are: 1510 o the key used for the previous message (hash ratcheting) 1512 o the counter of the previous message (needs to be known to new 1513 members of the group) 1515 o the hash of the previous message (proof that other participants 1516 saw the same history) 1518 The requirement for this is that all participants know these values. 1519 If additional clear-text fields are attached to messages (like the 1520 counter), those fields MUST be protected by a signed message 1521 envelope. 1523 Alternatively, the hash of the previous message can also be included 1524 as an additional field rather than change the encryption key. This 1525 allows for a more flexible approach, because the receiving party can 1526 choose to ignore it (if the value is not known, or if transcript 1527 security is not required). 1529 11. Security Considerations 1531 The security goals of MLS are described in [[the architecture doc]]. 1532 We describe here how the protocol achieves its goals at a high level, 1533 though a complete security analysis is outside of the scope of this 1534 document. 1536 11.1. Confidentiality of the Group Secrets 1538 Group secrets are derived from (i) previous group secrets, and (ii) 1539 the root key of a ratcheting tree. Only group members know their 1540 leaf private key in the group, therefore, the root key of the group's 1541 ratcheting tree is secret and thus so are all values derived from it. 1543 Initial leaf keys are known only by their owner and the group 1544 creator, because they are derived from an authenticated key exchange 1545 protocol. Subsequent leaf keys are known only by their owner. 1546 [[TODO: or by someone who replaced them.]] 1547 Note that the long-term identity keys used by the protocol MUST be 1548 distributed by an "honest" authentication service for parties to 1549 authenticate their legitimate peers. 1551 11.2. Authentication 1553 There are two forms of authentication we consider. The first form 1554 considers authentication with respect to the group. That is, the 1555 group members can verify that a message originated from one of the 1556 members of the group. This is implicitly guaranteed by the secrecy 1557 of the shared key derived from the ratcheting trees: if all members 1558 of the group are honest, then the shared group key is only known to 1559 the group members. By using AEAD or appropriate MAC with this shared 1560 key, we can guarantee that a participant in the group (who knows the 1561 shared secret key) has sent a message. 1563 The second form considers authentication with respect to the sender, 1564 meaning the group members can verify that a message originated from a 1565 particular member of the group. This property is provided by digital 1566 signatures on the messages under identity keys. 1568 [[ OPEN ISSUE: Signatures under the identity keys, while simple, have 1569 the side-effect of preclude deniability. We may wish to allow other 1570 options, such as (ii) a key chained off of the identity key, or (iii) 1571 some other key obtained through a different manner, such as a 1572 pairwise channel that provides deniability for the message 1573 contents.]] 1575 11.3. Forward and post-compromise security 1577 Message encryption keys are derived via a hash ratchet, which 1578 provides a form of forward secrecy: learning a message key does not 1579 reveal previous message or root keys. Post-compromise security is 1580 provided by Update operations, in which a new root key is generated 1581 from the latest ratcheting tree. If the adversary cannot derive the 1582 updated root key after an Update operation, it cannot compute any 1583 derived secrets. 1585 11.4. Init Key Reuse 1587 Initialization keys are intended to be used only once and then 1588 deleted. Reuse of init keys is not believed to be inherently 1589 insecure [dhreuse], although it can complicate protocol analyses. 1591 12. IANA Considerations 1593 TODO: Registries for protocol parameters, e.g., ciphersuites 1595 13. Contributors 1597 o Benjamin Beurdouche 1598 INRIA 1599 benjamin.beurdouche@ens.fr 1601 o Karthikeyan Bhargavan 1602 INRIA 1603 karthikeyan.bhargavan@inria.fr 1605 o Cas Cremers 1606 University of Oxford 1607 cas.cremers@cs.ox.ac.uk 1609 o Alan Duric 1610 Wire 1611 alan@wire.com 1613 o Srinivas Inguva 1614 Twitter 1615 singuva@twitter.com 1617 o Albert Kwon 1618 MIT 1619 kwonal@mit.edu 1621 o Eric Rescorla 1622 Mozilla 1623 ekr@rtfm.com 1625 o Thyla van der Merwe 1626 Royal Holloway, University of London 1627 thyla.van.der@merwe.tech 1629 14. References 1631 14.1. Normative References 1633 [I-D.ietf-tls-tls13] 1634 Rescorla, E., "The Transport Layer Security (TLS) Protocol 1635 Version 1.3", draft-ietf-tls-tls13-28 (work in progress), 1636 March 2018. 1638 [IEEE1363] 1639 "IEEE Standard Specifications for Password-Based Public- 1640 Key Cryptographic Techniques", IEEE standard, 1641 DOI 10.1109/ieeestd.2009.4773330, n.d.. 1643 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1644 Requirement Levels", BCP 14, RFC 2119, 1645 DOI 10.17487/RFC2119, March 1997, 1646 . 1648 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 1649 Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008, 1650 . 1652 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1653 Key Derivation Function (HKDF)", RFC 5869, 1654 DOI 10.17487/RFC5869, May 2010, 1655 . 1657 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1658 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1659 2016, . 1661 [X962] ANSI, "Public Key Cryptography For The Financial Services 1662 Industry: The Elliptic Curve Digital Signature Algorithm 1663 (ECDSA)", ANSI X9.62, 1998. 1665 14.2. Informative References 1667 [art] Cohn-Gordon, K., Cremers, C., Garratt, L., Millican, J., 1668 and K. Milner, "On Ends-to-Ends Encryption: Asynchronous 1669 Group Messaging with Strong Security Guarantees", January 1670 2018, . 1672 [dhreuse] Menezes, A. and B. Ustaoglu, "On reusing ephemeral keys in 1673 Diffie-Hellman key agreement protocols", International 1674 Journal of Applied Cryptography Vol. 2, pp. 154, 1675 DOI 10.1504/ijact.2010.038308, 2010. 1677 [doubleratchet] 1678 Cohn-Gordon, K., Cremers, C., Dowling, B., Garratt, L., 1679 and D. Stebila, "A Formal Security Analysis of the Signal 1680 Messaging Protocol", 2017 IEEE European Symposium on 1681 Security and Privacy (EuroS&P), 1682 DOI 10.1109/eurosp.2017.27, April 2017. 1684 [I-D.ietf-trans-rfc6962-bis] 1685 Laurie, B., Langley, A., Kasper, E., Messeri, E., and R. 1686 Stradling, "Certificate Transparency Version 2.0", draft- 1687 ietf-trans-rfc6962-bis-28 (work in progress), March 2018. 1689 [keyagreement] 1690 Barker, E., Chen, L., Roginsky, A., and M. Smid, 1691 "Recommendation for Pair-Wise Key Establishment Schemes 1692 Using Discrete Logarithm Cryptography", National Institute 1693 of Standards and Technology report, 1694 DOI 10.6028/nist.sp.800-56ar2, May 2013. 1696 [signal] Perrin(ed), T. and M. Marlinspike, "The Double Ratchet 1697 Algorithm", n.d., 1698 . 1701 Authors' Addresses 1703 Richard Barnes 1704 Cisco 1706 Email: rlb@ipv.sx 1708 Jon Millican 1709 Facebook 1711 Email: jmillican@fb.com 1713 Emad Omara 1714 Google 1716 Email: emadomara@google.com 1718 Katriel Cohn-Gordon 1719 University of Oxford 1721 Email: me@katriel.co.uk 1723 Raphael Robert 1724 Wire 1726 Email: raphael@wire.com