[MLS] Circular dependency in node hash calculation?

Hubert Chathi <hubertc@matrix.org> Mon, 06 July 2020 17:04 UTC

Return-Path: <hubertc@matrix.org>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 66B443A1578 for <mls@ietfa.amsl.com>; Mon, 6 Jul 2020 10:04:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (4096-bit key) header.d=matrix.org
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ShJ0l6ZafPhp for <mls@ietfa.amsl.com>; Mon, 6 Jul 2020 10:04:38 -0700 (PDT)
Received: from polemos.matrix.org (polemos.matrix.org [94.237.46.156]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4A14B3A16F3 for <mls@ietf.org>; Mon, 6 Jul 2020 10:04:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=matrix.org; s=polemos; h=Content-Transfer-Encoding:From:Message-ID:Subject:Date: MIME-Version:To:Content-Type:Sender:Reply-To:Cc:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=eepxV/3K9HPH7QuPK8cxNTrBdG+Kbp45cwsjhw+bQCI=; b=1sxl1ZW00JJB940uoHdO3nLojm uJ1o85qN3t9nuklT/7FpOWO9fS36RXPxpnoWHmvYgnmH0IDm/HBYC3lCQud9Z9BXUdalFPQspzz5n 8PHBolUdkbHNpAl2kUmaV0KQT37KpO2FcvdCMOoEtYkF8Ts3GTJOaZJz3ap5iDDxD5KPUR4KwhBJP XqhfdotQeocyPPF/244pGypBY0hnQFxjt+x32BXHdypGxsoClFg+ix1wLt4XNeYx6CzyoqGPBICHl Xx+ZfwhDq+gVNOMLxuxev9bxKYQg66zeNYyqjOU768/RC1TPjlo+VGofQZ0kUuPe9VwU/2aW9SC6+ 9ofr3dePfQDFizTdngbieOTtPqbveJRQoPuialG+dLldphmKTIz3Hnf/CjLI/Mdd9M81nZgqDpvGl nxh8E/WxJNkBEHBOmPh0c5vrN3M8NwrDtbwqhlLbhy4dEbiJAQ/sGzl3D4O5Xntic8+se5GEmdOvp PwVeqk85sL37PSuKbKVQ4dkxyPAuSfineYIKB5DK+gpCvSgBr9F7lzrYoX9hGU6J8W+X6ja0c1Vx4 Hv3SykXrhnh82ObOH1Ni9yysp5zISe/MfU4m3UUewMSOHi+bFGvajzqIlvBc3gsJMhX5IugG49KK5 4dcqoF2ATAH90JaDlDgOuXEP8FT/V9rIiHGj3Kjko=;
Received: from [127.0.0.1] (helo=localhost) by polemos.matrix.org with esmtp (Exim 4.89) (envelope-from <hubertc@matrix.org>) id 1jsUXk-00030j-Mc for mls@ietf.org; Mon, 06 Jul 2020 17:04:36 +0000
Content-Type: text/plain; charset="utf-8"
To: mls@ietf.org
User-Agent: SOGoMail 3.2.6
MIME-Version: 1.0
Date: Mon, 06 Jul 2020 18:04:36 +0100
Message-ID: <2d1b-5f035980-1-53713100@74279099>
X-Forward: 192.252.163.163
From: "Hubert Chathi" <hubertc@matrix.org>
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/UIWuwPC3ukryFUOANyH4cX4et3o>
Subject: [MLS] =?utf-8?q?Circular_dependency_in_node_hash_calculation=3F?=
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 06 Jul 2020 17:04:39 -0000

I may be missing something, but it seems to me like there is a circular dependency in the definition of the hash of a parent node.  In the "Tree Hashes" section, it says that when computing the hash of a parent node, you use the ParentNodeHashInput struct, which includes an item that is a ParentNode (which I assume is the data concerning the node that you are hashing), as well as the hashes of the two children.  However, ParentNode contains an item called parent_hash, which I assume is the hash of the node's parent.  Thus to calculate the hash of a node,  you need to calculate the hash of its parent, but that requires calculating the hash of both its children, meaning that you need to calculate the hash of node that you were trying to calculate in the first place.

Am I reading it wrong (and if so, can there be more clarification added), or is there a bug in the definitions?

Also, when calculating the hash of a struct, is there a prescribed serialization format to use, or is it up to the application to define the serialization format?

Thanks

Hubert