Re: [MLS] Re-randomized TreeKEM

Joel Alwen <jalwen@wickr.com> Tue, 22 October 2019 21:05 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 258CF12008D for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 14:05:22 -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 aLb3DXwcMKGs for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 14:05:20 -0700 (PDT)
Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) (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 EB866120077 for <mls@ietf.org>; Tue, 22 Oct 2019 14:05:19 -0700 (PDT)
Received: by mail-wm1-x335.google.com with SMTP id f22so17500824wmc.2 for <mls@ietf.org>; Tue, 22 Oct 2019 14:05:19 -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=YTze+rgmsITtLYLsgOApC0dyG9joyN86rFIP8S+XjgU=; b=A1gqTn0g0YRCc58qGgYXgCKWjx6PD8PZsHd1TlJSFJo/zdKpPtf1S8m0fhVpbmweJy mTxZ17IsmY/ffMhpPX8KWY5uOtgHeNaBAJXVNhdhklaTjU0cGvMGK+6B8mp8dmYcL3un yP9ok6AJ32DAEIRguY6BEajvlXbpKJoE4XKIZc9MNJAs5fIFuYErLzas3on7T/kXg5Mc p8BmjRThu2FmvuThZWG2Pdkv1kdQaxXw0LK0GcBlfWvJbYp/xhTF/6rVczj0uYORbRZe DivS7LK5LNgsezR5z5ugqRbAn4RrmlNjN7FZPQmsFtM+IQ9nFOzbnDEvG5FJCkNyYJQi wrXg==
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=YTze+rgmsITtLYLsgOApC0dyG9joyN86rFIP8S+XjgU=; b=Urk81ELZW4EnSd+WMAou6N9lKzAofqb3QTcikqIxMR3z/M3VOqt/NExtIvp16NKALl rqq88hCwQiBnfRUCGmIwUgzNUhWB02i9A/we5nYc+ZQOtETd8fJSVH4dWnhWnBM3xsI4 u8W9NIuXyOvAbwOZlM/3vLKz7XsHusZxjfyxzicJlICT/Ek+lCWGy4G5I/Gd1WkOx/Tm qhmS7/CocmrEu8YFO2wDGWekw84uKVlT64q2eZQxQOeH2K/38u+RIwAWJ2btcZN7Dp9N Heqnl128+6osLWpAN+DstjkcfVi2i0kM3muDjpcaQFSB75yPeOELkv61rPjvK7tJQhgL qW8g==
X-Gm-Message-State: APjAAAUflXgKKlMOdoUUlFFqpIQJ5go5TGwkK1Ui14P/u/ujgJlko6W8 n0ZwpeZOmIvgNCgfg3kqT8sJAUfiYdg=
X-Google-Smtp-Source: APXvYqyaiTkAvMcI42VDV50iNlGQg52lpUaC5mhMpwsqo76AcyQLaVQlB/2/tnu7KzVLRxdjxP8dyg==
X-Received: by 2002:a05:600c:2503:: with SMTP id d3mr5013154wma.44.1571778317750; Tue, 22 Oct 2019 14:05:17 -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 u68sm23677114wmu.12.2019.10.22.14.05.16 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 Oct 2019 14:05:16 -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> <a1033442-7394-bdb7-5be3-24b92d75290d@wickr.com> <CABP-pSQ5fQ8ohsnB2XJDLgXEh=PcHmhrrPY-76Pr9evx0g1_QQ@mail.gmail.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: <924d06c6-aa9e-2a8f-ba2e-abaae1b152e2@wickr.com>
Date: Tue, 22 Oct 2019 23:05:16 +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: <CABP-pSQ5fQ8ohsnB2XJDLgXEh=PcHmhrrPY-76Pr9evx0g1_QQ@mail.gmail.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/sqLTTz9sxdf2MAWJbaU_9Of359c>
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: Tue, 22 Oct 2019 21:05:22 -0000

> RTreeKEM might get to a secure state faster but it's not that much faster, and it doesn't change the promises we can make to our users.

I'm curious what leads you to this conclusion. Suppose Alice produces an update defining new group key K. If the
adversary can't already process the update then with RTreeKEM we get FS for K once the update is processed by all
parties. For TreeKEM not only must that hold but we then need a further order n other parties to send out their own
updates too. At least in terms of # of message flows and total bandwidth (and, most likely, in terms of time) that gap
seems pretty big to me.

Moreover, to me this sounds like both a qualitative and quantitative change in the security promise. E.g.
  Quantitative: FS is achieved with fewer message flows & bandwidth.
  Qualitative : FS can be maintained even when there o(n*log(n)) bandwidth. Instead, O(log n) suffices.

> Having everybody send an ACK requires either quadratic bandwidth or trusting the server, which isn't worth it imo.

I dont follow. If I understood your earlier email correctly you said that updates in TreeKEM serve as a signal to others
guiding their update policy. All I was proposing was to use a much more lightweight ACK msg in exactly the same way you
thought updates were being used to guide policy.

Regardless, I don't really understand the problem here. RTreeKEM needs linear updates too for PCS. So people should
still be doing regular updates if they can afford to. That means if I don't see updates from Alice for a long time I'll
eventually want her removed from the group because she's harming the group's PCS. In other words, there's still reason
to do frequent updates which means they still serve as a signal that people are present. The main difference to me is
what we can say about time periods where we can't afford linear number of updates. For those cases RTreeKEM can still
give us FS but not TreeKEM.

- Joël