Re: [MLS] somewhat better PCFS for cheap

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 <rlb@ipv.sx> 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 <jalwen@wickr.com <mailto:jalwen@wickr.com>> 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
> MLS@ietf.org <mailto:MLS@ietf.org>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls