Internet-Draft MLS Subgroups March 2025
McMillion Expires 7 September 2025 [Page]
Workgroup:
Messaging Layer Security
Internet-Draft:
draft-mcmillion-mls-subgroups-latest
Published:
Intended Status:
Informational
Expires:
Author:
B. McMillion

MLS Subgroups

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/.

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 7 September 2025.

▲

Table of Contents

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 ensure that all of the user's devices are added and removed from groups 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 has negative privacy implications for users, since group members can see which device a user sent a given message from and whenever any user changes their set of authorized devices.

This document describes how to synchronize the behavior of a user's devices such that other users of the messaging service only see the user as a single MLS client. It does this by relying on an MLS group called a subgroup, of which only the user's authorized devices are a member, to produce shared secrets from which private keys and other secrets for a single MLS virtual client can be deterministically generated. Deterministic generation allows all of the user's devices to participate equally in the operation of the virtual client.

This is done in a way that preserves the Forward Secrecy and Post-Compromise Security of the groups that virtual clients join. Secrets for virtual clients are generated such that they can be deleted once they are no longer needed. Secrets for virtual clients are also rotated regularly, corresponding to changes in the subgroup's membership, meaning that once a device is removed from a subgroup it also loses access to the virtual client's secret state.

Importantly, virtual clients work without changing the wire format of MLS. This allows one set of clients (for example, in a federated environment) to unilaterally choose to use virtual clients for privacy or operational reasons, and still operate seamlessly with non-virtual clients from other operators.

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.

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. To allow this, 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

Virtual clients use a Secret Tree similar to [RFC9420] to generate forward-secure shared secrets. 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

  • 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 once the exporter_secret for the epoch has also been deleted. Virtual clients MUST ensure that exporter_secret is deleted as soon as possible.

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 in big endian byte order, 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:

struct {
  uint64 epoch;
  uint32 leaf_index;
  uint32 random;
} PrivateKeyInfo;

opaque subgroup<V>;

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, this can create a situation where encryption keys and nonces are reused inappropriately. Critically, 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, as described below.

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

MLS clients typically generate the bytes for the reuse_guard randomly. Virtual clients, however, 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(leaf_node_secret, "reuse guard", key_schedule_nonce, 16)
reuse_guard = SmallSpacePRP.Encrypt(prp_key, x)

ExpandWithLabel is computed with the subgroup ciphersuite's algorithms. leaf_node_secret is the secret corresponding to the virtual client's LeafNode in the supergroup and key_schedule_nonce is the nonce provided by the key schedule for encrypting this message.

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.

4.3. Delivery Service

The method discussed above for computing reuse_guard prevents the devices in a subgroup from ever reusing the same key-nonce pair, as this would compromise the message. However, it does not prevent multiple devices from attempting to encrypt messages with the same key but different nonces. While this doesn't create any security issues, it is a functionality issue due to the MLS deletion schedule. Other group members will delete the encryption key after using it to decrypt the first message they receive and will be unable to decrypt subsequent messages.

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 need to simply retain messages and encryption keys for a short period of time after sending, in case it becomes necessary to decrypt another device's message and re-encrypt and re-send their original message with another encryption key.

Note that, in both cases, it's assumed that when a message is sent by a virtual client, all devices associated with the virtual client (except possibly the sending device) receive the message back from the DS. This may require a change in the implementation of the DS.

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.

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<V>;

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<V>;
  }
} SecretTreeNode;

struct {
  uint64 epoch;
  SecretTreeNode root;
} EpochSecretTree;

struct {
  KeyPackageRef ref;
  opaque init_secret<V>;
  opaque leaf_secret<V>;
} KeyPackageKey;

struct {
  opaque signature_private_key<V>;
  opaque subgroup_extension_key<V>;
  EpochSecretTree secret_trees<V>;
  KeyPackageKey key_package_keys<V>;
  MLSState group_states<V>;
} 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 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<V>;
  opaque subgroup_extension_key<V>;
} 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.

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

Table 1
Value Name Message(s) R Ref
0x0006 subgroup LN, KP - RFC XXXX
0x0007 new_device_state GI - RFC XXXX

8.2. MLS Exporter Labels

Table 2
Label Recommended Reference
"Subgroup Secret Tree" - RFC XXXX

9. References

9.1. Normative References

[NIST]
Dworkin, M., "Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption", n.d., <https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-38G.pdf>.
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/rfc/rfc2119>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/rfc/rfc8174>.
[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, , <https://www.rfc-editor.org/rfc/rfc9420>.

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-15, , <https://datatracker.ietf.org/doc/html/draft-ietf-mls-architecture-15>.

Acknowledgments

TODO acknowledge.

Author's Address

Brendan McMillion