Re: [MLS] Re-randomized TreeKEM

Brendan McMillion <> Thu, 24 October 2019 02:06 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 4862912011E for <>; Wed, 23 Oct 2019 19:06:11 -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 K2RuVhPphRuX for <>; Wed, 23 Oct 2019 19:06:09 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::72a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 0ED3512010D for <>; Wed, 23 Oct 2019 19:06:09 -0700 (PDT)
Received: by with SMTP id w2so21896952qkf.2 for <>; Wed, 23 Oct 2019 19:06:09 -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=OZiMSUye13gETSzB+k/aSQBzfLMTQIwHtGGE3INXLg8=; b=B0E80WDhs32Thi1robcIiDvENgoivxNdd4mTk7jiqVNsZY2HHxLwtM9DMYvvjR9nv5 BdKkTD8/RToG2fNVUcQxC3tzlXAD6fL2W6759/9j4eraqxWvqmDdmeBiunkoqmb0i0Ts 7D8ZpU1pnfev6Io0YQ4TiX+3q82b2cN24RJhg=
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=OZiMSUye13gETSzB+k/aSQBzfLMTQIwHtGGE3INXLg8=; b=MPBfVpCiLX7EhdTfhh3xDW5TwEWv/Mgz0F4UZ1WHVnoHokqX0e221Q2Kx8V15FyxgE 8wiPvhw8dQDHuEPpLI1T9jaE55rPgJp18EkC2S60980G/M2UU9HstwY466aYmF3DVkDy 9u9rgVI+xZgbXPUkqUCj5ycUxe+jIpvQLDmMDpbeAyzBN70qBMPmcp9p+42ie95q/Lay 5e3Jdc+cpexlHSwBaiFOxaK5RBUajsVjtESB329FXFFkbIalsz4TQNTLrbF92XYAUSrF NPphB9dHZBb+XMwBo5kmKvyvo6d2WQ72TP7xDmRidJhOEoX+Q4/4I75M1iRBsfvRQ43N wwGg==
X-Gm-Message-State: APjAAAXuxCtx+BClupThvsYTf+dOy66H2DS/jVBbQSI5TqSA3pdKJBV3 z8Hhxljv/DjtY58HTVbVrhIoUzheCOqzAHkzP6XxoJVSpVpEfA==
X-Google-Smtp-Source: APXvYqyno36sm2WTgfpxpYFtqFPqb76RGNNwlZbIhgpfwRaik9WgWNI6i5fZc0PmTJNQClxI5Wxxee/vxt7aXCg9hNs=
X-Received: by 2002:ae9:e508:: with SMTP id w8mr231194qkf.131.1571882767714; Wed, 23 Oct 2019 19:06:07 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
From: Brendan McMillion <>
Date: Wed, 23 Oct 2019 19:05:55 -0700
Message-ID: <>
To: Dennis Jackson <>,
Cc:, Messaging Layer Security WG <>, Joel Alwen <>
Content-Type: multipart/alternative; boundary="000000000000fff06805959e79e7"
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 02:06:11 -0000

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

 Ah, when an adversary compromises a user, the user's ClientInitKeys are
also compromised. That's a really interesting point.

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.

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.


I think I got your point, Brendan, and why we kept speaking past each
> other! And we are partially guilty here, by occasionally using the
> term "recover" to mean  two different things, contributing to the
> confusion.

I think I was using "recover" to refer to achieving both FS and PCS
simultaneously. Once the adversary is kicked out of the group, you have
PCS, but in TreeKEM you need to wait a bit to ensure future compromises
won't reveal past messages.

Whether this difference is "gargantuan" is a matter of taste.

I agree it's a matter of taste, which is why I don't expect to change my
mind. It's also why you won't hear me complain if the change is adopted
anyways. RTreeKEM has objectively better security.