Re: [MLS] New Parent Hash

[Raphael Robert <[e-mail]>]

Thanks for the lengthy explanation!

I’m glad we are on the same page regarding the definition of the resolution. I think I understand where the misunderstanding is coming from.

Initially you proposed a “strong hash” solution on the ML (on Oct 23 2020) that was the following:

"strong parent_hash" : Define parent_hash to include tree_hash (and tree_hash to
*not* include parent_hash). The tree_hash of a node covers all values in the
subtree rooted at that node  (except the parent_hashes and signatures). So
basically something like this:
	- leaf.tree_hash := H(leaf.data)
	- node.tree_hash := H(node.data, node.lchild.tree_hash, node.rchild.tree_hash)
	- root.parent_hash := 0
	- node.parent_hash := H(node.parent.tree_hash, node.parent.parent_hash).

This definition did include the whole subtree and therefore I was assuming that this would also end up in the spec change. As far as I now understand, you went for a more lightweight approach where you say that just using the resolution is enough, because pinning all nodes in the subtree is not necessary and would only prevent “benign” attacks. I guess I missed the part where you switched from one concept to the other.

What I discovered during implementation is that when you only use the resolution approach and the tree has no blanks, you are not always able to detect if the attacker has swapped two leaves. This might indeed just be a benign attack in the sense that the tree invariant is not violated. 

At this point I don’t have strong arguments for or against using the resolution approach, I would have to think about it some more. Just as a reminder for context, the original concept by Benjamin and Karthik was “parent hash covers the tree hash”. That’s pretty much what you initially proposed, except that it also covered the KeyPackage at the leaf level, not just the HPKE public key.

My question right now would be: What is the benefit of the lightweight resolution-based approach? If it’s just efficiency, we should look at whether there’s really that much to gain.

On efficiency:
The parent hashes are verified in two instances: a) when a new member joins the group and validates the public tree it received and b) when a member receives a full Commit from another member.

Re a): The spec now says "Moreover, when joining a group, new members MUST authenticate each non-blank parent node P. A parent node P is authenticated”. This means the effort is linear to start with. Depending on how you define the operation, it is even worse than linear. Say the tree has n leaves and therefore 2n-1 nodes. For every node, we need to iterate over at least a part of the subtree and collect public keys that we then concatenate. We end up only hashing once per node, but with a variable size payload. I think the cost of navigating the subtree and collecting the keys is O(log n) for the “resolution approach and O(n) for the “descendants" approach and the cost of hashing is linearly proportional to the size of the payload. If we assume that hashing is the most expensive operation, the total cost would be O(n * log n) for “resolution” and O(n ^ 2) for “descendants". 

Re b): It is very similar to a), except that we only have to iterate over log n nodes of the direct path, not the whole tree. That means that the total effort is O(log n * log n) for “resolution” and O(n * log n) for “descendants”.

There’s clearly a difference in terms of efficiency between the two approaches. That being said, we should keep in mind that for small payloads, hashing is a lot faster than other cryptographic operations like e.g. producing and verifying signatures. Since a new joiner needs to also verify n signatures when joining a group, it could well be that the effort of verifying the parent hashes is negligible compared to the cost of verifying all signatures.

In summary: I still don’t have strong arguments against the “resolution” approach, but I also have a feeling that the efficiency differences are not dramatic either.

Happy New Year and thanks!

Raphael

> On 1. Jan 2021, at 15:48, Mularczyk Marta <[e-mail]> wrote:
> 
> Hi Raphael,
> 
> Thanks
>  for explaining! Using "descendants" is definitely better for security, but also, as Hubert mentioned, less efficient.
> 
> Also
>  we did understand “resolution” the same way as you when we proposed the strong parent hash (sorry for the confusion). 
> 
> But
>  we obviously really want to understand if/why using resolution is insecure. Ultimately, the security property we care about is that privacy and authenticity of application messages holds. The Parent Hash mechanism helps us ensure this holds also for epochs
>  in adversarially generated groups, as long as the adversary does not control any leaves in this epoch (i.e. does not know the signing key of the leaf). So to really see if your examples break security, it would be good to see if they let us violate this security
>  goal.
> 
> To
>  see why we believe the new parent hash notion (i.e. with resolutions) achieves this, let us first clarify what technical property about (even adversarially produced) ratchet trees we want from verifying parent hashes. It’s not that the adversary can’t produce
>  manipulated trees at all. It’s that the only manipulations she is able to do will not let her produce a tree that violates the tree invariant. That’s because (in our model) when the tree invariant holds then we can show that the epoch is secure.
> 
> So
>  some manipulations *are* possible. They are just “benign”. For example, suppose adversary A controls a leaf L with HPKE key pk in tree T (i.e. she knows the signing key of L’s owner). Then A can construct a new tree T’ identical to T but where leaf L has pk’
>  != pk (say, by performing a commit at leaf L to obtain T’). But for this, in T’ leaf L must still be controlled by A. We call this manipulation “benign” because even though A might now break privacy of application messages in epoch with tree T’ it doesnt violate
>  our security goal because privacy is conditioned on A *not* controlling any leaves.
> 
> Conversely,
>  one thing A can *not* do is the following. Say T’ has a node V with HPKE public key pk0 such that A knows corresponding sk0. Then for T’ to pass verification, it must contain a leaf controlled by A. This holds since for T’ to pass verification there must be
>  a leaf in V’s subtree with a signature covering a hash that includes pk0. I.e. some leaf must “attest” to having inserted pk0 into T’. (Recall that in our model the adversary can’t just leak sk0 alone. They must leak a full state of some client which also
>  means leaking the client's signing key.)
> 
> So
>  our question to you is the following. (Does this make sense? And) we’re not exactly sure what you have in mind when you say “swapping out two leaf nodes”. But we think it would only be a problem if it is not benign. Is this true for your attack? Could you
>  expand a bit on what tree manipulation you have in mind?
> 
> Best,
> Joël
>  & Marta
> From: MLS <[e-mail]> on behalf of Hubert Chathi <[e-mail]>
> Sent: Thursday, December 31, 2020 5:36:53 PM
> To: [e-mail]
> Subject: Re: [MLS] New Parent Hash
>  
> 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 <https://www.ietf.org/mailman/listinfo/mls>
> > 
> > _______________________________________________
> > MLS mailing list
> > [e-mail]
> > https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> >
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>