Re: [MLS] ?==?utf-8?q? Circular dependency in node hash calculation?

Hubert Chathi <hubertc@matrix.org> Tue, 07 July 2020 15:24 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 69DBA3A0E2F; Tue, 7 Jul 2020 08:24:42 -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 4A7P-xEFG63L; Tue, 7 Jul 2020 08:24:41 -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 48E3F3A0E1D; Tue, 7 Jul 2020 08:24:40 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=matrix.org; s=polemos; h=Content-Transfer-Encoding:Subject:Message-ID:MIME-Version:To:Cc :Date:From:In-Reply-To:Content-Type:Sender:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=70m2dXrDBe7/sxhwP2IsnjDPaB33HF4fonOrZUCiC88=; b=Qaugl8g8ZUsB1LV5mnEeTaIsCh 7IUvlJ6bQozIgZVrnzHOAOUBoTVRlxlVDHfqXQJ/tnWHwM0o/jDBoyHju7IJM4e1TS1i3YL0L0Hza DuKeThPZBKqxF48lpGWl8WhPVTDAKVfz8KBEEx6t5G6EWHnN2yJxgsx1Ubn1+4BCb9DQuos5n9und zQ15mEO7aQKck7HGX0bHavjcr9aQCfD5uFw448PHygkuHF9TPfYsyn0/G14/1qniT03Rbph+TxKSX xLCMIxVnmLnuxAoaSogsJQm7GpU0pXWhem127s1xnw6h0FD0ScTyOYLc84s/a42odAgPSXbqMv5Wi YIcBFm9obIh18uguqTZARklEy/yaKsplpin9k2Jk4RxuzRYiJQE2/EoiPDAQmIffU8667cj2gFAt+ MHANL7Urt37slua3D+0yQBXnAcBjROwi7M5hkyQ/nSeowNS9+JP84FS4kU972Hsexdoeiw9BjogBt 57Bypp71r97rPZ+XLQ4tm7sAZeF5J68fE5LsSGuFuSenq79J9RItTCNYldC2S3TA1qbayJ6+e4vhv vo7iU1UvZghjreNS5Zt4icwhPEJq1oHzgX6RMulJKHREfn3YW8cqaaNPfiQtIL+4Ei3lJzFfxATok 8YGWPcrCQ/MxARtlMGSzCfRuFyDL8Hvj8Ws87nN10=;
Received: from [127.0.0.1] (helo=localhost) by polemos.matrix.org with esmtp (Exim 4.89) (envelope-from <hubertc@matrix.org>) id 1jspSY-0004md-Bm; Tue, 07 Jul 2020 15:24:38 +0000
Content-Type: text/plain; charset="utf-8"
In-Reply-To: <CAL02cgSWYZQMTx_sX6Kh9sSA9hCmURJmeXsvWNN1uCXQ-XSeJA@mail.gmail.com>
From: "Hubert Chathi" <hubertc@matrix.org>
X-Forward: 192.252.163.163
Date: Tue, 07 Jul 2020 16:24:38 +0100
Cc: "Raphael Robert" <raphael=40wire.com@dmarc.ietf.org>, "Messaging Layer Security WG" <mls@ietf.org>
To: "Richard Barnes" <rlb@ipv.sx>
MIME-Version: 1.0
Message-ID: <47d2-5f049380-1-53b35d00@74914386>
User-Agent: SOGoMail 3.2.6
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/njI1mMkd7b6oDqBtYTsYRrtMeHU>
Subject: Re: [MLS] =?utf-8?q?=3F=3D=3D=3Futf-8=3Fq=3F__Circular_dependency_in?= =?utf-8?q?_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: Tue, 07 Jul 2020 15:24:43 -0000

Thanks to both of you for the clarifications.  I'll see if I can come up with a way to make it clearer.
 
On Tuesday, July 07, 2020 11:21 EDT, Richard Barnes <rlb@ipv.sx> wrote: 
 
> Yeah, just to restate / reaffirm what Raphael says:
> 
> * You get parent_hash values when you get the tree initially (in Welcome)
> or when you process a DirectPath
> * You compute node hashes based on those hashes, plus the other contents of
> the nodes
> 
> Totally agree that this is tricky to get right, though :)  If you have
> suggestions for how we can make this clearer, they would be welcome.
> 
> --Richard
> 
> 
> On Mon, Jul 6, 2020 at 4:43 PM Raphael Robert <raphael=
> 40wire.com@dmarc.ietf.org> wrote:
> 
> > (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
> > >
> >
> > _______________________________________________
> > MLS mailing list
> > MLS@ietf.org
> > https://www.ietf.org/mailman/listinfo/mls
> >