Re: [MLS] TreeKEM: An alternative to ART

[Richard Barnes <[e-mail]>]

I'll claim that this isn't an official WG meeting, just a tutorial on the
side.  We're not going to make any decisions anyway.

--Richard

On Wed, May 30, 2018 at 10:45 AM Peter Saint-Andre <[e-mail]>
wrote:

> 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
> >
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>