[MLS] Inline proposals

Richard Barnes <rlb@ipv.sx> Thu, 08 October 2020 15:47 UTC

Return-Path: <rlb@ipv.sx>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 43C4E3A0A04 for <mls@ietfa.amsl.com>; Thu, 8 Oct 2020 08:47:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Di-ACJ8K-aNj for <mls@ietfa.amsl.com>; Thu, 8 Oct 2020 08:47:36 -0700 (PDT)
Received: from mail-qk1-x731.google.com (mail-qk1-x731.google.com [IPv6:2607:f8b0:4864:20::731]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3312B3A08C7 for <mls@ietf.org>; Thu, 8 Oct 2020 08:47:35 -0700 (PDT)
Received: by mail-qk1-x731.google.com with SMTP id z6so7517478qkz.4 for <mls@ietf.org>; Thu, 08 Oct 2020 08:47:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=8IkKMBGdFt642oojtdCHt3XOtxENpyF0HE8BZP2n0B0=; b=j4iaP+oBua89hPElWvnSV2isamEokoUnM0yav6aeK6zisGlqAJ2oUnoS2ZpOPisTTZ Z2OEAeKC00r/7xqox4WXwxc8e0bFm1EW/HhmsHqiY3whFqS7iQt0U9pvwxeLGEGB3CSq W5plZ8wMIh9qgE1/A1Hw2nrix8YQg6oZFqAW4f8WOjxl5gse48/ZofinbbkAfhf/N8g4 UXrDYNGXv3ckaBzWrgBqoYpl6YY0kLgBD29mUvlIJV0Nt+7pwcJ6mJWgb4hnCwvvgf5C WQxwnHc80VOgUqq5e+XOT+rffeaUEO1JpnQlAkw2HusUL0nMBUEqMdEf+Gx7QkwAKFP9 +Q8w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=8IkKMBGdFt642oojtdCHt3XOtxENpyF0HE8BZP2n0B0=; b=HynKeih/7YIQub4kIbr3M1afIXfJIjuIq5Y3GWTlAUhk/TY+1XkZ94FCcrOfYnouYR ZqXVvylEW8wQf/FUBKdl3lwcjuoQrijrleUl6eZqCh8q4PrciUaa6pln4cEdeXZoQl0z 25aA/2Rc1L/BtfoWxTMAniBdJgwt0LHxN4z/zMTRDO+/EtwsUYWxp/YpnejLxme9fks3 2xsOOkIWCniZ+iI/HHRrR32I0QhILxpgWC/5iNxRUioNNUGAvcVGIE6PQgjNOMExF9IM dI4Rt3YGI0wRUMVxVoXCu1hT3zz/waaGrpMNCMfmgHytOQYjk2+Y8GoGikKJca7k/jVe 1v5A==
X-Gm-Message-State: AOAM53265BWxDHWPvI1TSVsKxOjHbrv5wJd3gsrTuz3EyjIeZfa93xMD 0xNm7zNtguBODhMl/+reVa7h5I5PaaYdXgX01hVMwB0ZfufB/Q==
X-Google-Smtp-Source: ABdhPJxol/7oE5mkCHOXya+R9PVDHucSLZkSjINyaVpC8lmhyas+zjhYjQVfSp3ltGOZkrkcGKV7aBIy0aXSFjT15+Q=
X-Received: by 2002:a05:620a:15b6:: with SMTP id f22mr1537391qkk.490.1602172054445; Thu, 08 Oct 2020 08:47:34 -0700 (PDT)
MIME-Version: 1.0
References: <CAL02cgQCQtJS-_SWcaGDVaDBpKHsmu4P2Lkrq20ukEM3OkdRnQ@mail.gmail.com> <09F65ECA-9D11-4494-AFFF-8C49D7FF9A1A@wire.com> <e1187f1d-c559-bfc2-5390-8189946ddc4a@wickr.com> <27773A68-7CB9-4613-9AAB-57724F896D3A@wire.com> <CAL02cgT514YPqBOfer-TPo4UAi-psZHaQ=fb2pGCvQCffPmtJw@mail.gmail.com> <0E0C01DC-1BA3-4FD3-9A3F-48A736E5C1C0@wire.com> <CABP-pSRU_jxGk7TFHeajOWRPpTj24sdr6cLYMLb0OZwYRMVsOQ@mail.gmail.com>
In-Reply-To: <CABP-pSRU_jxGk7TFHeajOWRPpTj24sdr6cLYMLb0OZwYRMVsOQ@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Thu, 8 Oct 2020 11:47:21 -0400
Message-ID: <CAL02cgRLudAkS2MdG4T1u1ZVQm-ix-BzMTbw+0S0xfDeThC9NQ@mail.gmail.com>
To: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000002cb23a05b12ac0e0"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/CSe24hQVWc0OPvhkxHT9UACXimA>
Subject: [MLS] Inline proposals
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 08 Oct 2020 15:47:39 -0000

(Changing subject line because changing subject)

Since there seems to be some energy around inline proposals regardless of
ExternalCommit, I made a quick PR:

https://github.com/mlswg/mls-protocol/pull/414

The interesting nuance here is that the Commit specifies an order in which
Proposals are applied.  So there are basically two design options here:

1. Include proposals by value, and reference them by hash in the order
specification
2. Allow the order specification to reference proposals by value or by hash

I went with the latter approach, because it seemed slightly simpler to me.
But if folks feel strongly, we could go the other way as well.

--Richard


On Wed, Oct 7, 2020 at 8:45 PM Brendan McMillion <brendan@cloudflare.com>
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=
> 40wire.com@dmarc.ietf.org> wrote:
>
>> Good points again!
>>
>> On 7 Oct 2020, at 17:38, Richard Barnes <rlb@ipv.sx> 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=
>> 40wire.com@dmarc.ietf.org> 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 <jalwen@wickr.com> wrote:
>>> >
>>> > On 7 Oct 2020, at 03:20, Richard Barnes <rlb@ipv.sx> 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 <rlb@ipv.sx> 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
>>> >>> MLS@ietf.org https://www.ietf.org/mailman/listinfo/mls
>>> >>
>>> >> _______________________________________________ MLS mailing list
>>> >> MLS@ietf.org https://www.ietf.org/mailman/listinfo/mls
>>> >>
>>> >
>>> > _______________________________________________
>>> > MLS mailing list
>>> > MLS@ietf.org
>>> > https://www.ietf.org/mailman/listinfo/mls
>>>
>>> _______________________________________________
>>> MLS mailing list
>>> MLS@ietf.org
>>> https://www.ietf.org/mailman/listinfo/mls
>>>
>>
>> _______________________________________________
>> MLS mailing list
>> MLS@ietf.org
>> https://www.ietf.org/mailman/listinfo/mls
>>
>