Re: [MLS] Re-randomized TreeKEM

[Brendan McMillion <[e-mail]>]

>
> I might be confused what we're talking about here. In RTreeKEM processing a
> random update from a random user allows the processing party to achieve FS.
> Meaning that if previous messages and key material are deleted properly,
> even a
> full compromise of the processing party doesn't give the adversary access
> to
> those deleted messages. In regular TreeKEM on the other hand, processing
> the
> update only gives the sending party FS guarantees.
>

 Sorry, I think i confused PCS and FS. But still, if Alice and Bob are
talking and Alice is compromised, then having Bob send an Update doesn't
accomplish anything. In RTreeKEM, Alice needs to send and Update and Bob
needs to process it, and then we know that any messages sent after Bob
processes the Update are forward-secure again. I think we probably agree,
we're just talking past each other.

You have a good point in that the deletion of the init_secret gives you some
> form of FS, but it's somewhat fragile in that if the adversary has gotten
> hold
> of an init_secret in the past by some other means (e.g. compromise of
> another
> party), that fragile FS is gone.
>

Yes, this is the vulnerability that motivated the development of RTreeKEM,
but you're assuming multiple compromises while I wasn't. 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.