Re: [MLS] Syntax and mechanics for external commit

Raphael Robert <> Wed, 07 October 2020 10:36 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 60F893A08AE for <>; Wed, 7 Oct 2020 03:36:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 3XnurOjpyie0 for <>; Wed, 7 Oct 2020 03:36:25 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::530]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5DFE53A08AB for <>; Wed, 7 Oct 2020 03:36:25 -0700 (PDT)
Received: by with SMTP id l16so1625467eds.3 for <>; Wed, 07 Oct 2020 03:36:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=4I5l2jkAyCvPGZ606osTHEMiXtYElcH29Wr1135XuKg=; b=BfJYXeyZzK8dle6QLmIaazH+DDKyoHz9lUTQ5ndsT+oydfzdezaowgKH+n0E4lMJ1P /O7XYModmcPM9zPdLNxHXuXjAwUd+Bk/K8776sTfdaHvaggo/Ryj1wpxlMPEsn3ymS/h /dkuXzcY2PQ5nbN2b1M21ht6lb1w6b4f5T6QjLOgdxvIfA0u1+yVyFveHnqwqFoHbiw+ JueB9Hhd0fbDUhqO7uoEIvuBvAehoTVNaMuwRm7X70KkZzZmCp5zthz6qWT665YFAQNZ 7PUzHzLG7W8TEVJXHbTutG7i5pAwSyF8swt++tbIQhu+TSk4ymY0rhn8ObYuww9jWg01 JLtQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=4I5l2jkAyCvPGZ606osTHEMiXtYElcH29Wr1135XuKg=; b=Q9Xv8RoA37HUbNhL6KajySDxCIfNMWMHAkwn9fhBDuNgNwgKaLrTi+sKztFrEy4tAo RlcQpq/S6fOmat8PhWMl0GzMfc1nPCkQz70nI6EBJcpH4uY52fazLvFkcTK8uxkbq1V5 tv3500o10BqZxb8c5VLSxuV4wzgjmfKxJAL/5ghEHhWQUwinPS/iAtsFUF96c0cBgeTA OFD4y/IyQuQNrc7acLCga9qoDXM2ohU58DcZQv5DHIXeZsmboYQ5zdPP1ByUWxzexalM 6Hgis+Jf5YzIs1TX50w1zsNE5d/dxcmp/FOfU1ZXnieV9JhLuFtQ59aKQTXjOipkiAyT apsw==
X-Gm-Message-State: AOAM533NyKEWgZVTrOdoczxj0WXlWUNcZ4LWZEVGqWjKZEmMp1LjC71F kwgQQrBhZPl0FG7Ezbw7k8x3GvNpPsq0qQ==
X-Google-Smtp-Source: ABdhPJzuSFGrOU5EwosiW9UyPbrn/e4uLxsjMuYb5JRW3OZaPALyNUXJmmCVtA5FJ5wMdhdb/POZsg==
X-Received: by 2002:aa7:c256:: with SMTP id y22mr2834928edo.324.1602066983547; Wed, 07 Oct 2020 03:36:23 -0700 (PDT)
Received: from ([]) by with ESMTPSA id 92sm1165503edm.30.2020. (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Wed, 07 Oct 2020 03:36:22 -0700 (PDT)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.\))
From: Raphael Robert <>
In-Reply-To: <>
Date: Wed, 7 Oct 2020 12:36:21 +0200
Cc: Messaging Layer Security WG <>
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <>
To: Richard Barnes <>
X-Mailer: Apple Mail (2.3608.
Archived-At: <>
Subject: Re: [MLS] Syntax and mechanics for external commit
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 07 Oct 2020 10:36:27 -0000

Thanks Richard for looking at all aspects in detail!

I thought about these things as well and will comment inline:

> On 7 Oct 2020, at 03:20, Richard Barnes <> wrote:
> Hey all,
> I wanted to send some thoughts on how to implement external commit, as a prelude to a PR.  This is a little bit of an essay, so tl;dr, the proposal is:
> - Rather than re-using Proposal/Commit, we should make a new ExternalCommit message, parallel to Proposal/Commit

I think we are better off with re-using the current Commit syntax and I’ll explain why further below.

> - We should also define a syntax for telling the joiner the requisite information about the group
> # HPKE-based init secret
> The concept here is as follows:
> - An HPKE/KEM key pair `(skG, pkG)` is derived off of the key schedule for each epoch
> - The public key `pkG` of that key pair is published along with with other group metadata
> - The joiner calls SetupBaseS(pkG, some_public_group_context) to get an encapsulated key `enc` and an HPKE context `ctx`
> - The joiner sends the encapsulated key to the group with their external commit
> - The members of the group call SetupBaseS(enc, skG, some_public_group_context) to get an equivalent HPKE context `ctx`
> - Everyone calls `ctx.export(MLS_export_label, init_secret_size)` to derive the init secret
> So there are two syntactic requirements:
> 1. Publishing the group’s public key `pkG`
> 2. Sending the encapsulated key `enc` to the group

From the discussion at the interim, I think there is consensus about this part, we just need to add that to the PR.

> # What Proposals?
> The current PR correctly requires that the external Commit MUST cover an Add proposal for the new member.   It does not forbid the Commit covering *other* proposals.  It seems like it might be useful in a couple of cases to keep that option open:
> * Including PSK proposals for additional authentication when joining
> * Including a Remove proposal for your prior appearance when re-joining
> The only current proposal that would be nonsensical is an Update.  
> Whether we do this has some impact on the syntax, as discussed below.

While that is not very explicit in the current PR, my approach was the following:

All Proposals should be allowed in an external Commit:

 - Adds: The joiner (new member) could right away add more members, or Commit to already existing Add Proposals if those are accessible. 
 - Removes: The joiner can remove prior appearances of itself (like you pointed out) or Commit to already existing Remove Proposals.
 - Updates: The joiner should of course not issue own Updates and Commit to them, but that is already the case for internal Commits. The joiner can Commit to already existing Update Proposals from other members.

Whether all of the above is allowed should only be governed by the policy for a group, nothing else. As a reminder: all clients MUST have the same policy for a certain group in order ta validate/refute Proposals and Commits.

This pretty much motivates my idea for fully re-using the existing Commit syntax and only introduce the new ExternalInitSecret Proposal.

> # External commit syntax: Separate or Together
> Assume for the moment that we are not going to do the above asymmetric calculation for every commit.  Then we need some extra, optional syntax  to carry `enc`, either as an optional field on Commit or as a new Proposal, which is the agreed mechanism for extending Commits.  (If we do it every time, we can just make this part of Commit.)  In the below, I’ll assume a new Proposal, say ExternalInitSecret.
> struct {
>   opaque kem_output<0..2^16-1>;
> } ExternalInitSecret;

This is exactly the Proposal we need.

> Given the requirement for an Add proposal, the joiner now has to send a “flight of messages”:
> - Proposal(Add)
> - Proposal(ExternalInitSecret)
> - Commit

I see some more nuance here. The first Add Proposal does not have to be issued by the new joiner, it could very well be an external Proposal. The scenario I had in mind here is the following:

A server issues an external Add Proposal for a group. The following things can happen:

a) Ideal scenario:

 - A member of the group comes online, validates the Add Proposal according to the policy and references it in an internal Commit (no External Commit needed) and sends a Welcome message to the new member

b) Equally ideal scenario:

 - The new joiner comes online before anyone else, has access to the public group data but does not need to communicate with the group. Nothing happens.

c) Emergency scenario:

 - The new joiner comes online before anyone else and needs to urgently send a message to the group. The new joiner creates the ExternalInitSecret Proposal and the Commit and sends both to group.

> Let’s call this the Separate Option.  It’s a bit heavyweight, since each of these is signed separately.  It’s duplicative, since the KeyPackage in the Add is immediately overwritten by the (necessarily different) KP in the Commit.  And you have potential fate-sharing issues, since all three need to succeed or fail.
> You could also envision a Together Option, where we define another top-level content type (parallel to Proposal and Commit) for this purpose:
> struct {
>   opaque kem_output<0..2^16-1>;
>   UpdatePath path;
> } ExternalCommit;
> That would avoid all of the challenges above, but it optimizes out all of the flexibility to include other proposals.  So maybe it’s worth considering an Extensible Together Option, where we can put extra proposals into an ExternalCommit
> struct {
>   Proposal proposals<0..2^32-1>;
>   opaque kem_output<0..2^16-1>;
>   UpdatePath path;
> } ExternalCommit;
> Personally, I kind of like the Flexible Together Option, since it provides simplicity and extensibility.  And to be honest, I’ve been wondering if we should allow inline proposals in Commit for a while, along just these lines.  If we do this option, we should probably back-port it to Commit as well.

As mentioned above, I’m all for re-using the existing Commit syntax because of clarity, simplicity and flexibility. 

I do agree that the amount of signatures is sub-optimal, and this is something that also occurs in other situations. For example, when a member wants to add n new members at once to the group, it needs to compute n+1 signatures for that.
You mention the idea of inline proposals: Would that be a proposal that doesn’t have a signature, but still all other information? If so, I think it would be worthwhile looking at that separately, because as you say, it could be back-ported to internal Commits as well. I’m all for exploring that idea further.

> # Syntax for what the Joiner Needs
> The PR notes that the joiner needs to know a bunch of information about the group in order to make a well-formed ExternalCommit.  In earlier iterations of this style of join, we had a GroupInitKey that carried the right information. Following that pattern here, we get something like the following:
> struct {
>   CipherSuite cipher_suite;
>   opaque group_id<0..255>;
>   uint64 epoch;
>   opaque tree_hash<0..255>;
>   opaque confirmed_transcript_hash<0..255>;
>   Extension extensions<0..2^32-1>;
> } GroupKeyPackage;

This is what the PR currently says, except that the PR used GroupContext and has the full public tree. I agree that the tree hash should be enough and I’ll change the PR accordingly.

> Note that this object is essentially the same as a GroupInfo object.  The only things it is missing are interim_transcript_hash and signature, both of which might be useful.  So maybe all we need to do here is say that clients can publish GroupInfo unencrypted if they want to enable self-adds, in addition to distributing it in encrypted form in Welcome.

While the two are awfully similar, the signature on GroupInfo is not required here and might have undesired effects w.r.t deniability if this is publicly accessible. The other reason for not wanting the signature is that it would be an additional signature to compute with every Commit, making them even more expensive. I propose to keep the struct as-is.

> In any case, it seems like it would be useful to have some syntax for this.
> Hope this helps,
> —RLB


I propose the following:

 - Keep the current Commit syntax 
 - Allow all kinds of Proposals for External Commits, same as with internal Commits
 - Do the HPKE-based init secret for External Commits
 - Introduce the ExternalInitSecret Proposal and make it mandatory for External Commits
 - Explore the idea of inline proposals separately
 - Do not re-use signed GroupInfo struct and keep the adjusted ExternalCommitInfo instead


> _______________________________________________
> MLS mailing list