Re: [MLS] UPKE and Epoch Forward Secrecy

Joel Alwen <> Thu, 31 October 2019 13:54 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 3F81F120044 for <>; Thu, 31 Oct 2019 06:54:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.898
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id PO4F6DoJe7Iw for <>; Thu, 31 Oct 2019 06:54:33 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::836]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5F140120048 for <>; Thu, 31 Oct 2019 06:54:33 -0700 (PDT)
Received: by with SMTP id e14so8691558qto.1 for <>; Thu, 31 Oct 2019 06:54:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=/EKNpgCWg38N/mkZCrAXNZJrFE+wCSZbVyP4sHbuJLQ=; b=0h+c+gY7HBYJQpTKeYPvAuJlwAmaDExIvdZp0PZPvhSsoob+NL8IfDkCKHOYNyr0+Y yDA7Yscuyl5sfLg91mo6A+b10b7ujSlS+ZIjp26W9F9jJPK4TcZZX7GI4DapW3YGQbgp oq5QMSjwXrImgY1Jd9WeeOC62uV56g7nHkqGu79lLydvumEIAbxv59gaS+ZfLdaIS71U vJrlYxvMEApH74OpxYMR22mIPWEL/IqO+bfKzEcmnJFYCpjk3PlFJ8YetWRChEX7DAYA lFd0IHaA1pAC/3t371B6jmaEgcJbFeODjvXuJUPx2CADI89n5Vn7byNE9AHnEyf1YPOs QraA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=/EKNpgCWg38N/mkZCrAXNZJrFE+wCSZbVyP4sHbuJLQ=; b=c4ocRSBadDu0pjT6e4BirTiPiDrL4SDcLWw+EEchnmEwBho13B5wFc3km8XV3chsMX 2x9/8PR2j11pz/Q12vAMl0ichJ0wCuvNoMzlNpPqlln90H3bNwyTcF86Kl4t6mn1ujSc USUYv9iGJloUcETR9DILU59/WkHo8DPvzvn3esZvXY/nBlxyuvs8aQbJgGnNOdIOZwTL oAIZeLnf5bEX2gqEDIAmEtkH4DUbSX4ktf+XLwYglqkGoMKXMRiZSFo9wWgD4f19f8Vq i+l3MG7b+TypfW5mcv/EpIUyhkPWraJ8ByeeGaRl0czV+aBsceo8+PDuUOzbMn2W73yD julw==
X-Gm-Message-State: APjAAAWChigR9JKNa3zPkoD0IvIqrfAbtKStyRhgvWIqDIQ4zM2LDyEP 7FGTnXy2pBgzPUZErXSbyqivA6ShXJHgedl/pABWGw==
X-Google-Smtp-Source: APXvYqz7WfGiEQqJU8jFLHOwiIsHBsf2TKpSUmKcyzgKMZnb59EL5sTIL7StiENmMsn6j+WLk/j+zv3KtmxjwLnzdQ0=
X-Received: by 2002:a0c:c78b:: with SMTP id k11mr4782450qvj.47.1572530072317; Thu, 31 Oct 2019 06:54:32 -0700 (PDT)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Joel Alwen <>
Date: Thu, 31 Oct 2019 14:51:39 +0100
Message-ID: <>
To: Karthikeyan Bhargavan <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="0000000000005c0af60596353050"
Archived-At: <>
Subject: Re: [MLS] UPKE and Epoch Forward Secrecy
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 31 Oct 2019 13:54:38 -0000

Crap. Sent that last email to soon. Here are some correction.

The concern is not just Bob leaking keys that *directly* allow processing
Alice's (and subsequent) updates as described in my previous email. As
pointed out in the thread introducing RTreeKEM, there are only log(n) such
keys for any given update (assuming no blanks). Unfortunately, we must also
ensure that Bob leaks no keys that allow recovering other keys (from past
network traffic) that in turn then allow proccessing Alice's (or other)
updates. And so on and so forth. So there are really about n/2 keys to
worry about for any given update not just the log(n) that allow processing
the update.

IMO this accentuates the gap bewteen the PCFS guarantees of MLS and RMLS as
the former refreshes those critical keys slower than RMLS. The more
critical keys the worse for MLS in some sense.

As an aside: Its also worth noting that its probably pretty clear to the
adversary who still has which keys in their state just by watching the
encrypted network traffic making it easier to select the right target for
compromising a target epoch.

- Joël

On Thu, 31 Oct 2019, 14:12 Joel Alwen, <> wrote:

> 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, <
>> 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]
>> [2]
>> _______________________________________________
>> MLS mailing list