Re: [MLS] Re-randomized TreeKEM

[Dennis Jackson <[e-mail]>]

Hi Brendan,

On 24/10/2019 18:59, Brendan McMillion wrote:
> I want to state my position again very clearly:
> 
> Assume that a single user was compromised and their state was given to
> an adversary. Assume that the compromise has been *immediately healed*
> by an Update/Remove message affecting the compromised user, meaning that
> the adversary is no longer able to read messages. How long is it until
> we know that messages sent after the compromise was healed are again
> forward-secure, meaning that no future compromises will expose them?
> 
>   * *TreeKEM:* You need to wait until everyone sends an Update.
>   * *RTreeKEM:* You need to wait until everyone processes the
>     Update/Remove. How do you know everyone has processed the
>     Update/Remove, and aren't offline with old key material waiting to
>     be compromised? By waiting until everyone sends an Update.
> 
> Therefore RTreeKEM offers no material improvement over TreeKEM.
> RTreeKEM's improvement over TreeKEM is unmeasurable, unenforceable.

Your perspective seems quite warped. You've selected an arbitrary
scenario and criteria, decided there's no difference between the schemes
in that circumstance and concluded there's no difference between the two
under any circumstances. Spot the problem?

Typically, we analyze security protocols from the perspective of an
adversary who is trying to achieve some goal (learn a secret, forge a
message, etc). It is the adversary we wish to frustrate. RTreeKEM is
significantly better than TreeKEM in this light. There are many
situations (elucidated in earlier examples and the accompanying paper)
in which RTreeKEM resists attacks that TreeKEM does not.

The adversary is absolutely aware of the material improvement of
RTreeKEM over TreeKEM and can measure it quite easily. This difference
has numerous real world impacts, including the scenario I described in
an earlier email. The position that RTreeKEM doesn't offer security
benefits over TreeKEM is factually incorrect.

There are reasonable criticisms of RTreeKEM. It's more complex, it might
require different primitives, it increases message sizes etc. However,
"no material improvement in security" isn't a defendable position.

Regards,
Dennis