Re: [MLS] TreeKEM: An alternative to ART

Richard Barnes <> Wed, 30 May 2018 13:43 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 609DB12D7F7 for <>; Wed, 30 May 2018 06:43:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.609
X-Spam-Status: No, score=-2.609 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_LOW=-0.7, T_DKIMWL_WL_MED=-0.01] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id hsd0PupQrE_y for <>; Wed, 30 May 2018 06:43:23 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4003:c06::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 53CAB12DA17 for <>; Wed, 30 May 2018 06:43:23 -0700 (PDT)
Received: by with SMTP id a6-v6so16371802oia.2 for <>; Wed, 30 May 2018 06:43:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=jmVSwXpKYKz41cDWS3gRx/UbTuAFXagGruDgr/fuZXQ=; b=cxD7lV6ERg6z8U2GHdSBh5Ks67PvRFRxhWNSgK9VZPn8U3sc/kSuna6WsaSfK56Xn7 Vqzaf/5RwTzgrYdQsjORcJ/jQUfb/IyaaVoTMSsmpsrxDOtCG8lKvDcVqdgl9Ov1jOh/ bvBdPrLXIGBsY3PK8ya/h9MhwPefABxA4cBpfCd0nO4pDPvnub5v+74XlO/KDm7w7xZX 6AoYIwLEPnjYlB2QYNjU/w4XRaLmtNErQkYm40PFC8CUjToPIp9u9LKFvUItD1CFBdiO NT1CZYPHMXgD7MjGRnLzstCofaYLJYAPX7E6OVXGKhJ2aZXGac94JxIcl/lmVan/Dh5K 96jQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=jmVSwXpKYKz41cDWS3gRx/UbTuAFXagGruDgr/fuZXQ=; b=JjoA4RWRnm8vwmchKnM7zaqt7EOp+m5WJY2965ok8afYTgy/OFKsqdZ9uN6RCx2dH2 xpxPcMU2MSnygBoOGf/mu9f1M1DDjzvfLpsk5Kme8g05vEWxwbnYH04kvjoGcIcUUSAT AQV5qpGafPVForkdk8NuVBho9N2k1P9drJisWvBA8+ScrSG4hHdBoHWYhHFCnymUaeCg 92Lwvk4y28dwCftiidRKJaCsJi357Q+lW0RfmyLyrUbCre12NuAkieoFrxu3CwnsWjhw U7SPEGujpiluzsP9zPZ9pZ0fFI/CRfSG4zhsyb4VLTn0XgkJnZcvk3GPjcEN/SmM4sRR 3TQQ==
X-Gm-Message-State: ALKqPwe6intugDL+nmHF9eGTqeEqjaeRNS3ShdlraHLhS7sN8T662EJi 6M4s55PYn6wDNIqZFqZGX5wk6bQ3ywxAwOLTyGMipQ==
X-Google-Smtp-Source: ADUXVKIhfZgqZUED8Aio1RwYOv6czI6dEBtc4zIUxCrydCeIY6MO4CwdSOmrATqOHvE9Qeh3hb3xhB68A+ZWynheSZI=
X-Received: by 2002:aca:d80a:: with SMTP id p10-v6mr826553oig.29.1527687802228; Wed, 30 May 2018 06:43:22 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Wed, 30 May 2018 09:43:10 -0400
Message-ID: <>
To: Russ Housley <>
Cc: Sean Turner <>, Nick Sullivan <>,
Content-Type: multipart/alternative; boundary="000000000000c7a5ab056d6c887d"
Archived-At: <>
Subject: Re: [MLS] TreeKEM: An alternative to ART
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 30 May 2018 13:43:28 -0000

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.

The below Webex details should work:

Join from a video conferencing system or application
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 <> 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:
> On Thu, May 10, 2018 at 2:01 PM Russ Housley <> 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 <> 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 <> wrote:
>>> Oops. I forgot to attach the paper.
>>> On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <> 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:,
>>>> Explainer slides:
>>>> 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
>>>> 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.
>>>> 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.
>>>> 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.
>>>> The paper contains more details. but generally TreeKEM is somewhat
>>>> more efficient in terms of asymmetric crypto operations than ART.
>>>> 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 mailing list