Re: [MLS] Re-randomized TreeKEM

Brendan McMillion <> Wed, 23 October 2019 01:35 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 94B5C120048 for <>; Tue, 22 Oct 2019 18:35:15 -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 Y2Qh4acq7kWg for <>; Tue, 22 Oct 2019 18:35:13 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::734]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id C7B97120026 for <>; Tue, 22 Oct 2019 18:35:12 -0700 (PDT)
Received: by with SMTP id 71so14446132qkl.0 for <>; Tue, 22 Oct 2019 18:35:12 -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=igm55mC39kMoAah44BQdQXZ65ztj2Mv+AVfqNoHcFjI=; b=gkGxGjzFbrztufNtIf8wTV7yHEgAFR6b+rA+rOxEDzC8ddCW0PFSBTVs4QZfDx9jkp tHVCofhjTwMNmaPpu8zcdHybYT4jTVSliZimgI8HA1cnXx2+dYLnv7zYIC+Tb8F6DWBv gNK6UB1PTFve61vgVST02Rcp7cZJmKPO1Xp2U=
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=igm55mC39kMoAah44BQdQXZ65ztj2Mv+AVfqNoHcFjI=; b=k6TwwdE3T7nyX9EDjLMS1ui53hRZhv8F5H6tlP40z1mBJ5cV/gZzZ1zvvYL3gg24IZ 1X/YpOF7G7V9m4a/TkcPfWoe33SUJf8NSIxoSutucX5jPR4iKgNvJaLZ4747ML74vdl+ RZpAkgrouqjaa9QBBkILcl4gxMnngCBXzzvBkXl4lwZCcJJR57Kp4zjhTwe587prPEr5 lvTOq34QiHrOvC3rmVAC/gr0cqIty4LQlZTXookISlw3S9YjfAj5Oy+Dygj11PSSlYjV 9rRpNGEXC7U8gy/0As6itPsVsc/7uEHbx8O6fm+A+b8757b/cGQoFTy48Rolwbxhkg1X Uw6A==
X-Gm-Message-State: APjAAAUnnyLHL/3TyojrGECMyWdSpXtKq8KY7/lpJBPCoiRHmQTUazLq fEhmCQJSZoHe/S3FAlrEfsvHu1z/KCtxZvFVMkQToA==
X-Google-Smtp-Source: APXvYqyeYYIh0ktyC0yrj7VuSaYsFLD6YCus7GcfDeosD9TYoB6P7d+x/xoI1X3lPSZoG/kap2InCdn2wkozEe46DTw=
X-Received: by 2002:a05:620a:2092:: with SMTP id e18mr6120075qka.222.1571794511365; Tue, 22 Oct 2019 18:35:11 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
From: Brendan McMillion <>
Date: Tue, 22 Oct 2019 18:34:59 -0700
Message-ID: <>
To: Joel Alwen <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="00000000000082c931059589ed30"
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 01:35:15 -0000

> I'm curious what leads you to this conclusion. Suppose Alice produces an
> update defining new group key K. If the
> adversary can't already process the update then with RTreeKEM we get FS
> for K once the update is processed by all
> parties. For TreeKEM not only must that hold but we then need a further
> order n other parties to send out their own
> updates too. At least in terms of # of message flows and total bandwidth
> (and, most likely, in terms of time) that gap
> seems pretty big to me.

Let's work an example. Say we set a policy that everyone should try to
Update every 12h and those that don't will be removed after 24h. One user
is compromised. How long is it until full FS and PCS is restored?

   - If the user is prevented from sending new Updates:
      - Whether you use TreeKEM or RTreeKEM, the group is secure again
      after the user is removed. So after 24h at most, but 12h on
average if the
      user is compromised at a random time.
   - If the user is not prevented from sending new Updates:
   - With TreeKEM, you must wait until everyone sends an Update. We're
      secure again after 24h at most, per policy. The average would
trend toward
      12h if everybody's Updates are uniformly distributed.
      - With RTreeKEM, you must wait until the compromised user sends an
      Update. The user could be compromised immediately after sending
an Update,
      so we're secure again after 12h max. On average, you could say that it's
      more like 6h.

Yes, RTreeKEM has very good best-case behavior when you know exactly who is
compromised and when. But in reality, RTreeKEM can only be expected to
recover twice as fast in the best-case (6h vs 12h), and is the same in the
worst-case (24h).

> I dont follow. If I understood your earlier email correctly you said that
> updates in TreeKEM serve as a signal to others
> guiding their update policy. All I was proposing was to use a much more
> lightweight ACK msg in exactly the same way you
> thought updates were being used to guide policy.

The purpose of an ACK would be to let us know when everyone has processed
the most recent Update message -- that is, when FS has been achieved.
Without an ACK, the fact that RTreeKEM achieves FS faster than TreeKEM is
useless for applying any sort of policy to manage the FS properties of the
group, because nobody knows when FS is achieved.

Although of course, PCS still won't be achieved until everybody Updates. So
everybody Updates, everybody ACKs everybody's Updates, and the number of
messages sent is n^2. That's not scalable so the fact that RTreeKEM
achieves FS faster can't be enforced, which means it can't be relied on.