Messaging Layer Security B. McMillion Internet-Draft 20 March 2024 Intended status: Informational Expires: 21 September 2024 MLS Subgroups draft-mcmillion-mls-subgroups-00 Abstract This document describes how the user of an MLS-based messaging service can synchronize the operation of its devices, such that they behave as a single virtual MLS client. This prevents other users of the messaging service from being able to tell when a user changes its set of authorized devices, or which device the user sent a message from. About This Document This note is to be removed before publishing as an RFC. The latest revision of this draft can be found at https://Bren2010.github.io/draft-subgroups/draft-mcmillion-mls- subgroups.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-mcmillion-mls-subgroups/. Discussion of this document takes place on the Messaging Layer Security Working Group mailing list (mailto:mls@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/mls/. Subscribe at https://www.ietf.org/mailman/listinfo/mls/. Source for this draft and an issue tracker can be found at https://github.com/Bren2010/draft-subgroups. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. McMillion Expires 21 September 2024 [Page 1] Internet-Draft MLS Subgroups March 2024 Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 21 September 2024. Copyright Notice Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 3. Generation of Private Keys . . . . . . . . . . . . . . . . . 4 3.1. Secret Tree . . . . . . . . . . . . . . . . . . . . . . . 4 3.2. Private Keys . . . . . . . . . . . . . . . . . . . . . . 5 3.3. Subgroup Extension . . . . . . . . . . . . . . . . . . . 5 4. Application Messages . . . . . . . . . . . . . . . . . . . . 6 4.1. Small-Space PRP . . . . . . . . . . . . . . . . . . . . . 7 4.2. Reuse Guard . . . . . . . . . . . . . . . . . . . . . . . 7 5. Adding New Devices . . . . . . . . . . . . . . . . . . . . . 7 5.1. Synchronizing from Another Device . . . . . . . . . . . . 8 5.2. Joining Externally . . . . . . . . . . . . . . . . . . . 9 6. Aligning Security of Groups . . . . . . . . . . . . . . . . . 10 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 8.1. MLS Extension Types . . . . . . . . . . . . . . . . . . . 10 8.2. MLS Exporter Labels . . . . . . . . . . . . . . . . . . . 10 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 9.1. Normative References . . . . . . . . . . . . . . . . . . 11 9.2. Informative References . . . . . . . . . . . . . . . . . 11 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 11 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 11 McMillion Expires 21 September 2024 [Page 2] Internet-Draft MLS Subgroups March 2024 1. Introduction MLS allows users to communicate in an end-to-end encrypted fashion but doesn't describe how to synchronize the operation of a user's devices. Instead, applications are generally expected to create distinct MLS clients for each device that a user has, and to ensure that all of the user's devices are added or removed from a group atomically. This creates some technical difficulties, as it can be hard for other members to ensure that the group truly stays in-sync with each user's set of authorized devices. It also creates a privacy issue because the members of a group can see which device a user sent a given message from, or when any user changes its set of authorized devices. This document describes how to use an MLS group between all of a user's authorized devices to synchronize behavior, such that other users of the messaging service only see the user as a single MLS client. It does this in a way that preserves the Forward Secrecy and Post-Compromise Security guarantees of the groups that the user participates in, without requiring changes to the wire format of MLS. 2. Conventions and Definitions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. Device: A user interface for messaging, performing encryption as needed. User: A (normally) human operator of a device. Users may have many devices, but a device only belongs to one user. Subgroup: An MLS group whose membership is exactly the set of authorized devices of a single user. Virtual Client: An MLS client that is controlled by one of many devices and synchronized by a subgroup. Supergroup: Refers to any MLS group which is not a subgroup. McMillion Expires 21 September 2024 [Page 3] Internet-Draft MLS Subgroups March 2024 3. Generation of Private Keys When devices generate new asymmetric keypairs for a virtual client (such as a KeyPackage init_key or LeafNode encryption_key), they must do so in a way that the other devices participating in the subgroup can compute the private key as well. In the Subgroups protocol, a virtual client's private keys are derived deterministically from a secret exported from the most recent epoch in a subgroup. An extension is added to KeyPackages and LeafNodes generated this way to communicate to the other devices, which may not become aware of the keypair for several epochs, the epoch the private key was generated from. Note that signature private keys are not generated this way. A virtual client's signature private key is generated once and shared directly with new devices. 3.1. Secret Tree The Subgroups protocol uses a Secret Tree similar to [RFC9420]. The root of the Secret Tree is an exported secret from a given epoch of a subgroup: subgroup_secret_tree_root = MLS-Exporter("Subgroup Secret Tree", "", KDF.Nh) The left and right child of a node in the Secret Tree are computed as follows: tree_node_[N]_secret | | +--> ExpandWithLabel(., "tree", "left", KDF.Nh) | = tree_node_[left(N)]_secret | +--> ExpandWithLabel(., "tree", "right", KDF.Nh) = tree_node_[right(N)]_secret The Secret Tree maps bit strings to a value of size KDF.Nh. The root, subgroup_secret_tree_root, is the value associated with the empty bit string. Its left child is the value associated with the bit string "0", while its right child is the value associated with the bit string "1", and so on recursively. Devices follow a strict deletion schedule, and delete any node as soon as: * its left and right children have been computed, or McMillion Expires 21 September 2024 [Page 4] Internet-Draft MLS Subgroups March 2024 * a private key has been derived from the node. This ensures that any private keys that are derived from the Secret Tree can be deleted and won't be able to be re-derived, providing Forward Secrecy. 3.2. Private Keys Devices will need to generate either an init_key for a KeyPackage, or an encryption_key for a LeafNode. To do this, the device finds its leaf index in the subgroup leaf_index, chooses a 32-bit number random, converts both to a series of bits, and concatenates them to get a series of 64 bits: leaf_index || random. This series of bits is used to lookup a node in the Secret Tree, tree_node_secret. For a KeyPackage init_key, the device computes: init_secret = DeriveSecret(tree_node_secret, "Subgroup KeyPackage") init_priv, init_pub = KEM.DeriveKeyPair(init_secret) For a LeafNode encryption_key, the device computes: leaf_secret = DeriveSecret(tree_node_secret, "Subgroup LeafNode") leaf_node_secret = DeriveSecret(leaf_secret, "node") leaf_priv, leaf_pub = KEM.DeriveKeyPair(leaf_node_secret) If the LeafNode is part of a Commit message, the device also computes path_secret[0] from leaf_secret: path_secret[0] = DeriveSecret(leaf_secret, "path") Individual devices MUST take care to avoid reusing random values. Note that the Secret Tree nodes are computed with the subgroup ciphersuite's algorithms, but init_secret and leaf_secret are computed with the supergroup ciphersuite's algorithms. 3.3. Subgroup Extension As mentioned, devices may not always be immediately aware of when another device has generated a private key. This means that devices need a way to communicate to each other the information they used to derive a private key. The subgroup extension in a KeyPackage or LeafNode provides this information: McMillion Expires 21 September 2024 [Page 5] Internet-Draft MLS Subgroups March 2024 struct { uint64 epoch; uint32 leaf_index; uint32 random; } PrivateKeyInfo; opaque subgroup; The extension is a byte string containing a PrivateKeyInfo struct, which has been encrypted with the AEAD from the subgroup's ciphersuite: nonce is sampled at random subgroup = nonce || AEAD.Seal(key, nonce, "", PrivateKeyInfo) The epoch field is the epoch of the subgroup that was used, leaf_index is the index of the device's leaf in the subgroup, and random is the random value chosen by the device during generation. The key used for encryption is fixed long-term and shared among the devices in a subgroup. 4. Application Messages Given that MLS generates the encryption keys and nonces for application and handshake messages sequentially, but a virtual client may send messages from several devices simultaneously, devices must take care to avoid reusing encryption keys and nonces. If two devices encrypt a message with the same key simultaneously, they may have already deleted the relevant encryption key by the time they receive the other device's message, which will cause a decryption failure. This is a functional issue, and the best solution depends on whether the Delivery Service is strongly or eventually consistent [I-D.ietf-mls-architecture]. Devices communicating with a strongly consistent DS can prevent this issue by checking that they have processed all the messages sent to a group before sending their own message. Alternatively, devices communicating with an eventually consistent DS may simply need to retain encryption keys for a short period of time after use in case they are still necessary. However, if two devices encrypt a message with both the same key and nonce simultaneously, this could compromise the message's confidentiality and integrity. Devices prevent this by ensuring two devices in a subgroup never choose the same reuse_guard. McMillion Expires 21 September 2024 [Page 6] Internet-Draft MLS Subgroups March 2024 4.1. Small-Space PRP A small-space pseudorandom permutation (PRP) is a cryptographic algorithm that works similar to a block cipher, while also being able to adhere to format constraints. In particular, it is able to perform a psuedorandom permutation over an arbitrary input and output space. This document uses the FF1 mode from [NIST] with the input-output space of 32-bit integers, instantiated with AES-128. output = SmallSpacePRP.Encrypt(key, input) input = SmallSpacePRP.Decrypt(key, output) 4.2. Reuse Guard In the unmodified MLS protocol, the reuse_guard is chosen randomly. In the Subgroups protocol, devices choose a random value x such that x modulo the number of leaves in the subgroup is equal to its leaf_index. They then calculate: prp_key = ExpandWithLabel(key_schedule_nonce, "reuse guard", leaf_secret, 16) reuse_guard = SmallSpacePRP.Encrypt(prp_key, x) ExpandWithLabel is computed with the subgroup ciphersuite's algorithms. key_schedule_nonce is the nonce provided by the key schedule for encrypting this message, and leaf_secret is the secret corresponding to the virtual client's LeafNode in the supergroup. prp_key is computed in a way that it is unique to the key-nonce pair and computable by all the devices in a subgroup (but nobody else). reuse_guard is computed in a way that it appears random to outside observers (in particular, it does not leak which device sent the message), but two devices will never generate the same value. 5. Adding New Devices When a user adds a new authorized device to their account, there are several pieces of cryptographic state that need to be synchronized before the device can start sending and receiving messages. The device can either get this state from another one of the user's devices, or if all of the user's other devices are offline, the device can use a series of external joins to prepare itself. McMillion Expires 21 September 2024 [Page 7] Internet-Draft MLS Subgroups March 2024 5.1. Synchronizing from Another Device If the new device is being added by another online device, this device sends a Welcome message to the new device, adding the new device to the subgroup, that contains a new_device_state extension in the GroupInfo: opaque MLSState; enum { reserved(0), empty(1), present(2), } SecretTreeNodeType; struct { SecretTreeNodeType node_type; select(SecretTreeNode.node_type) { case empty: SecretTreeNode left; SecretTreeNode right; case present: opaque value; } } SecretTreeNode; struct { uint64 epoch; SecretTreeNode root; } EpochSecretTree; struct { KeyPackageRef ref; opaque init_secret; opaque leaf_secret; } KeyPackageKey; struct { opaque signature_private_key; opaque subgroup_extension_key; EpochSecretTree secret_trees; KeyPackageKey key_package_keys; MLSState group_states; } NewDeviceState; The signature_private_key contains the serialized signature private key of the virtual client. Every device and virtual client SHOULD have distinct signature keys. The subgroup_extension_key is the McMillion Expires 21 September 2024 [Page 8] Internet-Draft MLS Subgroups March 2024 encryption key for the subgroup extension (Section 3.3). The secret_trees array contains the serialized Secret Trees for any epochs where they may still be necessary. The key_package_keys array contains the init_secret and leaf_secret for any KeyPackages that are still unused but have been purged from the Secret Tree. And finally, the group_states array contains the cryptographic states of all the groups that the virtual client is a member of, serialized in an application-specific way. 5.2. Joining Externally Without another online device to bootstrap from, the new device can follow these steps to join externally: 1. Issue a credential for the virtual client with a new signature key and generate a new subgroup extension key. 2. Perform an External Join to the subgroup. Send an application message containing a ResyncMessage to the subgroup with the new keys. 3. Replace all unused KeyPackages with new KeyPackages, generated from the new subgroup epoch. 4. Perform an External Join to all of the groups that the virtual client is a member of, using LeafNodes generated from the new subgroup epoch. Welcome messages which were unprocessed by the offline devices are discarded, and these groups are Externally Joined instead (potentially being queued for user approval first). struct { opaque signature_private_key; opaque subgroup_extension_key; } ResyncMessage; Note that this involves changing the subgroup extension key. Devices that were in the subgroup before the new device joined externally can determine whether to use the new or old subgroup extension key by checking whether the new or old credential is in the relevant LeafNode. Also note that the new device learns the set of groups that the virtual client is a member of, including groups corresponding to unprocessed Welcome messages, from the Delivery Service, which has access to this information as part of supporting External Joins. McMillion Expires 21 September 2024 [Page 9] Internet-Draft MLS Subgroups March 2024 6. Aligning Security of Groups Subgroups deprive supergroup members of visibility into whether key rotation is happening on a regular basis, and the extent to which compromised devices may have access to group secrets. As such, subgroups need to enforce policies that manage this concern. A subgroup MUST have either the same or a stronger policy on how frequently devices must update their leaf node, than the groups that the virtual client is a member of. Any time that a device is removed from a subgroup, an Update (or Commit with path populated) MUST be sent to all groups that the virtual client is a member of. 7. Security Considerations TODO Security 8. IANA Considerations This document defines two new MLS Extension Types, and a new MLS Exporter Label. 8.1. MLS Extension Types +========+==================+============+===+==========+ | Value | Name | Message(s) | R | Ref | +========+==================+============+===+==========+ | 0x0006 | subgroup | LN, KP | - | RFC XXXX | +--------+------------------+------------+---+----------+ | 0x0007 | new_device_state | GI | - | RFC XXXX | +--------+------------------+------------+---+----------+ Table 1 8.2. MLS Exporter Labels +========================+=============+===========+ | Label | Recommended | Reference | +========================+=============+===========+ | "Subgroup Secret Tree" | - | RFC XXXX | +------------------------+-------------+-----------+ Table 2 9. References McMillion Expires 21 September 2024 [Page 10] Internet-Draft MLS Subgroups March 2024 9.1. Normative References [NIST] Dworkin, M., "Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption", n.d., . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [RFC9420] Barnes, R., Beurdouche, B., Robert, R., Millican, J., Omara, E., and K. Cohn-Gordon, "The Messaging Layer Security (MLS) Protocol", RFC 9420, DOI 10.17487/RFC9420, July 2023, . 9.2. Informative References [I-D.ietf-mls-architecture] Beurdouche, B., Rescorla, E., Omara, E., Inguva, S., and A. Duric, "The Messaging Layer Security (MLS) Architecture", Work in Progress, Internet-Draft, draft- ietf-mls-architecture-12, 3 March 2024, . Acknowledgments TODO acknowledge. Author's Address Brendan McMillion Email: brendanmcmillion@gmail.com McMillion Expires 21 September 2024 [Page 11]