[MLS] somewhat better PCFS for cheap

Joel Alwen <jalwen@wickr.com> Fri, 17 April 2020 07:51 UTC

Return-Path: <jalwen@wickr.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 9AD463A0FCA for <mls@ietfa.amsl.com>; Fri, 17 Apr 2020 00:51:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 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] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=wickr-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id hTY22CDwU4br for <mls@ietfa.amsl.com>; Fri, 17 Apr 2020 00:51:18 -0700 (PDT)
Received: from mail-pj1-x1041.google.com (mail-pj1-x1041.google.com [IPv6:2607:f8b0:4864:20::1041]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9120A3A0FCC for <mls@ietf.org>; Fri, 17 Apr 2020 00:50:57 -0700 (PDT)
Received: by mail-pj1-x1041.google.com with SMTP id a22so728626pjk.5 for <mls@ietf.org>; Fri, 17 Apr 2020 00:50:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=to:from:subject:autocrypt:message-id:date:user-agent:mime-version :content-language:content-transfer-encoding; bh=IEMyvTL0jVK7qJvA44W7u1CdnXWq2TaA3jtcrh6m9rg=; b=C/E2yZwaDPovkebLA1YEnuNSUHh+WgHBMDJ/4vXjjINKx10gC53xM8ZkGdXmkwQMPt wdctKHtY2mcZZslUSHfxKm6wmlAcionyiaQvtxqWw3Dsz+rklbb4yJ/Cu7egyqs+6H/8 WoDoExoFxCY8fM831xyIjJ1B/1w0YhgxRCNKH3CP9iaURFx5lD64aw1f4Q3hjMui9W2w qGxEk0ahNtTjqwwD5VAeie1VbF5GqDifQL6yh0yM9v+IZ2045JRQTVluq2xn/+UQyGhn 74F6uKGu/Xy5eIP5BmtbgXLrdRfG7E3dEk4MFKOJVoU7rXtKu4gkdxtnwSixBkRE0srY bskQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:autocrypt:message-id:date :user-agent:mime-version:content-language:content-transfer-encoding; bh=IEMyvTL0jVK7qJvA44W7u1CdnXWq2TaA3jtcrh6m9rg=; b=CztZvyOnGxN4yvjWe1G4vBxwcBMhBHgiKyuLvC559YiGuyERPoNIlWo8/s5J8/sNf9 9y0wYDNY2omTQHcOHf1LmtxBsF/y6GeW448qg6Q+tPkHKSgSKzrRsZRLNk/9qdbvFjM7 yPVyskusT4awXw31vl7qsyFusQGCEVUW6M3jhUDsnsSzXS95gFqa9xVVhP5S99C+EmH3 oFM3FS0AaxSixW5clxpE6AbEt/CkQKFkhVNbwIXASXIpM3Up5UqeUjcdU0vEJdUh+vbM laWZ3cClv/InPqc+kFgW0fVAZMAb2L4Me9oihSIpNTqrvdfn5Jz6mtcH0zi4J7bZ19DB L0yg==
X-Gm-Message-State: AGi0PuY/LdwGOmMHLyjr5RweDpM/BL+2jxDsFDizLUsO0/qKrivSxtlp XvGSzPSmhr5f9nuJ8ug/lWcZJAdERC4=
X-Google-Smtp-Source: APiQypI2reSgCUmREXjXXj7VGu/83LitHZn7n2vJ64J/HsGEFcKwzlvGBuQdVihEXhX7KFP2MFWw4A==
X-Received: by 2002:a17:90a:77cb:: with SMTP id e11mr3011399pjs.0.1587109856815; Fri, 17 Apr 2020 00:50:56 -0700 (PDT)
Received: from [] (zaq3dc06154.zaq.ne.jp. []) by smtp.gmail.com with ESMTPSA id b11sm18890358pfr.155.2020. for <mls@ietf.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 17 Apr 2020 00:50:56 -0700 (PDT)
To: Messaging Layer Security WG <mls@ietf.org>
From: Joel Alwen <jalwen@wickr.com>
Autocrypt: addr=jalwen@wickr.com; 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: <17d24e72-c331-3a2d-3d33-5dfd59d069ab@wickr.com>
Date: Fri, 17 Apr 2020 16:50:54 +0900
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/dUl3X_gjwiOt7_oOvBw2JaGM4D4>
Subject: [MLS] somewhat better PCFS for cheap
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 17 Apr 2020 07:51:22 -0000

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