Re: [MLS] Re-randomized TreeKEM

Joel Alwen <jalwen@wickr.com> Mon, 21 October 2019 21:50 UTC

Return-Path: <jalwen@wickr.com>
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 58ED11209AF for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:50:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 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] 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 ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id akTzCfyEggHv for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:50:38 -0700 (PDT)
Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) (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 AF81C12001A for <mls@ietf.org>; Mon, 21 Oct 2019 14:50:37 -0700 (PDT)
Received: by mail-wr1-x42b.google.com with SMTP id z9so15640551wrl.11 for <mls@ietf.org>; Mon, 21 Oct 2019 14:50:37 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=subject:to:cc:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=xP0puNht2FNPaxZ3s6FD2Kith9jZgAFLr4GyN6rBwBI=; b=iNBQk6V4qmmr3tmV4vWPjM7CFPPMDMbHPzC4zujSFblnLbU1Ti+oavrj6iQS89YgNZ vzYx0M6c2VOhDNwMLXl+uevgxppi7/zb6w6PUANQp5AI0yAkj4yhUozbao0nnXdRdAQC c01+uV6bXRy5e2vtNPSP7qF3YQTPbkFSREEKXEo8JnD9tQzMU/2i1g/jCIElw8qxwo6+ Nb+r39/sRg4XWuMm/CmPXtKCIipxWmG9B/HsHEq639n/PcbbF6WsylbT4qq7X4D5jm9G Sa0C6mvbLW3a1FFd8DSjZNAgJWCzlcZMUiPKHJPUb9KW4f3/ARnBsV1caqrtG9zOhteW VZQQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=xP0puNht2FNPaxZ3s6FD2Kith9jZgAFLr4GyN6rBwBI=; b=kEgYSivw6+n5rsLBvqtTuBsxTX5IyCxOl4ra9PwhDNnmCS2eVaNqFqu0Twf9bB/iyJ IffGWHL7aM+IgcwNC1H5hftEN0mfnc6nFCfxbmx/HTMiiR07tCkHZp8OrhsJ96rv/gCB SYDKlmvA0grKXQfj2+mrmTGXH513fAHCBq35rIyVkvJkjFscESERd/OttuXyBY+uI8oI 5ivuA3K6zYNf+F/jcyiaoP3eLXAvZUjrH+Fh1GRuI7O375gp66z6tGUiEhBRo8vbv9gf NITsn/SbnvCAA0Wy2vJ6VwNV2/f7c7APXyMm0k8FUjqpHdhSjkKDeewmUWN2Z1NBSGmH GUsw==
X-Gm-Message-State: APjAAAWsqN5/PR5MqXvcYPSTeQo04yKL+IK87vAlHU+7BQkS6CdEBzm9 WFssraNwoktmdOXPC7mi/ekZxevcjfw=
X-Google-Smtp-Source: APXvYqwRIqiTTX4XLmQv8j+kzyl1mRQcscrUBxIyD9u3gPzxkaafGbYiebR1+c6IqsZqod2vlf/awg==
X-Received: by 2002:a5d:540c:: with SMTP id g12mr317146wrv.335.1571694635563; Mon, 21 Oct 2019 14:50:35 -0700 (PDT)
Received: from [192.168.1.137] (84-114-27-5.cable.dynamic.surfer.at. [84.114.27.5]) by smtp.gmail.com with ESMTPSA id x7sm19865928wrg.63.2019.10.21.14.50.34 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 21 Oct 2019 14:50:35 -0700 (PDT)
To: Brendan McMillion <brendan@cloudflare.com>
Cc: Messaging Layer Security WG <mls@ietf.org>
References: <5b1d9cb1-509a-da7d-1361-188dfe0f21d6@wickr.com> <4BEAE096-9597-4619-ADD4-CE13E899481B@inria.fr> <CAMvzKsgMvLP5mmk8fOoTopKhFM6+EQzognv4Eq_FfMHSs9qwiA@mail.gmail.com> <5673C061-B15D-4DD2-A90C-4F179E82C31A@inria.fr> <133ba15a-037f-6a3b-182c-836b14ba233b@wickr.com> <B8059BBC-8368-4C6B-B64C-3B98153F9A4E@cloudflare.com>
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: <a1033442-7394-bdb7-5be3-24b92d75290d@wickr.com>
Date: Mon, 21 Oct 2019 23:50:34 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: <B8059BBC-8368-4C6B-B64C-3B98153F9A4E@cloudflare.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/BGfRnWHkP1UJb5ENX13m2K-5UJY>
Subject: Re: [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: Mon, 21 Oct 2019 21:50:40 -0000

Hey Brendan,

Thanks for taking the time to look at this stuff and answer! :-)

> This actually makes TreeKEM more attractive to me because it encourages
> implementors to keep the Update frequency high, 

If one can afford high update frequency then that's great. It helps
RTreeKEM too by the way. The longer between updates the less PCS we have
and the longer the corruption windows. So there's still plenty of
incentive in RTreeKEM to update as often as you can.

But more generally, to me a primary design goal for MLS is to get as
much security for as little bandwidth as possible. So I'm particularly
interested in the protocols behavior when there *isn't* that much
bandwidth to spare for frequent updates.

> and it provides an
> explicit signal to the group that everyone has processed every update.
> With TreeKEM, the policy would be “everybody Updates at least once per
> day”. But with RTreeKEM, the equivalent policy is “at least one person
> Updates every day” which isn’t as strong, because you don’t know whether
> or not everybody came online that day and processed the one Update.

If your not coming online then I'm not sure I see the difference between
using TreeKEM or RTreeKEM. I mean, either way your not refreshing any
key material so your preventing the group from achieving FS. Moreover,
coming online to send a daily update TreeKEM means already requires
processing other peoples updates first.

If, on the other hand, the concern is the lack of an explicit signal
wouldnt it be enough to have parties send out ACK msgs to the group when
they process an update? That would consume far less bandwidth (and
computation) than doing a full update alla TreeKEM.

> But RTreeKEM has costs like being harder to implement, and restricting what
> algorithms we can use.

FYI: In the mean time it looks like we may have found a way to make
RTreeKEM work with X25519/X448 groups. (See the email I just sent to the
group for more on this.) Harder to implement I do agree with. Albeit IMO
the difference is rather marginal compared to how much code is needed to
implement the rest of MLS, not to mention all the surrounding
infrastructure; e.g. the servers, the rest of the client, UX etc need to
actually deploy MLS. At the end of the day, I don't think we're talking
about much more than a few lines of code wrapping HPKE. But I might be
wrong here.

> It’s on this basis that I’m opposed to including RTreeKEM in the spec.

Fair enough! :-)

- Joël