Re: [MLS] TreeKEM: An alternative to ART
Richard Barnes <rlb@ipv.sx> Wed, 30 May 2018 16:26 UTC
Return-Path: <rlb@ipv.sx>
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 ADF1112EAFC for <mls@ietfa.amsl.com>; Wed, 30 May 2018 09:26:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.909
X-Spam-Level:
X-Spam-Status: No, score=-1.909 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, T_DKIMWL_WL_MED=-0.01] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.com
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 akz06AIUkph4 for <mls@ietfa.amsl.com>; Wed, 30 May 2018 09:26:28 -0700 (PDT)
Received: from mail-ot0-x235.google.com (mail-ot0-x235.google.com [IPv6:2607:f8b0:4003:c0f::235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C589A12EADB for <mls@ietf.org>; Wed, 30 May 2018 09:26:27 -0700 (PDT)
Received: by mail-ot0-x235.google.com with SMTP id n3-v6so21828736ota.5 for <mls@ietf.org>; Wed, 30 May 2018 09:26:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=5kMDc0FNuzOCa0fI4K3NU+cdaVbahVVkbW19KLYsolc=; b=aTAU7LUs6w8mtyH5KbUoCrDQyTIFeiNauhZsKkxDTZ+lVY2lyF3jBJddLWuKgnaWeb Hva2L+qA+2kADX0USjUjM/hYwbG5zJ4b5Iar3DYTfMOOUmKnKLzzBZLDvNRu6wRvgAeZ zDmDQrZr+APkCfauC410hv2pAW0IunfUS5T4oUeEtt7AT0SFDhTxQI0iMc8CtKMso1Sv +XJ+wc1bjVLicDF2NJ+7J3WR53E9vbdTXKxqLFsivZEYKf2X/Ja7APT+mliiKQZRCumP D27OHZjDC2BapvMw1DVYlxsSCQ7lmtD6riclitw/nD0GTMfMiCtqZctvxkL88nRZtIYI 2YvQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=5kMDc0FNuzOCa0fI4K3NU+cdaVbahVVkbW19KLYsolc=; b=Gmr/olAgYVH4p4gKch9dRQTop6zN0vHeMaADPNIKdg7JkwK5dXlfJBkV+YYS8FVWQs JEEx1Wd+UGGvkcp9JRTyRUd710Meva5MIJ09STKdBGeWzE1/PaXT0x6KCSBdAk2jjbfN 1ne8slVi9rIVooziTaDjX4L+GMKwCaqhPHdGqdtGrBIj3AJt7dYOAyqwT8Gf4EqVF8LU yPRyJ6d3hF4S83N4yB3DElGZhf1NdgdgkL/qn2jKNHuv51i9j7DRflTV0RIM1iif+Nzl 0O+Q434Qxyg1Xt4SIW2KkoP58NtJ4xYquTG2RhwDeY72+A/l9Moyyy9AKXdt5P55P7bj yQdQ==
X-Gm-Message-State: ALKqPwft8So8BXxZHfNYpxrcDkQ/pjg/W5NBGZd4QriKeIwGjecCGw+7 +TWxpWph7XYklIMvsjodEsYlm2pdSjEhyCN7ZL+DmA==
X-Google-Smtp-Source: ADUXVKIgJljve2ZK0ORCEYD+JotUj3dKHC2MiaVMHQhFg2gTcENmtF0shDV4vccZCQyhCv9bzQzzKnMF5NH/nexMElM=
X-Received: by 2002:a9d:2e47:: with SMTP id c7-v6mr2299420otd.383.1527697586636; Wed, 30 May 2018 09:26:26 -0700 (PDT)
MIME-Version: 1.0
References: <CABcZeBOGJTYTGqYLhqafM=yE9hCZP06KbjKfBqMVTr=yoUYUrw@mail.gmail.com> <CABcZeBOTTe=8mw3q7FXNLWD7pe=XTuKj3P3C1=-GXHZSFQybzw@mail.gmail.com> <CAL02cgRn6wHMDoCL+UCaHtD8GV30=+aSrvCY+Jf64tKtqkfV2Q@mail.gmail.com> <70623E37-4A6D-4B73-A97B-DF754D9DBBCE@vigilsec.com> <CAL02cgQwv4owGnoUHwY2s9fdiQNnusD3KGYP-yDru1XjLeYKPQ@mail.gmail.com> <CAL02cgRsUFvVr-a8FiUXb3YRff81rVUgQv5V8RYiBMjUDkswxA@mail.gmail.com> <29aeba9b-2b9d-76b9-72fd-20112d4e39b5@mozilla.com>
In-Reply-To: <29aeba9b-2b9d-76b9-72fd-20112d4e39b5@mozilla.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Wed, 30 May 2018 12:26:14 -0400
Message-ID: <CAL02cgTip-cs=nhqdJ5vUMYLwAKGPfidwAedDuZJf95Bfqf=EQ@mail.gmail.com>
To: stpeter@mozilla.com
Cc: mls@ietf.org, Nick Sullivan <nick@cloudflare.com>, Sean Turner <sean@sn3rd.com>
Content-Type: multipart/alternative; boundary="000000000000f9ddd3056d6ecf5e"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/epBfvZkWCJMHAgjtKA-SBudYO6U>
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: Wed, 30 May 2018 16:26:32 -0000
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 <stpeter@mozilla.com> 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: +1-866-432-9903 Toll: +1-408-525-6800 Access code: 201006237 > > > > > > > > On Thu, May 10, 2018 at 3:05 PM Richard Barnes <rlb@ipv.sx> 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:housley@vigilsec.com>> 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 <rlb@ipv.sx > >> <mailto:rlb@ipv.sx>> 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 > > https://www.ietf.org/mailman/listinfo/mls > > > > _______________________________________________ > MLS mailing list > 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