Re: [MLS] TreeKEM: An alternative to ART

[Peter Saint-Andre <[e-mail]>]

Yet this is no longer true...

  > Fortunately, we're not a WG yet, so we're not bound by the rules for
  > virtual interims :)

The tutorial would be beneficial, though!

Peter

On 5/30/18 7:43 AM, Richard Barnes wrote:
> Sorry, I dropped the ball on this, and now we're in the midst of these
> dates.  Based on the responses, I propose we do tomorrow at 11:00 ET ==
> 15:00 UTC.
> 
> https://www.timeanddate.com/worldclock/fixedtime.html?msg=TreeKEM+overview+%2F+discussion&iso=20180531T11&p1=263&ah=1
> 
> The below Webex details should work:
> 
> Join from a video conferencing system or application
> Dial https://cisco.webex.com/meet/richbarn
> Join by Phone
> Toll free: [phone] Toll: [phone] Access code: 201006237
> 
> 
> 
> On Thu, May 10, 2018 at 3:05 PM Richard Barnes <[e-mail]> wrote:
> 
>     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 <housley@vigilsec..com
>     <mailto:[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]
>>         <mailto:[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]
>>         <mailto:[e-mail]>> wrote:
>>
>>             Oops. I forgot to attach the paper.
>>
>>
>>             On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla
>>             <[e-mail] <mailto:[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] <mailto:[e-mail]>
>>         https://www.ietf.org/mailman/listinfo/mls
> 
>         _______________________________________________
>         MLS mailing list
>         [e-mail] <mailto:[e-mail]>
>         https://www.ietf.org/mailman/listinfo/mls
> 
> 
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>