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

[Richard Barnes <[e-mail]>]

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 <[e-mail]> wrote:

> 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 <[e-mail]> wrote:
>
>> 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 <[e-mail]> wrote:
>> >
>> >
>> >
>> > On Mon, Oct 1, 2018 at 10:34 PM Dave Cridland <[e-mail]>
>> wrote:
>> >>
>> >>
>> >>
>> >> On Mon, 1 Oct 2018 at 19:06, Richard Barnes <[e-mail]> wrote:
>> >>>
>> >>> 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
>> >>>
>> >>
>> >> 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.
>> >
>> >
>> >>
>> >> 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 described at the interim and in my earlier message today.
>> >>>
>> >>> https://github.com/mlswg/mls-protocol/pull/67
>> >>
>> >>
>> >> 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.
>> >
>> >
>> > 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
>> >
>> >
>> >>
>> >>
>> >>>
>> >>>
>> >>> Feedback welcome!
>> >>>
>> >>> Thanks,
>> >>> --Richard
>> >>> _______________________________________________
>> >>> MLS mailing list
>> >>> [e-mail]
>> >>> https://www.ietf.org/mailman/listinfo/mls
>> >
>> > _______________________________________________
>> > MLS mailing list
>> > [e-mail]
>> > https://www.ietf.org/mailman/listinfo/mls
>>
>