Re: [MLS] Re-randomized TreeKEM

Konrad Kohbrok <> Thu, 24 October 2019 07:24 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id EACFB120824 for <>; Thu, 24 Oct 2019 00:24:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.598
X-Spam-Status: No, score=-2.598 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] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id ehHi6jJuh-Cd for <>; Thu, 24 Oct 2019 00:24:28 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 68071120860 for <>; Thu, 24 Oct 2019 00:24:27 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 81073A3369 for <>; Thu, 24 Oct 2019 09:24:23 +0200 (CEST)
X-Virus-Scanned: amavisd-new at
Received: from ([]) by ( []) (amavisd-new, port 10030) with ESMTP id Pco-9pNpX-5L for <>; Thu, 24 Oct 2019 09:24:20 +0200 (CEST)
References: <> <> <> <> <> <> <> <> <> <> <> <> <> <>
From: Konrad Kohbrok <>
Message-ID: <>
Date: Thu, 24 Oct 2019 09:24:18 +0200
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
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: Thu, 24 Oct 2019 07:24:31 -0000

Hi Brendan,

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

I might be confused what we're talking about here. In RTreeKEM processing a
random update from a random user allows the processing party to achieve FS.
Meaning that if previous messages and key material are deleted properly, even a
full compromise of the processing party doesn't give the adversary access to
those deleted messages. In regular TreeKEM on the other hand, processing the
update only gives the sending party FS guarantees.

Regarding Dennis' example:

> This doesn't agree with my understanding of MLS. The way I'm reading your
> example, AEAD(m, ...) is application data? There's a section in the spec titled
> "Sender Ratchets" that describes how after application data is decrypted, the
> symmetric decryption key and anything that you might be able to derive it from
> is erased. So all of that erasing happens at t+1 and the adversary has nothing
> to work with at t+2.
> If on the other hand, AEAD(m, ...) is referring to something in the handshake
> messages, that shouldn't be an issue either. Yes, the ciphertexts can still be
> decrypted but epoch_secret[n] = HKDF(init_secret[n-1] || update_secret) where
> update_secret is what's decrypted, and init_secret[n-1] was deleted after the
> handshake message was processed. The adversary shouldn't have access to
> init_secret[n-1], so he can't compute the next epoch secret.

You have a good point in that the deletion of the init_secret gives you some
form of FS, but it's somewhat fragile in that if the adversary has gotten hold
of an init_secret in the past by some other means (e.g. compromise of another
party), that fragile FS is gone.

The way I understand MLS (and I might well be confused about this) and the way
FS works is as follows.

The adversary compromises A and thus gets the init_secret of epoch t. Then A
issues an update, recovering from the compromise. Some messages are sent and
some parties send updates. However, in TreeKEM if the adversary compromises some
party B at epoch t+x that has not issued an update since the compromise of A,
all messages sent in epochs t..t+x are exposed. This is because that party's
HPKE keys have not changed. Those compromised HPKE keys of B allow the adversary
to decrypt the update messages from the wire and, together with the init_secret
of epoch t, lets them decrypt any message that was sent since then. Handshake or
otherwise. In RTreeKEM on the other hand, the HPKE keys are updated as soon as
A's (or any other) update is processed and thus every processing party
immediately achieves FS.

Note, that if I understand the key schedule correctly, deleting the encryption
key doesn't give you FS, because the adversary can still derive all the
necessary keys once they have compromised the handshake secrets and get the
group key as detailed in the example. Feel free to correct me on this, though.