Re: [MLS] Re-randomized TreeKEM

Dennis Jackson <dennis.jackson@cs.ox.ac.uk> Thu, 24 October 2019 19:05 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 2470912008F for <mls@ietfa.amsl.com>; Thu, 24 Oct 2019 12:05:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Level:
X-Spam-Status: No, score=-4.2 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] 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 jmep9-ddAlhN for <mls@ietfa.amsl.com>; Thu, 24 Oct 2019 12:05:06 -0700 (PDT)
Received: from relay15.mail.ox.ac.uk (relay15.mail.ox.ac.uk [163.1.2.163]) (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 3A70C120025 for <mls@ietf.org>; Thu, 24 Oct 2019 12:05:06 -0700 (PDT)
Received: from smtp4.mail.ox.ac.uk ([129.67.1.207]) by relay15.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 1iNiPw-000AXW-oh; Thu, 24 Oct 2019 20:05:04 +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 1iNiPw-0003jL-EA; Thu, 24 Oct 2019 20:05:04 +0100
To: Brendan McMillion <brendan=40cloudflare.com@dmarc.ietf.org>, Konrad Kohbrok <konrad.kohbrok@datashrine.de>
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> <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>
From: Dennis Jackson <dennis.jackson@cs.ox.ac.uk>
Openpgp: preference=signencrypt
Autocrypt: addr=dennis.jackson@cs.ox.ac.uk; prefer-encrypt=mutual; keydata= mQINBFbAmb8BEADCLixsrAJyvknI95ZIZNVeDJbYvldeXpw7iyhrdUdRK69USU5S9EESulYh k1KlxDB5VfG8CCA/WzG1IonONdXmgLFa1NcmdVvkFjbXf5mbGYG+9pTkieM+UHikniAizIOi ibdTWEEc2opOAvpVypek4SSsfCoXfXqj0j5AXSapHiVzhhWuaXhKVuFdLtYwJDU/x0FXgStm erFMIOeZ5FLFnjkkNyEa1t3XCcf7bfgw8J86UmWzgkVLmtBYbDK0ZAFjtFep5Kps11iTDIa3 xYXzuqgkWwkg7b1mhn5gQUl/kKZqQbuG+Sk+BydjH8e1PJkO6p2eAprO0AoucRuuBl1pmg/F bf/WJC6/XD3AV87ERAdXbb9cH+vrRT8GpiNX5r+7OuXavc3/LNU9stqsdshXwdZlDyPyDIG2 Llj6hB4eS0tEpat3otcPDkXUjXjyOUQ6jKTNSZ+xTBtVTXznflDCGdn9GV0q+4ZbdRZ5tfXM DXM+uMqVxjvh2IjCrka7zf1rRWg1WZu+NrzAUrvPMPddDJfd8JNrIcvV+DIBxPVsUTJLEGt9 PW8LkQb5FrG7T6a813JYNoAtL4w7296UYmUpV1Kvv8otO+uH860x5Ci83ZCXb7gKr9Rankn5 Jcg+shWnDFgSq6uM/u3MmyRV2iw7aCSgcgfy4EPTojJdy3KjzQARAQABtCtEZW5uaXMgSmFj a3NvbiA8ZGVubmlzLmphY2tzb25AY3Mub3guYWMudWs+iQIwBBMBCgAaBAsJCAcCFQoCFgEC GQAFglsIFtUCngECmwMACgkQYQWndYzSRqzvkA//djyyIydK5jhxNFqmMvJTkTZwawKWV7Tc cEntsIwYsHw8ec9Edo/M6fwp8aFmddPnzRo0EBmh6KNm887VxgH0FXmcR7k8bD3qUzIhfq11 4ezWtTk0nWjpieEsFb20lCMZjK9dsfXVRgFrfe00x2lhjPWQ5G5mTkfX8KYcDs5nmc+13qHK Ux6e6aSdEa4mnxrT0NsEg2H2xKgwrGkNIxJO6snrh3A3mT6+2F8ZCiRWwmOhcHBzNCFp1enR bMJpNRhcmGBDNJ9TpnQHDRVE67ds3PC/vKDkYQ3tEIkdgc/KVGOo7+kZxSU/n1gARDZ4PYUw IGOM81aEhmrbXoF33Jbic2jnuLfqsC8uXeP6wGgGpEdGThQ+7zslOPDradgDZBlUmYenuwOb JwJEj+JbbZPcND17VrgVDzcM1rh1w9wcKrRDMIw/zLCpEDOfLRe2ad/V380q/Eh3qa4QrZE7 tnXcOTIZfxd1zZ6TcpOvMVYQPN5Zfrlazmw9bTsdkm3WVrzvxc9DJ/D5Ws+aMu+JfSD+C5Nd n5w2fW7OOiDudeFXj88CL7oBehPJ2ajCDmHd/vc1W7CSoPte6aHBgSGER9cWm5hpEOXacQt+ pEz/uMvq+zkDIydy9YL/8hDo5TsVA4Yo8wNdKOuyaStk/oh3WNda05N0jr8VhRMdxnLN/hWY Ely5Ag0EVsCZvwEQAOBD1BmNy7FWbpg9Tm3OfMNC/yLs6G7rk3OFw7BhpjHXHSsEge48HbvP lfdR9abA1cmbgYR7EyaOav1s9ugU7EtDCcK8zHZcaUg3gC+FdjsnkIQCkf/3HK2sxcbBSrkX 2Uu2jjufvZu10g/aavkCuTHIUiYAHhQU5kCkRI7NYvXIKmaPY2Km3YIVJ50x+4GlE/WVZk8w HpvisxDInBioziUjAIqTt0at5tE1ObZksl2eNHNCwlo15WE2hKIYCuJKb57wCBKaOKo/gSw/ yN2DX3HaU/PF+8rCikkKDhHDrefFwGkqBf3zHlrLiHIr+ONVZ8i9dxMyg5TERxjd3vZ4ha+7 8cr8G83HC8lSBEpPYmoeU4J8vWf8kjBlai0UmzyZRF3SeZlqldxo7zJhYq3xIsDGKVuSCn68 2TcoEsR5WS/Zjc0ZoH/YIpdVy8FRu45dJ2IUzHVyszMfNWKob7ZsQ9JCXiXypmIF6ut5mwv8 ddCMdG6Jdpvg1fr0coABNbJSrUM8uFEldmRFpBdbNx5xSCJjNo+QuTHOXWuO3/GFRmux8/kW TlfF3+dvff2Pw3CKENoysgcOflYShcjOv/03sQ6AfxTm2Jnh5dqJSoVnPWpcDyPqn3k4zoZW 0ISqorI8yehJbfT3C0J5iEX75c8vJWfUUjIhyO0CpHxATNW3j3QxABEBAAGJAh8EGAEIABMF AlbAmccJEGEFp3WM0kasAhsMAAD8JhAAtkUWMLjr1RYTSMPrmTp3NGZfNSblv0GGHtL7TvT1 kFwdT/hs29Gjrj0FffZE6RKDEGls9AL6LY/g3wA5WQsXaK0wqwb8MBeIPWvFPvVQbqrifN3A bpukTl4OCBOwJbHS/GO1V3AwaLl4l3U/+kzR7UsnszWs4kizE9lBJ0AYFbxB0xbPF6iI32Cm K3nrLPfkXBXw2xX01nOLxTx9E7YdVpP3Re1c96aBTflm4CAGUfTZ5xgQMW6rgJ8FBc3oLckt 9MT0qB5XkmKGI1kkRypN7hIFRBcPxegeO8S3fpBUOop5F0el24TVx6KJTktpLmlIfUsEQ0Lx CqNtUk1v3eMCoKmeky8WbFcUArRV4DKXDAK1e3C8poMaehRgfl8sjz6SuH1VXpCMLNPpNMtZ EK4FU+C0jGgJyHS9N1UZjq8Qa8FnYKruyPgTpKEAsqlo5vB6J8phiaKXxnren8HqIfzQdrt8 3M+raXc7+Fqis4pYS49vfIpxUzcqvKUiSgDGKemqMw9w9U5dBEQeLNW08uOKSjyENU4e1Ob/ IiimIpEPA5LEIhSfOP9CN9TculGqvo0g12XnB+g5AAtm1ohMkb33T17IR3rKkhlvIITuY1qi fZz7OgGbXh4G5oUHXNBOhXHaqRIzQCCRbBUFA09OyJBLWAGH6HcM/DeM0I7Ng55uMl8=
Message-ID: <1e5c700d-6ec8-1264-7f0c-d16deb144dd9@cs.ox.ac.uk>
Date: Thu, 24 Oct 2019 20:05:03 +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-pSRqDfnkzTtXuo2_inpwcZQWSuU2BZdmro0wPLSOhwGu3g@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Oxford-Username: exet4027
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/wqzUsgm7gyOn41kLEzoWUtKmDy4>
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 19:05:08 -0000

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