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

Richard Barnes <rlb@ipv.sx> Tue, 07 July 2020 15:21 UTC

Return-Path: <rlb@ipv.sx>
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 79D223A0E70 for <mls@ietfa.amsl.com>; Tue, 7 Jul 2020 08:21:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 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_NONE=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=ipv-sx.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 12CkosFetNuA for <mls@ietfa.amsl.com>; Tue, 7 Jul 2020 08:21:46 -0700 (PDT)
Received: from mail-qk1-x72b.google.com (mail-qk1-x72b.google.com [IPv6:2607:f8b0:4864:20::72b]) (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 0BED63A0E5C for <mls@ietf.org>; Tue, 7 Jul 2020 08:21:45 -0700 (PDT)
Received: by mail-qk1-x72b.google.com with SMTP id b185so27865997qkg.1 for <mls@ietf.org>; Tue, 07 Jul 2020 08:21:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=MSKL96ZN6ZyWq9nyvWVLbKbFMT6ELcFPty//VhYMDf4=; b=a8erGem39UqH1GpV1ToZBTqQXFn9NGRkEfpTjIGvdXK6NVLJZ7Dav/AFpNVeM59OAx iv8Ky+oaepf4+/U0sF1vLkzpoYSY5H3d1XgtP//1/1MKJtXiH9thjzLEK3mhnDWiOV53 xxjesAMcF1byvyahcim5y89PmHoLX5slCEkwk0EPa5Itznmn8YitjOY780ydEeHUmzMr RuBWhPA+4uTZsZOdaGGDqP1e4rlP/X25jj+mE5C+STsmJDcK9UTT2PnBobFTVC0/KEln ZAgO8nDEuBYfoYKSMAU4vtVbCBkvEb9SD9//J717J6+7E2fMpHijG2NQyronBJ9G6rhw VWag==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=MSKL96ZN6ZyWq9nyvWVLbKbFMT6ELcFPty//VhYMDf4=; b=JZS5XMB5ifVHWQILZIe0gUkCO5tCZZPHvDeZilzbDF5IzCXcpUYUuTEED1n2QLK4Aq 78mC6sss7zsgDfERmMz3VPXjwmCy2bRgB0AcHjck16joPRag5NGBeK9Y4hiosZF10kjB zBGkGzEGZGxDWmTj3DWjaNzm1gMU9sEFwf9W7NC7LitsI0dRC633DRHcRipQPVkl0885 rMUijh8lyphNi7RFjONbsAn8HanJFFIvB7LiCDoCRIAZKSdmmV8MhyLaXzpEpGH/pjEI VOo2awxJ5+t8rm8HjzhHCpJmTw9IzLKZATFxjePclh18hAxTukXp25oKU0YTgyt7VOlH qpYQ==
X-Gm-Message-State: AOAM530eHAA6OFTamcQcJIz+G24Z14QAR1qir8fIj5JwnR3MaOqAx5R5 BFeoz+gL/O06yb8xp6j04B7+cJBKIib9mQ/+UY5dKfsY
X-Google-Smtp-Source: ABdhPJyHoSOCOs4GYlP/LTXihj4yip3fwKTFKg8Mm8qov9GN8MOajm4ru2LymIs0ph7i++6ZR4Rkap/U3YN9aKzjYOA=
X-Received: by 2002:a37:cd4:: with SMTP id 203mr53781093qkm.490.1594135304119; Tue, 07 Jul 2020 08:21:44 -0700 (PDT)
MIME-Version: 1.0
References: <2d1b-5f035980-1-53713100@74279099> <51A5B187-EAAB-4126-BE29-C18ADAFFB179@wire.com> <4BB46738-4B7D-472C-B8DA-A51A93B33DD9@wire.com>
In-Reply-To: <4BB46738-4B7D-472C-B8DA-A51A93B33DD9@wire.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Tue, 7 Jul 2020 11:21:26 -0400
Message-ID: <CAL02cgSWYZQMTx_sX6Kh9sSA9hCmURJmeXsvWNN1uCXQ-XSeJA@mail.gmail.com>
To: Raphael Robert <raphael=40wire.com@dmarc.ietf.org>
Cc: Hubert Chathi <hubertc@matrix.org>, Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="00000000000086c0c405a9db8c36"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/eTAHlvt_Csb6P3y_p9ITf5XnnUU>
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: Tue, 07 Jul 2020 15:21:55 -0000

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
>