Re: [MLS] somewhat better PCFS for cheap

[Richard Barnes <[e-mail]>]

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 <[e-mail]> 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
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>