Re: [MLS] UPKE and Epoch Forward Secrecy

[Yevgeniy Dodis <[e-mail]>]

Just to add to an excellent summary by Joel, you guys are right that "full
MLS" is a combination of continuous group key agreement (CGKA) - which is
what we call TreeKEM - and purely symmetric component which we called
forward secure authenticated encryption. Indeed, CGKA defines only update
secret, which is then used to generate new epoch secret by hashing it with
the old epoch secret (more or less).

As such, it is indeed slightly harder to attack the full MLS than to attack
TreeKEM. In particular, while TreeKEM is not even forward secure in
isolation, full MLS at least achieves FS in isolation, and breaking full
MLS requires at least two compromises. Unfortunately, the good news stops
here. Every attack on TreeKEM easily extends to only marginally more
complex attack on full MLS.
- corrupt some user A
- either update A or remove A  (so we should recover in the ideal world)
- do more or less the same attack on full MLS as you did on TreeKEM

In particular, when TreeKEM would have update secret i insecure by future
corruption at epoch j >i, in full MLS we will
have epoch secret i insecure by corruption at some time k<i, recovery
before i (by update or delete), and future corruption at j>i.
So, yes, marginally more complicated, but nothing changes conceptually:
periods between k and j which should be secure
in the ideal world, are not secure.

We will definitely add a section to our paper to emphasize that,
unfortunately, all our attacks on TreeKEM easily extends to the "full MLS".

Thank you for bringing this important point.
Yevgeniy

On Thu, Oct 31, 2019, 9:54 AM Joel Alwen <[e-mail]> wrote:

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