Re: [MLS] Re-randomized TreeKEM

Yevgeniy Dodis <dodis@cs.nyu.edu> Thu, 24 October 2019 00:48 UTC

Return-Path: <zaumka@gmail.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 C2B9F1200A1 for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 17:48:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.423
X-Spam-Level:
X-Spam-Status: No, score=-1.423 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.226, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no 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 9U8ybOKGfugq for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 17:48:42 -0700 (PDT)
Received: from mail-io1-f53.google.com (mail-io1-f53.google.com [209.85.166.53]) (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 7B71112003F for <mls@ietf.org>; Wed, 23 Oct 2019 17:48:42 -0700 (PDT)
Received: by mail-io1-f53.google.com with SMTP id u8so27301900iom.5 for <mls@ietf.org>; Wed, 23 Oct 2019 17:48:42 -0700 (PDT)
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=R/wPM/obqDk8yU6wFA33/JsizstQvXAshDNOgeBX0ck=; b=pAyf/DCA56NWtJzcn8uzGn9yX99bHJiO6jiGe5lFB/MHGZzq9ZB3x4lMwDtU3UBqG3 3C42tJO0vIB6VHCvRWJhs2DrzQtB2wTkOwRUuM5lXW5VT4UR0cPPNC324iQ0m7OU92H9 7KNoqGRdtVQpm/UpzN2B6OwloKY4+Rj/MjHQL7+u9eKNeyOf8tFAUkp4ylhM5B4dEnZR YwCojShZpl310DzpCE1Cysn0FINoGkdvSGZJzBDI8seoT0PFgOaK3WkSjeWRCfRTJBxB oFHcKTKU936rawvBx2GDZATHbuEDUofuFmmqezSHC1/caYGKaixcsQzn09G1zYRUZ1lm 3m7Q==
X-Gm-Message-State: APjAAAVIiYd2Ds7bnZ+7C+IzDfzrQ0qsU2JNt7c89kVgatqRgVokFixc vmVPd53BH/iX1ibcOp8xurxMjcoeJ3YLSmMTMZI=
X-Google-Smtp-Source: APXvYqyJb7AAmSV30/YR2P22h2nXChQGstjSJ+36AJ61Zk+ln5v/Iwzw+WLhFh2g7SM1IYv88gMcO5N7wYHLTqjhOgk=
X-Received: by 2002:a5e:d90f:: with SMTP id n15mr833848iop.20.1571878121419; Wed, 23 Oct 2019 17:48:41 -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>
In-Reply-To: <5a2a13e8-30d5-a3be-a49c-c4495f45e498@cs.ox.ac.uk>
From: Yevgeniy Dodis <dodis@cs.nyu.edu>
Date: Wed, 23 Oct 2019 20:48:31 -0400
Message-ID: <CAMvzKsiMqSeMEgj3m26TGrH9znQ7DcQdHeZMwOfJ+nSynDbr3Q@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>, Joel Alwen <jalwen@wickr.com>
Content-Type: multipart/alternative; boundary="0000000000000eb95e05959d65f9"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/DBo9wsSDGI0ThzxP2D3sNBm_jUc>
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:48:45 -0000

I love your email, Dennis! Will use it in the future. Thank you!

"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 :)."

On Wed, Oct 23, 2019 at 8:39 PM Dennis Jackson <dennis.jackson@cs.ox.ac.uk>;
wrote:

> 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
>
>