Re: [MLS] TreeKEM: An alternative to ART

[Eric Rescorla <[e-mail]>]

Hi Cas,

Interesting point about the randomness. One more idea for the pile would be
to tell implementers to generat the new key they send by generating a
random variate Z and then sending HKDF(Tree-root, Z). In that case, you at
least don't take a regression from the current state of the tree.

-Ekr


On Tue, May 8, 2018 at 3:27 AM, Cas Cremers <[e-mail]> wrote:

> Hi all,
>
> I like the clean design of TreeKEM a lot, but I think there are plenty of
> subtle differences in terms of the security guarantees.
>
> One thing that came to mind: If ART is instantiated with a stronger AKE
> (HMQV style or NAXOS-like) then you get some protection against bad
> randomness from the setup, by integrating the long-term keys into the
> derived key. Currently, TreeKEM keys don't seem to depend at  all on the
> long-term keys. I think one can also achieve some form of protection
> against this for TreeKEM by something like we proposed in
> https://tools.ietf.org/html/draft-cremers-cfrg-randomness-improvements-00,
> but my gut feeling is that even that is not quite the same as ART with HMQV
> in terms of guarantees. Introducing something equivalent in TreeKEM seems
> cumbersome. We'll need to think this one through in a bit more detail.
>
> Best,
>
> Cas
>
>
> On Mon, May 7, 2018 at 6:40 AM Karthikeyan Bhargavan <
> [e-mail]> wrote:
>
>> Hi Katriel,
>>
>> If that's correct, it might be a good separation to make in the
>> design/analysis, and perhaps even a good idea to separate out the fresh
>> value that gets hashed into the master secret chain from the keys used in
>> the tree. (I am a little worried about attacks whereby an adversary manages
>> to receive and decrypt say h^2(k), and then derive h^5(k) and hash it into
>> the master secret to break PCS. Having agents generate one set of keys for
>> the tree and another key for the master chain might help a compositional
>> proof.)
>>
>>
>> This is an interesting idea, and I don’t see why this cannot be done,
>> especially if it helps with analysis.
>> Yes, it does mean we need to send one extra key encrypted to each
>> recipient: this doubles the computation and message size.
>> But there may be other benefits to separately sending master secret key,
>> which is to provide a proof of consistency for the updates.
>> (This is hinted at in the end of the document; we’ll try to flesh this
>> out better.)
>>
>> Best,
>> Karthik
>>
>>
>>
>>
>> One other minor nit: I think TreeKEM, like ART, might need a function
>> mapping bitstrings to KEM keypairs. This could be the same i as in ART if
>> the encryption is something like ECIES.
>>
>> best,
>> Katriel
>>
>> On Thu, 3 May 2018, at 3:36 PM, Richard Barnes 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 <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
>>
>>
>> _______________________________________________
>> MLS mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/mls
>>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>