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

A big thank you to Richard and Katriel for fleshing this out to this level of detail!

It is nice to see that we can potentially address two somewhat orthogonal issues with one solution. I still maintain that a deferred execution of “Proposals” adds a real benefit to the protocol, because it allows for more flexibility in scenarios where immediate execution is not needed. I also maintain that the total cost of CPU time and bandwidth might be less on average with this approach, since I foresee that Adds and Removes will cancel each other out in groups that are dormant (i.e. where no messages are exchanged).

I’d like to raise some practical questions:

 - How are Proposals encrypted? The intuition would be that we can encrypt them the same way we encrypt handshake messages today, if the proposals are issued by an existing member of the group. If they are issued by the server, they could be either in plaintext or the server could encrypt them using HPKE with the current root public key of a tree.
 - 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.
 - At the January interim we also talked about the possibility for members that were added by the server to send messages right away by encrypting them to the root of the tree. I wonder if we would pursue this idea and how we would do it in practice. The idea of instant communication is certainly nice, but it would mean that messages would be sent to the group before a Commit has happened. This in turn means that a member that is supposed to be evicted (through a erred Remove) could still potentially have the key material to decrypt those messages. Specifically, this would happen in the sequence {Add D, Remove B}, D would encrypt messages to the group that can still be read by B until the commit is issued and B is properly evicted.
 - If we go for the Proposals concept, we should probably make it very clear that clients should issue and execute Commits as soon as possible. Concrete example: if a client determines it has enough processing power and enough bandwidth, it should pre-emptively issue a Commit in groups with pending Proposals in order to heal the tree somewhat and restore all security properties. I can however see that such a strategy is not uncontroversial, so I’d be happy to hear some arguments of why we shouldn’t do this.

Raphael

> On 23 Aug 2019, at 00:17, Richard Barnes <rlb@ipv.sx> wrote:
> 
> BTW, big thanks to Raphael for setting us down this path, and to Katriel for talking this through with me earlier this week (and for coming up with the Welcome-by-Committer part).
> 
> On Thu, Aug 22, 2019 at 6:16 PM Richard Barnes <rlb@ipv.sx> 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
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls