Re: [MLS] Re-randomized TreeKEM

[Yevgeniy Dodis <[e-mail]>]

I love your email, Dennis! Will use it in the future. Thank you!

"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 :)."

On Wed, Oct 23, 2019 at 8:39 PM Dennis Jackson <[e-mail]>
wrote:

> 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
>
>