Re: [MLS] Re-randomized TreeKEM

Brendan McMillion <> Wed, 23 October 2019 23:40 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 9AD47120103 for <>; Wed, 23 Oct 2019 16:40:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id NJc9-b_xxEQs for <>; Wed, 23 Oct 2019 16:40:23 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::32d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9864C12001A for <>; Wed, 23 Oct 2019 16:40:23 -0700 (PDT)
Received: by with SMTP id q70so692030wme.1 for <>; Wed, 23 Oct 2019 16:40:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=aNG+yaphvebGktBP2KBQbMj/3fetF2pnGhCoNYWJ1y0=; b=OpjmpcqUw3ip84X4fsY36dFhdWk46DtnL8ANYMeWZL5UMQiprXmq2tiiThkocDJnrn XzAs6gcfz34wXMZtGe9RbOPMtb2UoupBdIeEgwZ1RBVqQfmTlZJqDWGh1Uf5QOg/pK3K UdcfiOfZ2OUClQ3bQTLPwe02qx6tsXHaX0BAQ=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=aNG+yaphvebGktBP2KBQbMj/3fetF2pnGhCoNYWJ1y0=; b=E0X4YODcSACQ+tXJQjlMNZzqBdgv4GZr8PU+yw20AF8C5rpsAsiCwDNqGwfDp5UmwH 1fnJhVpgqXrEO0d53j4MmJ+0aLuZArEUzIgdUP/mINKJQaiI7GXOmzPGYVaJ6ryN3iza UuYdv+DR1CaUFQhz1m+6qF5xV7c5pqbadCd8aUkwvm8bQXwL1AIcszblvoyXK+8e27+n viVAcXmVK1loWXsH182ApzzoHiqGFzw/lq0dsOysOiUNf7mCC7cxQf87YF1pzcnLlKIh yMIXydlIWlvGQFqHW7ZyLjwaOpqOa+XppK3op/PJP2dpHb1L/AH5d+5+ed+plvRQjhQ0 U3jQ==
X-Gm-Message-State: APjAAAXbjA6o3nkWJzWiRHzUlJgP0VUleHvfgtqJpu1W12/kC5rh1eBQ ps5Eo0ajSK82pD6FEQoL77MpSK7TWaCxyb4w/J3LKQ==
X-Google-Smtp-Source: APXvYqz2Qvid49iwC+LiKcD7SxVwLaOiIqoEjDu02cDu4YNDbRes3WOKgwRfDuNyKfXWHeoIkxxkLolEseqwG1k2qYI=
X-Received: by 2002:a7b:c3c8:: with SMTP id t8mr1883678wmj.87.1571874021766; Wed, 23 Oct 2019 16:40:21 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
From: Brendan McMillion <>
Date: Wed, 23 Oct 2019 16:40:10 -0700
Message-ID: <>
To: Dennis Jackson <>,,
Cc: Joel Alwen <>, Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="000000000000b32f3205959c7077"
Archived-At: <>
Subject: Re: [MLS] Re-randomized TreeKEM
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 23 Oct 2019 23:40:26 -0000

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?

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 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 can be enforced. If a user is compromised and goes offline permanently,
then eventually you'll remove them and messages sent *after* the removal
will have forward-security again (assuming nobody else has been
compromised). Forward-security doesn't apply to messages sent while the
compromised user is in the group, that ship has obviously sailed.


Hey Konrad

In those cases, getting
> FS for everyone just by processing a single update of any member is pretty
> significant. I guess my expectation is that in large groups, other
> constraints
> that also exist with "simple" TreeKEM will dictate a lower update
> frequency and
> thus PCS guarantees will be rather weak, but that doesn't mean that FS
> guarantees have to be.

There's no benefit to processing random Updates from random users. Even in
RTreeKEM, the benefit comes from processing the one Update from the one
compromised user. In TreeKEM, you need to process the compromised user's
Update and then everybody else's, which takes 2-4 times as long or so. So
this is the same, regardless of the group size.

Although I'll say that, especially in large groups, the biggest threat to
forward-security is most likely going to be devices going offline
permanently and being removed once somebody notices. TreeKEM vs RTreeKEM
doesn't improve anything there. Large groups seems like a case where
RTreeKEM is really giving up a lot to optimize the best-case scenario and
ignoring the most-likely scenario.


Hey Yevgeniy

In particular, under such limiting
> and narrow point of view, no "security" is possible if one user is not
> processing updates for a while, unless one mandates
> "kicking out" such users. Which, as others pointed, is problematic in many
> settings. But also does not allow to compare
> schemes, as none of them will be secure under such a narrow viewpoint.

I don't think that removing users who aren't updating is controversial.
That's always been my understanding of what we should do with users who
aren't updating.

So this is a huge difference - just passively processing something vs
> issuing an actual update operation.

 That RTreeKEM recovers faster from compromise is a clear benefit of using
the scheme, but it's not a gargantuan difference. It's only recovers about
2-4x faster than TreeKEM best-case, is the same in the worst-case, and
doesn't reduce the total number of Updates that have to be sent.