Re: [MLS] Re-randomized TreeKEM

[Yevgeniy Dodis <[e-mail]>]

I think I got your point, Brendan, and why we kept speaking past each
other! And we are partially guilty here, by occasionally using the
term "recover" to mean  two different things, contributing to the confusion.

1) "Recover" = achieve PCS. Namely, if attacker corrupts current state of
some user U (including current group key),
how long until the group key is secure, assuming no further corruptions. In
this sense the answer is the same in RTReeKEM
and TreeKEM (or any other secure scheme): corrupted user U should issue an
update (or be removed from group).
So, for multiple corruptions, we should wait until all corrupted uses
UPDATE. And, indeed, we formally show that
TreeKEM is what we call "backward secure" = "achieves PCS in isolation". So
here *you are right* and there is indeed
no security benefit of RTreeKEM over TreeKEM: a corrupted user should
update in order to recover
in *any secure scheme*, more or less by definition.

2) "Recover" = achieve FS. Namely, assuming an UPDATE (or ADD/REMOVE)
operation just happened resulting in a new
group key. What should happen from now until the FUTURE corruption to
guarantee this corruption does not harm the
current key? So I suggest we use the term "preempt" rather than "recover"
for this, as we are not recovering from anything which
happened, but  instead trying to prevent damage from a future hypothetical
corruption. For this notion, the difference between the
schemes is very clear:
 - in RTreeKEM, a user who already moved to the next key (i.,e. merely
PROCESSED)  is not helpful to the attacker. This is
clearly the best we can hope for.
 - in TreeKEM, only if a user  issues an UPDATE one can be sure this user
is not helpful (although sometimes one could get lucky, but this is hard
to describe concisely).

Whether this difference is "gargantuan" is a matter of taste. But I believe
it is, especially in large groups. And here I think
the dual point of view I advocated in my earlier email could be very
useful. Namely, rather than thinking as a policy maker,
what do we do to ensure the given key is secure (against either past or
future corruption), or how long it takes to preempt
(let's use this instead of "recover" going forward!), etc. Think of any
given situation instead: some sequence of operations
happens, including attacker corrupting several states of the users. Never
mind how and why, it just happened.
Which keys are compromised? I believe in majority of even typical cases,
the set of compromised keys in TreeKEM will be noticeably
larger than in RTreeKEM. Certainly in most examples I can think of. To me
this is the reason RTreeKEM offers substantially
more security than TreeKEM.

Do you agree?
Yevgeniy

On Wed, Oct 23, 2019 at 7:40 PM Brendan McMillion <[e-mail]>
wrote:

> Hey Dennis
>
> I think it is worth noting the trade off between evictions and leaving
>> members in the group. Evicting a member who is not updating improves the
>> group's PCS, but it harms the member's PCS. Worse, if the evicted member
>> subsequently rejoins then the group's PCS is also destroyed.
>>
>
> I'm not sure I understand what you mean by "member's PCS" or how allowing
> a previously compromised user to rejoin harms the group's PCS. Do you mind
> explaining in more detail?
>
> I think it is important to achieve PFS very quickly - ideally after
>> receiving a message the PFS guarantee should kick in. If a user receives
>> a message and immediately deletes it, then has their device compromised
>> it should indeed be gone forever.
>>
>
> TreeKEM does give you that property, assuming that there's been no
> compromises, or you've fully recovered from any compromise. All that
> RTreeKEM improves is how quickly the group recovers from compromise. Your
> statement that TreeKEM doesn't achieve this, or needs ACKs to achieve it,
> is simply not true.
>
> I'm not sure this is a good way to think about FS. If a device goes
>> offline permanently, FS can never be achieved in this definition. FS can
>> never be enforced in manner you seem to want in any realistic setting.
>>
>
> It can be enforced. If a user is compromised and goes offline permanently,
> then eventually you'll remove them and messages sent *after* the removal
> will have forward-security again (assuming nobody else has been
> compromised). Forward-security doesn't apply to messages sent while the
> compromised user is in the group, that ship has obviously sailed.
>
> ---
>
> Hey Konrad
>
> In those cases, getting
>> FS for everyone just by processing a single update of any member is pretty
>> significant. I guess my expectation is that in large groups, other
>> constraints
>> that also exist with "simple" TreeKEM will dictate a lower update
>> frequency and
>> thus PCS guarantees will be rather weak, but that doesn't mean that FS
>> guarantees have to be.
>>
>
> There's no benefit to processing random Updates from random users. Even in
> RTreeKEM, the benefit comes from processing the one Update from the one
> compromised user. In TreeKEM, you need to process the compromised user's
> Update and then everybody else's, which takes 2-4 times as long or so. So
> this is the same, regardless of the group size.
>
> Although I'll say that, especially in large groups, the biggest threat to
> forward-security is most likely going to be devices going offline
> permanently and being removed once somebody notices. TreeKEM vs RTreeKEM
> doesn't improve anything there. Large groups seems like a case where
> RTreeKEM is really giving up a lot to optimize the best-case scenario and
> ignoring the most-likely scenario.
>
> ---
>
> Hey Yevgeniy
>
> In particular, under such limiting
>> and narrow point of view, no "security" is possible if one user is not
>> processing updates for a while, unless one mandates
>> "kicking out" such users. Which, as others pointed, is problematic in
>> many settings. But also does not allow to compare
>> schemes, as none of them will be secure under such a narrow viewpoint.
>>
>
> I don't think that removing users who aren't updating is controversial.
> That's always been my understanding of what we should do with users who
> aren't updating.
>
> So this is a huge difference - just passively processing something vs
>> issuing an actual update operation.
>>
>
>  That RTreeKEM recovers faster from compromise is a clear benefit of using
> the scheme, but it's not a gargantuan difference. It's only recovers about
> 2-4x faster than TreeKEM best-case, is the same in the worst-case, and
> doesn't reduce the total number of Updates that have to be sent.
>