Re: [MLS] Re-randomized TreeKEM
Brendan McMillion <brendan@cloudflare.com> Wed, 23 October 2019 23:40 UTC
Return-Path: <brendan@cloudflare.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 9AD47120103 for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 16:40:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, 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 (1024-bit key) header.d=cloudflare.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 NJc9-b_xxEQs for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 16:40:23 -0700 (PDT)
Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) (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 9864C12001A for <mls@ietf.org>; Wed, 23 Oct 2019 16:40:23 -0700 (PDT)
Received: by mail-wm1-x32d.google.com with SMTP id q70so692030wme.1 for <mls@ietf.org>; Wed, 23 Oct 2019 16:40:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=aNG+yaphvebGktBP2KBQbMj/3fetF2pnGhCoNYWJ1y0=; b=OpjmpcqUw3ip84X4fsY36dFhdWk46DtnL8ANYMeWZL5UMQiprXmq2tiiThkocDJnrn XzAs6gcfz34wXMZtGe9RbOPMtb2UoupBdIeEgwZ1RBVqQfmTlZJqDWGh1Uf5QOg/pK3K UdcfiOfZ2OUClQ3bQTLPwe02qx6tsXHaX0BAQ=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=aNG+yaphvebGktBP2KBQbMj/3fetF2pnGhCoNYWJ1y0=; b=E0X4YODcSACQ+tXJQjlMNZzqBdgv4GZr8PU+yw20AF8C5rpsAsiCwDNqGwfDp5UmwH 1fnJhVpgqXrEO0d53j4MmJ+0aLuZArEUzIgdUP/mINKJQaiI7GXOmzPGYVaJ6ryN3iza UuYdv+DR1CaUFQhz1m+6qF5xV7c5pqbadCd8aUkwvm8bQXwL1AIcszblvoyXK+8e27+n viVAcXmVK1loWXsH182ApzzoHiqGFzw/lq0dsOysOiUNf7mCC7cxQf87YF1pzcnLlKIh yMIXydlIWlvGQFqHW7ZyLjwaOpqOa+XppK3op/PJP2dpHb1L/AH5d+5+ed+plvRQjhQ0 U3jQ==
X-Gm-Message-State: APjAAAXbjA6o3nkWJzWiRHzUlJgP0VUleHvfgtqJpu1W12/kC5rh1eBQ ps5Eo0ajSK82pD6FEQoL77MpSK7TWaCxyb4w/J3LKQ==
X-Google-Smtp-Source: APXvYqz2Qvid49iwC+LiKcD7SxVwLaOiIqoEjDu02cDu4YNDbRes3WOKgwRfDuNyKfXWHeoIkxxkLolEseqwG1k2qYI=
X-Received: by 2002:a7b:c3c8:: with SMTP id t8mr1883678wmj.87.1571874021766; Wed, 23 Oct 2019 16:40:21 -0700 (PDT)
MIME-Version: 1.0
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> <924d06c6-aa9e-2a8f-ba2e-abaae1b152e2@wickr.com> <CABP-pSSwjq33c7Rg3BWHEgAJH2hkGzvOczjuXtv7GNwHbtFpYw@mail.gmail.com> <0c91edbb-2426-c175-2d35-2ca3fed76902@cs.ox.ac.uk>
In-Reply-To: <0c91edbb-2426-c175-2d35-2ca3fed76902@cs.ox.ac.uk>
From: Brendan McMillion <brendan@cloudflare.com>
Date: Wed, 23 Oct 2019 16:40:10 -0700
Message-ID: <CABP-pSTiR7aYhDKT3P5jqjBHvFQ7a8C7SZUDLtvZqc7gSkEBcg@mail.gmail.com>
To: Dennis Jackson <dennis.jackson@cs.ox.ac.uk>, konrad.kohbrok@datashrine.de, dodis@cs.nyu.edu
Cc: Joel Alwen <jalwen@wickr.com>, Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000b32f3205959c7077"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/q1mSfrmXbafkBBPrmB1eUAKncZw>
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: Wed, 23 Oct 2019 23:40:26 -0000
Hey Dennis I think it is worth noting the trade off between evictions and leaving > members in the group. Evicting a member who is not updating improves the > group's PCS, but it harms the member's PCS. Worse, if the evicted member > subsequently rejoins then the group's PCS is also destroyed. > I'm not sure I understand what you mean by "member's PCS" or how allowing a previously compromised user to rejoin harms the group's PCS. Do you mind explaining in more detail? I think it is important to achieve PFS very quickly - ideally after > receiving a message the PFS guarantee should kick in. If a user receives > a message and immediately deletes it, then has their device compromised > it should indeed be gone forever. > TreeKEM does give you that property, assuming that there's been no compromises, or you've fully recovered from any compromise. All that RTreeKEM improves is how quickly the group recovers from compromise. Your statement that TreeKEM doesn't achieve this, or needs ACKs to achieve it, is simply not true. I'm not sure this is a good way to think about FS. If a device goes > offline permanently, FS can never be achieved in this definition. FS can > never be enforced in manner you seem to want in any realistic setting. > It can be enforced. If a user is compromised and goes offline permanently, then eventually you'll remove them and messages sent *after* the removal will have forward-security again (assuming nobody else has been compromised). Forward-security doesn't apply to messages sent while the compromised user is in the group, that ship has obviously sailed. --- Hey Konrad In those cases, getting > FS for everyone just by processing a single update of any member is pretty > significant. I guess my expectation is that in large groups, other > constraints > that also exist with "simple" TreeKEM will dictate a lower update > frequency and > thus PCS guarantees will be rather weak, but that doesn't mean that FS > guarantees have to be. > There's no benefit to processing random Updates from random users. Even in RTreeKEM, the benefit comes from processing the one Update from the one compromised user. In TreeKEM, you need to process the compromised user's Update and then everybody else's, which takes 2-4 times as long or so. So this is the same, regardless of the group size. Although I'll say that, especially in large groups, the biggest threat to forward-security is most likely going to be devices going offline permanently and being removed once somebody notices. TreeKEM vs RTreeKEM doesn't improve anything there. Large groups seems like a case where RTreeKEM is really giving up a lot to optimize the best-case scenario and ignoring the most-likely scenario. --- Hey Yevgeniy In particular, under such limiting > and narrow point of view, no "security" is possible if one user is not > processing updates for a while, unless one mandates > "kicking out" such users. Which, as others pointed, is problematic in many > settings. But also does not allow to compare > schemes, as none of them will be secure under such a narrow viewpoint. > I don't think that removing users who aren't updating is controversial. That's always been my understanding of what we should do with users who aren't updating. So this is a huge difference - just passively processing something vs > issuing an actual update operation. > That RTreeKEM recovers faster from compromise is a clear benefit of using the scheme, but it's not a gargantuan difference. It's only recovers about 2-4x faster than TreeKEM best-case, is the same in the worst-case, and doesn't reduce the total number of Updates that have to be sent.
- [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Karthik Bhargavan
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Karthik Bhargavan
- Re: [MLS] Re-randomized TreeKEM Karthik Bhargavan
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Karthikeyan Bhargavan
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Benjamin Beurdouche
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Richard Barnes
- Re: [MLS] Re-randomized TreeKEM Karthikeyan Bhargavan
- Re: [MLS] Re-randomized TreeKEM Richard Barnes
- Re: [MLS] Re-randomized TreeKEM Benjamin Beurdouche
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Raphael Robert
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Richard Barnes