Re: [MLS] TreeKEM: An alternative to ART

["Alexey Ermishkin" <[e-mail]>]

Hello everyone,

There’s a use case which I think should be taken into consideration. 

IoT.

I myself had no idea about it but it turns out IoT devices often communicate in groups like one group for one apartment/room/building, etc. And they do broadcasting all the time to each other.

Prerequisites is that every device knows either other device’s public keys or a root key that signs each of them so that could establish trust.

The second thing that I know is that right now there’s a complex procedure which involves transmitting a symmetric group key to each member of the group using whatever they have now like ECIES.

And I believe MLS can help with that.

So, my question is, in terms of resources, what would be the better choice for such medium sized but low on CPU and RAM groups? Is it ART or TreeKEM? 

 

From: MLS <[e-mail]> On Behalf Of Karthikeyan Bhargavan
Sent: Tuesday, May 8, 2018 4:35 PM
To: Cas Cremers <[e-mail]>
Cc: Katriel Cohn-Gordon <[e-mail]>; [e-mail]
Subject: Re: [MLS] TreeKEM: An alternative to ART

 

Hello Cas,

 

It would be great to tease out the differences, especially with regards to implicit threats and goals that we’ve not yet made explicit in MLS.

 

Broken randomness is a good example. Do we wish to resist bad randomness at the group creator, for example?

If we can trust the creator to have access to a fresh key K, which it then uses to derive the initial leaf keys for the tree, 

we would then be resistant to bad randomness at all other devices, yes?

 

Best,

Karthik

 





On 8 May 2018, at 12:27, Cas Cremers <[e-mail] <mailto:[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] <mailto:[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] <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
 <mailto:[e-mail]> [e-mail]
 <https://www.ietf.org/mailman/listinfo/mls> https://www.ietf.org/mailman/listinfo/mls

 

_______________________________________________
MLS mailing list
[e-mail] <mailto:[e-mail]> 
https://www.ietf.org/mailman/listinfo/mls