Re: [MLS] TreeKEM: An alternative to ART

Stephen Farrell <stephen.farrell@cs.tcd.ie> Thu, 10 May 2018 19:51 UTC

Return-Path: <stephen.farrell@cs.tcd.ie>
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 8F580127136 for <mls@ietfa.amsl.com>; Thu, 10 May 2018 12:51:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.3
X-Spam-Level:
X-Spam-Status: No, score=-4.3 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cs.tcd.ie
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 UAEEDfsmygpI for <mls@ietfa.amsl.com>; Thu, 10 May 2018 12:51:21 -0700 (PDT)
Received: from mercury.scss.tcd.ie (mercury.scss.tcd.ie [134.226.56.6]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2E84D120724 for <mls@ietf.org>; Thu, 10 May 2018 12:51:19 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mercury.scss.tcd.ie (Postfix) with ESMTP id C7EC5BE5C; Thu, 10 May 2018 20:51:17 +0100 (IST)
X-Virus-Scanned: Debian amavisd-new at scss.tcd.ie
Received: from mercury.scss.tcd.ie ([127.0.0.1]) by localhost (mercury.scss.tcd.ie [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id p6AkyU4XFPoZ; Thu, 10 May 2018 20:51:07 +0100 (IST)
Received: from [10.244.2.138] (95-45-153-252-dynamic.agg2.phb.bdt-fng.eircom.net [95.45.153.252]) by mercury.scss.tcd.ie (Postfix) with ESMTPSA id 3B7BBBE5F; Thu, 10 May 2018 20:51:07 +0100 (IST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cs.tcd.ie; s=mail; t=1525981867; bh=PyAJ83Dpg2q4QirpwBShrKjnF6T0qlF2vVDzwwM+loA=; h=Subject:To:Cc:References:From:Date:In-Reply-To:From; b=FdjsoLk47n3hw1ddobe5eOUotDpxA1a82PZUq7MqhLayIwlS77EgIMFjBoHaU8jgF ae/6x7PAZjrdcu4Acf6FgMG4by/ii9fGeJjDzPMZN803xv0rxGXy2HRkEntFi8Vkdq uMi5nSjQR81PvJ1uD+Ye7joYJ7jt/+MGS1QpPtcE=
To: Richard Barnes <rlb@ipv.sx>, Russ Housley <housley@vigilsec.com>
Cc: mls@ietf.org, Nick Sullivan <nick@cloudflare.com>, Sean Turner <sean@sn3rd.com>
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>
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
Openpgp: id=5BB5A6EA5765D2C5863CAE275AB2FAF17B172BEA; url=
Autocrypt: addr=stephen.farrell@cs.tcd.ie; prefer-encrypt=mutual; keydata= xsFNBFo9UDIBEADUH4ZPcUnX5WWRWO4kEkHea5Y5eEvZjSwe/YA+G0nrTuOU9nemCP5PMvmh 5Cg8gBTyWyN4Z2+O25p9Tja5zUb+vPMWYvOtokRrp46yhFZOmiS5b6kTq0IqYzsEv5HI58S+ QtaFq978CRa4xH9Gi9u4yzUmT03QNIGDXE37honcAM4MOEtEgvw4fVhVWJuyy3w//0F2tzKr EMjmL5VGuD/Q9+G/7abuXiYNNd9ZFjv4625AUWwy+pAh4EKzS1FE7BOZp9daMu9MUQmDqtZU bUv0Q+DnQAB/4tNncejJPz0p2z3MWCp5iSwHiQvytYgatMp34a50l6CWqa13n6vY8VcPlIqO Vz+7L+WiVfxLbeVqBwV+4uL9to9zLF9IyUvl94lCxpscR2kgRgpM6A5LylRDkR6E0oudFnJg b097ZaNyuY1ETghVB5Uir1GCYChs8NUNumTHXiOkuzk+Gs4DAHx/a78YxBolKHi+esLH8r2k 4LyM2lp5FmBKjG7cGcpBGmWavACYEa7rwAadg4uBx9SHMV5i33vDXQUZcmW0vslQ2Is02NMK 7uB7E7HlVE1IM1zNkVTYYGkKreU8DVQu8qNOtPVE/CdaCJ/pbXoYeHz2B1Nvbl9tlyWxn5Xi HzFPJleXc0ksb9SkJokAfwTSZzTxeQPER8la5lsEEPbU/cDTcwARAQABzTJTdGVwaGVuIEZh cnJlbGwgKDIwMTcpIDxzdGVwaGVuLmZhcnJlbGxAY3MudGNkLmllPsLBgAQTAQgAKgIbAwUJ CZQmAAULCQgHAgYVCAkKCwIEFgIDAQIeAQIXgAUCWj6jdwIZAQAKCRBasvrxexcr6o7QD/9m x9DPJetmW794RXmNTrbTJ44zc/tJbcLdRBh0KBn9OW/EaAqjDmgNJeCMyJTKr1ywaps8HGUN hLEVkc14NUpgi4/Zkrbi3DmTp25OHj6wXBS5qVMyVynTMEIjOfeFFyxG+48od+Xn7qg6LT7G rHeNf+z/r0v9+8eZ1Ip63kshQDGhhpmRMKu4Ws9ZvTW2ACXkkTFaSGYJj3yIP4R6IgwBYGMz DXFX6nS4LA1s3pcPNxOgrvCyb60AiJZTLcOk/rRrpZtXB1XQc23ZZmrlTkl2HaThL6w3YKdi Ti1NbuMeOxZqtXcUshII45sANm4HuWNTiRh93Bn5bN6ddjgsaXEZBKUBuUaPBl7gQiQJcAlS 3MmGgVS4ZoX8+VaPGpXdQVFyBMRFlOKOC5XJESt7wY0RE2C8PFm+5eywSO/P1fkl9whkMgml 3OEuIQiP2ehRt/HVLMHkoM9CPQ7t6UwdrXrvX+vBZykav8x9U9M6KTgfsXytxUl6Vx5lPMLi 2/Jrsz6Mzh/IVZa3xjhq1OLFSI/tT2ji4FkJDQbO+yYUDhcuqfakDmtWLMxecZsY6O58A/95 8Qni6Xeq+Nh7zJ7wNcQOMoDGj+24di2TX1cKLzdDMWFaWzlNP5dB5VMwS9Wqj1Z6TzKjGjru q8soqohwb2CK9B3wzFg0Bs1iBI+2RuFnxM7BTQRaPVAyARAA+g3R0HzGr/Dl34Y07XqGqzq5 SU0nXIu9u8Ynsxj7gR5qb3HgUWYEWrHW2jHOByXnvkffucf5yzwrsvw8Q8iI8CFHiTYHPpey 4yPVn6R0w/FOMcY70eTIu/k6EEFDlDbs09DtKcrsT9bmN0XoRxITlXwWTufYqUnmS+YkAuk+ TLCtUin7OdaS2uU6Ata3PLQSeM2ZsUQMmYmHPwB9rmf+q2I005AJ9Q1SPQ2KNg/8xOGxo13S VuaSqYRQdpV93RuCOzg4vuXtR+gP0KQrus/P2ZCEPvU9cXF/2MIhXgOz207lv3iE2zGyNXld /n8spvWk+0bH5Zqd9Wcba/rGcBhmX9NKKDARZqjkv/zVEP1X97w1HsNYeUFNcg2lk9zQKb4v l1jx/Uz8ukzH2QNhU4R39dbF/4AwWuSVkGW6bTxHJqGs6YimbfdQqxTzmqFwz3JP0OtXX5q/ 6D4pHwcmJwEiDNzsBLl6skPSQ0Xyq3pua/qAP8MVm+YxCxJQITqZ8qjDLzoe7s9X6FLLC/DA L9kxl5saVSfDbuI3usH/emdtn0NA9/M7nfgih92zD92sl1yQXHT6BDa8xW1j+RU4P+E0wyd7 zgB2UeYgrp2IIcfG+xX2uFG5MJQ/nYfBoiALb0+dQHNHDtFnNGY3Oe8z1M9c5aDG3/s29QbJ +w7hEKKo9YMAEQEAAcLBZQQYAQgADwUCWj1QMgIbDAUJCZQmAAAKCRBasvrxexcr6qwvD/9b Rek3kfN8Q+jGrKl8qwY8HC5s4mhdDJZI/JP2FImf5J2+d5/e8UJ4fcsT79E0/FqX3Z9wZr6h sofPqLh1/YzDsYkZDHTYSGrlWGP/I5kXwUmFnBZHzM3WGrL3S7ZmCYMdudhykxXXjq7M6Do1 oxM8JofrXGtwBTLv5wfvvygJouVCVe87Ge7mCeY5vey1eUi4zSSF1zPpR6gg64w2g4TXM5qt SwkZVOv1g475LsGlYWRuJV8TA67yp1zJI7HkNqCo8KyHX0DPOh9c+Sd9ZX4aqKfqH9HIpnCL AYEgj7vofeix7gM3kQQmwynqq32bQGQBrKJEYp2vfeO30VsVx4dzuuiC5lyjUccVmw5D72J0 FlGrfEm0kw6D1qwyBg0SAMqamKN6XDdjhNAtXIaoA2UMZK/vZGGUKbqTgDdk0fnzOyb2zvXK CiPFKqIPAqKaDHg0JHdGI3KpQdRNLLzgx083EqEc6IAwWA6jSz+6lZDV6XDgF0lYqAYIkg3+ 6OUXUv6plMlwSHquiOc/MQXHfgUP5//Ra5JuiuyCj954FD+MBKIj8eWROfnzyEnBplVHGSDI ZLzL3pvV14dcsoajdeIH45i8DxnVm64BvEFHtLNlnliMrLOrk4shfmWyUqNlzilXN2BTFVFH 4MrnagFdcFnWYp1JPh96ZKjiqBwMv/H0kw==
Message-ID: <6d4a211b-70a4-c288-9c35-7c68341ec210@cs.tcd.ie>
Date: Thu, 10 May 2018 20:51:05 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0
MIME-Version: 1.0
In-Reply-To: <CAL02cgQwv4owGnoUHwY2s9fdiQNnusD3KGYP-yDru1XjLeYKPQ@mail.gmail.com>
Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="hvOYPMyz8Z2azEM0pSIRY9SDFFVlFDf8q"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/3y7sCJPBKDVfGRQJq0Y3WSs6DCg>
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: Thu, 10 May 2018 19:51:26 -0000

Fine idea/hope to attend.

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

S

On 10/05/18 20:05, Richard Barnes 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> 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> 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> wrote:
>>
>>> Oops. I forgot to attach the paper.
>>>
>>>
>>> On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <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
>> 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
>