Re: [MLS] Proposal: Proposals (was: Laziness)

"Katriel Cohn-Gordon" <> Fri, 30 August 2019 16:40 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 59031120B6D for <>; Fri, 30 Aug 2019 09:40:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key) header.b=KPG6NxEs; dkim=pass (2048-bit key) header.b=GOZl+dm1
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id bjAsWURjsMuH for <>; Fri, 30 Aug 2019 09:40:26 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 513BE120B62 for <>; Fri, 30 Aug 2019 09:40:26 -0700 (PDT)
Received: from compute6.internal (compute6.nyi.internal []) by mailout.nyi.internal (Postfix) with ESMTP id 35DAD21DFB for <>; Fri, 30 Aug 2019 12:40:25 -0400 (EDT)
Received: from imap36 ([]) by compute6.internal (MEProxy); Fri, 30 Aug 2019 12:40:25 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; h=mime-version:message-id:in-reply-to:references:date:from:to :cc:subject:content-type; s=mesmtp; bh=a5jwYiRTO8VhEMpgIC4VdV/BH +KYaCkXlmiP1jK8LAQ=; b=KPG6NxEsiIxiNNVcF9cIAtNfAKBBnMXPVEi7RpVGD JFNK7z2TLy0KrkA6GWu/Ho2r0h5HHI05dYF/m7opd4wa7eVTfIfiMrWu4V6hfw1l YnDQa1S8pQO4TiJE3BI1djXZxXBR68rmhodVbfRGp7CGkwrz+5K7LUh8D6LONYTy x0=
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=a5jwYi RTO8VhEMpgIC4VdV/BH+KYaCkXlmiP1jK8LAQ=; b=GOZl+dm1/KX2415PghMcby +o3B7xPtRaEolXeAupXqzyY2v//rmsUR1BRmiTOOdOXkjRljV/FCgWIt48i+LWwq je9HcSG3WDT9ds5eDRxenFT6pky4rlsH4/NeHNRE19PW0ksacJIMCYxXHX9Yvj4N icZ/alPy5S2/797r36TUg4xRhgS5YmqxMynsr4KvJa/U/PuI8DcY8EvjGIQN4YsD 2W+LfxJIRtMt5cultwnUezZFlgTNFZ4+QVH+Uap5SevnU7SgTEKkn5MjXO/2rwu6 wPDgppf+KDRtNK+4qtc+lizHfbuw2sRcj8dHuyHheTKiGYEQ9jVVZx3AVgyfiw/w ==
X-ME-Sender: <xms:eVFpXWa2CKZEZdZZtuQ0ZRuBMu3l2z2B31V9w_UTKEK3Y_rI9E7cMg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduvddrudeigedguddtgecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgesrg dtreerreerjeenucfhrhhomhepfdfmrghtrhhivghlucevohhhnhdqifhorhguohhnfdcu oehmvgeskhgrthhrihgvlhdrtghordhukheqnecuffhomhgrihhnpehivghtfhdrohhrgh enucfrrghrrghmpehmrghilhhfrhhomhepmhgvsehkrghtrhhivghlrdgtohdruhhknecu vehluhhsthgvrhfuihiivgeptd
X-ME-Proxy: <xmx:eVFpXf86xK_DL7JV2qot65vd24i_EFehbhb81O8J9lHIXYuEffPoog> <xmx:eVFpXdvNpZhG8MgsxMrLqJK3Mw7gxSZ17FI13p9DoZOOKlfCxhvfDg> <xmx:eVFpXRRT0ke-WNYQy0NJcMLBeaCGpSjkgD8CUMwWj2rmCEnoTxXZaA> <xmx:eVFpXYNWrGMQEK1NJcGJpVmzyQ-agOR2_qGCPHGNlTe1RtGfLUrzkw>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id D25E612200A2; Fri, 30 Aug 2019 12:40:24 -0400 (EDT)
X-Mailer: Webmail Interface
User-Agent: Cyrus-JMAP/3.1.7-154-gfa7592a-fmstable-20190829v1
Mime-Version: 1.0
Message-Id: <>
In-Reply-To: <>
References: <> <> <> <> <> <> <> <> <> <> <> <>
Date: Fri, 30 Aug 2019 17:40:03 +0100
From: "Katriel Cohn-Gordon" <>
Cc: "Messaging Layer Security WG" <>
Content-Type: multipart/alternative; boundary=2595ba6b76d840188c5c25255aa2f6ce
Archived-At: <>
Subject: Re: [MLS] Proposal: Proposals (was: Laziness)
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: Fri, 30 Aug 2019 16:40:38 -0000

This abstraction seems sensible. Server add/remove is important in many practical use cases: you buy a new phone and log in; the server wants to remove your old phone from all groups it's in, and add the new phone. Since we of course don't want to give the server the ability to actually effect this change, only to propose it, it seems to me that we already need a way to disconnect proposals and commits anyway. Once that's the case, it doesn't seem too big a leap to cleanly factor all operations into that structure.

My main worry would be complicating the analysis. However, it seems like if the separation is clean enough then it might not actually make the analysis too bad, because there is a clean property (that Karthik described) for each epoch change. So, on balance, I think I'm in favour of this proposal.


On Tue, 27 Aug 2019, at 6:23 PM, Karthik Bhargavan wrote:
> Hi Richard,
>> On 23 Aug 2019, at 18:48, Richard Barnes <> wrote:
>> Just to confirm I understand, the key exchange protocol in this conception would be something like, at each epoch:
>> 1. KEM a secret to some set of people whom you believe to be the current members of the group
>> 2. Send that KEM'ed value out to the group together with a description of the current membership
>> 3. KDF the KEM'ed secret together with the prior epoch secret to get the new epoch secret
>> 4. Use the new epoch secret to generate a confirmation over the current state of the group
>> Where the KEM in (1) would be something like TreeKEM or just "encrypt to a list of public keys". Then the proposals would just be a way for people to sync up on who the current members of the group are (by leaf key).
> This is essentially correct, of course with a bunch of details to guarantee that everyone gets the same keys.
> It remains mostly unchanged from what we have currently.
>> The major thing I would be worried about in such a split is how it would deal with authority over changes, which affect the authentication properties of the protocol. The current Proposals proposal maintains the property that everyone agrees on the proposals and can verify that they were proper, e.g., only the holder of a leaf can update that leaf. If we sever the connection between the proposals and the top-level transcript entirely, then I'm not sure how you would continue to assure that, say, the sender of a Commit didn't just swap out Joe's leaf key for the NSA.
> The changes would be signed by the sender, as usual. The only question is whether this signature is enough, without binding the signature to the key exchange transcript or current epoch secret.
> Note that the tree synchronization protocol has its own transcript on how the tree has changed over time, and certainly we could require each update to sign this “state history” transcript.
> We should of course impose the requirement that only the "holder of the signature key corresponding to a leaf” can update that leaf.
> In fact, the tree update protocol can ensure that only members of a subtree can change the root of that subtree.
> This is what we guarantee now anyway. I don’t see that substantially changing in the decoupled design.
>> I agree that there is degree of separation here (since, e.g., it's easy to imagine swapping in a "list of keys" KEM for TreeKEM). But it seems like a fairly high degree of coupling is necessary to maintain authentication.
> So, what would be the authentication property you would want for a tree change?
> The tree changing sender must know the signature key for a member *and must also know the current epoch secret*?
> Perhaps what you are pointing out is that we cannot remove signatures from the key exchange protocol, and so we’d end up needing two signatures; one for tree synchronization and the other for authenticating the key exchange.
> Actually, we also need a third signature for the message protection. How and when we can share these signatures is an optimization problem, but they serve different purposes.
> -Karthik
>> --Richard
>> On Fri, Aug 23, 2019 at 1:22 PM Karthik Bhargavan <> wrote:
>>> Hello All,
>>> It seems to me that one way to think about “laziness” would be to cleanly separate the MLS key exchange into two different protocols.
>>> The first is a “classic” authenticated synchronization protocol where members of a group can create and modify a shared data structure (in this case, the group membership tree).
>>> The second is a novel key establishment protocol where some member of the group generates a fresh group secret that will be delivered only to the current members computed from the (current) group state.
>>> Currently the first and second protocols are tightly interleaved: every time the group data structure is modified by some member (or admin), that member must also generate and distribute the fresh group secret.
>>> The laziness proposal can be thought of as detaching the two protocols: the key establishment protocol can follow group modifications with some delay.
>>> So rather than trying to add “laziness” to the existing protocol, should we try to do this detachment in a principled way by defining two independent sub-protocols?
>>> It would have the advantage that we may be able to consider other designs for synchronization and key establishment, which may well be orthogonal concerns.
>>> In our model of MLS, we can already factor out the protocol in this way, but it makes the security invariants a bit harder to express in a user-friendly way.
>>> Still, I would prefer to compose proofs for simpler sub-protocols rather than try to prove security for a single complex protocol with lots of options.
>>> Best,
>>> -Karthik
>>>> On 23 Aug 2019, at 10:48, Richard Barnes <> wrote:
>>>> On Fri, Aug 23, 2019 at 10:21 AM Stephen Farrell <> wrote:
>>>>> Hiya,
>>>>> On 23/08/2019 15:10, Richard Barnes wrote:
>>>>> > 
>>>>> > I'm not clear on what you mean by "meaningfully handled by members".
>>>>> > 
>>>>> I'm assuming that MLS protocol data will likely be
>>>>> handled by a library. ISTM more likely that such a
>>>>> library might default to, or be carelessly used to,
>>>>> honor anything the server proposes if this is an MLS
>>>>> protocol feature rather than an application layer
>>>>> feature. That'd be an example of not meaningfully
>>>>> handling this:-) We have seen similar kinds of
>>>>> failure with applications and TLS libraries in the
>>>>> past where certs aren't checked etc.
>>>> Oh I see. That would actually be a pretty difficult policy to implement, at least without turning off authentication altogether, at least in the envisioned protocol. By which I mean:
>>>> - Right now, clients are expected to maintain a list of members' signing keys
>>>> - So signers are just indicated by their index in that list
>>>> - The obvious way to add non-member signers is to reserve a block of indices (say 0xFFFFFFxx) that can correspond to application-specific entities
>>>> - Then clients need to get configured with which server keys go with which reserved indices
>>>> Assuming we go in that direction, the natural, "I don't care about server-initiated stuff" library design would be to just not implement any special handling for those reserved indices, in which case you'll reject anything from the server. I would expect a library that does anything else to have an API for the configuration required in the last point.
>>>> The obvious screw-up case would be, "Treat a signature from the reserved block as trusted". But that's actually a little hard to implement; because the public keys aren't provided, you would have to also not do any signature verification at all, which means you're now totally open to the world. Hopefully that would raise some red flags for developers.
>>>> So it's not impossible to screw up, but not trivial either. At least if you want to maintain authentication for group members. If you turn that off too, I don't think we can save you.
>>>> --Richard 
>>>>> I do accept the argument that it can happen at the
>>>>> application layer if not defined in the MLS protocol,
>>>>> but doing this kind of thing at the application layer
>>>>> seems safer to me.
>>>>> It's also not clear to me that all MLS applications
>>>>> would need this feature. (That may be true, I just
>>>>> don't know.) If they don't, then again, it seems to
>>>>> be more conservative to leave it to applications.
>>>>> I agree that there are sharp edges however this kind
>>>>> of thing is done though.
>>>>> Cheers,
>>>>> S.
>>>> _______________________________________________
>>>> MLS mailing list
> _______________________________________________
> MLS mailing list