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

From: Richard Barnes <[email-masked]>
Date: Thu, 22 Aug 2019 18:16:43 -0400

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: Richard Barnes <[email-masked]>
Date: Thu, 22 Aug 2019 18:17:46 -0400

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 <[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
>
>     * A direct path that KEMs new entropy to the group (basically an
> update from the Committer)
>     * 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)
>     * 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)
> 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

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 23 Aug 2019 10:08:04 +0100

Sorry for not following mls in detail but can you explain
how:

> 2. Allow some flavor of server-initiated Add and Remove

...compares to the status quo ante?

Thanks,
S.

---

From: Raphael Robert <[email-masked]>
Date: Fri, 23 Aug 2019 12:21:33 +0200

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 <[email-masked]> 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).
> 
> 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
> 
> 1.. Not requiring DH operations in groups where no messaging is happening
> 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
>     * Update = “Please replace the leaf at ${index} with ${key} and blank its direct path”
>     * If there are outstanding proposals, you SHOULD send a Commit before sending a message
>     * 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)
>     * 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
> 
>     * 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
> 
> -----
> 
> 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
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Raphael Robert <[email-masked]>
Date: Fri, 23 Aug 2019 12:24:41 +0200

Right now, Add and Remove handshake messages have to be signed by an existing member of the group. There is no way for the server to make any changes to the group membership.

> On 23 Aug 2019, at 11:08, Stephen Farrell <[email-masked]> wrote:
> 
> Signed PGP part
> 
> <0x5AB2FAF17B172BEA.asc>

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 23 Aug 2019 12:26:30 +0100

Hiya,

On 23/08/2019 11:24, Raphael Robert wrote:
> Right now, Add and Remove handshake messages have to be signed by an
> existing member of the group. There is no way for the server to make
> any changes to the group membership.

Thanks. As you note in your other mail, that seems a
bit concerning, from a potentially ghostly point of
view. My initial reaction (again with the "benefit"
of not having kept up to date with the drafts:-) is
that a service using MLS could put itself in a position
to do the same thing within the application layer if
necessary, so it'd seem better for it not to be a
feature of the MLS protocol.

I've no opinion on the general idea of proposals, my
concern is only really about a non-member of the group
(the server or anyone else) being able to control
group membership like that, for what I guess would
effectively be all applications using MLS.

Cheers,
S.

>> Sorry for not following mls in detail but can you explain how:
>> 
>> Thanks, S. <0x5AB2FAF17B172BEA.asc>
>> 
>> 
> 
>

---

From: Raphael Robert <[email-masked]>
Date: Fri, 23 Aug 2019 14:17:53 +0200

The ghost user scenario is precisely what we want to avoid. In Richard’s Proposals draft, every Proposal has to be validated by a Commit message, and the latter can only be issued by an existing member of the group. Therefore the server still cannot control the group membership, it can rather only make proposals on how the membership list should be modified. Naturally we need to make sure that everything works as intended.

> On 23 Aug 2019, at 13:26, Stephen Farrell <[email-masked]> wrote:
> 
> 
> Hiya,
>

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 23 Aug 2019 13:26:03 +0100

Hiya,

On 23/08/2019 13:17, Raphael Robert wrote:
> The ghost user scenario is precisely what we want to avoid. In
> Richard’s Proposals draft, every Proposal has to be validated by a
> Commit message, and the latter can only be issued by an existing
> member of the group. Therefore the server still cannot control the
> group membership, it can rather only make proposals on how the
> membership list should be modified. Naturally we need to make sure
> that everything works as intended.

Sure, I get that. My concern is that I'm not clear how
such proposals could meaningfully be handled by members
in general - it seems like it could be quite a footgun.

Cheers,
S.

>>> Right now, Add and Remove handshake messages have to be signed by
>>> an existing member of the group. There is no way for the server
>>> to make any changes to the group membership.
>> 
>> Thanks. As you note in your other mail, that seems a bit
>> concerning, from a potentially ghostly point of view. My initial
>> reaction (again with the "benefit" of not having kept up to date
>> with the drafts:-) is that a service using MLS could put itself in
>> a position to do the same thing within the application layer if 
>> necessary, so it'd seem better for it not to be a feature of the
>> MLS protocol.
>> 
>> I've no opinion on the general idea of proposals, my concern is
>> only really about a non-member of the group (the server or anyone
>> else) being able to control group membership like that, for what I
>> guess would effectively be all applications using MLS.
>> 
>> Cheers, S.
>> 
>>> 
> _______________________________________________ MLS mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/mls
>

---

From: Richard Barnes <[email-masked]>
Date: Fri, 23 Aug 2019 10:10:40 -0400

> in general - it seems like it could be quite a footgun.

It was pointed out in the discussion at IETF 105 that given that vendors
seem to want server-initiated Add/Remove, they will do it somehow, either
using a mechanism in the protocol, or as you say, using something at the
application layer.

It seems to me that between those two options, having it in the protocol is
the better one.  It at least provides clear accountability for who is in
the group and how they were added: The records of who made the proposal and
who committed the proposal are both in the transcript, and thus have to be
revealed to everyone.  In the application-layer alternative, you'd still
have the commiter in the transcript, but the server could just whisper to
one participant, and nobody else would need to know that the server had
anything to do with the transaction.

I'm not clear on what you mean by "meaningfully handled by members".  Even
in the Proposal / server-initiated-in-the-protocol case, messages from the
server are authenticated, and endpoints should be expected to apply
authorization policy to them.  (The presumption would be that the clients
in a given environment would be configured to trust their servers.)  In
addition, like current Add messages, Add proposals would have the full
ClientInitKey for the proposed member, which means that members can see
their credential and possibly make a decision based on that.  So there are
two authenticated identities to use for authorization decisions, (1) the
server / proposer's identity, and (2) the new member's identity.

There are some sharp edges here, but that will be true with any
server-initiated case (whether or not in this document), and I think the
proposal here provides good guard rails to guide people to better solutions.

--Richard

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 23 Aug 2019 15:21:05 +0100

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.

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.

---

From: Richard Barnes <[email-masked]>
Date: Fri, 23 Aug 2019 10:48:05 -0400

> 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

---

From: Karthik Bhargavan <[email-masked]>
Date: Fri, 23 Aug 2019 13:22:17 -0400

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]> wrote:
> 
> 
> 
> On Fri, Aug 23, 2019 at 10:21 AM Stephen Farrell <[email-masked] <mailto:[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:
> 
> - Right now, clients are expected to maintain a list of members' signing keys
> - 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  
> 
>  
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Richard Barnes <[email-masked]>
Date: Fri, 23 Aug 2019 18:48:01 -0400

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

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.

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.

--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 Fri, Aug 23, 2019 at 10:21 AM Stephen Farrell <
> [email-masked]> wrote:
>
>>
>> Hiya,
>>

---

From: Karthik Bhargavan <[email-masked]>
Date: Tue, 27 Aug 2019 13:23:46 -0400

Hi Richard,

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

---

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Fri, 30 Aug 2019 17:40:03 +0100

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:
>> On Fri, Aug 23, 2019 at 1:22 PM Karthik Bhargavan <[email-masked]> wrote:
>>> Hello All,
>>> 
>>>> On Fri, Aug 23, 2019 at 10:21 AM Stephen Farrell <[email-masked]> wrote:
>>>>> 
>>>>> Hiya,
>>>>>