Re: [MLS] Re-randomized TreeKEM

Konrad Kohbrok <> Fri, 25 October 2019 06:02 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id D4F9212006F for <>; Thu, 24 Oct 2019 23:02:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.597
X-Spam-Status: No, score=-2.597 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id V5o_PUzK4jJW for <>; Thu, 24 Oct 2019 23:02:49 -0700 (PDT)
Received: from ( [IPv6:2001:67c:2050:104:0:2:25:2]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A939412003F for <>; Thu, 24 Oct 2019 23:02:48 -0700 (PDT)
Received: from ( [IPv6:2001:67c:2050:105:465:1:1:0]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 668C5A1BB7 for <>; Fri, 25 Oct 2019 08:02:44 +0200 (CEST)
X-Virus-Scanned: amavisd-new at
Received: from ([]) by ( []) (amavisd-new, port 10030) with ESMTP id stoGOpaRVeZw for <>; Fri, 25 Oct 2019 08:02:38 +0200 (CEST)
References: <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <>
From: Konrad Kohbrok <>
Message-ID: <>
Date: Fri, 25 Oct 2019 08:02:37 +0200
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-GB
Content-Transfer-Encoding: 8bit
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: Fri, 25 Oct 2019 06:02:52 -0000

Hi Brendan,

I'm sorry you feel frustrated with this discussion and I can see why. I agree
with you that we should be very careful with adding new stuff to MLS that
increases costs (be it bandwidth, complexity or otherwise). I also think it's
good to keep an eye on the measurability and enforcability of security
guarantees, which is something I hadn't thought about too much until now.
Although I have to admit that I can't follow your argument with those points
(who is measuring?).

I think one reason we're talking past each other is that to a certain degree I
(and probably a few of the other cryptographers here) am guilty of thinking very
much along the lines of the formal definitions of things like PCS and FS, while
losing sight of the probabilities for certain scenarios in the real world. Under
the formal definition of FS it shouldn't matter if A was compromised in the
past. B should get FS guarantees independent of that.

With a weaker definition of FS there might not be a difference between RTreeKEM
and TreeKEM. However, as Dennis said, it's then easy to lose track of the
scenarios where we're actually secure and the security model becomes complicated
very quickly (especially in a protocol like MLS with a lot of keys flying around
in a lot of different places). I've not been in the community for that long, but
I think sticking to the formal definitions and looking out for nuances and has
proven to be a good idea in the past.

Just as an afterthought: I think the attack would also work in a more likely
real-world scenario, where the adversary is part of the group and subsequently
gets kicked out (maybe a disgruntled employee). Then they have a past init
secret and the attack still works and everyone needs to issue an update to gain
FS. That sounds more likely in a real-world scenario.


On 24.10.19 23:03, Brendan McMillion wrote:
> I feel like I'm the only one with a realistic perspective, while everyone else
> is focusing on the Platonic benefits of RTreeKEM.
> Does it use less bandwidth? No.
> Does it guarantee faster PCS? No.
> Does it guarantee faster FS? No.
> Is it easy to implement in JavaScript? No.
> On Thu, Oct 24, 2019, 12:05 PM Dennis Jackson <
> <>> wrote:
>     Hi Brendan,
>     On 24/10/2019 18:59, Brendan McMillion wrote:
>     > 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..
>     Your perspective seems quite warped. You've selected an arbitrary
>     scenario and criteria, decided there's no difference between the schemes
>     in that circumstance and concluded there's no difference between the two
>     under any circumstances. Spot the problem?
>     Typically, we analyze security protocols from the perspective of an
>     adversary who is trying to achieve some goal (learn a secret, forge a
>     message, etc). It is the adversary we wish to frustrate. RTreeKEM is
>     significantly better than TreeKEM in this light. There are many
>     situations (elucidated in earlier examples and the accompanying paper)
>     in which RTreeKEM resists attacks that TreeKEM does not.
>     The adversary is absolutely aware of the material improvement of
>     RTreeKEM over TreeKEM and can measure it quite easily. This difference
>     has numerous real world impacts, including the scenario I described in
>     an earlier email. The position that RTreeKEM doesn't offer security
>     benefits over TreeKEM is factually incorrect.
>     There are reasonable criticisms of RTreeKEM. It's more complex, it might
>     require different primitives, it increases message sizes etc. However,
>     "no material improvement in security" isn't a defendable position.
>     Regards,
>     Dennis
>     _______________________________________________
>     MLS mailing list
> <>
> _______________________________________________
> MLS mailing list