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

Karthik Bhargavan <> Tue, 27 August 2019 17:23 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 4FEE6120130 for <>; Tue, 27 Aug 2019 10:23:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -6.898
X-Spam-Status: No, score=-6.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id A0ucKZeIpy28 for <>; Tue, 27 Aug 2019 10:23:55 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 79209120074 for <>; Tue, 27 Aug 2019 10:23:54 -0700 (PDT)
X-IronPort-AV: E=Sophos;i="5.64,438,1559512800"; d="scan'208,217";a="399083236"
Received: from (HELO mp141-pro.home) ([]) by with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 27 Aug 2019 19:23:51 +0200
From: Karthik Bhargavan <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_87D6BEA0-A938-4628-A76C-71C84536B9CB"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\))
Date: Tue, 27 Aug 2019 13:23:46 -0400
In-Reply-To: <>
Cc: Stephen Farrell <>, Messaging Layer Security WG <>, Raphael Robert <>
To: Richard Barnes <>
References: <> <> <> <> <> <> <> <> <> <> <>
X-Mailer: Apple Mail (2.3445.104.11)
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: Tue, 27 Aug 2019 17:23:59 -0000

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.


> --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
>> <>
>> <>