Re: [MLS] somewhat better PCFS for cheap

Joel Alwen <> Wed, 22 April 2020 12:50 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 35A6F3A0B7B for <>; Wed, 22 Apr 2020 05:50:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-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 gNqlZdMaPYkV for <>; Wed, 22 Apr 2020 05:50:42 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::641]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 823D23A0B79 for <>; Wed, 22 Apr 2020 05:50:42 -0700 (PDT)
Received: by with SMTP id h11so884808plr.11 for <>; Wed, 22 Apr 2020 05:50:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=subject:to:cc:references:from:autocrypt:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=YivFJU2JylubC5boGDBC9NHoSx0AjTQK82pvV42kw5A=; b=Um1UMk6Oc/fDAAYWnFwNKiYgRT9xzAAvn+pOqJUpZ6huMdtJqE7cPS9aGq/Br27aLX +1N+b5LMS72JizR4sri4bbZRivSq6FafLqRKTUyxF0SJvqAaHN++XrC1/76MUBk+edP9 tbcXVUcH86sWDvmo5hHZRdcuueBtmLSVloYJ2jEbOOPl6h+N5bYvJoUa379061C4n0uC ThrBJlcx8gc+LRcgDz8mME/dzYQN78kM6HRBdBD+DAOZLwWk92UjpgNlK8KGa2DTzGci GTnsUXeMWCMUgbzctm2Ff8fsCRKkrxGTdr8+Ybk2WVNwZUicEwMLEPZHY9p79eIDXzeM S4qA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=YivFJU2JylubC5boGDBC9NHoSx0AjTQK82pvV42kw5A=; b=R63Z2KOZ/mlK4I6qrksuuccba41ha8rwT6fNAepe7fDcKCxzMkKP6lm8RL0I67P3N9 otboppMo5nbFIDp3LsG6pFZcCx0Ao6X+s9SzyrxDQ0wi3KNypCcBzGGZgo/cfaZd+/rM JhmHHi6e0IrY3tRv1uI/IUngIW34YlbvGNZoL1UoIUBOX8yMf0z40d86P0G8hnLIi0yB gnb/rDx1LEuyqTM/3/qbKmSzshlOUvgN4/fqSbkCadVN5Z74OlBr4RbLHWyWuTpQyzWB goO5PxNzjKhzC9XyP67oalch4IA06ROyWt96BI2xvULGRzIK9p9M0qSdfLD3uQsZD09t zv0w==
X-Gm-Message-State: AGi0PuZzEZQQQjasTB2lIl5mRFCCFMp8nHTwcNiyWhV54FqAU4iWLKXk kNKTkBo9JDykjF7fSFc/nR67AgxwsaY=
X-Google-Smtp-Source: APiQypJ5fwZrCPpppMd33TA9GsX/PT3KhvVvK7HsnMZq4mDWf+br2nJG4/pgiKqdbilFB5t+ymeVww==
X-Received: by 2002:a17:90a:7482:: with SMTP id p2mr11447555pjk.151.1587559841626; Wed, 22 Apr 2020 05:50:41 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id j26sm5050444pgm.20.2020. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 22 Apr 2020 05:50:41 -0700 (PDT)
To: Richard Barnes <>
Cc: Messaging Layer Security WG <>
References: <> <>
From: Joel Alwen <>
Autocrypt:; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0Lw==
Message-ID: <>
Date: Wed, 22 Apr 2020 21:50:38 +0900
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
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: Wed, 22 Apr 2020 12:50:44 -0000

> Do you want to draft a PR?

Yup, I'll go for it.

- Joël

On 17/04/2020 22:32, Richard Barnes wrote:
> 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?
> --Richard
> 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
> <>