Re: [MLS] TreeKEM: An alternative to ART
Daniel Van Geest <Daniel.VanGeest@isara.com> Sun, 06 May 2018 21:21 UTC
Return-Path: <Daniel.VanGeest@isara.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1DB8D126C19 for <mls@ietfa.amsl.com>; Sun, 6 May 2018 14:21:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id cqQin12E1vgg for <mls@ietfa.amsl.com>; Sun, 6 May 2018 14:21:30 -0700 (PDT)
Received: from esa2.isaracorp.com (esa2.isaracorp.com [207.107.152.176]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id AE377120713 for <mls@ietf.org>; Sun, 6 May 2018 14:21:29 -0700 (PDT)
Received: from 172-1-110-12.lightspeed.sntcca.sbcglobal.net (HELO cas.isaracorp.com) ([172.1.110.12]) by ip2.isaracorp.com with ESMTP; 06 May 2018 21:21:28 +0000
Received: from V0501WEXGPR01.isaracorp.com (10.5.8.20) by V0501WEXGPR01.isaracorp.com (10.5.8.20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1466.3; Sun, 6 May 2018 17:17:33 -0400
Received: from V0501WEXGPR01.isaracorp.com ([fe80::d802:5aec:db34:beba]) by V0501WEXGPR01.isaracorp.com ([fe80::d802:5aec:db34:beba%6]) with mapi id 15.01.1466.003; Sun, 6 May 2018 17:17:33 -0400
From: Daniel Van Geest <Daniel.VanGeest@isara.com>
To: Eric Rescorla <ekr@rtfm.com>, Richard Barnes <rlb@ipv.sx>
CC: Katriel Cohn-Gordon <me@katriel.co.uk>, "mls@ietf.org" <mls@ietf.org>
Thread-Topic: [MLS] TreeKEM: An alternative to ART
Thread-Index: AQHT4ur2qffPVVEGiEKDo5M1/KBUbKQeVFIAgAABQ4CAAGRDAIAAHYqAgAACf4CABMQMAA==
Date: Sun, 06 May 2018 21:17:33 +0000
Message-ID: <7068826C-9C92-4E57-A721-46B96B53A260@isara.com>
References: <CABcZeBOGJTYTGqYLhqafM=yE9hCZP06KbjKfBqMVTr=yoUYUrw@mail.gmail.com> <CABcZeBOTTe=8mw3q7FXNLWD7pe=XTuKj3P3C1=-GXHZSFQybzw@mail.gmail.com> <CAL02cgRn6wHMDoCL+UCaHtD8GV30=+aSrvCY+Jf64tKtqkfV2Q@mail.gmail.com> <1525379746.825004.1360053824.4E4ADFCA@webmail.messagingengine.com> <CAL02cgTpwZQboYZ-wjUGPG3ACsORxJuk9_sneKcFD+=rMSuyuA@mail.gmail.com> <CABcZeBN8adkXcTc+qiJwu5197vu6ybnvLY1ekjtwvVzpGoRicA@mail.gmail.com>
In-Reply-To: <CABcZeBN8adkXcTc+qiJwu5197vu6ybnvLY1ekjtwvVzpGoRicA@mail.gmail.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [172.31.5.52]
Content-Type: multipart/alternative; boundary="_000_7068826C9C924E57A72146B96B53A260isaracom_"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/f4rqoCDd6oyxoBjufulrCYCaxi8>
Subject: Re: [MLS] TreeKEM: An alternative to ART
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 06 May 2018 21:21:34 -0000
On 2018-05-04, 12:31 AM, "MLS on behalf of Eric Rescorla" <mls-bounces@ietf.org<mailto:mls-bounces@ietf.org> on behalf of ekr@rtfm.com<mailto:ekr@rtfm.com>> wrote: On Thu, May 3, 2018 at 3:21 PM, Richard Barnes <rlb@ipv.sx<mailto:rlb@ipv.sx>> wrote: On Thu, May 3, 2018 at 4:35 PM Katriel Cohn-Gordon <me@katriel.co.uk<mailto:me@katriel.co.uk>> 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 <ekr@rtfm.com<mailto:ekr@rtfm.com>> wrote: Oops. I forgot to attach the paper. On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <ekr@rtfm.com<mailto:ekr@rtfm.com>> 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 MLS@ietf.org<mailto:MLS@ietf.org> https://www.ietf.org/mailman/listinfo/mls _______________________________________________ MLS mailing list MLS@ietf.org<mailto:MLS@ietf.org> https://www.ietf.org/mailman/listinfo/mls _______________________________________________ MLS mailing list MLS@ietf.org<mailto:MLS@ietf.org> https://www.ietf.org/mailman/listinfo/mls
- [MLS] TreeKEM: An alternative to ART Eric Rescorla
- Re: [MLS] TreeKEM: An alternative to ART Eric Rescorla
- Re: [MLS] TreeKEM: An alternative to ART Richard Barnes
- Re: [MLS] TreeKEM: An alternative to ART =JeffH
- Re: [MLS] TreeKEM: An alternative to ART Eric Rescorla
- Re: [MLS] TreeKEM: An alternative to ART Katriel Cohn-Gordon
- Re: [MLS] TreeKEM: An alternative to ART Richard Barnes
- Re: [MLS] TreeKEM: An alternative to ART Eric Rescorla
- Re: [MLS] TreeKEM: An alternative to ART Daniel Van Geest
- Re: [MLS] TreeKEM: An alternative to ART Karthikeyan Bhargavan
- Re: [MLS] TreeKEM: An alternative to ART Cas Cremers
- Re: [MLS] TreeKEM: An alternative to ART Karthikeyan Bhargavan
- Re: [MLS] TreeKEM: An alternative to ART Alexey Ermishkin
- Re: [MLS] TreeKEM: An alternative to ART Richard Barnes
- Re: [MLS] TreeKEM: An alternative to ART Russ Housley
- Re: [MLS] TreeKEM: An alternative to ART Richard Barnes
- Re: [MLS] TreeKEM: An alternative to ART Stephen Farrell
- Re: [MLS] TreeKEM: An alternative to ART Benjamin Kaduk
- Re: [MLS] TreeKEM: An alternative to ART Benjamin Beurdouche
- Re: [MLS] TreeKEM: An alternative to ART Eric Rescorla
- Re: [MLS] TreeKEM: An alternative to ART Richard Barnes
- Re: [MLS] TreeKEM: An alternative to ART Peter Saint-Andre
- Re: [MLS] TreeKEM: An alternative to ART Richard Barnes
- Re: [MLS] TreeKEM: An alternative to ART Peter Saint-Andre