[MLS] somewhat better PCFS for cheap

[Joel Alwen <[e-mail]>]

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