Re: [MLS] New Parent Hash

Raphael Robert <> Thu, 31 December 2020 15:44 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 1BC513A0D43 for <>; Thu, 31 Dec 2020 07:44:35 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Cfj1r9skBSv3 for <>; Thu, 31 Dec 2020 07:44:32 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::632]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 327D13A0D44 for <>; Thu, 31 Dec 2020 07:44:32 -0800 (PST)
Received: by with SMTP id g20so25792563ejb.1 for <>; Thu, 31 Dec 2020 07:44:32 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=eHlRmvQ+LH5KHEad9qDO2/ETQhtYnumEqPtpsflVvww=; b=v77FiDxD7hrtRHrd6yXMAnnmPEfzHywXB0RCMkvwUBdy3xJxUeGWVo3cYoLFuGMNHR E8Ruz+HmdtTzB9hH3gsMJttOFmgrIWFHmkHSKD6R7ZxYA3fBs9KevLQ8s57ktV4nwohj oip0EVBzLFvJdPKN2akkasxZ/vzJXPwkZ/YaLLm1PEAToZatzXpgUsdBz8w75IaRZWxR yV5PxZKbBcFHLcgFECYr452JrDgbk3Nt3tAc9779lgpoweBwGzPA/D0zY66WfidJ0XZ7 I/bMViqC+s4XIYyyrhBLbsVVls2afCWvJacjM49sYelr/QtRWKje8Vd365U3A5BWA8Cd xCrw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=eHlRmvQ+LH5KHEad9qDO2/ETQhtYnumEqPtpsflVvww=; b=VIPekacRAnW29wMpjpTrNu7PDMjp6dnvaBDsJFVmTk6MkuPctXNi/pb5THK2kS7Fyc eP+EVzR52axDnK87mrzMartemhQuBQ3u398XemZ1qSibt4JMURY4U3mxh9tx7GCoaNtO BTKDGc3m6hLuvwwDws6Q9Ksy9IKA9g1tcKE4UTQRrmbgLyxH8fizyAYtSVupMu4OOhFV x6B7ttSAHubon3p1bRKZF3PUM81EmDyikJ+7xKevm2cdTJzWcWvuT6jrYm6ANz3p2DZr ueTNdYcLvsac82R0GWqnJkOIkBDpffW+tHGNzNSg7MbguuJZ8QQYw49wfRe5fk4eqPO5 3Dgw==
X-Gm-Message-State: AOAM533WWlyR9eKSdXrKun/y7bgnmgjB+Mcho4weTS8OEA/fmAt80XYx vK4MlqoMBCiyrDCYS1LQZD1NEg==
X-Google-Smtp-Source: ABdhPJyAMD8/l1CQJrgnH9tFMMfb4DYXL3H0R6yWwcnkUhZfBrhzsRPLa6XtWySbHnDsJL1mwfeaWg==
X-Received: by 2002:a17:907:118e:: with SMTP id uz14mr52657809ejb.83.1609429470415; Thu, 31 Dec 2020 07:44:30 -0800 (PST)
Received: from ([]) by with ESMTPSA id t15sm15917611eds.38.2020. (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 31 Dec 2020 07:44:29 -0800 (PST)
From: Raphael Robert <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_1DAB79FC-C5CC-42CF-AD4E-06AB9B197CE6"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.\))
Date: Thu, 31 Dec 2020 16:44:27 +0100
In-Reply-To: <>
Cc: Joel Alwen <>, "" <>, Messaging Layer Security WG <>
To: Mularczyk Marta <>
References: <> <> <>
X-Mailer: Apple Mail (2.3654.
Archived-At: <>
Subject: Re: [MLS] New Parent Hash
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 31 Dec 2020 15:44:35 -0000

Hi Marta,

I am talking about draft-11 (which is the only one that contains the new strong parent hash scheme).

Looking at it again, I agree that that particular sentence is indeed a bit ambiguous. “Descendants” are direct descendants in that case (or non-blank children of blank nodes). We should change that confusing wording. However the part that follows is correct I think:

	• The resolution of a non-blank node comprises the node itself, followed by its list of unmerged leaves, if any
	• The resolution of a blank leaf node is the empty list
	• The resolution of a blank intermediate node is the result of concatenating the resolution of its left child with the resolution of its right child, in that order

If you apply these three rules recursively, you only get a list of certain non-blank nodes in the subtree, not the whole subtree. In the extreme case that the subtree does not have any blank nodes, you only get the head of the subtree and its unmerged leaves (if any).

As for the example, you are right that the resolution includes unmerged leaves (I forgot about that because it was only added later), so the resolution of node 5 is indeed [CD, C]. 

That being said, I still think the “original child resolution” of S should cover all non-blank nodes in the subtree of S that are not in the unmerged leaves list of S. As mentioned before, in the example from above that would be [CD, D] (C is removed because it is in the unmerged leaves list).

To avoid any confusion with the current resolution, I would propose the following naming and definition:

"Finally, child_subtree_nodes is the array of HPKEPublicKey values of the nodes in the subtree under S but with the unmerged_leaves of P omitted. The nodes in the subtree under S are all non-blank nodes of that subtree including S itself, if S is not a blank node. The nodes in the list are ordered by their indexes.”

Would that work?



> On 31. Dec 2020, at 16:02, Mularczyk Marta <> wrote:
> Hi Raphael,
> There indeed seems to be a misunderstanding about how "resolution" is defined. In the version of the draft I see, in 5.2 the resolution is defined as "an ordered list of non-blank nodes that collectively cover all non-blank descendants of the node" and not just the first one. Also, 5.2 says that the resolution of node 5 is the list [CD,C] and not [CD]. Can you point to the version of the draft you're referring to?
> Best,
> Marta
> From: MLS <> on behalf of Raphael Robert <>
> Sent: Thursday, December 31, 2020 12:47:28 PM
> To: Messaging Layer Security WG
> Cc: Joel Alwen
> Subject: Re: [MLS] New Parent Hash
> 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 <> 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
> >
> > <>
> _______________________________________________
> MLS mailing list
> <>
> <>