Subject: [MLS] somewhat better PCFS for cheap

From: Joel Alwen <[email-masked]>
Date: Fri, 17 Apr 2020 16:50:54 +0900

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

---

From: Richard Barnes <[email-masked]>
Date: Fri, 17 Apr 2020 09:32:14 -0400

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 <[email-masked]> wrote:

> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Russ Housley <[email-masked]>
Date: Fri, 17 Apr 2020 10:01:13 -0400

Mixing new and old is a clean solution.  Thanks for writing it down so clearly.

Russ

> On Apr 17, 2020, at 9:32 AM, Richard Barnes <[email-masked]> 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.
> 
> On Fri, Apr 17, 2020 at 3:51 AM Joel Alwen <[email-masked] <mailto:[email-masked]>> wrote:
> Hey Everyone,
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Joel Alwen <[email-masked]>
Date: Wed, 22 Apr 2020 21:50:38 +0900

> 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.
> 
> 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.
>