[MLS] TreeKEM: An alternative to ART

Eric Rescorla <ekr@rtfm.com> Thu, 03 May 2018 14:27 UTC

Return-Path: <ekr@rtfm.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 9B5D112EAC5 for <mls@ietfa.amsl.com>; Thu, 3 May 2018 07:27:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.908
X-Spam-Status: No, score=-1.908 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, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=rtfm-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id QNYbt8FgwJFk for <mls@ietfa.amsl.com>; Thu, 3 May 2018 07:27:51 -0700 (PDT)
Received: from mail-ot0-x231.google.com (mail-ot0-x231.google.com [IPv6:2607:f8b0:4003:c0f::231]) (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 F144E12E8C7 for <mls@ietf.org>; Thu, 3 May 2018 07:27:30 -0700 (PDT)
Received: by mail-ot0-x231.google.com with SMTP id g7-v6so20823660otj.11 for <mls@ietf.org>; Thu, 03 May 2018 07:27:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rtfm-com.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=xRsvOfTiP8oqcXKF6PNU0Cf4uyepmw863cp6yUpTy/0=; b=Csi7j72l48Yhgf2VYtV3N+EWx1vxBw3Y4jmSA6mBNemqOr3Jt/dJ5Cw8se9MGjA+ac 10/nQU8PZnU2MbvRfEfmgnzND3QMuwJ2UlV3/q6K6Kp5elOhj7tAPyHMY4L25TaYVAnt Ye/723/AEOcS+kssp7tSRHUcA+l82oqF6TMIsUO4ErPOy5SvjX4VCPoomUZO24gp7LHJ Z3eCrpkHoaEiERRVXla2HnR2LeoVHNv1j1XRrxBxF0thUSuYDYgFFKTGBVR5O07XodIg bY+LldIXlbHbLoT2Sfhw69hBHh841Ap77pJUU1LSz4WcvkMrbrhM7EOjgb7kfoWeGFHA DsDg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=xRsvOfTiP8oqcXKF6PNU0Cf4uyepmw863cp6yUpTy/0=; b=pnxrtdwOJHApz90FgrrELIz98kXnItdhnboj28JFXaInAN1p+Zt9RX/cc+DjjXOoyt g6YT/IBmJlmTjgwG0Ysy2A6xraM7hwJeDuw8ljjeyli8IySUN+RbRet9Hzs7S+uvnVf2 SGTqrCHkirVgUY3tOeReWWkXZXfm5NSnh6qZJ4JpWu20pBi2kmSITD8PbO3Wxc20y+v9 IhiCARLlj81AqUViYpps5xHDSN4ciAYEa/LT4VBS554wDvUYbgBMQaSDjS6wDz3WDPKV K1bNWn/M563L825YviQVrUDclX0LRwGG/TPMdoTrqNDeElFgMpVdbNEKyON7nT4zyEl6 t8Rg==
X-Gm-Message-State: ALQs6tA7twiPesbgYZxdnKnCw+s9EVov0LAC1InjsBv202iviaE5gLw0 7m/XrkThQ8xUIJhMw75QbuE3jq91JfDRzYoVzM14Kftc598=
X-Google-Smtp-Source: AB8JxZrF9ZB+QcTyvj9bLtxAfYM27MbiQoTdlQbS5WglpItT4U4A0E5oLs91pRGxmImv1D0m4xf61L88CMGCus78BmA=
X-Received: by 2002:a9d:72c6:: with SMTP id d6-v6mr3895597otk.392.1525357650041; Thu, 03 May 2018 07:27:30 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Thu, 3 May 2018 07:26:49 -0700 (PDT)
From: Eric Rescorla <ekr@rtfm.com>
Date: Thu, 03 May 2018 07:26:49 -0700
Message-ID: <CABcZeBOGJTYTGqYLhqafM=yE9hCZP06KbjKfBqMVTr=yoUYUrw@mail.gmail.com>
To: mls@ietf.org, Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>, Richard Barnes <rlb@ipv.sx>
Content-Type: multipart/alternative; boundary="000000000000e2f062056b4e005e"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/e3ZKNzPC7Gxrm3Wf0q96dsLZoD8>
Subject: [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, 03 May 2018 14:28:01 -0000

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,
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(b)    H(d)
    / \     / \
   a   b   c   d

Now say that b wants to update its key to b', giving us the tree:

      /     \
    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(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.

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.

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.