Re: [MLS] Re-randomized TreeKEM

Dennis Jackson <dennis.jackson@cs.ox.ac.uk> Thu, 24 October 2019 00:38 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 5371E1200FB for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 17:38:58 -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 vODdaS2UR9VL for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 17:38:55 -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 4006C12006A for <mls@ietf.org>; Wed, 23 Oct 2019 17:38:55 -0700 (PDT)
Received: from smtp6.mail.ox.ac.uk ([163.1.2.206]) 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 1iNR9R-00065y-kS; Thu, 24 Oct 2019 01:38:53 +0100
Received: from 61.ip-51-38-113.eu ([51.38.113.61] helo=[192.168.2.2]) by smtp6.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 1iNR9Q-000A6X-KS; Thu, 24 Oct 2019 01:38:52 +0100
To: Brendan McMillion <brendan=40cloudflare.com@dmarc.ietf.org>, konrad.kohbrok@datashrine.de, dodis@cs.nyu.edu
Cc: Messaging Layer Security WG <mls@ietf.org>, Joel Alwen <jalwen@wickr.com>
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>
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: <5a2a13e8-30d5-a3be-a49c-c4495f45e498@cs.ox.ac.uk>
Date: Thu, 24 Oct 2019 01:38:50 +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-pSTiR7aYhDKT3P5jqjBHvFQ7a8C7SZUDLtvZqc7gSkEBcg@mail.gmail.com>
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="SLqZDJLnZjp1XPqMLcupXkS5KXA0mNPIs"
X-Oxford-Username: exet4027
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/YHdmQED0q0Q267YGsVAkZ-WBMbI>
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 00:38:58 -0000

Hi Brendan,

On 24/10/2019 00:40, Brendan McMillion wrote:
> 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?

Informally, in this context, the PCS property w.r.t to some set of
participants is the earliest timepoint at which a compromise of the
state of one of the participants allows the adversary to recover the
current state of a participant (or equiv recover a 'current' group
secret). Note: the adversary is required to have been passive at some
point between the earliest compromise and the current timepoint
otherwise no security can hold.

The better the PCS guarantee, the more recently the adversary must have
acted in order to recover the current group secret. Conversely, the PCS
guarantee is weak/non-existent if the adversary could have compromised
an agent a very long time ago and still recover the current group secret.

Let us assume the adversary compromised the initial state of some member
of a group at t=0. In either version of TreeKEM: once that group member
has successfully updated their state, the adversary will no longer have
access to the current group secret. However, if we ever throw out that
member and have them rejoin, the adversary has a way back into the
group. The group does not know whether the initial member rejoined, or
the adversary posing as the initial member. Likewise, the initial member
loses their guarantee on the rest of the group's identity/security.

>     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 where the misunderstanding lies so I will expand on this point:

Timepoint: Event
t: User receives a message AEAD(m,...) and decrypts it
t+1: User deletes the message m
t+2: Adversary compromises user's device.

At t+3, can the adversary learn m?

In TreeKEM, the following attack works:

1. At t: the adversary records AEAD(m,...) as it is sent to the user.
2. At t+3, the adversary uses the user's state to decode AEAD(m,...)

This attack doesn't work in RTreeKEM because the user updated their
state after receiving the message at timepoint t. This attack doesn't
work in TreeKEM with ACKs because the user will have updated their state
and sent an update message at t+0.5.

The ability to achieve PFS immediately after receiving a message, rather
than after the transmission of the next message makes a huge difference
in practice. It's clear that having every member of a group ACK each
message isn't going to scale. Having a PFS window of hours, days or
weeks is much much worse than a PFS window of "immediately".

Think about the practical implications for individuals. In many
situations, e.g. inspection at a border, users are aware their device
has been compromised. This guides their future actions (which PCS aims
to protect), but it is typically too late for their past actions (which
PFS aims to protect). Consequently,weak PFS guarantees are much worse in
practice than weak PCS guarantees because future compromise is harder to
predict than deducing past compromise. Although obviously we want strong
forms of both to hold :).

Best,
Dennis