Re: [MLS] Re-randomized TreeKEM

Brendan McMillion <brendan@cloudflare.com> Thu, 24 October 2019 20:03 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 76FD7120047 for <mls@ietfa.amsl.com>; Thu, 24 Oct 2019 13:03:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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, URIBL_BLOCKED=0.001] autolearn=unavailable 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 bWd9ika94zB6 for <mls@ietfa.amsl.com>; Thu, 24 Oct 2019 13:03:19 -0700 (PDT)
Received: from mail-qt1-x82f.google.com (mail-qt1-x82f.google.com [IPv6:2607:f8b0:4864:20::82f]) (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 D6E0A120020 for <mls@ietf.org>; Thu, 24 Oct 2019 13:03:18 -0700 (PDT)
Received: by mail-qt1-x82f.google.com with SMTP id w14so39721604qto.9 for <mls@ietf.org>; Thu, 24 Oct 2019 13:03:18 -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=w0uKvo7oxd2KuWoh5e2GcSQ/uTJme1p+eqRKb94OBRQ=; b=Ru9NfknTN1y0cqFD0su7izq7PwcpxDj90kBS5Dhwwm+FMSxaa1UQ/q+b2AeuZcrN8h T7IU/xnV5TFw6RlCoTHq3gpf+z06Fi9EqZQO+1eEsH9WD9c1wIubhIMz2bCBMfJLupxF TNlxUz6zjuZo5O+xdwa2nTkP7RmIBA4rJiCa8=
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=w0uKvo7oxd2KuWoh5e2GcSQ/uTJme1p+eqRKb94OBRQ=; b=amYkvZSbQSLCYToBXfShs/+5HlzU4i797imFvFfX8LnM1E3uZV3ySRz4N2UBPdBRMT IUxM9cL+bOERmvYoDQmz1DpDMMCy42B+Qkuy7HmtDwxNDUgz/Co7ec7x7wafSAAv5KSL fIWW5DusAkkbZtwofP/WzK4KTFz/IJ8V18HTiz+yOnrIvZveWWXkh1dJzQ8/gQl8TDEr xVLLgTOoZtTz8yW5PCz3/ySUQK3OVxOYux/C1l2v31qhzqjEZv1SN6hZLBzEyMuBgG9w koJYQRZD8mBD4ENzOAwzDBXEblcO0BM+YH281ENa7KSEDMqDPXSh85HksAqs0F2paITV /lng==
X-Gm-Message-State: APjAAAVUA1OuNDPX7r4q/rDDsuB1x9/VPmC9akdmfkEARUTT5IzAT6PR 9vyAX5pb4WxyPMu3z/5oZ9N1d+Qg/Y92LGlTlOipTT0G5T4=
X-Google-Smtp-Source: APXvYqzJzOzoOBdqC16EHKoMMlrXE/U2LogABFaE2ch7hs8i8FPze2iC7NDwYQMUhiRiezqOJtjqJjfzmFNM7EBTyQc=
X-Received: by 2002:ac8:6744:: with SMTP id n4mr6206954qtp.26.1571947397664; Thu, 24 Oct 2019 13:03:17 -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> <CABP-pSTiR7aYhDKT3P5jqjBHvFQ7a8C7SZUDLtvZqc7gSkEBcg@mail.gmail.com> <5a2a13e8-30d5-a3be-a49c-c4495f45e498@cs.ox.ac.uk> <CABP-pSQGQEc39hJ-WDp7rJcJGzOrW-03NY5gyVhm_WywFRL__g@mail.gmail.com> <360fb300-6171-3def-4ca7-8d56b5f8bef0@datashrine.de> <CABP-pSRqDfnkzTtXuo2_inpwcZQWSuU2BZdmro0wPLSOhwGu3g@mail.gmail.com> <1e5c700d-6ec8-1264-7f0c-d16deb144dd9@cs.ox.ac.uk>
In-Reply-To: <1e5c700d-6ec8-1264-7f0c-d16deb144dd9@cs.ox.ac.uk>
From: Brendan McMillion <brendan@cloudflare.com>
Date: Thu, 24 Oct 2019 13:03:05 -0700
Message-ID: <CABP-pSSe8+RVR2txPKqcxGzyfYKURaPWFAG2g9E0KrYGWZ=UXA@mail.gmail.com>
To: Dennis Jackson <dennis.jackson@cs.ox.ac.uk>
Cc: Brendan McMillion <brendan=40cloudflare.com@dmarc.ietf.org>, Konrad Kohbrok <konrad.kohbrok@datashrine.de>, Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000003e87b30595ad8666"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/zzSpdsaBDmiBQVVzQFI5X61mNjk>
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: Thu, 24 Oct 2019 20:03:23 -0000

I feel like I'm the only one with a realistic perspective, while everyone
else is focusing on the Platonic benefits of RTreeKEM.

Does it use less bandwidth? No.
Does it guarantee faster PCS? No.
Does it guarantee faster FS? No.
Is it easy to implement in JavaScript? No.


On Thu, Oct 24, 2019, 12:05 PM Dennis Jackson <dennis.jackson@cs.ox.ac.uk>;
wrote:

> Hi Brendan,
>
> On 24/10/2019 18:59, Brendan McMillion wrote:
> > I want to state my position again very clearly:
> >
> > Assume that a single user was compromised and their state was given to
> > an adversary. Assume that the compromise has been *immediately healed*
> > by an Update/Remove message affecting the compromised user, meaning that
> > the adversary is no longer able to read messages. How long is it until
> > we know that messages sent after the compromise was healed are again
> > forward-secure, meaning that no future compromises will expose them?
> >
> >   * *TreeKEM:* You need to wait until everyone sends an Update.
> >   * *RTreeKEM:* You need to wait until everyone processes the
> >     Update/Remove. How do you know everyone has processed the
> >     Update/Remove, and aren't offline with old key material waiting to
> >     be compromised? By waiting until everyone sends an Update.
> >
> > Therefore RTreeKEM offers no material improvement over TreeKEM.
> > RTreeKEM's improvement over TreeKEM is unmeasurable, unenforceable.
>
> Your perspective seems quite warped. You've selected an arbitrary
> scenario and criteria, decided there's no difference between the schemes
> in that circumstance and concluded there's no difference between the two
> under any circumstances. Spot the problem?
>
> Typically, we analyze security protocols from the perspective of an
> adversary who is trying to achieve some goal (learn a secret, forge a
> message, etc). It is the adversary we wish to frustrate. RTreeKEM is
> significantly better than TreeKEM in this light. There are many
> situations (elucidated in earlier examples and the accompanying paper)
> in which RTreeKEM resists attacks that TreeKEM does not.
>
> The adversary is absolutely aware of the material improvement of
> RTreeKEM over TreeKEM and can measure it quite easily. This difference
> has numerous real world impacts, including the scenario I described in
> an earlier email. The position that RTreeKEM doesn't offer security
> benefits over TreeKEM is factually incorrect.
>
> There are reasonable criticisms of RTreeKEM. It's more complex, it might
> require different primitives, it increases message sizes etc. However,
> "no material improvement in security" isn't a defendable position.
>
> Regards,
> Dennis
>
>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>