Re: [MLS] UPKE and Epoch Forward Secrecy

[Joel Alwen <[e-mail]>]

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, <[e-mail]> 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, <
> [e-mail]> 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
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/mls
>>
>