Re: [MLS] Re-randomized TreeKEM

Dennis Jackson <dennis.jackson@cs.ox.ac.uk> Thu, 24 October 2019 20:08 UTC

Return-Path: <dennis.jackson@cs.ox.ac.uk>
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 46C82120090 for <mls@ietfa.amsl.com>; Thu, 24 Oct 2019 13:08:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.199
X-Spam-Level:
X-Spam-Status: No, score=-4.199 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 hZWtm5Etzl4h for <mls@ietfa.amsl.com>; Thu, 24 Oct 2019 13:08:12 -0700 (PDT)
Received: from relay14.mail.ox.ac.uk (relay14.mail.ox.ac.uk [163.1.2.162]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A5CF5120020 for <mls@ietf.org>; Thu, 24 Oct 2019 13:08:12 -0700 (PDT)
Received: from smtp4.mail.ox.ac.uk ([129.67.1.207]) by relay14.mail.ox.ac.uk with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from <dennis.jackson@cs.ox.ac.uk>) id 1iNjP1-000ClX-jV; Thu, 24 Oct 2019 21:08:11 +0100
Received: from 61.ip-51-38-113.eu ([51.38.113.61] helo=[192.168.2.2]) by smtp4.mail.ox.ac.uk with esmtpsa (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.89) (envelope-from <dennis.jackson@cs.ox.ac.uk>) id 1iNjP0-000Ajn-Et; Thu, 24 Oct 2019 21:08:10 +0100
From: Dennis Jackson <dennis.jackson@cs.ox.ac.uk>
To: Brendan McMillion <brendan@cloudflare.com>
Cc: Brendan McMillion <brendan=40cloudflare.com@dmarc.ietf.org>, Konrad Kohbrok <konrad.kohbrok@datashrine.de>, Messaging Layer Security WG <mls@ietf.org>
References: <5b1d9cb1-509a-da7d-1361-188dfe0f21d6@wickr.com> <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> <CABP-pSSe8+RVR2txPKqcxGzyfYKURaPWFAG2g9E0KrYGWZ=UXA@mail.gmail.com>
Message-ID: <96aed028-564e-0f5b-72b4-fd68654653ca@cs.ox.ac.uk>
Date: Thu, 24 Oct 2019 21:08:09 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: <CABP-pSSe8+RVR2txPKqcxGzyfYKURaPWFAG2g9E0KrYGWZ=UXA@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Oxford-Username: exet4027
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/Ypz0An6WUfhqXO_XPtrBzKq8gtY>
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:08:15 -0000

>> Does it guarantee faster FS? *Yes*

Fixed that for you :)
On 24/10/2019 21:03, Brendan McMillion wrote:
> 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 <mailto: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 <mailto:MLS@ietf.org>
>     https://www.ietf.org/mailman/listinfo/mls
>