Re: [MLS] somewhat better PCFS for cheap

Richard Barnes <> Fri, 17 April 2020 13:32 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 239ED3A088E for <>; Fri, 17 Apr 2020 06:32:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id eiph3wXJxNdV for <>; Fri, 17 Apr 2020 06:32:33 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::833]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 0E8563A088C for <>; Fri, 17 Apr 2020 06:32:32 -0700 (PDT)
Received: by with SMTP id o10so1880161qtr.6 for <>; Fri, 17 Apr 2020 06:32:32 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=px4r3JtHnDiCKioRBQ203k821iioutm0zlp+0Gq74ZM=; b=oa6GrHFRdRwYwFHPw190MVXHiwfFXGbLJcUPFsSFHz78rhPBPHnwWLwbjHiUEfTHmV F2Eb5RkKE2PrD6aXg83udzp8wXMZ5ca9Ct1Cc3QgkTWM71+lniPTVkbOhjpS3B1ttnkK mEV/3IIZvAZuXgYwlHadroJRm2LaL+aNeDDrAAEqn1jW0buZL1//9xYkZ/K1PgspcVQG ylUxoqxjd4AaolNgT8hkQnZvKnkR+r9W0RhR1irDBSB0T9IQyjCPnM3//B64YbiD/2cg FiYz0WYJZdunWWfHAeXKlxDgRrXA3GdA1FSEKkHQbZ2jQub4SKww03IFW/tggVMSDOFH I9Lg==
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=px4r3JtHnDiCKioRBQ203k821iioutm0zlp+0Gq74ZM=; b=RrBqW0XojKaLOy1vOUUVfmm9j1cUrB11q0TxnQcpCL5U8Hl9eaKx1IjcI7daGJxKFg t1viwIbt6AqWdJD6HE/j9aKRPvlEeJjSNS3rAEHnbG1pXyswx5eRta5geP2aHQq8xgxw TRsHjJTLL42kepQxM0XG98ERV5aYsNuID2oj0YDtDmzclOzQNbOGcH24WtvuD52yLf11 HceGZCuSQTr/GdUdEF00AC3mNPRu+08dcgAGqFBvwKIygx2/LR4xJN1DEQ1SNrglShsU IEaBhwLG0B4ugwHz3pxWqktEwgzFKYOFLa2RoDc4RT7HtEN/QkWw5UDWJ5BDsR+hJR90 by4A==
X-Gm-Message-State: AGi0PuY1yRztg44IwzRlOTMr6NX3+OPIY9vLhCryCwH4BdEnrqPZvRHn 8FdWdYNa8AwZqquiigMhWcMGe16BZM2TxdF+Z2hH4KRsgT0=
X-Google-Smtp-Source: APiQypI8Y2uj9mli/yZoJTi1aeCz58m8oDQf1v2aCt3cLu04HUNhCN39bTn9wxxmv0ufOQPBpz7iya5BXVnU7XEtEZQ=
X-Received: by 2002:ac8:6d23:: with SMTP id r3mr2845300qtu.84.1587130351807; Fri, 17 Apr 2020 06:32:31 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Fri, 17 Apr 2020 09:32:14 -0400
Message-ID: <>
To: Joel Alwen <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="000000000000d501a805a37c9480"
Archived-At: <>
Subject: Re: [MLS] somewhat better PCFS for cheap
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, 17 Apr 2020 13:32:35 -0000

Hi Joël (and Sandro),

Thanks for the thoughts.  I agree that Option 2 makes sense.  In fact, I
think it agrees pretty much with what I was thinking, and the current doc
is wrong.  In particular, where it says "the HPKE secret key
"leaf_hpke_secret"" in the text you quote, I would have expected that
"leaf_hpke_secret" to be a secret from which the leaf HPKE private key was
derived, basically the same as your pre-seed.

One note to all this, though: None of this is visible to anyone except the
holder of the leaf.  So the other members of the group have to trust that
the leaf holder is doing the right thing.  The issue is the same as with
decoherence higher up the path; either way, we lack a way to prove that two
public keys correspond to private keys that are derived from sequential
path secrets going up the tree.  As before, I don't think this is fatal,
and we should proceed.

Do you want to draft a PR?


On Fri, Apr 17, 2020 at 3:51 AM Joel Alwen <> wrote:

> Hey Everyone,
> Sandro Coretti and I have the following suggestions for how "hash up the
> tree"
> during a Commit works. (C.f. Section 5.4 in MLS protocol version 9). The
> goal is
> to (cheaply) fix the FS of TreeKEM (ergo the PCFS of MLS).
> The Issue: Currently all new keys inserted into the ratchet tree in a
> commit
> (not to mention the resulting commit_secret) are all derived
> deterministically
> from leaf_hpke_secret of committer's new leaf key. That value is in turn
> sampled
> freshly at commit time by the committer.
> For concreteness: offending lines in mls-protocol-09 Pg. 17
> -------- snip ----------
> The generator of the Commit starts by using the HPKE secret key
> "leaf_hpke_secret" associated with the new leaf KeyPackage (see
> Section 7) to compute "path_secret[0]" and generate a sequence of
> "path secrets", one for each ancestor of its leaf.
> path_secret[0] = HKDF-Expand-Label(leaf_hpke_secret,
>                                       "path", "", Hash.Length)
> -------- snip ----------
> The Problem: Suppose Alice commits. If her resulting leaf HPKE priv key
> ever
> leaks, the adversary learns all keys generated in her commit. Thing is,
> thats
> true even if all those keys have since been overwritten and removed from
> her
> state by the time her state leaks. Her leaf priv key alone is enough to
> re-derive all of them. Zooming out a bit, for TreeKEM this means poorer FS
> than
> need be. Zooming out further, for MLS we get poorer PCFS than need be.
> Proposed Solution: We say "poorer than need be" because there are many easy
> fixes here. E.g.
>  - Option 1 (simplicity) sample the HPKE leaf key pair using fresh random
> bytes.
> Also sample a "derive_secret" independently for doing the deterministic
> deriving
> up the tree.
>  - Option 2 (saves on consumed random bytes) sample a pre-seed. Expand it
> (e.g.
> with HKDF-Expand) to two independent secrets. Use one to generate HPKE
> pub/priv
> key pair for leaf. Use the other to do the hashing up the tree. (This is
> how we
> modeled TreeKEM in eprint/2019/1189.)
> Personally, I'm partial to 2 because, as a general rule of thumb, I like to
> conserve entropy demand. It can be a rare commodity in some deployments
> and when
> implementers start doing things like calling /dev/random instead of
> /dev/urandom
> you can end up depleting entropy.
> So, for concreteness how about this?
> -------- snip ----------
> pre-seed <-- {0,1}^secparam
> //first half of output goes in seed, second half in leaf_hpke_secret
> seed, leaf_hpke_secret = HPKDF-Expand(pre-seed, "leafgen",
>                                                         "", Hash.Length)
> -------- snip ----------
> leaf_hpke_priv, leaf_hpke_pub = Derive-Key-Pair(seed)
> - Joël & Sandro
> _______________________________________________
> MLS mailing list