Subject: [MLS] TreeKEM: An alternative to ART

From: Eric Rescorla <[email-masked]>
Date: Thu, 3 May 2018 07:26:49 -0700

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

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 3 May 2018 07:32:24 -0700

Oops. I forgot to attach the paper.

On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <[email-masked]> wrote:

> Code: https://github.com/bifurcation/treekem, https://github.com/
> bifurcation/treekem
> Explainer slides: https://docs.google.com/presentation/d/
> 1myiQ22ddxHAcF8uCJBXk9cdJMvAQfAw9nmKiqE5seJc/edit?usp=sharing
>

---

From: Richard Barnes <[email-masked]>
Date: Thu, 03 May 2018 14:36:55 +0000

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

---

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Thu, 03 May 2018 21:35:46 +0100

Thanks for this, it seems like a solid proposal and has a lot of good
points! A couple of things I particularly like:
 * using an abstract KEM instead of DH arithmetic is a nice, clean
   separation
 * it could well be more amenable to formal analysis, particularly for
   symbolic tools which can struggle with complicated DH trickery

One thing I would like to understand better is how the PCS guarantees
interact with merged updates.  I think (please correct me if I am
wrong!) that a key insight is that the tree is  not really part of the
update process at all. Instead, the PCS guarantees seem to come from the
fact that  each agent's update  hashes a fresh secret value N into the
master secret chain, and the tree is kind of like a broadcast encryption
scheme for distributing N.
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.)

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:
> confidential to the group members.  There's still a need for more
> mechanism to provide authentication.> 
> 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
> 
>>> 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.
>>> 
>>> 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
>>> 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
>>> 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.
>>> 
>>> a copy of the new key to the node being added.. Note that this
>>> creates>>> a double-join, which we will cover later.
>>> 
>>> 
>>> REMOVAL
>>> 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).
>>> 
>>> 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
>>> 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.
> _________________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Thu, 03 May 2018 22:21:29 +0000

On Thu, May 3, 2018 at 4:35 PM Katriel Cohn-Gordon <[email-masked]> wrote:

>    - using an abstract KEM instead of DH arithmetic is a nice, clean
>    separation
>    - it could well be more amenable to formal analysis, particularly for
> interact with merged updates. I think (please correct me if I am wrong!)
> that a key insight is that the tree is not really part of the update
> process at all. Instead, the PCS guarantees seem to come from the fact that
> each agent's update hashes a fresh secret value N into the master secret
> chain, and the tree is kind of like a broadcast encryption scheme for
> distributing N.
>

Yes, I think that's an accurate way to think about it.  To put it slightly
differently, for a member X to update, it broadcasts a fresh secret value
to the whole group except old-X, which everyone hashes into the running
group secret.  The upshot of that in the merged-update case is that if you
get updates from X, Y, Z, and apply them all, you are secure unless someone
compromises all three of X, Y, and Z -- just as if they had been issued in
sequence instead of in parallel.

> 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.)
>

I think this can be done, but it might be expensive in terms of bytes.
When you send an update, you need to distribute:

1. A new root secret to everyone
2. Private keys for nodes in your direct path, to other nodes in the
corresponding subtrees (and not others)
3. Public keys for nodes in your direct path, to nodes with those nodes in
their copaths

The current design combines (1) and (2).  You could have completely random
private keys, and a single root secret, but that doubles the number of
octets you have to encrypt each copath node.

> mapping bitstrings to KEM keypairs. This could be the same i as in ART if
> the encryption is something like ECIES.
>

Indeed, in prototyping this, I used ECIES and had to define an \iota
function.

https://github.com/bifurcation/treekem/blob/master/src/iota.js

--Richard

> 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
>
> a copy of the new key to the node being added.. Note that this creates
> *_______________________________________________*
> MLS mailing list
> [email-masked]
> _______________________________________________
> MLS mailing list
> [email-masked]

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 3 May 2018 15:30:25 -0700

> 3. Public keys for nodes in your direct path, to nodes with those nodes in

Nit: I don't think you actually need to send the public keys. It's helpful,
sure,  but you don't need it to process the update, and there are
operations where those keys aren't enough (delete of an arbitrary node).

-Ekr

---

From: Daniel Van Geest <[email-masked]>
Date: Sun, 6 May 2018 21:17:33 +0000

On 2018-05-04, 12:31 AM, "MLS on behalf of Eric Rescorla" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

On Thu, May 3, 2018 at 3:21 PM, Richard Barnes <[email-masked]<mailto:[email-masked]>> wrote:

On Thu, May 3, 2018 at 4:35 PM Katriel Cohn-Gordon <[email-masked]<mailto:[email-masked]>> wrote:
Thanks for this, it seems like a solid proposal and has a lot of good points! A couple of things I particularly like:

·         using an abstract KEM instead of DH arithmetic is a nice, clean separation
·         it could well be more amenable to formal analysis, particularly for symbolic tools which can struggle with complicated DH trickery

One thing I would like to understand better is how the PCS guarantees interact with merged updates. I think (please correct me if I am wrong!) that a key insight is that the tree is not really part of the update process at all. Instead, the PCS guarantees seem to come from the fact that each agent's update hashes a fresh secret value N into the master secret chain, and the tree is kind of like a broadcast encryption scheme for distributing N.

Yes, I think that's an accurate way to think about it.  To put it slightly differently, for a member X to update, it broadcasts a fresh secret value to the whole group except old-X, which everyone hashes into the running group secret.  The upshot of that in the merged-update case is that if you get updates from X, Y, Z, and apply them all, you are secure unless someone compromises all three of X, Y, and Z -- just as if they had been issued in sequence instead of in parallel.

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.)

I think this can be done, but it might be expensive in terms of bytes.  When you send an update, you need to distribute:

1. A new root secret to everyone
2. Private keys for nodes in your direct path, to other nodes in the corresponding subtrees (and not others)
3. Public keys for nodes in your direct path, to nodes with those nodes in their copaths

Nit: I don't think you actually need to send the public keys. It's helpful, sure,  but you don't need it to process the update, and there are operations where those keys aren't enough (delete of an arbitrary node).

-Ekr

You wouldn’t necessarily need to distribute private keys in your direct path, you could still distribute a seed (either a seed per level, or a single seed which is hashed N times depending on level) if a Derive-Key-Pair function is defined like in the original draft.

Or the MLS protocol could leave it up to the messaging ecosystem using MLS as to whether private keys or seeds should be distributed (as long as the security properties remain the same).  Distributing private keys may be expensive in terms of bytes, but distributing seeds and having all devices derive between 1 and log(n) private keys may be expensive in terms of CPU.  Depending on the constraints of the system using MLS, one option may be more efficient than the other.  And thinking ahead to when NIST’s quantum resistant algorithm recommendations come out, we don’t yet know whether the selected KEM(s?) will have large or small private keys, or will have a fast or slow keygen time.  Some of the proposed KEMs are designed to allow static keys, so they may have tradeoffs in keygen efficiency vs security or encapsulate/decapsulate time.

In general, I think TreeKEM is a great idea.  I had just recently begun tossing around ideas in my head how to integrate KEMs into ART, specifically because NISTs PQC project called for KEMs, and TreeKEM simply addresses many or all of the issues I’d encountered when trying to combine secrets from child nodes into the parent using KEMs.

Thanks,
Daniel

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 <[email-masked]<mailto:[email-masked]>> wrote:
Oops. I forgot to attach the paper.

On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:
Hi folks,

Code: https://github.com/bifurcation/treekem, https://github.com/bifurcation/treekem
Explainer slides: https://docs.google.com/presentation/d/1myiQ22ddxHAcF8uCJBXk9cdJMvAQfAw9nmKiqE5seJc/edit?usp=sharing

       H^2(d)
      /     \
    H(b)    H(d)
    / \     / \
   a   b   c   d

UPDATES

       H^2(b')
      /     \
    H(b')   H(d)
    / \     / \
   a   b'  c   d

This requires providing

  - E(pubkey(a), H(b'))

CONCURRENT UPDATES

       H^2(c')
      /     \
    H(b')   H(c')
    / \     / \
   a   b'  c   d

ADDS

REMOVAL

STATE

EFFICIENCY

DOUBLE JOINS

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

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

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

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Mon, 7 May 2018 07:40:42 +0200

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…

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, May 3, 2018 at 10:33 AM Eric Rescorla <[email-masked] <mailto:[email-masked]>> wrote:
>> On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <[email-masked] <mailto:[email-masked]>> wrote:
>> Hi folks,
>> 
>> Code: https://github.com/bifurcation/treekem <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 <https://docs.google.com/presentation/d/1myiQ22ddxHAcF8uCJBXk9cdJMvAQfAw9nmKiqE5seJc/edit?usp=sharing>
>> 
>> [email-masked] <mailto:[email-masked]>
>> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Cas Cremers <[email-masked]>
Date: Tue, 08 May 2018 10:27:35 +0000

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 <
[email-masked]> wrote:

> 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.

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Tue, 8 May 2018 13:35:26 +0200

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 <[email-masked]> 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 <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 <[email-masked] <mailto:[email-masked]>> wrote:
> Hi Katriel,
>

---

From: "Alexey Ermishkin" <[email-masked]>
Date: Wed, 9 May 2018 23:38:06 +0500

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 <[email-masked]> On Behalf Of Karthikeyan Bhargavan
Sent: Tuesday, May 8, 2018 4:35 PM
To: Cas Cremers <[email-masked]>
Cc: Katriel Cohn-Gordon <[email-masked]>; [email-masked]
Subject: Re: [MLS] TreeKEM: An alternative to ART

Hello Cas,

Best,

Karthik

On 8 May 2018, at 12:27, Cas Cremers <[email-masked] <mailto:[email-masked]> > wrote:

Hi all,

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 <[email-masked] <mailto:[email-masked]> > wrote:

Hi Katriel,

Best,

Karthik

 

best,

Katriel

--Richard

On Thu, May 3, 2018 at 10:33 AM Eric Rescorla <[email-masked] <mailto:[email-masked]> > wrote:

 

On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <[email-masked] <mailto:[email-masked]> > wrote:

Hi folks,

requested changes.

       H^2(d)

      /     \

    H(b)    H(d)

    / \     / \

   a   b   c   d

UPDATES

       H^2(b')

      /     \

    H(b')   H(d)

    / \     / \

   a   b'  c   d

This requires providing 

  - c and d with H^2(b')

do this by sending:

  - E(pubkey(a), H(b'))

 

CONCURRENT UPDATES

       H^2(c')

      /     \

    H(b')   H(c')

    / \     / \

   a   b'  c   d

 

ADDS

to the root.

 

REMOVAL

 

STATE

 

EFFICIENCY

 

DOUBLE JOINS

-Ekr

MLS mailing list

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

---

From: Richard Barnes <[email-masked]>
Date: Wed, 09 May 2018 18:52:30 +0000

On Wed, May 9, 2018 at 2:38 PM Alexey Ermishkin <[email-masked]>
wrote:

> 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.
>
> 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?
>

It depends on which resource you're lower on :)

TreeKEM requires slightly less computation, especially for passive nodes.
Receivers of an Update have to do O(log N) DH operations in ART, and O(1)
in TreeKEM.

However, TreeKEM messages are roughly twice the size of ART messages, since
they carry (public key, ciphertext) pairs instead of just public keys.

--Richard

>
>
> *From:* MLS <[email-masked]> *On Behalf Of *Karthikeyan Bhargavan
> *Sent:* Tuesday, May 8, 2018 4:35 PM
> *To:* Cas Cremers <[email-masked]>
> *Cc:* Katriel Cohn-Gordon <[email-masked]>; [email-masked]
> *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.
>
>
>
> 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,
>

---

From: Russ Housley <[email-masked]>
Date: Thu, 10 May 2018 14:01:36 -0400

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 <[email-masked]> wrote:
>

---

From: Richard Barnes <[email-masked]>
Date: Thu, 10 May 2018 19:05:21 +0000

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

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 10 May 2018 20:51:05 +0100

Fine idea/hope to attend.

If recording were possible, that'd also be good.

S

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 10 May 2018 18:25:12 -0500

> And I believe MLS can help with that.

Perhaps.  I'll note that I did raise IoT at the BoF, and the sense
of the room seemed to be that it was out of scope.  That said, the
draft charter should be going out for community review real soon
now, and we can certainly have a discussion then.

> 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? 

(The above should not be construed as a request to not explore the
answers to these questions.)

-Ben

---

From: Benjamin Beurdouche <[email-masked]>
Date: Fri, 11 May 2018 01:52:04 +0200

> now, and we can certainly have a discussion then.

I don’t think so, my feeling was that the room didn’t want to make the center of the work, but I do think that MLS is useful and might be used for IoT.

We definitely are and, in the future, should be keeping in mind constraint environments when designing MLS even though it is not the top priority...

B.

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 11 May 2018 10:26:33 -0700

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 <[email-masked]> wrote:

>> Code: https://github.com/bifurcation/treekem, https://
>> github.com/bifurcation/treekem <https://github..com/bifurcation/treekem>

---

From: Richard Barnes <[email-masked]>
Date: Wed, 30 May 2018 09:43:10 -0400

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: +1-866-432-9903 Toll: +1-408-525-6800 Access code: 201006237

---

From: Peter Saint-Andre <[email-masked]>
Date: Wed, 30 May 2018 08:45:31 -0600

Yet this is no longer true...

  > virtual interims :)

The tutorial would be beneficial, though!

Peter

On 5/30/18 7:43 AM, Richard Barnes wrote:
>     virtual interims :)  Here's a Doodle to see if there's a time that
>     looks good to folks:
> 
>     On Thu, May 10, 2018 at 2:01 PM Russ Housley <housley@vigilsec..com
>     <mailto:[email-masked]>> wrote:
> 
>>         On May 3, 2018, at 10:36 AM, Richard Barnes <[email-masked]
>>         <mailto:[email-masked]>> 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
>>         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 7:26 AM, Eric Rescorla
>>             <[email-masked] <mailto:[email-masked]>> wrote:
>>
>>                 Hi folks,
>>
>>                 arranging nodes

---

From: Richard Barnes <[email-masked]>
Date: Wed, 30 May 2018 12:26:14 -0400

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

---

From: Peter Saint-Andre <[email-masked]>
Date: Wed, 30 May 2018 10:30:46 -0600

WFM. :-)

On 5/30/18 10:26 AM, Richard Barnes wrote:
> 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 <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>       > Fortunately, we're not a WG yet, so we're not bound by the rules for
>       > virtual interims :)
> 
>     >     <mailto:[email-masked] <mailto:[email-masked]>>>
>     wrote:
>     >
>     >>         <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>     >>
>     >>         On Thu, May 3, 2018 at 10:33 AM Eric Rescorla
>     <[email-masked] <mailto:[email-masked]>
>     >>         <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>     >>
>     >>             <[email-masked] <mailto:[email-masked]>
>     <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>     >>
>     >>                 Hi folks,
>     >>
>     >>                 many ways, but is more cryptographically
>     efficient and
>     >>                 is much better
>     >>                 ones own key) can be executed completely
>     concurrently,
>     >>                 merging all the
>     >>                 requested changes.
>     >>
>     >>                 in a binary tree. In the steady state, each node
>     i has
>     >>                 a key pair but
>     >>                 encrypting to the appropriate set of parent
>     nodes. So,
>     >>                 we can
>     >>                 do this by sending:
>     >>
>     >>                   - E(pubkey(a), H(b'))
>     >>                 of concurrent updates, just by applying them in
>     order.
>     >>                 Again,
>     >>                 The way to handle (1) is probably to have some
>     defined
>     >>                 "window"
>     >>                 to hold onto its old key until that window has
>     passed.
>     >>                 (2) can
>     >>                 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
>     >>                 you need to be able to access every node's public
>     key.
>     >>                 However,
>     >>                 The paper contains more details. but generally
>     TreeKEM
>     >>                 is somewhat
>     >>                 group member. In the case of GROUPADD, the double
>     join
>     >>                 will resolve itself
>     >>         [email-masked] <mailto:[email-masked]> <mailto:[email-masked]
>     <mailto:[email-masked]>>
>     >         [email-masked] <mailto:[email-masked]> <mailto:[email-masked]
>     <mailto:[email-masked]>>