Re: [MLS] UPKE and Epoch Forward Secrecy

[Karthikeyan Bhargavan <[e-mail]>]

Thanks Joel and Yevgeniy, this discussion is very useful, and I would have struggled to understand it just from the paper.

To further my understanding, am I correct in thinking that the same “attack” works on two-party Signal conversations if one party only receives but does not send messages?
Suppose A and B are engaged in two-party Signal.
The attacker obtains A’s state and hence the current root+chain keys.
A sends a new flight of messages, and hence DH-ratchets the key forward.
We expect the session to be “healed” because of PCS.
But until B sends a message back, the conversation is vulnerable to an FS attack on B.

Of course, it is much more reasonable in Signal to expect B to respond at some point, and much less reasonable for MLS to assume that all members in a 1000-member group will send updates very soon.
I am just checking if I am missing something. I find that many MLS intuitions are easier to understand if they have a 2-party counterpart.

Best,
Karthik

> On 31 Oct 2019, at 21:43, Yevgeniy Dodis <[e-mail]> wrote:
> 
> 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] <mailto:[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] <mailto:[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] <mailto:[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 <https://eprint.iacr.org/2018/954>_______________________________________________
> MLS mailing list
> [e-mail] <mailto:[e-mail]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> _______________________________________________
> MLS mailing list
> [e-mail] <mailto:[e-mail]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls