Re: [MLS] Quicker Provisional GroupContext

[Richard Barnes <[e-mail]>]

Hey Joël,

I actually don't find updating the tree hash all that intimidating, in that
it's pretty easily streamlined with caching.  The hashes from the old tree
still apply, except where they've been invalidated by applying proposals.
An Add/Remove/Update invalidates hashes along its direct path, so you
basically end up needing to update N_proposals * log(N_leaves) nodes.
Truncation can add more nodes to the mix here, but the main effect of that
is to require updated hashes along the right edge of the tree, again
log-size.

You need to do log(N_leaves) more updates once you apply the UpdatePath.
But still, everything is roughly log-scale.

--Richard

On Tue, Apr 26, 2022 at 9:55 PM Alwen, Joel <alwenjo=
[e-mail]> wrote:

> Hey people,
>
> Marta, Tom and I had the following thought. When creating/processing a
> commit, clients must create a provisional GroupContext to feed as context
> to HPKE. The provisional GroupContext includes a "provisional tree-hash"
> i.e. of a tree-hash of the ratchet tree after the proposals have been
> applied but before the update path. That means we have to recompute a
> tree-hash which, for large trees can end up being a fair bit of work which
> we could avoid quite easily as follows.
>
> Instead, the context we give HPKE is defined to be the hash of
> 1) The old epoch's GroupContext and
> 2) The list of proposals.
>
> In terms of security & functionality this changes nothing as (1) and (2)
> combined fully determine the "provisional GroupContext" we currently use.
> In other words, the new context commits to the same info as now. But it
> avoids any, possibly expensive-ish, tree-hash computation / tree traversal
> since we've already got the old GroupContext from when we started the
> previous epoch.
>
> Are people OK with this change? We're willing to put together a PR to
> implement it. It should be very small.
>
> - Joël
>
>
>
>
> PS. Funny related observation: The role of the HPKE context is to bind the
> ciphertext as much as possible to its intended use e.g. to constrain as
> much as possible how an adversaries can reuse honestly generated ciphertext
> in injected traffic. So normally I'd say, lets add the specific node and/or
> public key to which our MLS ciphertexts are being encrypted since: why not?
> Bind to everything we can right? It can only make an adversaries life
> harder.
>
> Thing is, at first glance, provisional GroupContext only fixes the epoch's
> state but *not* the specific node to which we're encrypting. But if you
> unwrap HPKE, you'll see that context is bound to the HPKE ciphertext by
> feeding it to HKDF when deriving the DEM encryption key. As it turns out
> though, the receiver PK is *already* being mixed in to that key in an
> earlier HKDF call in it's derivation chain (just not as part of the
> "key_schedule_context" variable). So adding it to HPKE context would
> actually be redundant. In fact, this even locks down the node to which
> we're encrypting because we include tree-hash. Happy coincidence? Or clever
> engineering? I'm going with the latter. :-)
>
> In theory we could lock down things juuuuust a bit more by including the
> actual node index to which we're encrypting. E.g. in theory PK's could
> repeat at leaves, e.g. at a pair of leaves if one of them belongs to an
> adversary. But maybe that's just taking this whole context binding one step
> too far...
>
>
> Amazon Development Center Austria GmbH
> Brueckenkopfgasse 1
> 8020 Graz
> Oesterreich
> Sitz in Graz
> Firmenbuchnummer: FN 439453 f
> Firmenbuchgericht: Landesgericht fuer Zivilrechtssachen Graz
>
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>