Re: [MLS] Circular dependency in node hash calculation?

Raphael Robert <raphael@wire.com> Mon, 06 July 2020 20:43 UTC

Return-Path: <raphael@wire.com>
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 87FAA3A0A8D for <mls@ietfa.amsl.com>; Mon, 6 Jul 2020 13:43:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-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 (2048-bit key) header.d=wire-com.20150623.gappssmtp.com
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 epv-DsJ381ob for <mls@ietfa.amsl.com>; Mon, 6 Jul 2020 13:43:38 -0700 (PDT)
Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B3AB53A0A8C for <mls@ietf.org>; Mon, 6 Jul 2020 13:43:38 -0700 (PDT)
Received: by mail-wm1-x333.google.com with SMTP id 22so40641648wmg.1 for <mls@ietf.org>; Mon, 06 Jul 2020 13:43:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wire-com.20150623.gappssmtp.com; s=20150623; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=ofW7sbbmnuku+q8wr9k0xagljrDAlnncTb/dP0iXYGU=; b=xfCdYi7JeUe5ud2d+rVUEvBEqPudqyVb6HO5Kn6B3A/FuEF8kIAufnNDCR6CjO2BUg D+8UVR1Qgr+E7u6QZ6unwololF1AOs5mGQLVk9WNanQqPKU+b5pRDO74zRqKVM2gH3fl Lzxsqcr8wC6ws+dgEXGM7LIUQiAx2Vu5YzS0gePEsWr2hWtUL/hECTHm9j547B/Icd2e xylMI89ZJg2ROKmrSWINLsXkrBguj8jXEnDBZ7MvG/P3Y/PeYh3qgG0i0/Q29PfwjMAL hKhXJI3B+OQiUvI6AQqKJI5Y0zVeHSQYGQxKNICcd/El3ttxyONj1Ch/VHGyjCouvfbQ h3dQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=ofW7sbbmnuku+q8wr9k0xagljrDAlnncTb/dP0iXYGU=; b=oWuE5AyDmVBLq0MDbKfMct7KkXH50CccLuYWJsbS1dw/sA3EHuBsAYglQXqhZWi8Ku fILwTlUQc56U6QmM1G1iaKARRZgV48P20c6ySk0SPnRaKwAlTERPch8M5JGqEofODmY6 hZq+RrBzCw5Mo5pGrRO4L3lpqFi97u1oSyK8E1jUP1GK//xkRETxPz20nIiwrJPvFw9d hOL34fXYVmmzvldpqhMZCxHCVRL65o9hNlc4Yrks1WDqK1wpEaCS1qciCz11/6B3Lm1w fVeP13NqdEG6cG6ZllH+X1tu/u3eERt19G/Bo1b4eF7KHIrmrg4f/iN/adAZi3Iqbovm R9Gg==
X-Gm-Message-State: AOAM5330vsaMXEghRzRj6ROcm4Dpyg4MGWMmWkM4wwVKePvISHqREG/A GNMOlU4fNGdlq57bExO+7MAtB7Xj20s=
X-Google-Smtp-Source: ABdhPJwSZpQV/7b1WHGuB5ChAccI59rDLihi5d2mcS+pifRXcuBx3jthXrONbcbKVLbbT54snZoOCQ==
X-Received: by 2002:a1c:4c16:: with SMTP id z22mr896801wmf.103.1594068216983; Mon, 06 Jul 2020 13:43:36 -0700 (PDT)
Received: from [192.168.178.21] ([134.3.30.253]) by smtp.gmail.com with ESMTPSA id l8sm25207572wrq.15.2020.07.06.13.43.36 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 06 Jul 2020 13:43:36 -0700 (PDT)
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.80.23.2.2\))
From: Raphael Robert <raphael@wire.com>
In-Reply-To: <51A5B187-EAAB-4126-BE29-C18ADAFFB179@wire.com>
Date: Mon, 6 Jul 2020 22:43:05 +0200
Cc: Messaging Layer Security WG <mls@ietf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <4BB46738-4B7D-472C-B8DA-A51A93B33DD9@wire.com>
References: <2d1b-5f035980-1-53713100@74279099> <51A5B187-EAAB-4126-BE29-C18ADAFFB179@wire.com>
To: Hubert Chathi <hubertc@matrix.org>
X-Mailer: Apple Mail (2.3608.80.23.2.2)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/XLxFN0UHfE8KYkrtofsQSk4jaLA>
Subject: Re: [MLS] Circular dependency in node hash calculation?
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 20:43:41 -0000

(forgot to include the list)

> On 6 Jul 2020, at 22:05, Raphael Robert <raphael@wire.com> wrote:
> 
> Hi Hubert,
> 
> I admit this looks a bit confusing. The parent_hash field of a ParentNode is not to be calculated at that point in time. Instead, it should already be there. It gets populated by processing a Commit message, where a LeafNode gets updated and its entire direct path is also updated. In other words, calculating the tree hash is strictly a top down operation.
> 
> Regarding the serialisation: MLS uses the TLS presentation language specified in RFC8446.
> 
> Raphael
> 
>> On 6 Jul 2020, at 19:04, Hubert Chathi <hubertc@matrix.org> wrote:
>> 
>> 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
>> 
>> _______________________________________________
>> MLS mailing list
>> MLS@ietf.org
>> https://www.ietf.org/mailman/listinfo/mls
>