Re: [MLS] Re-randomized TreeKEM

[Dennis Jackson <[e-mail]>]

Hi Brendan,

On 24/10/2019 00:40, Brendan McMillion 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?

Informally, in this context, the PCS property w.r.t to some set of
participants is the earliest timepoint at which a compromise of the
state of one of the participants allows the adversary to recover the
current state of a participant (or equiv recover a 'current' group
secret). Note: the adversary is required to have been passive at some
point between the earliest compromise and the current timepoint
otherwise no security can hold.

The better the PCS guarantee, the more recently the adversary must have
acted in order to recover the current group secret. Conversely, the PCS
guarantee is weak/non-existent if the adversary could have compromised
an agent a very long time ago and still recover the current group secret.

Let us assume the adversary compromised the initial state of some member
of a group at t=0. In either version of TreeKEM: once that group member
has successfully updated their state, the adversary will no longer have
access to the current group secret. However, if we ever throw out that
member and have them rejoin, the adversary has a way back into the
group. The group does not know whether the initial member rejoined, or
the adversary posing as the initial member. Likewise, the initial member
loses their guarantee on the rest of the group's identity/security.

>     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 where the misunderstanding lies so I will expand on this point:

Timepoint: Event
t: User receives a message AEAD(m,...) and decrypts it
t+1: User deletes the message m
t+2: Adversary compromises user's device.

At t+3, can the adversary learn m?

In TreeKEM, the following attack works:

1. At t: the adversary records AEAD(m,...) as it is sent to the user.
2. At t+3, the adversary uses the user's state to decode AEAD(m,...)

This attack doesn't work in RTreeKEM because the user updated their
state after receiving the message at timepoint t. This attack doesn't
work in TreeKEM with ACKs because the user will have updated their state
and sent an update message at t+0.5.

The ability to achieve PFS immediately after receiving a message, rather
than after the transmission of the next message makes a huge difference
in practice. It's clear that having every member of a group ACK each
message isn't going to scale. Having a PFS window of hours, days or
weeks is much much worse than a PFS window of "immediately".

Think about the practical implications for individuals. In many
situations, e.g. inspection at a border, users are aware their device
has been compromised. This guides their future actions (which PCS aims
to protect), but it is typically too late for their past actions (which
PFS aims to protect). Consequently,weak PFS guarantees are much worse in
practice than weak PCS guarantees because future compromise is harder to
predict than deducing past compromise. Although obviously we want strong
forms of both to hold :).

Best,
Dennis