Re: [MLS] TreeKEM: An alternative to ART

[Richard Barnes <[e-mail]>]

Fortunately, we're not a WG yet, so we're not bound by the rules for
virtual interims :)  Here's a Doodle to see if there's a time that looks
good to folks:

https://doodle.com/poll/u84kpg2i4vfvnmsz

On Thu, May 10, 2018 at 2:01 PM Russ Housley <[e-mail]> wrote:

> I think that a virtual interim to go through a tutorial of TreeKEM would
> be very useful.
>
> Russ
>
>
> On May 3, 2018, at 10:36 AM, Richard Barnes <[e-mail]> wrote:
>
> Just for context: Note that TreeKEM, like ART, is an "inner loop" /
> "subroutine" for MLS.  It handles the establishment of a key that's
> confidential to the group members.  There's still a need for more mechanism
> to provide authentication.
>
> Speaking of protocol, in protocol terms, TreeKEM, while we haven't
> elaborated a precise protocol, if you look at the very basic sketch that's
> in the repo EKR linked, the protocol looks very similar to what we have for
> ART now.  Basically, where ART sends public keys, TreeKEM needs to send
> (public key, PKE ciphertext) pairs.  So there's a bit of additional
> communications overhead, but not a dramatic reworking of the messages.
>
> Having spent some time with this approach, I appreciate that it can be
> kind of hard to digest; it has a few more moving parts than ART.  I would
> be happy to set up a call sometime if people wanted to talk this through.
>
> --Richard
>
> On Thu, May 3, 2018 at 10:33 AM Eric Rescorla <[e-mail]> wrote:
>
>> Oops. I forgot to attach the paper.
>>
>>
>> On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <[e-mail]> wrote:
>>
>>> Hi folks,
>>>
>>> Several of us (Karthik, Richard, and I) have been working on an
>>> alternative to ART which we call TreeKEM. TreeKEM parallels ART in
>>> many ways, but is more cryptographically efficient and is much better
>>> at handling concurrent changes. The most common behaviors (updating
>>> ones own key) can be executed completely concurrently, merging all the
>>> requested changes.
>>>
>>> We've attached a draft technical paper describing the details, and
>>> some slides, but here's a brief overview of TreeKEM.
>>>
>>> Code: https://github.com/bifurcation/treekem,
>>> https://github.com/bifurcation/treekem
>>> Explainer slides:
>>> https://docs.google.com/presentation/d/1myiQ22ddxHAcF8uCJBXk9cdJMvAQfAw9nmKiqE5seJc/edit?usp=sharing
>>>
>>> As with ART, TreeKEM addresses the scaling problem by arranging nodes
>>> in a binary tree. In the steady state, each node i has a key pair but
>>> instead of having two siblings do DH to determine their shared key, we
>>> derive the shared key by hashing the key of the last node to update.
>>> As before, each node knows all the keys to its parents.
>>>
>>> Imagine we have the four node tree a, b, c, d which was constructed
>>> in that order. The private keys at each vertex are shown below.
>>>
>>>        H^2(d)
>>>       /     \
>>>     H(b)    H(d)
>>>     / \     / \
>>>    a   b   c   d
>>>
>>>
>>> UPDATES
>>> Now say that b wants to update its key to b', giving us the tree:
>>>
>>>        H^2(b')
>>>       /     \
>>>     H(b')   H(d)
>>>     / \     / \
>>>    a   b'  c   d
>>>
>>> This requires providing
>>>
>>>   - a with H(b') -- note that a can compute H^2(b') for itself.
>>>   - c and d with H^2(b')
>>>
>>> Recall that you can encrypt to any subset of the tree by just
>>> encrypting to the appropriate set of parent nodes. So, we can
>>> do this by sending:
>>>
>>>   - E(pubkey(a), H(b'))
>>>   - E(pubkey(H^2(d)), H^2(b'))
>>>
>>> Where pubkey(k) gives the public key derived from private key k.
>>>
>>> As with ART, you then mix the new tree root (H^2(b')) into the current
>>> operational keys and use the result to derive the actual working keys.
>>>
>>>
>>> CONCURRENT UPDATES
>>> The big win in TreeKEM is that you can handle an arbitrary number
>>> of concurrent updates, just by applying them in order. Again,
>>> consider our starting tree, but assume that b and c both try to
>>> update at once. a thus receives two updates
>>>
>>>   - E(pubkey(a), H(b'))       [b's update]
>>>   - E(pubkey(H(b)), H^2(c'))  [c's update]
>>>
>>> If we apply these in order b, c we get the tree:
>>>
>>>        H^2(c')
>>>       /     \
>>>     H(b')   H(c')
>>>     / \     / \
>>>    a   b'  c   d
>>>
>>> a can easily compute this.
>>>
>>> In order to make this work, we need two things:
>>>
>>> 1. a needs to keep a copy of its current tree around until it has
>>>    received all updates based on that tree
>>> 2. there needs to be an unambiguous ordering of updates
>>>
>>> The way to handle (1) is probably to have some defined "window"
>>> of time during which an update can be received. The node needs
>>> to hold onto its old key until that window has passed. (2) can
>>> be handled by having the messaging system provide a consistent
>>> order and then agreeing to apply updates consecutively. If we
>>> want to concurrently apply other changes, we may need to sort
>>> based on change type within the window.
>>>
>>>
>>> ADDS
>>> In order to add itself to the group (USERADD), a node merely puts
>>> itself at the right position in the tree and, generates a random key,
>>> and then sends the appropriate keying material to everyone in its path
>>> to the root.
>>>
>>> In order to add another node to the group (GROUPADD), the adding
>>> node does exactly the same thing as with a USERADD, but also sends
>>> a copy of the new key to the node being added.. Note that this creates
>>> a double-join, which we will cover later.
>>>
>>>
>>> REMOVAL
>>> In order to remove another node from the tree, the removing node
>>> sends the same message that the evicted node would have sent if
>>> it had sent an update, but with a new key not known to the evicted
>>> node (note that this naturally omits the evicted node, because you
>>> encrypt to the co-path). This also creates a double-join, where the
>>> removing node knows the dummy key.
>>>
>>>
>>>
>>> STATE
>>> In order to receive messages, a node need only keep its secret keys,
>>> which range between 1 key (if it was the last to update) and log(N)
>>> keys (in the worst case).
>>>
>>> In the best case, in order to update, a node needs to also know
>>> the public keys for everyone on its co-path. However.
>>>
>>> In order to be able to do deletes, a node also needs to be able
>>> to get the public key for any node in the tree (leaf or internal).
>>> It's easy to see this by realizing that to delete a node you need
>>> to encrypt a new key to its sibling, and so to delete any node,
>>> you need to be able to access every node's public key. However,
>>> a node need not store this information, but can retrieve it
>>> on demand when it needs to delete another node.
>>>
>>>
>>> EFFICIENCY
>>> The paper contains more details. but generally TreeKEM is somewhat
>>> more efficient in terms of asymmetric crypto operations than ART.
>>>
>>>
>>> DOUBLE JOINS
>>> Like ART, TreeKEM has double-join problems whenever one group member
>>> provides a service (or a disservice, in the case of remove) for another
>>> group member. In the case of GROUPADD, the double join will resolve
>>> itself
>>> as soon as the added node updates its key. However in the case of
>>> REMOVE, this cannot happen, and so double join needs to be
>>> dealt with in some other way.
>>>
>>> One option is to have selective updates: each node keeps track of
>>> extra tree state and uses it to control its updates. For instance,
>>> if we never send updates to deleted nodes, than as soon as a deleted
>>> node's sibling sends an update, the double-join will be resolved.
>>> In a more sophisticated -- but also more expensive to implement --
>>> version, we track which nodes control the keys of other nodes and
>>> REMOVE all affected nodes when we do a delete.
>>>
>>> -Ekr
>>>
>>>
>> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>