Subject: [MLS] Removing ART; maybe adding partial-tree

From: Richard Barnes <[email-masked]>
Date: Mon, 1 Oct 2018 20:06:26 +0200

Hey all,

At the interim last week, there was agreement to remove the discussion of
ART from the protocol draft and focus on TreeKEM.  I have implemented that
change in the following pull request:

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

If a couple of folks could give a quick review, it would be appreciated.  I
also put together a PR describing how to do the "partial tree" approach
described at the interim and in my earlier message today.

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

Feedback welcome!

Thanks,
--Richard

---

From: Dave Cridland <[email-masked]>
Date: Mon, 1 Oct 2018 21:33:54 +0100

> https://github.com/mlswg/mls-protocol/pull/66
I'm not objecting to the change - I lack sufficient cryptographic knowledge
to express an opinion - but it'd be very useful to read a synopsis of the
reasoning behind it, and a summary of the discussion. I imagine future
participants would find it useful too, and of course, all decisions need to
go by the list anyway.

I reviewed the PR for clarity/typos.

> If a couple of folks could give a quick review, it would be appreciated.
> I also put together a PR describing how to do the "partial tree" approach

Also reviewed for clarity/typos. I admit I'm mildly confused as to why
adding a node needs to blank the direct path, but at the same time I'm not
sure it makes any difference. (That is, here:
https://github.com/mlswg/mls-protocol/pull/67/commits/7a7cd37aec0ceff773600564b5c9619c3d06a115#diff-a87cc9081154f564150420544170f1c9R1113
). That's probably just my lack of understanding somewhere.

>
> Feedback welcome!
>
> Thanks,
> --Richard
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Richard Barnes <[email-masked]>
Date: Mon, 1 Oct 2018 23:14:38 +0200

On Mon, Oct 1, 2018 at 10:34 PM Dave Cridland <[email-masked]> wrote:

> I'm not objecting to the change - I lack sufficient cryptographic
> knowledge to express an opinion - but it'd be very useful to read a
> synopsis of the reasoning behind it, and a summary of the discussion. I
> imagine future participants would find it useful too, and of course, all
> decisions need to go by the list anyway.
>

To recap the discussions at the interim, I think the reasons are basically
as follows, in descending order of importance:

1. ART requires each recipient of a message to do O(log N) DH operations,
where as TreeKEM only requires O(1).  This is a significant difference for
large groups / small devices.
2. TreeKEM offers the possibility of doing Add/Remove without double join
3. TreeKEM offers the possibility of being able to merge Update messages

While I don't think anyone has proved that (2) and (3) aren't possible with
ART, the fact that it's contributive makes them more difficult.

> ). That's probably just my lack of understanding somewhere.

The reason is symmetric for Add and Remove.

Recall that the invariant property the tree is supposed to have is that a
node's secret value and private key are only known to the holders of leaves
below that node in the tree.  For both Add and Remove, you need to change
the intermediate nodes above the target leaf, either to make it so that the
removed member doesn't know them or so that the added member does.  The
question is what relationship those intermediate nodes have to the sender
of the Add/Remove -- does the sender know the secret / private key or not?

On the one hand, if the sender does know the private key, then you have a
"double join" situation, where the sender knows something he's not supposed
to.  The phrase "double join" arises from the Add case, since the relevant
intermediate node secrets are known both to the new member and to the
sender of the Add.  Effectively, they both occupy the new member's leaf,
which complicates things quite a bit.  For example, if you now want to
evict the sender of the Add, you have to also evict the newly added leaf,
etc.  In the Remove case, the main impact of the double-join is that you
don't have a true Remove operation, you only have a Take-over operation.
That makes it difficult to imagine how you would ever compact the tree.

On the other hand, if the sender doesn't know the private key, then the
node has to be blank.  In the Add case, there's no way (AFAIK) to set the
intermediate node values to something that is known to (a) the existing
members under those nodes and (b) the new member, without it also being
known to the sender of the add.  So the values that get decrypted to
intermediate nodes during the Add are only for the purpose of computing the
new root secret; the intermediate nodes can't have a non-blank value
without violating the tree invariant.

It may be possible to avoid blanks in the Remove case, but we would have to
modify TreeKEM.  You could still do the "hash to the root" trick to
generate the fresh shared entropy for the epoch, but you couldn't just
overwrite the values of the intermediate nodes (as is done now).  You would
have to fold in some entropy only known to the existing members.  This is
probably worth some thought.

Anyway, hope that helps,
--Richard

---

From: Cas Cremers <[email-masked]>
Date: Tue, 2 Oct 2018 11:52:15 +0200

Hi Dave and all,

I would like to add one thing to Richard's explanation of the
rationale for dropping ART in favor of TreeKEM for now:

An important implicit assumption is that TreeKEM doesn't seem to offer
less security guarantees than ART.

However, given that the specification of protocols, threat models, and
properties isn't completely fleshed out, we don't really yet know if
this is true in any formal sense.  Analysis is continuing in parallel,
and we might need to backtrack in the worst case.

This choice is not (and must not be) about efficiency alone.

Best,

Cas

-- 
https://people.cispa.io/cas.cremers/index.html

On Mon, Oct 1, 2018 at 11:15 PM Richard Barnes <[email-masked]> wrote:
>>> At the interim last week, there was agreement to remove the discussion of ART from the protocol draft and focus on TreeKEM.  I have implemented that change in the following pull request:
>>>
>> I'm not objecting to the change - I lack sufficient cryptographic knowledge to express an opinion - but it'd be very useful to read a synopsis of the reasoning behind it, and a summary of the discussion. I imagine future participants would find it useful too, and of course, all decisions need to go by the list anyway.
>
>
> To recap the discussions at the interim, I think the reasons are basically as follows, in descending order of importance:
>
> 1. ART requires each recipient of a message to do O(log N) DH operations, where as TreeKEM only requires O(1).  This is a significant difference for large groups / small devices.
> While I don't think anyone has proved that (2) and (3) aren't possible with ART, the fact that it's contributive makes them more difficult.
>
>
>>
>>> If a couple of folks could give a quick review, it would be appreciated.  I also put together a PR describing how to do the "partial tree" approach described at the interim and in my earlier message today.
>>>
>> Also reviewed for clarity/typos. I admit I'm mildly confused as to why adding a node needs to blank the direct path, but at the same time I'm not sure it makes any difference. (That is, here: https://github.com/mlswg/mls-protocol/pull/67/commits/7a7cd37aec0ceff773600564b5c9619c3d06a115#diff-a87cc9081154f564150420544170f1c9R1113 ). That's probably just my lack of understanding somewhere.
>
>
> Recall that the invariant property the tree is supposed to have is that a node's secret value and private key are only known to the holders of leaves below that node in the tree.  For both Add and Remove, you need to change the intermediate nodes above the target leaf, either to make it so that the removed member doesn't know them or so that the added member does.  The question is what relationship those intermediate nodes have to the sender of the Add/Remove -- does the sender know the secret / private key or not?
>
> On the one hand, if the sender does know the private key, then you have a "double join" situation, where the sender knows something he's not supposed to.  The phrase "double join" arises from the Add case, since the relevant intermediate node secrets are known both to the new member and to the sender of the Add.  Effectively, they both occupy the new member's leaf, which complicates things quite a bit.  For example, if you now want to evict the sender of the Add, you have to also evict the newly added leaf, etc.  In the Remove case, the main impact of the double-join is that you don't have a true Remove operation, you only have a Take-over operation.  That makes it difficult to imagine how you would ever compact the tree.
>
> On the other hand, if the sender doesn't know the private key, then the node has to be blank..  In the Add case, there's no way (AFAIK) to set the intermediate node values to something that is known to (a) the existing members under those nodes and (b) the new member, without it also being known to the sender of the add.  So the values that get decrypted to intermediate nodes during the Add are only for the purpose of computing the new root secret; the intermediate nodes can't have a non-blank value without violating the tree invariant.
>
> It may be possible to avoid blanks in the Remove case, but we would have to modify TreeKEM.  You could still do the "hash to the root" trick to generate the fresh shared entropy for the epoch, but you couldn't just overwrite the values of the intermediate nodes (as is done now).  You would have to fold in some entropy only known to the existing members.  This is probably worth some thought.
>
> Anyway, hope that helps,
> --Richard
>
>
>>
>>
>>>
>>>
>>> Feedback welcome!
>>>
>>> Thanks,
>>> --Richard

---

From: Richard Barnes <[email-masked]>
Date: Fri, 5 Oct 2018 16:53:36 -0400

One additional possibly-nice thing here: Adds can O(1) for existing members.

Someone pointed out at the interim (I think Cas or Karthik) that in the Add
case, there's no need for the existing members of the group to fold in new
entropy into the group secrets, they just need to hash everything forward.
This means that the sender of an add doesn't need to encrypt any fresh
entropy to the group, and the existing group members don't need to decrypt
it.  The member sending the Add just needs to send the init_secret for the
group to the new member and tell everyone to ratchet forward.

Now, this doesn't mean that Adds are free.  It's just that instead of
paying in units of computation to send/process the message, you pay in
terms of future updates being more expensive, due to the ancestors of the
new member being blanked.  If you have a tree of size N and do M adds, then
the next Update/Remove will involve (log(N) + log(N) + M)
encryptions/ciphertexts in the worst case.  (The extra log(N) comes from
existing nodes being blanked out.)

That said, if the new node updates quickly, then you're back to a whole
tree and only log(N) operations.

--Richard

On Tue, Oct 2, 2018 at 5:52 AM Cas Cremers <[email-masked]> wrote:

> >>> At the interim last week, there was agreement to remove the discussion
> of ART from the protocol draft and focus on TreeKEM.  I have implemented
> that change in the following pull request:
> >>>
> > To recap the discussions at the interim, I think the reasons are
> basically as follows, in descending order of importance:
> >
> > 1. ART requires each recipient of a message to do O(log N) DH
> operations, where as TreeKEM only requires O(1).  This is a significant
> difference for large groups / small devices.
> > While I don't think anyone has proved that (2) and (3) aren't possible
> with ART, the fact that it's contributive makes them more difficult.
> >
> >
> >>
> >>> If a couple of folks could give a quick review, it would be
> appreciated.  I also put together a PR describing how to do the "partial
> tree" approach described at the interim and in my earlier message today.
> >>>
> > Recall that the invariant property the tree is supposed to have is that
> a node's secret value and private key are only known to the holders of
> leaves below that node in the tree.  For both Add and Remove, you need to
> change the intermediate nodes above the target leaf, either to make it so
> that the removed member doesn't know them or so that the added member
> does.  The question is what relationship those intermediate nodes have to
> the sender of the Add/Remove -- does the sender know the secret / private
> key or not?
> >
> > On the one hand, if the sender does know the private key, then you have
> a "double join" situation, where the sender knows something he's not
> supposed to.  The phrase "double join" arises from the Add case, since the
> relevant intermediate node secrets are known both to the new member and to
> the sender of the Add.  Effectively, they both occupy the new member's
> leaf, which complicates things quite a bit.  For example, if you now want
> to evict the sender of the Add, you have to also evict the newly added
> leaf, etc.  In the Remove case, the main impact of the double-join is that
> you don't have a true Remove operation, you only have a Take-over
> operation.  That makes it difficult to imagine how you would ever compact
> the tree.
> >
> node has to be blank..  In the Add case, there's no way (AFAIK) to set the
> > It may be possible to avoid blanks in the Remove case, but we would have
> to modify TreeKEM.  You could still do the "hash to the root" trick to

---

From: Richard Barnes <[email-masked]>
Date: Fri, 5 Oct 2018 17:04:59 -0400

Forgot to mention, I updated the PR to do this:

https://github.com/mlswg/mls-protocol/pull/67/commits/79f617200260682da5458d70f5972ef269babc7b

Also, with this change, you could really do Init as a pile of Adds stapled
together, with an Update tacked on the end if you want.

In a related vein, note that if you have a group and all you ever do are
Adds and Removes, then you basically have S/MIME / PGP with a degree of
forward secrecy; everything's linear and based on static keys.  Which
re-emphasizes the point that TreeKEM with partial trees supports a smooth
transition from that case to the full-tree, log(N) case.

On Fri, Oct 5, 2018 at 4:53 PM Richard Barnes <[email-masked]> wrote:

> Someone pointed out at the interim (I think Cas or Karthik) that in the
> Add case, there's no need for the existing members of the group to fold in
> new entropy into the group secrets, they just need to hash everything
> forward.  This means that the sender of an add doesn't need to encrypt any
> fresh entropy to the group, and the existing group members don't need to
> decrypt it.  The member sending the Add just needs to send the init_secret
> for the group to the new member and tell everyone to ratchet forward.
>
>> >>> At the interim last week, there was agreement to remove the
>> discussion of ART from the protocol draft and focus on TreeKEM.  I have
>> implemented that change in the following pull request:
>> >>>
>> > It may be possible to avoid blanks in the Remove case, but we would
>> have to modify TreeKEM.  You could still do the "hash to the root" trick to