Re: [MLS] New Parent Hash

[Hubert Chathi <[e-mail]>]

I think that if you use "descendants" as you define it, then calculating the parent_hash will become O(n) all the time, rather than O(log n) in the best-case, since the size of the descendants list will be O(n).  I'm not sure if there's a good way to maintain O(log n) and still provide the desired security.

On Thu, 31 Dec 2020, at 06:47, Raphael Robert wrote:
> Hi Joël, Daniel and Marta,
> 
> I just implemented the stronger parent hash scheme you proposed in the 
> way it is described in the spec now.
> The good news is that it is implementable, the bad news is that is does 
> not solve the problem you initially describe. Specifically, swapping 
> out two leaf nodes still goes undetected.
> 
> I think it is due to a terminology conflict, but it would be great if 
> you could validate that assumption.
> In 7.4 you introduce the notion of “original child resolution” as " the 
> array of HPKEPublicKey values of the nodes in the resolution of S”. The 
> term “resolution” is defined in 5.2. It is essentially a way of dealing 
> with blank nodes by substituting them with the first non-blank 
> descendants you find when descending the subtree of a node. 
> Here is my assumption: You probably thought the resolution would cover 
> all non-blank descendants of a node, not just the first non-blank 
> descendant. In that case we would need another function that does that 
> (let’s call it “descendants”).
> 
> If we look at the example of 5.2:
> 
>  - The resolution of node 3 is the list [A, CD, C]
>  - The descendants of node 3 is the list [A, CD, C, D]
> 
>  - The resolution of node 5 is the list [CD]
>  - The descendants of node 5 is the list [CD, C, D] (we just need to 
> additionally filter out C, because it is an unmerged leaf of node 5)
> 
> Here is a code snippet of what the “descendants” function would look 
> like (sorry that it’s Rust, not Python):
> 
> fn descendants(x: NodeIndex, size: LeafIndex) -> Vec<NodeIndex> {
>     if level(x) == 0 {
>         vec![x]
>     } else {
>         let left_child = left(x);
>         let right_child = right(x, size);
>         [
>             descendants(left_child, size),
>             vec![x],
>             descendants(right_child, size),
>         ]
>         .concat()
>     }
> }
> 
> There’s a more efficient implementation of course, this is just to illustrate.
> 
> In other words, the new “original child resolution” of S would be the 
> subtree under S, but with filtered-out blank nodes and unmerged leaves 
> of S.
> 
> If my assumption is correct, I’ll follow up quickly with a PR since 
> this is currently a blocker for interop based on draft-11.
> 
> Thanks
> 
> Raphael
> 
> 
> 
> > On 12. Nov 2020, at 22:14, Joel Alwen <[e-mail]> wrote:
> > 
> > Hey people,
> > 
> > Just a quick heads up that Daniel, Marta and I put in a PR with a new version of
> > strong parent hash to prevent the attacks from the earlier thread. We tried to
> > make it as minimal as we could to help with deniability while still preventing
> > the attacks permitted by weak parent hashes.
> > 
> > In a nutshell, when computing parent_hash at node v with parent p and sibling w
> > we include
> > - p's HPKE pubkey
> > - p's parent_hash value and
> > - HPKE pub keys in the resolution of w except for those belonging to leaves
> > unmerged at p.
> > 
> > As a sanity check, notice that as long as p's keys remain the same one can
> > always recompute the same parent_hash value at v as was initially computed by
> > the member that set p's keys. (In other words, new members can verify that the
> > stored parent_hash values match whats in the tree.) In particular, that's coz as
> > long as p's keys are unchanged so is the resolution of w. The only exception are
> > leaves being added as unmerged at w. But those leaves are also added as unmerged
> > at p so they are left out of the hash.
> > 
> > As for deniability, at least parent_hash only binds HPKE keys and nothing else
> > (like, say, credentials or signatures). Its the best we were able to come up
> > with for now...
> > 
> > - joël
> > 
> > _______________________________________________
> > MLS mailing list
> > [e-mail]
> > https://www.ietf.org/mailman/listinfo/mls
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>