mls J. Alwen
Internet-Draft M. Mularczyk
Intended status: Standards Track Amazon
Expires: 24 April 2025 21 October 2024
MLS Split Commits
draft-mularczyk-mls-splitcommit-00
Abstract
This document describes an extension to the MLS protocol [RFC940]
that improves its efficiency in terms of per-member download size.
This comes at essentially no cost. In essence, this document defines
a new message type called split commit which replaces regular MLS
commits. Unlike regular commits, a split commit can be "split" by
the Delivery Service (DS) into much smaller per-member commits, one
for each receiving member. The size of a per-member commit is always
logarithmic in the group size, while the size of a regular MLS commit
can be linear. This extension works in settings with a DS that can
do the splitting which can be demanding with encrypted MLS handshake
messages. This is motivated by academic research [KKP22], [HKPPW22],
[AHKM22].
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.
Copyright Notice
Copyright (c) 2024 IETF Trust and the persons identified as the
document authors. All rights reserved.
Alwen & Mularczyk Expires 24 April 2025 [Page 1]
Internet-Draft MLS Split Commits October 2024
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 . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Protocol Overview . . . . . . . . . . . . . . . . . . . . 2
2. Conventions and Definitions . . . . . . . . . . . . . . . . . 4
3. Split Commits . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Transcript Hashes . . . . . . . . . . . . . . . . . . . . . . 7
5. Delivering Split Commits without the Ratchet Tree . . . . . . 7
6. Security Considerations . . . . . . . . . . . . . . . . . . . 7
6.1. Transcript Hashes . . . . . . . . . . . . . . . . . . . . 7
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
8.1. Normative References . . . . . . . . . . . . . . . . . . 8
8.2. Informative References . . . . . . . . . . . . . . . . . 8
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9
1. Introduction
1.1. Protocol Overview
Consider the example ratchet tree from Section 7.4 of [RFC9420]:
Y
|
.-+-.
/ \
X Z[C]
/ \ / \
A B C D
0 1 2 3
Figure 1: A Full Tree with One Unmerged Leaf
In a group with a ratchet tree of this form, if member 0 were to
commit, they would compute two updated path secrets X' and Y', and
three encrypted versions of these path secrets:
Alwen & Mularczyk Expires 24 April 2025 [Page 2]
Internet-Draft MLS Split Commits October 2024
1. X' encrypted to B
2. Y' encrypted to C
3. Y' encrypted to D
With a normal MLS Commit, all three of these encrypted values are
sent to each other member -- even though each member can only decrypt
one of the encrypted values. Since the number of encrypted values
can grow linearly as the size of the group, in the worst case, this
creates quadratic data to be transmitted.
With split Commits, each member receives only what they decrypt. The
committer can make individual messages for each member, or they can
emit a single message with all encrypted values, which the DS can use
to construct per-member messages. We call the per-member messages
PerMemberCommits, and the message carrying all of the encrypted
values a SplitCommit.
A B C D
| E(B; X') | | |
+--------->| | |
| | | |
| E(C; Y') | | |
+-------------------->| |
| | | |
| E(D; Y') | | |
+------------------------------->|
| | | |
Figure 2: A committer creates per-member commits
A DS B C D
| E(B; X') | | | |
| E(C; Y') | | | |
| E(D; Y') | | | |
+--------->| | | |
| | | | |
| | E(B; X') | | |
| +--------->| | |
| | | | |
| | E(C; Y') | | |
| +-------------------->| |
| | | | |
| | E(D; Y') | | |
| +------------------------------->|
| | | | |
Alwen & Mularczyk Expires 24 April 2025 [Page 3]
Internet-Draft MLS Split Commits October 2024
Figure 3: The DS creates per-member commits
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.
3. Split Commits
A Split Commit uploaded to the DS consists of two parts. First, it
contains a SplitUpdatePath object which is a regular UpdatePath
defined in {!RFC9420}} but without the committer's LeafNode. Second,
it contains a split_commit_message MlsMessage (PublicMessage or
PrivateMessage) which includes an epoch identifier, the committed
list of proposals and the committer's LeafNode.
The split_commit_message is signed and encrypted, while
SplitUpdatePath is not. The reason is that the DS includes in per-
member commits only parts of the SplitUpdatePath and receivers can
still verify authenticity and decrypt all that is needed. (The
split_commit_message must be delivered in full but its size is worst-
case logarithmic.) The lack of encryption for SplitUpdatePath is not
a problem because it contains only HPKE public keys and ciphertexts.
The proposals and LeafNode (the latter containing a credential) are
encrypted.
The purpose of the epoch identifier is to provide authenticity. In
particular, with Split Commit, the committer does not sign the HPKE
keys they chose for their updated path in the ratchet tree. However,
we need authenticity for these keys (else the adversary can replace
them by their own). Thus, the committer signs instead (as part of
message framing) the epoch identifier that binds the tree hash of the
new epoch. In particular, the epoch identifier is derived from the
new epoch's key schedule.
Alwen & Mularczyk Expires 24 April 2025 [Page 4]
Internet-Draft MLS Split Commits October 2024
struct {
UpdatePathNode nodes<V>;
} SplitUpdatePath;
struct {
opaque epoch_identifier<V>;
ProposalOrRef proposals<V>;
optional<LeafNode> leaf_node;
} SplitCommit;
struct {
// PrivateMessage or PublicMessage
MLSMessage split_commit_message;
optional<SplitUpdatePath> path;
} SplitCommitMessage;
struct {
// PrivateMessage or PublicMessage
// content_type = split_commit
MLSMessage split_commit_message;
optional<HPKECiphertext> encrypted_path_secret;
} PerMemberCommit;
The SplitCommit object is a new content type and SplitCommitMessage
is a new wire format. Other MLS objects account for this as
specified below.
enum {
reserved(0),
application(1),
proposal(2),
commit(3),
split_commit(4),
(255)
} ContentType;
struct {
opaque signature<V>;
select (FramedContent.content_type) {
case commit:
MAC confirmation_tag;
case application:
case proposal:
case split_commit:
struct{};
};
} FramedContentAuthData;
Alwen & Mularczyk Expires 24 April 2025 [Page 5]
Internet-Draft MLS Split Commits October 2024
struct {
opaque group_id<V>;
uint64 epoch;
Sender sender;
opaque authenticated_data<V>;
ContentType content_type;
select (FramedContent.content_type) {
case application:
opaque application_data<V>;
case proposal:
Proposal proposal;
case commit:
Commit commit;
case split_commit:
SplitCommit split_commit;
};
} FramedContent;
struct {
ProtocolVersion version = mls10;
WireFormat wire_format;
select (MLSMessage.wire_format) {
case mls_public_message:
PublicMessage public_message;
case mls_private_message:
PrivateMessage private_message;
case mls_welcome:
Welcome welcome;
case mls_group_info:
GroupInfo group_info;
case mls_key_package:
KeyPackage key_package;
case mls_split_commit:
SplitCommitMessage split_commit_message;
};
} MLSMessage;
A committing group member generates a SplitCommitMessage using the
following steps: 1. Perform a regular MLS commit, without message
framing. 2. Export a secret epoch_identifier from the new epoch with
the label "SplitCommit". 3. Generate a SplitCommit object
split_commit with epoch_identifier from Step 2 and leaf_node from
path in the commit generated in Step 1. 4. Generate MlsMessage
split_commit_message by framing split_commit. 5. Output
SplitCommitMesage with path including nodes from path in the commit
in Step 1, epoch_identifier from Step 2 and split_commit_message from
Step 4.
Alwen & Mularczyk Expires 24 April 2025 [Page 6]
Internet-Draft MLS Split Commits October 2024
If the DS knows the ratchet trees before and after the split commit,
it generates a PerMemberCommit for a receiver group member from a
SplitCommit member as follows by choosing from the SplitUpdatePath
only the HPKECiphertext for the receiver. If the SplitCommit does
not contain the SplitUpdatePath or the commit removes the receiver,
the PerMemberCommit does not include the HPKECiphertext.
Section 5 considers DS's that do not know the ratchet tree.
A receiver group member processes a PerMemberCommit using the
following steps: 1. Process the split_commit_message MLSMessage to
recover split_commit. 2. Recover path_secret decrypting that
HPKECiphertext. 3. Use path_secret, public keys from path and
proposals to process the commit as specified in [RFC9420]. 4. Verify
that epoch_identifier in split_commit matches the secret exported
from the new epoch with the label "SplitCommit" .
4. Transcript Hashes
With split commits, the input to the confirmed transcript hash is the
same as in [RFC9420]. In particular, it contains the FramedContent
with a SplitCommit object inside. Split commits contain no
confirmation tags, so the interim transcript hash is simply equal to
the confirmed transcript hash.
5. Delivering Split Commits without the Ratchet Tree
If the DS does not know the ratchet tree, then it cannot determine
which ciphertexts to deliver to which members. Dealing with this is
outside the scope of this document.
In general, there are several ways to deal with this. For example,
the sender can annotate the ciphertexts in the split commit.
Alternatively, the receiver can "pull" the split commit without path,
identify the sender and indicate the index of the ciphertext it
expects before pulling it. However, most DS's work in the push not
pull model and are therefore incompatible with this solution.
6. Security Considerations
6.1. Transcript Hashes
The transcript hash with split commits covers FramedContent with a
SplitCommit that contains epoch_identifier, proposals and leaf_node.
The transcript hash with regular commits covers FramedContent with a
Commit that contains proposals, leaf_node and path, as well as the
confirmation tag.
Alwen & Mularczyk Expires 24 April 2025 [Page 7]
Internet-Draft MLS Split Commits October 2024
Since epoch_identifier is derived from the key schedule and the tree
hash of the new epoch is mixed into the key schedule, the transcript
hash with split commits binds the public keys from path. There is no
security-related reason to agree on ciphertexts, so there is no
reason to include path in the transctipt hash. Note that group
members do agree on _content_ of the ciphertexts in path. That is,
they agree on the commit secret hashed into the key schedule (and
used to derive epoch_identifier), so they also agree on all path
secrets that they can derive (assuming no hash collisions).
7. IANA Considerations
This document has no IANA actions.
8. References
8.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<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,
May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.
[RFC940] Gateway Algorithms and Data Structures Task Force, "Toward
an Internet standard scheme for subnetting", RFC 940,
DOI 10.17487/RFC0940, April 1985,
<https://www.rfc-editor.org/rfc/rfc940>.
[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, <https://www.rfc-editor.org/rfc/rfc9420>.
8.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,
November 2022, <https://doi.org/10.1145/3548606.3560632>.
[HKPPW22] Hashimoto, K., Katsumata, S., Postlethwaite, E., Prest,
T., and B. Westerbaan, "A Concrete Treatment of Efficient
Continuous Group Key Agreement via Multi-Recipient PKEs",
Alwen & Mularczyk Expires 24 April 2025 [Page 8]
Internet-Draft MLS Split Commits October 2024
ACM, Proceedings of the 2021 ACM SIGSAC Conference on
Computer and Communications Security,
DOI 10.1145/3460120.3484817, November 2021,
<https://doi.org/10.1145/3460120.3484817>.
[KKP22] Hashimoto, K., Katsumata, S., and T. Prest, "How to Hide
MetaData in MLS-Like Secure Group Messaging: Simple,
Modular, and Post-Quantum", ACM, Proceedings of the 2022
ACM SIGSAC Conference on Computer and
Communications Security, DOI 10.1145/3548606.3560679,
November 2022, <https://doi.org/10.1145/3548606.3560679>.
Acknowledgments
TODO acknowledge.
Authors' Addresses
Joël Alwen
Amazon
Email: alwenjo@amazon.com
Marta Mularczyk
Amazon
Email: mulmarta@amazon.com
Alwen & Mularczyk Expires 24 April 2025 [Page 9]