Re: [MLS] Re-randomized TreeKEM

Dennis Jackson <dennis.jackson@cs.ox.ac.uk> Wed, 23 October 2019 12: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 BE36B12002E for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 05:38:59 -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 ZoHU8eziH29l for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 05:38:57 -0700 (PDT)
Received: from relay12.mail.ox.ac.uk (relay12.mail.ox.ac.uk [129.67.1.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 0548D120072 for <mls@ietf.org>; Wed, 23 Oct 2019 05:38:56 -0700 (PDT)
Received: from smtp6.mail.ox.ac.uk ([163.1.2.206]) by relay12.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 1iNFuh-0003Yf-dL; Wed, 23 Oct 2019 13:38:55 +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 1iNFug-00038H-LV; Wed, 23 Oct 2019 13:38:54 +0100
To: Brendan McMillion <brendan=40cloudflare.com@dmarc.ietf.org>, Joel Alwen <jalwen@wickr.com>
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>
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: <0c91edbb-2426-c175-2d35-2ca3fed76902@cs.ox.ac.uk>
Date: Wed, 23 Oct 2019 13:38:53 +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-pSSwjq33c7Rg3BWHEgAJH2hkGzvOczjuXtv7GNwHbtFpYw@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/P7WRmzT9lddBmmrNek5JOTtXnZo>
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 12:39:00 -0000

# PCS and Eviction

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.

In short, quick eviction policies are not a panacea for PCS and in fact
are harmful in the current protocol. This motivates some kind of ability
to rejoin a group by proving knowledge of a recent epoch secret. This
was discussed as a way to recover from a faulty update / device state
loss at the last interim, but it would also be useful in this context.

# PFS Frequency

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.

Key Point: PFS should be a function of how frequently a user receives
messages, not limited by how frequently they send them, because we might
to 'use' the PFS property after receiving any particular message.

RTreeKEM achieves this, TreeKEM does not. TreeKEM with ACKS does, but
requires O(n) messages per content message which seems infeasible.

# PCS Frequency

I think in most use cases PCS can have a looser time bound than PFS. For
example, as frequently as user sends a message or a most a week is not
inherently unreasonable. On the other hand, a PFS window of a week would
have clear real world repercussions.

On 23/10/2019 02:34, Brendan McMillion wrote:
> [...]
> The purpose of an ACK would be to let us know when everyone has
> processed the most recent Update message -- that is, when FS has been
> achieved. Without an ACK, the fact that RTreeKEM achieves FS faster than
> TreeKEM is useless for applying any sort of policy to manage the FS
> properties of the group, because nobody knows when FS is achieved.
> 
> Although of course, PCS still won't be achieved until everybody Updates.
> So everybody Updates, everybody ACKs everybody's Updates, and the number
> of messages sent is n^2. That's not scalable so the fact that RTreeKEM
> achieves FS faster can't be enforced, which means it can't be relied on.

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 is worthwhile clarifying what we mean by PFS in this context. It is
quite common for people to talk about PFS being a property of the
plaintext of a message and ask "at what point is it impossible to
recover that plaintext?". This leads to some requirement on the entire
set of recipients involving deletion of their key material and the
stored plaintext. The involvement of every recipient makes this a
non-local property which can't be meaningfully enforced.

I think a more useful notion is to talk about PFS with respect to some
particular ciphertext and recipient. At what future time, would an
adversary with a copy of the network traffic and the compromised state
of the recipient at that time, be incapable of decrypting the
ciphertext? This definition means we do not have to worry about whether
the application stores the decrypted plaintext or not. Nor do we have to
worry about what other recipients do. This gives us a property that can
actually be enforced locally and will hold globally IF the other
recipients are also honest and received our message.

Best,
Dennis