Re: [MLS] Re-randomized TreeKEM

[Dennis Jackson <[e-mail]>]

# PCS and Eviction

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.

In short, quick eviction policies are not a panacea for PCS and in fact
are harmful in the current protocol. This motivates some kind of ability
to rejoin a group by proving knowledge of a recent epoch secret. This
was discussed as a way to recover from a faulty update / device state
loss at the last interim, but it would also be useful in this context.

# PFS Frequency

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.

Key Point: PFS should be a function of how frequently a user receives
messages, not limited by how frequently they send them, because we might
to 'use' the PFS property after receiving any particular message.

RTreeKEM achieves this, TreeKEM does not. TreeKEM with ACKS does, but
requires O(n) messages per content message which seems infeasible.

# PCS Frequency

I think in most use cases PCS can have a looser time bound than PFS. For
example, as frequently as user sends a message or a most a week is not
inherently unreasonable. On the other hand, a PFS window of a week would
have clear real world repercussions.

On 23/10/2019 02:34, Brendan McMillion wrote:
> [...]
> The purpose of an ACK would be to let us know when everyone has
> processed the most recent Update message -- that is, when FS has been
> achieved. Without an ACK, the fact that RTreeKEM achieves FS faster than
> TreeKEM is useless for applying any sort of policy to manage the FS
> properties of the group, because nobody knows when FS is achieved.
> 
> Although of course, PCS still won't be achieved until everybody Updates.
> So everybody Updates, everybody ACKs everybody's Updates, and the number
> of messages sent is n^2. That's not scalable so the fact that RTreeKEM
> achieves FS faster can't be enforced, which means it can't be relied on.

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 is worthwhile clarifying what we mean by PFS in this context. It is
quite common for people to talk about PFS being a property of the
plaintext of a message and ask "at what point is it impossible to
recover that plaintext?". This leads to some requirement on the entire
set of recipients involving deletion of their key material and the
stored plaintext. The involvement of every recipient makes this a
non-local property which can't be meaningfully enforced.

I think a more useful notion is to talk about PFS with respect to some
particular ciphertext and recipient. At what future time, would an
adversary with a copy of the network traffic and the compromised state
of the recipient at that time, be incapable of decrypting the
ciphertext? This definition means we do not have to worry about whether
the application stores the decrypted plaintext or not. Nor do we have to
worry about what other recipients do. This gives us a property that can
actually be enforced locally and will hold globally IF the other
recipients are also honest and received our message.

Best,
Dennis