Re: [MLS] New Parent Hash

Raphael Robert <raphael@wire.com> Thu, 31 December 2020 11:47 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 9EF1E3A0936 for <mls@ietfa.amsl.com>; Thu, 31 Dec 2020 03:47:34 -0800 (PST)
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 mf14eul8eH8L for <mls@ietfa.amsl.com>; Thu, 31 Dec 2020 03:47:33 -0800 (PST)
Received: from mail-ed1-x530.google.com (mail-ed1-x530.google.com [IPv6:2a00:1450:4864:20::530]) (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 BAFF03A08BB for <mls@ietf.org>; Thu, 31 Dec 2020 03:47:32 -0800 (PST)
Received: by mail-ed1-x530.google.com with SMTP id r5so17950320eda.12 for <mls@ietf.org>; Thu, 31 Dec 2020 03:47:32 -0800 (PST)
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=YRD2BVYmKzIVpdtjdOsKcyUuk/l9ugtQ7FiBDEysaqo=; b=ngH4wIRdjdFCm0FhRY5KRAG+enaqLboNNOg3HXXGXqlMSbusGsSSsRELCMQaHmWSr1 s3Ryybl3cnczYKZT/X7/HrcCyRYulKw7fnoHFxoWGkx1hAdD57NAwSxYFHnoNgIWB0rY 4hfyi7R+7xSslI1DesGgfaaRFZeRT95PlYBRmlOezx5IfeDDjIcQV5KdZutR366m/aiy 151EPAepNcyw4hZoQC9G1nB5fvMrHJSqH6QCrtYifMQo6p4IdvOLPbVqMjh0OrgZnKA4 yeesCt9TO/O1nD069+VJF4vFhyQwVTR6DFru3XEL+wXIiIppS/9nADRWIt/Ju7k1njNg ALzg==
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=YRD2BVYmKzIVpdtjdOsKcyUuk/l9ugtQ7FiBDEysaqo=; b=ioVTAUwhu8Nxf5CWUArfQWdUqdZmAol+mBiVYOl5GbTI61ygjZl0Jk5TlfOeIZg0so fuot3ZjI8pEivuunwQg5SeEqYFMW20MI5qSMXQaSo2TMIu5e4hiu1oy+T2txNy0vnphI d+WxTKnRUk+Zk/qEDxJMuU3tZLM09Ej7M1Dan0k7xv7IynIgLBXw79r1PAcAlLP/GYzl RZArHAjfnl4T6CnZ8cJwIZJl7j84FfkzJYiaY+eIQ/O7O4rcZRMlk+KjXVCZQsszAJDi 9ll0X6hsvFm47spYKt2MXl5UxW6vPthpSxXY9HQBlAPiepCXg4A4qkOCcq4MivHO8txx U9rA==
X-Gm-Message-State: AOAM531hA+8cKjKDlybWJi0ugLlwAPVbt2LARS7Mtf1AAh+zkaPeN1Sm ceuq5gmyALN9LglBczbU2vrKaJi68fBvXomw
X-Google-Smtp-Source: ABdhPJysRn0zTxGH/0Jb19RfaUtF2pMQRf4PIW47hbeCnY6LcbM7QwIOrFUBJQfN8+25wa/crLoH4w==
X-Received: by 2002:a50:cd8c:: with SMTP id p12mr53922803edi.380.1609415250675; Thu, 31 Dec 2020 03:47:30 -0800 (PST)
Received: from rmbp.fritz.box ([37.209.98.242]) by smtp.gmail.com with ESMTPSA id rh2sm20003916ejb.68.2020.12.31.03.47.29 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 31 Dec 2020 03:47:29 -0800 (PST)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.20.0.2.21\))
From: Raphael Robert <raphael@wire.com>
In-Reply-To: <68acccb2-9e5f-f52d-b32c-3b6e3195bc2d@wickr.com>
Date: Thu, 31 Dec 2020 12:47:28 +0100
Cc: Joel Alwen <jalwen@wickr.com>
Content-Transfer-Encoding: quoted-printable
Message-Id: <7A25FA3A-25E9-47AD-9D8F-112F24748062@wire.com>
References: <68acccb2-9e5f-f52d-b32c-3b6e3195bc2d@wickr.com>
To: Messaging Layer Security WG <mls@ietf.org>
X-Mailer: Apple Mail (2.3654.20.0.2.21)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/EHnzrt9mW54i6nMjQLeVU86ms0g>
Subject: Re: [MLS] New Parent Hash
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: Thu, 31 Dec 2020 11:47:35 -0000

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 <jalwen@wickr.com> 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@ietf.org
> https://www.ietf.org/mailman/listinfo/mls