[MLS] New Parent Hash

Joel Alwen <jalwen@wickr.com> Thu, 12 November 2020 21:14 UTC

Return-Path: <jalwen@wickr.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id C3DCE3A0977 for <mls@ietfa.amsl.com>; Thu, 12 Nov 2020 13:14:32 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 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] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=wickr-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id dIite9yDE3az for <mls@ietfa.amsl.com>; Thu, 12 Nov 2020 13:14:31 -0800 (PST)
Received: from mail-ej1-x634.google.com (mail-ej1-x634.google.com [IPv6:2a00:1450:4864:20::634]) (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 986613A096B for <mls@ietf.org>; Thu, 12 Nov 2020 13:14:31 -0800 (PST)
Received: by mail-ej1-x634.google.com with SMTP id dk16so10099510ejb.12 for <mls@ietf.org>; Thu, 12 Nov 2020 13:14:31 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=to:from:subject:message-id:date:user-agent:mime-version :content-language:content-transfer-encoding; bh=4A6SQCBmEklR6+3ug2tPmOcBsyEHWGwNcPdLrLTQsKA=; b=nQa6ozLEaVskF0qC6x0pDofXsAj+fvzk7Te5sblrzr42tfZGpmseZwpIuHH7QwznS2 q4xz4h0abONz0rZOJjqxbZsUBJJDAPH9k2UL+gwiZqi4VsgUYuySj++pYI53PobXYQIv K9UQV8HpdLxleH9DyNY6gjHf3FB1fZOIToAvMq5v15lI9s8WxIkALGNkquPw7Lfxkjv2 FKHkXhS66RFFGUyHZExGaeS6rAIbAUevYkcwb8gm03R867bKA4tz77jPkupZF1FkB8jK QtB96NEgB1nFXSPg7m5IzcHP2KZf5NKG7IZlY6IHjeajuRtBof8FmjqvA7e+XdWMLhbF peOA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:message-id:date:user-agent :mime-version:content-language:content-transfer-encoding; bh=4A6SQCBmEklR6+3ug2tPmOcBsyEHWGwNcPdLrLTQsKA=; b=EPBj7NrxUHSGsNTYt9QDxvsEkeogDUlMoYuTZRuwNTjcFntY9eWAPaEIfKvTn/CF2c UMBkr/EYOXJLaq/TgYFagZclJHEG7AOQlYKG1oMJdO4RCW8OKBEA0hS0UDsq3BVncrbg d+lDAuYEUtmejo0lZ3xuPW19fzDAH7aApkcOj+tCclb89rB+6oDjrQmvoUJ8JyhE5toH LZLH2b4+B12rPXUY2RcwMClsiYTUFEWhcsHFo411cSWoIPyIzK54RReFPDlX8TJuwiKP zIK5wRO10Gqyp/63NAdUEv5zpBLObPVGNIjL74+QZdjUk8lDuMAQneCjpwu/NzQ1Znsm 2ckw==
X-Gm-Message-State: AOAM533Cj9GSP5RaEVCCD/hSHPw2mYpkXQ5Wk90oifzJdw7qEsHPy8oI ZgcmPc2CfsoJ1FFWvbUxdWKylBUqgt0HFw==
X-Google-Smtp-Source: ABdhPJx54u/9Pu6a5Hh5nJ4Pj4bN6Hfue1r7qv3jwPzs6ZgiLOBPbaTVqlcutxxmNRchvgiccwRv5Q==
X-Received: by 2002:a17:906:fcc2:: with SMTP id qx2mr1254608ejb.549.1605215669375; Thu, 12 Nov 2020 13:14:29 -0800 (PST)
Received: from [] (84-114-27-5.cable.dynamic.surfer.at. []) by smtp.gmail.com with ESMTPSA id g13sm858383ejh.18.2020. for <mls@ietf.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 12 Nov 2020 13:14:28 -0800 (PST)
To: Messaging Layer Security WG <mls@ietf.org>
From: Joel Alwen <jalwen@wickr.com>
Message-ID: <68acccb2-9e5f-f52d-b32c-3b6e3195bc2d@wickr.com>
Date: Thu, 12 Nov 2020 22:14:28 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.4.1
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/3IGZ_bQZpz6mRu5RruNksb7itzg>
Subject: [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, 12 Nov 2020 21:14:33 -0000

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