Re: [MLS] Re-randomized TreeKEM

[Yevgeniy Dodis <[e-mail]>]

Thank you, Konrad, Joel and Dennis, totally agree with your responses. But
also grateful for Brendan
for voicing his concern, as it clarifies some confusion people might have
about combination of FS and PCS.
Couple of small points to hopefully reach consensus and convince Brendan.

1) As others said, the view "what should be done by users so that given
epoch key k is secure NO MATTER
WHAT THE ATTACKER DOES FROM NOW ON" is useful, but way too limiting. 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.

2) But even with the above super-narrow and restrictive view of forward
security, RTreeKEM has a clear advantage over
TreeKEM. Imagine the system is currently secure, and some control operation
(update/add/remove) is issued.
What should happen for the current key to be secure no matter what?
- In RTreeKEM, as long as all users PROCESSED this operation, the key is
secure no matter what.
- In TreeKEM, as Brandon pointed out, if you want to be absolutely sure,
more or less every user has to UPDATE
(sometimes you could get lucky and need less, but this is super-dependent
on what happened up to now).

So this is a huge difference - just passively processing something vs
issuing an actual update operation.

3) As others pointed out, a better way to think of FS/PCS combination might
be this. Assuming some sequence of
operations (Init, Add, Remove, Update, Corrupt) happened. Never mind how
and why. The question is which "epoch keys"
are secure? Ignoring the subtlety explained in the paper (about attacker
forcing honest users to "not delete" stuff),
in RTreeKEM, the answer is very clear, intuitive, and clearly OPTIMAL:
- All keys k_t, where all users corrupted at some time t' before t, updated
their keys from time t' to t.

In contrast, I cannot give an easy answer for TreeKEM. On a positive, we
have a polynomial time predicate which
gives an answer to this question. And has to do with graph reachability
question we explain in the paper. On a negative,
this predicate is very non-intuitive, and it very hard to visualize or
understand. In is also intricately specific to TreeKEM
(i.e., cannot be described as some general property of group messaging
protocols). More importantly, in most situations
the set of secure keys under TreeKEM will be dramatically smaller than for
RTreeKEM (see examples given in the
paper, by Joel, and in the slides we sent).

Thus, in many concrete situations "here is what the attacker knows; what is
secure?", RTreeKEM simply leaves more keys
secure.

Yevgeniy

On Wed, Oct 23, 2019 at 10:51 AM Konrad Kohbrok <
[e-mail]> wrote:

> > Let's work an example. Say we set a policy that everyone should try to
> Update
> > every 12h and those that don't will be removed after 24h. One user is
> > compromised. How long is it until full FS and PCS is restored?
> >
> >   * If the user is prevented from sending new Updates:
> >       o Whether you use TreeKEM or RTreeKEM, the group is secure again
> after the
> >         user is removed. So after 24h at most, but 12h on average if the
> user is
> >         compromised at a random time.
> >   * If the user is not prevented from sending new Updates:
> >       o With TreeKEM, you must wait until everyone sends an Update.
> We're secure
> >         again after 24h at most, per policy. The average would trend
> toward 12h
> >         if everybody's Updates are uniformly distributed.
> >       o With RTreeKEM, you must wait until the compromised user sends an
> Update.
> >         The user could be compromised immediately after sending an
> Update, so
> >         we're secure again after 12h max. On average, you could say that
> it's
> >         more like 6h.
> >
>
> You're right in this particular example (although I think that eviction
> after
> 24h is pretty draconic). However, if you're looking at larger groups
> (>10.000
> members) you might want to scale down the update frequency to avoid
> everyone
> having to process 10.000 updates of a 10.000-member group every 12h. I'm
> not an
> implementer, but I could imagine that this is pretty costly on battery
> powered
> devices (please feel free to correct me if I'm wrong). 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.
>
> Also keep in mind that even if it's not very beneficial in the example, we
> generally get substantially better FS guarantees at a relatively small
> price in
> bandwidth and local computation. Throwing that away because the upside is
> not
> very big in some cases seems unnecessary to me.
>
> If I understand you correctly, then your concern is that implementers could
> think that due to the guarantees provided by RTreeKEM, they can get away
> with a
> lower update frequency while maintaining the same security guarantees. That
> seems to be a problem that can be solved by providing clear information on
> what
> guarantees are provided upon an update and/or emphasizing the difference
> between
> FS and PCS.
>
> Cheers,
> Konrad
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>