Internet-Draft Light MLS October 2024
Kiefer, et al. Expires 24 April 2025 [Page]
Workgroup:
Network Working Group
Internet-Draft:
draft-kiefer-mls-light-01
Published:
Intended Status:
Informational
Expires:
Authors:
F. Kiefer
Cryspen
K. Bhargavan
Cryspen
R. L. Barnes
Cisco
J. Alwen
AWS Wickr
M. Mularczyk
AWS Wickr

Light MLS

Abstract

The Messaging Layer Security (MLS) protocol provides efficient asynchronous group key establishment for large groups with up to thousands of clients. In MLS, any member can commit a change to the group, and consequently, all members must download, validate, and maintain the full group state which can incur a significant communication and computational costs, especially when joining a group. This document defines an MLS extension to support "light clients" that don't undertake these costs. A light client cannot commit changes to the group, and only has partial authentication information for the other members of the group, but is otherwise able to participate in the group. In exchange for these limitations, a light client can participate in an MLS group with significantly lower requirements in terms of download, memory, and processing.

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://example.com/LATEST. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-kiefer-mls-light/.

Discussion of this document takes place on the WG Working Group mailing list (mailto:WG@example.com), which is archived at https://example.com/WG.

Source for this draft and an issue tracker can be found at https://github.com/USER/REPO.

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 24 April 2025.

Table of Contents

1. Introduction

The Messaging Layer Security protocol [RFC9420] enables continuous group authenticated key exchange among a group of clients. The design of MLS requires all members to download, validate, and maintain the full MLS tree, including validating the credentials and signatures of all members. The size of the MLS tree is linear in the size of the group. Consequently, the MLS design results in a performance bottleneck for new members seeking to join a large group, and significant storage and memory requirements once the member has joined.

This document defines an extension to MLS to allow for "light clients" -- clients that do not download, validate, or maintain the entire ratchet tree for the group. On the one hand, this "lightness" allows a light client to participate in the group with much significantly lower communication and computation complexity. On the other hand, without the full ratchet tree, the light client cannot create Commit messages to put changes to the group into effect. Light clients also only have authentication information for the parts of the tree they download, not the whole group.

This document does not change the core logic of MLS, including: The structure of the ratchet tree and its associated algorithms, the key schedule, the secret tree, and application message protection. The messages sent and received by normal clients in the course of an MLS session are likewise unchanged. With proper modifications to the MLS Delivery Service, standard MLS clients can participate in a group with light client without any modification.

The only modifications this document makes are to the local state stored at light clients, namely the component of MLS that manages, synchronizes, and authenticates the public group state. We also defines some "annotations" that need to be appended to group messages so that they can be processed by light clients. Light clients effectively run normal MLS algorithms, but with just-in-time delivery of exactly the subset of the public group state needed by a given algorithm. We achieve lightness due to the fact that aside from initial tree validation and sending commits, a client only needs log-scale information.

2. Terminology

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.

Tree slice:

A tree slice is the direct path from a leaf node to the root, together with the tree hashes on the co-path.

Membership proof:

A tree slice that proves that a given leaf node is part of a ratchet tree with a given tree hash.

Light client:

An MLS client that does not download, validate, and maintain a copy of the group's ratchet tree. A light client does not store any public data about the group's ratchet tree, only the HPKE decryption keys associated to nodes on the client's direct path.

Full client:

A normal MLS client, in possession of the full MLS ratchet tree for the group.

Sender-authenticated message:

A signed MLS message such as Welcome or PublicMessage, together with a membership proof that proves the sender's membership in the group.

Annotated Welcome:

A Welcome message together with information that a light client needs to process it.

Annotated Commit:

A Commit message (as a PublicMessage or PrivateMessage) together with information that a light client needs to process it.

As in MLS, message structures are defined using the TLS presentation syntax [RFC8446]. Unlike most MLS messages, however, these structures are not encapsulated in a signed or MAC'ed structure. So it may be more convenient for applications to encode these structures in application-specific encodings.

3. Protocol Overview

A light client does not receive or validate a full copy of the ratchet tree for a group, but still possesses the group's secrets, including receiving updated secrets as the group evolves. When MLS messages are sent to a light client, they need dto be accompanied by annotations that provide the light client with just enough of information about the ratchet tree to process the message. These annotations can be computed by any party with knowledge of the group's ratchet tree, including the committer and sometimes the DS.

Full Delivery Light Light Full Client A Service Client B Client C Client D Commit Welcome AnnotatedWelcome = Welcome + Proofs AnnotatedCommit = Commit + Proofs + Resolution Info Commit PrivateMessage PrivateMessage SenderAuthMessage = PrivateMessage + Proof(D) Proof(C)
Figure 1: Overview of Light MLS

Figure 1 illustrates the three main changes introduced by Light MLS:

  1. When a light client is added to the group, they are provided an AnnotatedWelcome message, which comprises a normal Welcome message plus membership proofs for the sender and joiner.

  2. From each Commit that is generated in the group, an individual AnnotatedCommit is generated for each light client. An AnntatedCommit comprises a normal MLS Commit message, together with membership proofs and the information that the light client needs in order to process the update path in the Commit.

  3. When messages are sent in the group, e.g., carrying application data, they are extended with a membership proofs so that light clients can authenticate the sender's membership in the group.

  4. Light clients can download membership proofs to authenticate individual other users. Here B authenticates C.

In this example, we have shown the required annotations being added by the DS. This allows full clients to behave as they would in normal MLS, but requires that the DS maintain a copy of the group's ratchet tree. It is also possible for committers to generate the required annotated messages. This document does not define who generates annotated messages from the base MLS messages, or how this entity learns which clients are light or full clients.

Light clients still need to be provided with access to any proposals sent in a group outside of Commits. Light clients cannot process proposals that modify the structure of the tree, in particular Add, Update, or Remove proposals. They can, however, verify that these proposals were included in a given Commit. And they need to see proposals such as PreSharedKey or GroupContextExtensions so that they can update their state appropriately.

Depending on how light MLS is deployed, a client might need to inform the DS or other members of its status (light or full), so that the proper annotations can be generated when it is light. It is harmless for a full client to receive an AnnotatedCommit; the annotations can simply be ignored.

4. Upgrading and Downgrading

A light client can upgrade to being a full client at any time by downloading the full ratchet tree; a full client can downgrade by deleting its local copy of the ratchet tree. Before a light client uses a copy of the ratchet tree to upgrade ot being a full client, it MUST verify the integrity of the ratchet tree in the same way it would when joining as a full client, following the steps in Section 12.4.3.1 of [RFC9420].

5. Membership Proofs and Partial Trees

Although light clients do not have a copy of the group's ratchet tree, they still agree on the root tree hash of the ratchet tree, via the MLS key schedule as usual. This fact, together with the Merkle-tree-like structure of the MLS tree hash, allows a light client to verify the legitimacy of partial information about the ratchet tree. In particular, for any leaf in the tree, anyone in possession of the public data of the ratchet tree can construct a "membership proof" that proves that a leaf node with specific contents is located at a specific leaf index in the tree.

A membership proof for a leaf node comprises:

struct {
    opaque hash_value;
} CopathHash;

struct {
  uint32 leaf_index;
  uint32 n_leaves;
  optional<Node> direct_path_nodes<V>;
  CopathHash copath_hashes<V>;
} MembershipProof;

From these values, the root tree hash of the ratchet tree can be recomputed, following the same recursive algorithm specified in Section 7.8 of [RFC9420]. The selection of nodes and subtree hashes provides the precise collection of inputs required by the algorithm.

A membership proof is said to be valid relative to a given tree hash if the tree hash recomputed in this way is equal to the given tree hash.

Two membership proofs are said to reference the same tree if their n_leaves fields are equal, and they produce identical root tree hashes.

6. Sender-Authenticated Messages

For several types of message, MLS authenticates that a message was created by the member at a specific leaf node of the group's ratchet tree by signing the message with the private key corresponding to the signature_key in the leaf node. Full clients verify these messages by looking up the required signature verification key in their local copy of the ratchet tree.

Since light clients do not store the group's ratchet tree, they cannot perform this lookup. A SenderAuthenticatedMessage presents a message along with a membership proof for the sender of a message, which provides the required leaf node and a proof of its inclusion in the tree.

struct {
    T message;
    MembershipProof sender_membership_proof;
} SenderAuthenticatedMessage;

Before using the sender_membership_proof to verify the included message, a client processing a SenderAuthenticatedMessage MUST verify that the proof is valid relative to the group's tree hash for the epoch in which the message was sent. For a PublicMessage or PrivateMessage, this is the tree hash for the epoch indicated in the FramedContent. For a GroupInfo or Welcome, it is the tree hash in the object itself.

7. Joining via Annotated Welcome

An AnnotatedWelcome message provides a client joining a group with membership proofs for the sender and the joiner (i.e., the recipient of the message).

struct {
    SenderAuthenticated<Welcome> welcome;
    MembershipProof joiner_membership_proof;
} AnnotatedWelcome;

The fields in the AnnotatedWelcome have the following semantics:

welcome:

A MLSMessage containing PrivateMessage or PublicMessage with content_type commit, together with a membership proof for the sender.

joiner_membership_proof:

A proof of the receipient's membership in the ratchet tree specified in the Welcome.

An AnnotatedWelcome can be generated by any party that knows the group's ratchet tree and the indices of the sender and joiner in the tree.

A light client processes an AnnotatedWelcome in the following way:

  1. Verify that the sender_membership_proof and joiner_membership_proof reference the same tree.

  2. Join the group using the procedure defined in Section 12.4.3.1 of [RFC9420], with the following modifications:

    • When verifying the signature on the GroupInfo object, the signature public key is taken from the LeafNode in the sender_membership_proof tree slice. The signer field of the group_info object MUST be equal to the leaf_index field of the sender_membership_proof.

    • The "Verify the integrity of the ratchet tree" step is replaced with a check that the tree_hash in the GroupInfo matches the root tree hash produced by the membership proofs.

    • The my_leaf value is taken from the the leaf_index field of the joiner_membership_proof, instead of found by searching the tree.

8. Joining via External Commit

A light client cannot join via an external Commit, because light clients cannot generate commits. A client could, however, join as a full client via an external commit, then transition to being a light client by deleting its copy of the tree. This would still require the client to download and validate the tree, but would save the client the effort of maintaining their copy of the tree.

9. Annotated Commit

There are two main challenges for a light client processing a Commit. First, the light client cannot compute the resolution of the committer's copath, so they cannot determine which of the HPKECiphertext objects in the UpdatePath they should decrypt to obtain a path secret. Second, the light client cannot compute the updated tree hash, since they don't have the full tree. An AnnotatedCommit provides these pieces of information, along with proof that the sender and receiver are both still in the group after the Commit.

struct {
    MLSMessage commit;
    optional<MembershipProof> sender_membership_proof;

    opaque tree_hash_after<V>;
    optional<uint32> resolution_index;

    MembershipProof sender_membership_proof_after;
    MembershipProof receiver_membership_proof_after;
} AnnotatedCommit;

The fields in the AnnotatedCommit have the following semantics:

commit:

An MLSMessage containing PrivateMessage or PublicMessage with content_type commit, together with a membership proof for the sender.

sender_membership_proof:

A membership proof for the sender of the Commit relative to the tree for the epoch in which the Commit is sent. This field MUST be present if the sender_type for the Commit is member, and otherwise MUST be absent.

tree_hash_after:

The tree hash of the group's ratchet tree after the Commit has been applied.

resolution_index:

The recipient can compute which entry in the UpdatePath in the Commit it should use based on the sender index in the Commit. This index specifies which HPKECiphertext in the UpdatePathNode to use. This field MUST be included if and only if the Commit has a path field populated.

sender_membership_proof_after:

A membership proof for the sender of the Commit relative to the tree after the Commit has been applied.

receiver_membership_proof_after:

A membership proof for the receiver of the Commit relative to the tree after the Commit has been applied.

An AnnotatedCommit can be generated by any party that knows the group's ratchet tree (both before and after the Commit) and the indices of the sender and joiner in the tree. It is safe for the recipient to accept the tree_hash supplied by an unauthenticated party because the tree hash is authenticated by the confirmation_tag in the Commit.

A light client processes an AnnotatedCommit in the following way:

  1. Verify that the sender_membership_proof in the commit field is valid relative to the group's current tree hash.

  2. Verify that the sender_membership_proof_after and receiver_membership_proof_after reference the same tree, and that they are valid relative to tree_hash_after.

  3. Process the Commit using the procedure defined in Section 12.4.2 of [RFC9420], with the following modifications:

10. Application Messages

MLS clients can exchange messages by sending application data within the PrivateMessage framing. In a group where light clients are present, these messages should be further encapsulated in a SenderAuthenticatedMessage, so that light clients have the membership proof necessary to verify the sender's membership, the public key necessary to verify the message signature, and the credential necessary to verify the sender's identity.

As noted above, this can be accomplished either by the sender creating a SenderAuthenticatedMessage, or by the DS adding the relevant membership proof while the message is in transit.

11. Operational Considerations

The major operational challenge in deploying Light MLS is ensuring that light clients receive the proper annotations to Welcome and Commit messages. As discussed in Section 3, this is up to the application. Since full clients don't need the annotations, applications will be more robust if they send annotations in a way that they can be cleanly ignored by full clients.

Light MLS substantially reduces the amount of data required to join an MLS group, since it replaces the linear-scale ratchet tree with two log-scale membership proofs. Light MLS does not address the potentially linear scaling of Commit messages; in fact, it makes Commits slightly bigger. There are other approaches to reducing Commit sizes, e.g., the SplitCommit approach in [I-D.mularczyk-mls-splitmls]. These approaches can be cleanly integrated with Light MLS via the AnnotatedCommit structure. Table 1 summarizes the scaling of the amount of data that a client needs to download in order to perform various MLS operations.

Table 1: Download scaling under protocol variations
Operation RFC MLS Light MLS Split Commits Light + Split
Join O(N) O(log N) O(N) O(log N)
Process Commit O(N) O(N) O(log N) O(log N)

12. Security Consideratiosn

The MLS protocol in [RFC9420] has a number of security analyses attached. To describe the security of light MLS and how it relates to the security of full MLS we summarize the following main high-level guarantees of MLS as follows:

As a corollary of Group Key Secrecy, we also obtain authentication and confidentiality guarantees for application messages sent and received within a group.

To verify the security guarantees provided by light clients, a new security analysis was needed. We have analyzed the security of the protocol using two verification tools ProVerif and F*. The security analysis, and design of the security mechanisms, are inspired by work from Alwen et al. [AHKM22].

Light MLS preserves the invariants above and thereby all the security goals of MLS continue to hold at full members. However, a light member may not know the identities of all other members in the group, and it may only discover these identities on-demand. Consequently, the Member Identity Authentication guarantee is weaker on light clients. Furthermore, since light members do not store the MLS tree, membership agreement only holds for the hash of the MLS tree:

Another technical caveat is that since light members do not have the full tree, they cannot validate the uniqueness of all HPKE and signature keys in the tree, as required by RFC MLS. The exact security implications of removing this uniqueness check is not clear but is not expected to be significant.

13. IANA Considerations

This document makes no request of IANA.

[[ NOTE: We could registere new WireFormat values for AnnotatedCommit and AnnotatedWelcome. It's not clear that this is necessary or useful, though, since the annotations are basically outside the MLS envelope. ]]

14. References

14.1. Normative References

[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>.
[RFC8446]
Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, , <https://www.rfc-editor.org/rfc/rfc8446>.
[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>.

14.2. Informative References

[AHKM22]
Alwen, J., Hartmann, D., Kiltz, E., and M. Mularczyk, "Server-Aided Continuous Group Key Agreement", ACM, Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, DOI 10.1145/3548606.3560632, , <https://doi.org/10.1145/3548606.3560632>.
[I-D.mularczyk-mls-splitmls]
"*** BROKEN REFERENCE ***".

Appendix A. Known Issues

Acknowledgments

TODO acknowledge.

Authors' Addresses

Franziskus Kiefer
Cryspen
Karthikeyan Bhargavan
Cryspen
Richard L. Barnes
Cisco
Joël Alwen
AWS Wickr
Marta Mularczyk
AWS Wickr