Re: [MLS] UPKE and Epoch Forward Secrecy

Joel Alwen <jalwen@wickr.com> Thu, 31 October 2019 13:12 UTC

Return-Path: <jalwen@wickr.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 AE5FC1200A1 for <mls@ietfa.amsl.com>; Thu, 31 Oct 2019 06:12:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=wickr-com.20150623.gappssmtp.com
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 9nGk1OOF376b for <mls@ietfa.amsl.com>; Thu, 31 Oct 2019 06:12:13 -0700 (PDT)
Received: from mail-qk1-x736.google.com (mail-qk1-x736.google.com [IPv6:2607:f8b0:4864:20::736]) (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 AC0FD120058 for <mls@ietf.org>; Thu, 31 Oct 2019 06:12:13 -0700 (PDT)
Received: by mail-qk1-x736.google.com with SMTP id u184so6929302qkd.4 for <mls@ietf.org>; Thu, 31 Oct 2019 06:12:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Wli093s4LTLptH8/Ic1xw0+qE74ppizsrmUuh/NPKUk=; b=KbG0CnhAG55NTwZ13Pp9IdHK3kIrNS5CgFMqINA///kraNlUjq1XhZBWi8XeA7Iwl7 dCtPbkUTWtmX/cknbRVIaVT6aGKMicZVVb8fEKQq2gZohL+454uNwJvTWWFxkzMkq5PP 6b/k1rMHqjgU26batezqmwelgIaN3RX1bHokABCKyKcgATZfLLbA6tqWGiTwOUY/j+BI O8qK4keZPnNoFsrpdcq1DyXz06RdtCjmXcPwx28ThDiBASn/kbJzco9GS4yaYrXT3V1T K+OgKaTmmlOg/fChfzepGVc7ukvPb5ozQN4F/A/WRVoQQZLt8GzCjzvIuvD6hGAYxxa9 JCRA==
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=Wli093s4LTLptH8/Ic1xw0+qE74ppizsrmUuh/NPKUk=; b=bYhRyFy/u73OSwVHo5B7Sj7HRDRZ/058qFWQYtp0cpSescry/9RthStaEEraPJZgZ7 9PbGrZAI+cvnyhyQvPUoFJ+k+IhYS4gbqGbHYU/4adqAzUiKBSbY6HfLyKmNr2pbxcP6 WT6Cy1WgH+X7pLdXnWCZAyPqEOxjsNe4fVsnEpgluQu24TxFXnRR/R9fUV1wyuFylZ8x 4swHcDJAT5EiG+iLkOh7z1VF3pw87e73xyi8S7EDtWPZNoLa4sGACbq54vtgPbywraqY fwkUlAiK+YvH2bmmxyPiSUBq/oI9sjapt4g39+/FmI6iUVPdiHa0ujmZJaxwFsCJzOPO 9+OQ==
X-Gm-Message-State: APjAAAUFIag1PG7a1H8BiLsO3R5oPeneaDgnsYsuwmpOhWlY2seulFYY TwaqJEqpy3mcHjIbraLfIWIrWy+TAnHW5o1vSABdMw==
X-Google-Smtp-Source: APXvYqzkJGJPMovIhYjh/jg1iqUoa+52SdKf1WeAeJ7Q2VYK1eEi9wkudGNrUwFlmOlzmEuw0bExYDltu7NZFt85Kd0=
X-Received: by 2002:a05:620a:1346:: with SMTP id c6mr1447868qkl.236.1572527532585; Thu, 31 Oct 2019 06:12:12 -0700 (PDT)
MIME-Version: 1.0
References: <2E73A0A5-1D4A-4E76-A2FA-AFFE51598407@gmail.com>
In-Reply-To: <2E73A0A5-1D4A-4E76-A2FA-AFFE51598407@gmail.com>
From: Joel Alwen <jalwen@wickr.com>
Date: Thu, 31 Oct 2019 14:12:00 +0100
Message-ID: <CANYP603VS5iRtdG+n-TSsrVzynUMy4VqutSqjmWMzTYJiSaPgA@mail.gmail.com>
To: Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>
Cc: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000fac969059634983c"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/m01h3nE-uXmZBeasQqttxHhZaRg>
Subject: Re: [MLS] UPKE and Epoch Forward Secrecy
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, 31 Oct 2019 13:12:17 -0000

Hey,

Yeah, we should have been more explicite about how this all plays out for
MLS. Good that you asked. :-)

"PCFS" is exactly the term we were using to talk about how change from
TreeKEM -> RTreeKEM affects MLS. In a nutshell, FS for epochs after a
compromise is healed (with an update) takes no less but (potentially quite
a bit) longer to kick in for "MLS" (MLS+TreeKEM) than for "RMLS"
(MLS+RTreeKEM).

Here's an example scenario that highlights the difference for MLS.

Suppose Alice's state leaked in the past and now she does an update
defining epoch_secret[i]. Intuitively, until the next corruption (say of
Bob when he's in epoch j>i) we'd like that all epoch_secrets in [i,j)
remain secure. (This property is what we've informally been calling PCFS.
I.e. Forward Security for epochs after a compromise.) We consider what
security we get for (R)MLS.

MLS: Assume (for a moment) all handshake messages are delivered in the same
order to all group messages. Because TreeKEM lets Bob keep HPKE keys around
even after using them Bob could still have the keys to process Alice's
update. Whether this is true or not depends on who's update between [i,j)
and their, Alice and Bob's possitions in the ratchet tree. To guarantee Bob
doesn't have said keys we'd need to know e.g. Bob updated between [i,j) or
someone strictly closer to Bob than Alice has updated. (Closer = shorter
path ratchet tree from Bob's leaf to Charlie's leaf than from Alice's leaf
to Charlie's.)

RMLS: Now consider RMLS when the same assumption holds. All epoch_secrets
in [i,j) remain secure even after Bob's compromise because Bob already
deleted any keys he had that can proccess Alice's update. In more detail:
the adversary knows init_secret[n-1] (from having corrupted Alice). So to
get epoch_secret[n] she still needs update_secret[n] defined by Alice's
update. By assumption Bob processed that update himself. So RTreeKEM (but
not TreeKEM) guarantees Bob no longer has the keys to re-process it. Thus,
corrupting him doesnt let the adversary recover epoch_secret[i] (nor any
ones after that since its always missing at least the required init_secret).



Now lets consider what happens if the global ordering assumption doesn't
hold.

RMLS: Suppose we know only that Bob processed Alice's update. Then just as
above (and regardless of anything else in the execution) corrupting Bob
reveals nothing about any epoch_secrets (or init_secrets) other than the
ones currently held by Bob. So the Adversary breaks no other "epoch
security" (besides the one Bob is in at the time of corruption).

MLS: Assuming Bob processed Alice's update doesn't help us like it did for
RMLS because TreeKEM doesnt require him to then delete the keys he used.
Instead, any keys Bob still has for processing handshake messages starting
just before Alice's update let the adversary recover the corresponding
update_secrets. So the adversary can ratchet the global key schedule
forward through all those epochs (startin with init_secret[n-1] she had
from corrupting Alice).



Suppose finally, that we have neither global ordering nor did Bob ever
process Alice's message.

RMLS: For RMLS, this is the only way that corrupting Bob can (potentially)
help the adversary break "epoch security" for any epoch besides the one Bob
is in during corruption. That is, it might be that Bob still has keys to
proccess Alice's update (and even some further sequences of handshake
messages as long as they depend directly on Alice's update. This works
until the Adversary hits the first handshake message in a sequence for
which Bob doesn't have keys to process.

MLS: First (and as in all cases) anything the adversary could compute for
RMLS they can compute for MLS too. So the above "forking attack" exhists
for MLS. But even here RMLS can behave better than MLS because RTreeKEM
generally causes Bob to refresh his key material more frequently than
TreeKEM.


Let me know if this helps clarify stuff a bit.

- Joel


On Thu, 31 Oct 2019, 08:27 Karthikeyan Bhargavan, <
karthik.bhargavan@gmail.com>; wrote:

> I must begin by saying that I have been enjoying reading Alwen et al’s
> work [1] and they make some excellent points.
> I particularly like the idea of using a primitive like UPKE (or SkuPke as
> [2] calls it) to improve the forward secrecy guarantees of TreeKEM.
> If this can be made to work with standards-compliant EC implementations,
> we should definitely consider adding this mechanism to MLS.
>
> For my own better understanding, however, I am trying to figure out the
> exact forward secrecy improvement this will bring to the protocol.
> It is clear from [1] that the *update secret* and each *subgroup secret*
> in TreeKEM provides weak Forward Secrecy (since each update
> only modifies one leaf key, leaving the attacker N-1 members to
> compromise.)
>
> However, the public key part of TreeKEM is only part of the Forward
> Secrecy story, we must also account for the “init_secret” which
> changes with every update. As far as I can see, the discussion in [1]
> appears to ignore the “init_secret -> update_secret ->
> epoch_secret+init_secret”
> ratchet which has always been part of MLS. So I don’t fully see how the
> attack of [1] works, and maybe someone can explain.
>
> One may argue that the goal of TreeKEM is to provide FS and PCS for the
> epoch_secret, not the update_secret.
> If every member of the group is honest, then A sends an update , then B
> accepts the update (ratcheting forward its init_secret),
> and then B is compromised, then how can the attacker learn the new epoch
> secret?
>
> Perhaps we are worried about post-compromise forward secrecy (PCFS), but I
> don’t see any attack on that either.
> It is likely I am missing something, so do chime in and explain.
>
> Best,
> Karthik
>
>
> [1] https://eprint.iacr.org/2019/1189.pdf
> [2] https://eprint.iacr.org/2018/954
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>