[MLS] Re-randomized TreeKEM

Joel Alwen <jalwen@wickr.com> Wed, 16 October 2019 21:51 UTC

Return-Path: <jalwen@wickr.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 89AE712090C for <mls@ietfa.amsl.com>; Wed, 16 Oct 2019 14:51:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=wickr-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id Hv0HQ3WNZuTo for <mls@ietfa.amsl.com>; Wed, 16 Oct 2019 14:51:31 -0700 (PDT)
Received: from mail-wr1-x431.google.com (mail-wr1-x431.google.com [IPv6:2a00:1450:4864:20::431]) (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 B23F1120046 for <mls@ietf.org>; Wed, 16 Oct 2019 14:51:30 -0700 (PDT)
Received: by mail-wr1-x431.google.com with SMTP id o18so29658363wrv.13 for <mls@ietf.org>; Wed, 16 Oct 2019 14:51:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=to:from:subject:openpgp:autocrypt:message-id:date:user-agent :mime-version:content-language; bh=y35pFvUpTC6UWGJheBGj21Rr3AzeYxspADTAnPZwK8Y=; b=1x5yN4+F/P9vzqb4C2EhvX7fbTLOE+T+aQvBkkmy0lTJRA0fJLHxLYIaxgo9yRtRGr 5dxtrIOXWrM0/FW1K2AvqcQfZepw7VacNasoSrms/VPRUKJodoW6JHXUH4WY5SNCqWjE QDFitPikJZmaBxEACmcnVeYm96QRUmHKEi3wC40rxXxBq2KJV2L3IKdxNpjlFWk9jWVa ZktxUg97eYdZ4H/RIxOdlQjmtH8J1qraeJZT+su9wahhtsa9UIeIOci0jOwGQnHtWNkS 2PAW0XBadwL3MhH15eSRAg8KM9pJmjcbbQX4ub+n7ShcbqS6N+eR7IPhtJTfdLG0Wsrw dKrw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:openpgp:autocrypt:message-id :date:user-agent:mime-version:content-language; bh=y35pFvUpTC6UWGJheBGj21Rr3AzeYxspADTAnPZwK8Y=; b=JoQkFH5LTKCAKv4fTb3QupgrKghP/YB6f2gwe5NG4t+2xKo0dQ3jXbnvBHLV1LyITm q+cwMEIcc5yFhwFknx0BelSDbtYPMxQMNx4/kQDPdjFay9HNhWagAKTcNVQLOOfjtDXW eDbOWSG36H/oht0UeIAdOz5O/gECRnPCo2aFJdCoazl7xXGGisfAA1opAtUVHACi0CZn 7fe6tX7txHMIBhUhVky8j4dMnVkgO5lvQfrahuNAhvEKccfjXelSqbkB64LufQnjNpFC pY+h4eG0eIkUmoHx9OagTz6vb8k3s7NzmQ/a8fEHM5ztzHdeYguR4KqN26voxgT1nlBH ZokA==
X-Gm-Message-State: APjAAAVB9pzjcf5W3c9foHp1EV3mq4oixDm09xrHYMlQkISHmh4syHGy QoKRwsHTFARcUNScjiI2th5dBNnvr1I=
X-Google-Smtp-Source: APXvYqyNMBQqls02u2fed0cfBuL5k1xkY1KNhsAqqQQW0OUhxBeaEtPxnsTYELS1emUbX5Co1ikd9w==
X-Received: by 2002:a5d:540e:: with SMTP id g14mr28348wrv.177.1571262687550; Wed, 16 Oct 2019 14:51:27 -0700 (PDT)
Received: from [] (84-114-27-5.cable.dynamic.surfer.at. []) by smtp.gmail.com with ESMTPSA id k24sm8267723wmi.1.2019. for <mls@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 16 Oct 2019 14:51:25 -0700 (PDT)
To: mls@ietf.org
From: Joel Alwen <jalwen@wickr.com>
Openpgp: preference=signencrypt
Autocrypt: addr=jalwen@wickr.com; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0L7kB DQRciGbxAQgA0Qx9LlxvJ0LGZlZRVyV8kPIxg8pNMmxJwJJ+JnTciW0LpfigfdAvGVf6PU0x 3V6SJKtz8D61c8KLyztxwPGRgJX2TRK3zvTlT5mqqnGYMAANttCF1+8DNpiYOMg3ibPRby46 4JPhMgWgvCJ1vHGu9cghjn1ttWIwBuKBXMc8HgACKYWsYZJiYtFEsnOdsD6aPWCg6NiImoc7 vRwNMKNNtDPxY95Yj4CRiLPVrZje3LyJlA9S+y2/p3w69R4AVLSRzAwDlupjXYs03QdNjGjP 2IR2u8RhstDgqW8+Bk3p7wjJ1kHTHgyox81/aHbnIRGKksPGPMPT3bvbpxevfqZ7ywARAQAB iQE8BBgBCAAmFiEEYFNg9IH2SV6e03O3FR5tDZv8eygFAlyIZvECGwwFCQHhM4AACgkQFR5t DZv8eygbLQf+OHSG6K9qiPdYxe61IR2kZdyogc2ArEGrl6AmcNzySXC8wlnreZo3FjfkD6xV CQWwWDxI7B0JPM86IcfCfn45ADeI8rwm6yYIs00B4ag9Mmo0GQ4kQd2aTy60/QaE2ZSrnEtt 0fuz1G8DGnhPnOnMyCnCnkSNuTNG20OlI0cn5EJSxBS4fXVeBMBaV91DEmvLU6DjL+fOBQPq CXIbFY7XffOmC4VxtAGhTadJ8WmUD8ZezXNs8c40Btpukr7j4piUshITfazPGEMXzTUTkimf fAhNX1QQBsfP9kjfjxBn6jDl+lDJY34mANWwEJ8BKjgr09P0sOz4zjjFL62GcFczQA==
Message-ID: <5b1d9cb1-509a-da7d-1361-188dfe0f21d6@wickr.com>
Date: Wed, 16 Oct 2019 23:51:23 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------1AA7E09B652DF5246C8D07F6"
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/pZ-dWq6A8XyFR64_fB6B9hoVFlo>
Subject: [MLS] Re-randomized TreeKEM
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
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, 16 Oct 2019 21:51:36 -0000

Hey everyone,

Sandro, Yevgeniy, Yiannis and I wanted to give you a heads up about some
work we've been doing around TreeKEM. I'll summarize the main points
here. You can also check the slides (attached to this email) which go a
bit more in depth about some of the results with lots of pretty
pictures. But for those interested in the full story we invite you to
look at the full paper on eprint [1].

Basically, we're eager to hear what you all think about it all! More
specifically, one thing I think we could discuss on the list is whether
the work group wants to adopt the proposed changes to TreeKEM. While we
are quite convinced this would significantly improve security for MLS,
it does come at a price which we tried to summarize to the best of our
knowledge below.

Besides general feedback, here are some specific options to consider for
moving forward (just to get the ball rolling).

(1) Adopt the changes as part of MLS.
(2) Make it an optional mode for MLS.
(3) Save it for a future version of MLS.
(4) Just forget about it all together.

- Joël

1) We describe the poor Forward Secrecy properties of TreeKEM. Suppose a
path is updated resulting in a new update key k being fed into the MLS
key schedule. We show that an adversary seeing network traffic can
recover k by leaking any of roughly *n/2 different keys* from the
ratchet tree, some of which are known to multiple parties. That means FS
for k only kicks in once about half the nodes in the ratchet tree have
been assigned new key material. (I.e., its *not* enough to refresh the
log(n) keys on the co-path of the update that produces k.)

For MLS this means we have poorer PCS properties than hoped for. When
Alice is compromised and then updates to define new epoch key K there
remain n/2 keys spread across group member's states, any one of which
allows the adversary to recover K.

2) We prove security for TreeKEM but only under a pretty weak security
notion (which is unavoidable given the above issue).

3) We describe a modification of TreeKEM based on the proposal by Konrad
in the mailing list 24/Jan/2019 [2]. (We call it RTreeKEM for
"Re-randmoized TreeKEM" but the eprint version hasn't been updated yet
to reflect this nomenclature.) Essentially, RTreeKEM replaces HPKE with,
so called, "updatetable public key encryption" (UPKE). Its the same as
HPKE except that when encrypting to a PK, the output includes both a
ciphertext c and an updated (re-randomized) public key PK'. Decryption
of c with SK produces the plaintext and updated secret key SK'
corresponding to PK'.

The intuition here is that this gives TreeKEM a second mechanism for
updating ratchet tree key material besides updates. As a result a node's
SK is used to decrypt no more than 1 ciphertext before it's refreshed.
The offshoot is faster replacement of keys in the ratchet tree and so
faster FS. (Ergo, faster PCS for MLS.) In a sense, we are motivated by
treating the event that a group member actually comes online as a
valuable comodity so RTreeKEM tries to take more advantage of them than
TreeKEM does.

Technically, we define and construct UPKE, RTreeKEM, and prove their
security. In particular, we show that, *if* the delivery service ensures
Handshake (i.e. TreeKEM) packets are delivered in an arbitrary but same
order to all group members then RTreeKEM gives us "optimal" FS and PCS.
That is, assuming global handshake ordering, no protocol can give us FS
or PCS with *fewer* message flows exchanged in any type of execution.
Indeed, any such security improvement would necessarily imply curtailing
the functionality MLS wants from TreeKEM. (Put differently, better
security will invariably mean that there will be some situation in which
an honest group member can't produce an update secret they need to
advance to the next epoch and ends up getting left behind.)

Finally, to qualify "optimal": our results don't mean there can't be a
protocol with the same security but *smaller* packet sizes (just not
with *fewer* packets). Also if the global ordering assumption fails we
could still hope for better security with some other protocol.
(Although, personally, I suspect that will only be possible using
cryptographic primitives that are much less efficient and more advanced
-- read not publicly implemented let alone standardized yet).

The Trade-off
The stronger FS for RTreeKEM comes at a price which we believe can be
summarized as:

1) Currently, we aren't sure how to build UPKE from the X25519 and X448
groups. In particular, UPKE is currently formulated based on abstracting
the underlying ECC group and DH function as modular exponentiation
function (over a generic prime order group). But that's not quite the
case for those X* functions. They first fix some bits of the scaler
(called "clamping") before performing modular exponentiation so modeling
them as simple exponentiations is not accurate. If this doesn't change,
it would mean not supporting the X* functions as a ciphersuite.

Assuming we don't get things to work for X* groups then alternative DH
groups over (essentially) the same curves we could use instead are the
Ristretto variants. E.g. [3] currently under consideration by the CFRG
works in place of X25519. A downside here (relative to, say, X25519) is
that there are fewer public implementations (especially one's audited by
3rd parties if any?). To be clear, we can still use NIST curves and we
are quite confident that having a post-quantum instantiation (e.g. based
on various NIST PQ submissions) is relatively straight-forward.

2) When updating node secrets on a path the corresponding protocol
packet must now include one additional public key per UPKE (formerly
HPKE) ciphertext. Also UPKE ciphertexts are a bit larger (approx. one
extra AES block) than HPKE ones. The public key is needed to inform
group members that *can't* decrypt that ciphertext what the new
(re-randomized) public key at that node is. The extra AES block comes
from including the re-randomizer as part of the plaintext. No more than
$BIT_SECURITY bits are really needed here as they can be expanded
deterministically using a PRG (built from, say, HKDF) to get a
re-randomizer of the desired length. (This little optimization is not in
the eprint version yet. This approach also makes it much harder for an
colluding insider's to use knowledge of SK to choose a re-randomizer
resulting in some targeted SK' as that now requires inverting the PRG.)

In any case, the mitigating observation here is that the increased
packet size means faster FS. So from the point of view of "global
bandwidth required to achieve FS for a given update key" we actually get
a significant *reduction*, (especially if the server delivers things in
a global order). I.e. Basically, RTreeKEM has bigger packets but less of
them are needed.

[1] https://ia.cr/2019/1189

[2] https://mailarchive.ietf.org/arch/msg/mls/WRdXVr8iUwibaQu0tH6sDnqU1no

[3] https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/