Re: [MLS] Syntax and mechanics for external commit

[Raphael Robert <[e-mail]>]

Thanks for implementing it! That’s always good for validation.

> On 11 Oct 2020, at 21:09, Richard Barnes <[e-mail]> wrote:
> 
> To help flush out additional details needed here, I went ahead and prototyped out external commits in mlspp:
> 
> https://github.com/cisco/mlspp/pull/118 <https://github.com/cisco/mlspp/pull/118>
> 
> As outlined in the PR, there are few additional things we need in the spec PR:
> 
> 1. The ExternalInit proposal type and its handling
> This is largely just what was sketched up-thread.
> 
> 2. Defining the minimal requirements for an external Commit
> We probably need a section describing some special additional constraints that apply to external Commits, beyond general Commits:
> - It MUST cover an Add proposal for the committer
> - It MUST include an inline an ExternalInit proposal
> - It MAY cover other proposals
> - Commit.path MUST be populated

This is what we currently already have in the PR:

- External Commits MUST reference the Add Proposal that adds the issuing new member to the group      
- External Commits MUST be signed by the new member      
- External Commits MUST contain a `path` field (and is therefore a "full" Commit)      
[ - When processing a Commit, both existing and new members MUST use an empty init secret (all-zero vector of size Hash.length) ] (outdated)
- If the Add Proposal is also issued by the new member, its member SenderType MUST be `new_member`

> 
> 3. A new SenderType value for external commits and signature validation logic
> The above PR defines a new SenderType value "external_joiner", and when an MLSPlaintext with that sender type is encountered, uses the public key from Commit.path.leaf_key_package.  (The latter so that it doesn't have to look up an Add proposal within the Commit.)  I think that validation strategy is probably the right balance of simplicity and correctness.  As far as the SenderType, we could probably re-use the "new_member" type, with the understanding that:
> - new_member + Proposal => Proposal MUST be an Add, and the signature must validate with the public key from Add.key_package
> - new_member + Commit => Commit MUST be an external Commit (with Add and ExternalInit proposals), and the signature must validate with the public key from Commit.path.leaf_key_package
> 
> But if we can nail those down, I think we have a tool here that's pretty powerful, and not all that complicated to implement.

Thanks for confirming my intuition!

Raphael

> 
> --Richard
> 
> On Wed, Oct 7, 2020 at 8:45 PM Brendan McMillion <[e-mail] <mailto:[e-mail]>> wrote:
> I know you're all tired of hearing me say this, but I still feel strongly we should always use asymmetric Commits. If MLS is otherwise secure, then there's simply no reason not to, and it simplifies implementations. There wouldn't have to be a new ExternalInitSecret proposal, validation logic wouldn't get substantially more complicated, and there wouldn't be this worry about bundling several proposals. Otoh, I think allowing inline proposals in Commits is a good idea but it's orthogonal to asymmetric Commits.
> 
> On Wed, Oct 7, 2020 at 1:24 PM Raphael Robert <raphael=[e-mail] <mailto:[e-mail]>> wrote:
> Good points again!
> 
>> On 7 Oct 2020, at 17:38, Richard Barnes <[e-mail] <mailto:[e-mail]>> wrote:
>> 
>> OK, how about the following proposal (heh):
>> 
>> - Add ExternalInitSecret proposal
>> - Add an "inline proposals" field to Commit that lets the committer send proposals with a commit
>> 
>> Two remaining worries here: 
>> 
>> - Validation: You want it to be the case that an ExternalInitSecret is only present for a Commit signed by a new joiner.  So some that information will have to be passed from MLSPlaintext validation to Commit processing.  Or maybe we don't care about that restriction?  It seems like a member sending ExternalInitSecret should at least be SHOULD NOT, but maybe it's not bad enough to absolutely forbid / have hard checks against.
> 
> Good question. I guess you want to detect early on if it is an External Commit or an internal one, perhaps also to block External Commits by policy. Indeed only the signature and sender type would reveal that. 
> Should internal Commits be allowed to have a ExternalInitSecret proposal that then just gets ignored? I don’t have strong feelings about it, but I’m leaning towards the safe approach of saying it MUST not.
> 
>> 
>> - Complexity: MLSPlaintext signature validation has to find a key to verify the signature.  I guess in this case, it should take the one for the Committer (Commit.update_path.leaf_key_package.public_key), but it should also be the case that that key was added to the group with this Commit.  In any case, this probably calls for a new sender type.
>> 
>> Maybe these can both be solved with a flag passed into Commit processing:
>> 
>> if (external_commit) {
>>   // verify that there is an Add corresponding to update_path.leaf_key_package
>> } else {
>>   // verify that ExternalInitSecret is not present
>> }
> 
> I’m thinking that the MLSPlaintext framing the External Commit will reference a previously empty leave (namely the left most empty leave in the tree). Normally clients would look up the leave to verify a signature, but in this case it’s an indication that it is an External Commit. Instead, clients have to parse the list of Add Proposal the precede the Commit to determine who the signer/sender is. Lastly the ExternalInitSecret Proposal MUST also be there.
> 
> As for the sender type, couldn’t we use new_member here? Both for the Add Proposal and the Commit?
> 
>> 
>> Even if so, that logic should get specified in the commit processing section of the spec.
> 
> I agree that this should be written up in detailed steps to avoid any confusion.
> 
> Raphael
> 
>> 
>> --RLB
>> 
>> 
>> On Wed, Oct 7, 2020 at 8:57 AM Raphael Robert <raphael=[e-mail] <mailto:[e-mail]>> wrote:
>> I think that’s exactly the motivation we need for inline proposals, this surplus of signatures is not specific to this use case!
>> 
>> Raphael
>> 
>> > On 7 Oct 2020, at 13:27, Joel Alwen <[e-mail] <mailto:[e-mail]>> wrote:
>> > 
>> > On 7 Oct 2020, at 03:20, Richard Barnes <[e-mail] <mailto:[e-mail]>> wrote:
>> >> 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.
>> > Isn't it a bit redundant to have the External party prepare a full
>> > (ExternInitSecret) proposal packet only to then immediately commit to it? That
>> > means a full extra frame of bandwidth, an extra signature for the external party
>> > and an extra sig verification for group members.
>> > 
>> > I'm wondering what the motivation is for making this an explicit proposal
>> > instead of, say, a second mode for commits. (E.g. a commit uses init_secret[n]
>> > iff no kem_output field is included in the commit packet. Otherwise it uses the
>> > "external_init_secret" computed as Richard described.)
>> > 
>> > ATM I can't think of a scenario where we wouldnt want the external committer to
>> > also be the one creating the ExternalInitSecret proposal and immediatly
>> > committing to it...
>> > 
>> > - Joël
>> > 
>> > 
>> > On 07/10/2020 12:36, Raphael Robert wrote:
>> >> 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 <[e-mail] <mailto:[e-mail]>> 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
>> >> 
>> >> 
>> >> TL;DR:
>> >> 
>> >> 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
>> >> 
>> >> Raphael
>> >> 
>> >>> _______________________________________________ MLS mailing list 
>> >>> [e-mail] <mailto:[e-mail]> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
>> >> 
>> >> _______________________________________________ MLS mailing list 
>> >> [e-mail] <mailto:[e-mail]> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
>> >> 
>> > 
>> > _______________________________________________
>> > MLS mailing list
>> > [e-mail] <mailto:[e-mail]>
>> > https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
>> 
>> _______________________________________________
>> MLS mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> 
> _______________________________________________
> MLS mailing list
> [e-mail] <mailto:[e-mail]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>