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

From: Richard Barnes <[email-masked]>
Date: Wed, 18 Sep 2019 18:16:08 -0400

I've written up a PR that implements this proposal:

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

Please take a look; there's plenty in there to disagree about, and several
OPEN ISSUEs.  I would like to have this landed in the next week or so, so
that we can rebase some other PRs on it (e.g., non-destructive add) and
publish a new draft for the interim.

Thanks,
--Richard

On Thu, Aug 22, 2019 at 6:16 PM Richard Barnes <[email-masked]> wrote:

> Hey all,
>
> I’d like to pose a question to the group of whether we should do
> “laziness” or not.   The complete form will be long, but the short version
> is: Do we care enough about DH overhead and server-initiated operations to
> do a pretty significant refactor and possibly add some complexity to the
> protocol?
>
> I would like to get a go/no-go on this idea before writing a PR, since
> it's going to be a big PR.  And it would be helpful to make that decision
> in the next week or two, so that we can get the edits done and a new
> version out a bit in advance of the interim.  So let's get this party
> started!
>
> # Objectives
>
> The overall goal is to meet two objectives:
>
> 1. Not requiring DH operations in groups where no messaging is happening
> 2. Allow some flavor of server-initiated Add and Remove
>
> The first of these objectives was raised by Raphael some time ago; see his
> presentation at the January interim for more details [1].  The second has
> been a long-outstanding feature request, from Facebook and Cisco, among
> others.
>
> The useful insight is that both of these require deferred operations.  In
> the first case, you want to defer DH operations until someone wants to send
> a message.  In the second case, you might have the server propose an
> operation that it can’t do, so that the execution of the operation is
> deferred until someone in the group does it.
>
> # Proposal
>
> The proposal here is to refactor the protocol from “immediate mode” to
> “deferred mode”.  None of the underlying tree math changes, just how we
> talk about it.
>
> * Add, Remove, and Update become “Proposals” that describe an operation,
> rather than carrying the information to accomplish the information
> immediately
>     * Add = “Please add ${ClientInitKey}”
>     * Update = “Please replace the leaf at ${index} with ${key} and blank
> its direct path”
>     * Remove = “Please  remove the member at ${index}
> * Each epoch contains a set of proposals, followed by a Commit message
>     * None of the proposed changes take effect until the Commit message
>     * If there are outstanding proposals, you SHOULD send a Commit before
> sending a message
> * A Commit message contains:
>     * A description of which proposals were applied and how
>     * In particular, the committer chooses the positions where new members
> are added
>     * A direct path that KEMs new entropy to the group (basically an
> update from the Committer)
> * The committer also generates Welcome messages for any new participants
>     * With handshake encryption, the Welcome just needs to have the key
> for the Commit
>     * The Commit should commit to the state of the tree after the
> proposals are executed (just like handshake messages do today)
>     * ... so the new joiner doesn't need to see the proposals, just the
> Commit
>
> # Observations
>
> * In the framework above, there's no need to synchronize proposals, just
> Commits
> * If the Commit includes the proposals by value or hash, then we can just
> run the transcript over the Commit messages, and the proposals will be
> included transitively
> * Note that proposals can overwrite one another, e.g., an update and a
> remove for the same slot
> * If we refactor in the above form, an application could reconstruct what
> we have now by always sending a (Proposal, Commit) combo
> * In fact, one way to view this is as splitting off the Commit from the
> current Handshake messages
>
> # Benefits
>
> * We get the objectives that we set out to achieve:
>     * Quiescent groups can just pile up proposals, and Commit before
> messaging
>     * The server can synthesize Add and Remove proposals as long as
> clients have a way to authenticate them (e.g., a designated sender index
> for the server)
> * There's a certain conceptual simplicity to only having one message that
> advances the group state
> * With regard to the "ghost account" concerns that DKG raised at the IETF
> meeting, this ensures that the proposals to add users are part of the
> transcript, thus visible to the group
>
> # Costs
>
> * The longer you go before a Commit, the more expensive the Commit is,
> since the proposals are all destructive, in the sense that they blank out
> parts of the tree
> * The logic for a new joiner might get more complicated, since they're not
> actually added until the Commit.  In particular, you can't send an Add
> proposal and have the new member immediately able to transmit, you have to
> do a Commit as well.
> * At least in the form above, we lose the property that Adds are constant
> time, since you would always do an asymmetric ratchet operation.  If this
> were a problem, you could special-case it (if the Commit only has Adds...)
> * Retry logic might get more complicated; need to wait for a Commit before
> I know whether my change made it in
> * The protocol gets more verbose since you need the glue to refer to the
> proposals from the Commit
>
> -----
>
> Thanks for reading all the way to the bottom!
>
> Personally, I'm pretty split on this.  On the one hand, I think this can
> be done pretty elegantly.  On the other hand, it does feel more complex,
> and I'm worried we're spending a lot of complexity budget on some fairly
> niche use cases.  On the third hand, I do think we need server-initiated
> Add/Remove, and all the approaches that come to mind end up looking kind of
> like this
>
> Happy to have questions / comments here, or if there’s enough interest, it
> might be good to have a quick phone call.
>
> —Richard
>

---

From: Jon Millican <[email-masked]>
Date: Thu, 19 Sep 2019 13:59:42 +0000

Sorry for jumping onto this thread quite late, but just a couple comments to add:

>  Can Update Proposals be issued by anyone but the member itself? If we say yes, the analysis will be more straight forward, but it is also more limited. If we say no, the question remains who can issue them. They could be issued by the server or another member. Right now I don’t see why another member should be allowed to do so, but I could think of reasons why the server should be allowed to do so (multi-device context). We should again be very careful w.r.t the ghost user scenario in order to avoid the possibility that the server can sneak in a malicious participant that way.

I don't see a good reason for anyone other than a leaf-owner to ever issue an update to that leaf. If we treat multi-device as a special case of group, then the server would also not need to do this – it could instead just issue adds and removes as devices change.

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

To stress this point, server-controlled group membership is a practical necessity in many cases. I can’t think of any significant messaging service that does not allow account resets, and I believe the majority will allow multi-device/group threads to continue when this happens. For example, membership of a thread in Messenger is based on user account rather than device – if a device is attached to a given user account, then it is inherently in any threads that this user account is also in. Logging into an account is not a cryptographic process attached to some other device, but authenticating to an online service (e.g. username + password). I believe Wire follows the same model. In this world, a device which logs into an account needs to be able to not only receive future messages to that account’s threads (which could be achieved at the application level without server-add), but also to send messages to any of these threads (potentially before any other device in the thread has come online) – which would be more challenging to implement at the application level. For this reason, I’d strongly favour server add in the protocol.

Jon

From: MLS <[email-masked]> on behalf of Katriel Cohn-Gordon <[email-masked]>
Date: Friday, 30 August 2019 at 17:41
To: "[email-masked]" <[email-masked]>
Cc: Messaging Layer Security WG <[email-masked]>
Subject: Re: [MLS] Proposal: Proposals (was: Laziness)

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.

--katriel

On Tue, 27 Aug 2019, at 6:23 PM, Karthik Bhargavan wrote:

Hi Richard,

On 23 Aug 2019, at 18:48, Richard Barnes <[email-masked]<mailto:[email-masked]>> 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 <[email-masked]<mailto:[email-masked]>> 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 <[email-masked]<mailto:rlb@ipv..sx>> wrote:

On Fri, Aug 23, 2019 at 10:21 AM Stephen Farrell <[email-masked]<mailto:[email-masked]>> 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
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/mls<https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_mls&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=M0CVEJydBVUX_bvEqMa84Q&m=gabsgG53OsRWJChybmvBPhP4Bww6dRbrbur9MZMqSbA&s=jPen3uhkJSug-XGStQZg7vWn_ys1LeXbX5NwQS0CwCg&e=>
_______________________________________________
MLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Thu, 19 Sep 2019 10:24:19 -0400

I think the current PR is pretty good w.r.t. these comments.

W.r.t. Updates: "An Update proposal requests that the sender's leaf node in
the tree be updated with a new HPKE public key."  No affordance for Updates
other than by the leaf holder.

W.r.t. Server-initiated: That's not in this PR, but I think it lays the
groundwork.  In the sense that once Proposals are split out, the
constraints on who can make a proposal can be looser than who can make a
Commit.  So for example, you could configure the application to accept
Proposals from the server and include them in the next Commit.  That takes
care of server-initiated Remove completely.  For server-initiated Add, you
would also need a way for someone external to the group to send to the
group, for the interim period in between Proposal/Add and  Commit.  But
that seems like it can be handled in a future iteration.

--Richard

On Thu, Sep 19, 2019 at 10:00 AM Jon Millican <[email-masked]> wrote:

> >  Can Update Proposals be issued by anyone but the member itself? If we
> say yes, the analysis will be more straight forward, but it is also more
> limited. If we say no, the question remains who can issue them. They could
> be issued by the server or another member. Right now I don’t see why
> another member should be allowed to do so, but I could think of reasons why
> the server should be allowed to do so (multi-device context). We should
> again be very careful w.r.t the ghost user scenario in order to avoid the
> possibility that the server can sneak in a malicious participant that way.
>
>
>
> I don't see a good reason for anyone other than a leaf-owner to ever issue
> an update to that leaf. If we treat multi-device as a special case of
> group, then the server would also not need to do this – it could instead
> just issue adds and removes as devices change.
>
>
>
>
>
> > 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.
>
>
>
> To stress this point, server-controlled group membership is a practical
> necessity in many cases. I can’t think of any significant messaging service
> that does not allow account resets, and I believe the majority will allow
> multi-device/group threads to continue when this happens. For example,
> membership of a thread in Messenger is based on user account rather than
> device – if a device is attached to a given user account, then it is
> inherently in any threads that this user account is also in. Logging into
> an account is not a cryptographic process attached to some other device,
> but authenticating to an online service (e.g. username + password). I
> believe Wire follows the same model. In this world, a device which logs
> into an account needs to be able to not only receive future messages to
> that account’s threads (which could be achieved at the application level
> without server-add), but also to send messages to any of these threads
> (potentially before any other device in the thread has come online) – which
> would be more challenging to implement at the application level. For this
> reason, I’d strongly favour server add in the protocol.
>
>
>
> Jon
>
>
>
>
>
> *From: *MLS <[email-masked]> on behalf of Katriel Cohn-Gordon <
> [email-masked]>
> *Date: *Friday, 30 August 2019 at 17:41
> *To: *"[email-masked]" <[email-masked]>
> *Cc: *Messaging Layer Security WG <[email-masked]>
> *Subject: *Re: [MLS] Proposal: Proposals (was: Laziness)
>
>
>
> 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.
>
>
>
> --katriel
>
>
>
> On 23 Aug 2019, at 18:48, Richard Barnes <[email-masked]> wrote:
>
>
>
> 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.
>
> 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.
>
> 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.
>
>
>
> 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 <
> [email-masked]> 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 <[email-masked] <rlb@ipv..sx>> wrote:
>
>
>
>
>
>
>
> On Fri, Aug 23, 2019 at 10:21 AM Stephen Farrell <
> [email-masked]> wrote:
>
>
>
> Hiya,
>
>
>
> 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:
>
>
>
> - The obvious way to add non-member signers is to reserve a block of
> indices (say 0xFFFFFFxx) that can correspond to application-specific
> entities
>
> 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
>
>
>
>
>
>
>
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_mls&d=DwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=M0CVEJydBVUX_bvEqMa84Q&m=gabsgG53OsRWJChybmvBPhP4Bww6dRbrbur9MZMqSbA&s=jPen3uhkJSug-XGStQZg7vWn_ys1LeXbX5NwQS0CwCg&e=>
>