[MLS] Switch to signing strategy using one signature per leaf.

Brendan McMillion <brendan@cloudflare.com> Thu, 30 January 2020 19:45 UTC

Return-Path: <brendan@cloudflare.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 39D2D12013D for <mls@ietfa.amsl.com>; Thu, 30 Jan 2020 11:45:32 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id uLFNS4jd4Y-G for <mls@ietfa.amsl.com>; Thu, 30 Jan 2020 11:45:30 -0800 (PST)
Received: from mail-qv1-xf2b.google.com (mail-qv1-xf2b.google.com [IPv6:2607:f8b0:4864:20::f2b]) (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 36DAD12008F for <mls@ietf.org>; Thu, 30 Jan 2020 11:45:30 -0800 (PST)
Received: by mail-qv1-xf2b.google.com with SMTP id n8so2075414qvg.11 for <mls@ietf.org>; Thu, 30 Jan 2020 11:45:30 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:from:date:message-id:subject:to; bh=8Xw9VFVbkQudtz+8j1tZo3sGXs7JlJVVDFNoqgDfTBk=; b=XzqYfbaOk9s2UwzsO0GK9uuEZ2GTVzbWCxVge51pw3cnaTx7IkCe4TIi4i2KKfptL6 Z5W+rLKhr/F5dswSwuYIGY4Q/ulFf4HOE9N5AtrzI6M7MmgBYZcVZha/whQntc3Wo52I kcIiKSbMvu3IU3acsX57WS3i7iKMRxKDtqM5A=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=8Xw9VFVbkQudtz+8j1tZo3sGXs7JlJVVDFNoqgDfTBk=; b=n5YbA6rfDGnk/uXl3ZF11USpVKX65PikTjLPLvRQ04nhP/yeas/5rkLRM/v9qxogbh GG/WpoNzau1OSg697YPwPRc8o5v4bNh8IBw4PnkiDkCXW9nupaUcNkm+dUDIqfOAvxW7 2Lgw2BfVVFkNfp4sCMOtF5WqH5GeAQ2zs4w7fjJHH2hV4tV/ihuh7CQCQyaNG+SedI4n 2QsexovTG2hKWLhtM5r3+nrbUcsA6qlQVppdDul1q/3YUgf6WzzJ0G6raK+1cuwAqDVq 7aZapkd8J8T7TBo3N/zIN6hoOwj2jrSiMYxFzokDGVzx/srlOq8nxKT4j18cF6GlTlP8 0Jvg==
X-Gm-Message-State: APjAAAV0xHfHLx5Kcnd3M8/XrorWJUAeDGRKtGslU576YmbFRe0EgC0T SzyIEmahCK8Cby71q4nbB7c4KJ0RYdOjvGRF/ivUJhZIaEsASQ==
X-Google-Smtp-Source: APXvYqwrCtn6xQPJ7DkONLHkW63wlWaEBCGJ4JHt7bf8pvItsjkD9aTb+17m7KIMjoua3FS4BHLswDmetNXaeWAZv/k=
X-Received: by 2002:a0c:f513:: with SMTP id j19mr6398507qvm.206.1580413528882; Thu, 30 Jan 2020 11:45:28 -0800 (PST)
MIME-Version: 1.0
From: Brendan McMillion <brendan@cloudflare.com>
Date: Thu, 30 Jan 2020 11:45:18 -0800
Message-ID: <CABP-pSSibZqEmhNzvvGz5xYEs5OFacXxOudRw7=ozQpeAFG_YQ@mail.gmail.com>
To: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000fcec9e059d60b29f"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/EJj8TyXavgfxYb9AXYAbcTnN7Vs>
Subject: [MLS] Switch to signing strategy using one signature per leaf.
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, 30 Jan 2020 19:45:32 -0000

Hello mls@

As per the minutes from the last virtual interim, it looks like there's
consensus around merging PR #287, "Switch to signing strategy using one
signature per leaf." Before that happens, I wanted to write a message to
the list formally introducing the change.

A while ago, we started having the members of a group sign the nodes in the
ratchet tree, along with a hash of the node's subtree, as the nodes were
changed (through Update/Commit messages). The purpose of this was to
authenticate the tree when it's sent in a Welcome message.

Without authentication, the member that sends the Welcome message could
falsify the tree and add themselves in subtrees they don't appear to be in.
This attack makes it impossible for the new member to reasonably remove the
welcomer from the group.

The proposed change in my PR switches from a scheme where every node and a
subtree hash is signed, to a scheme where each leaf and a "path hash" is
signed. The path hash of a node is defined as the hash of all the node's
ancestors. Path hashes work differently from the tree hashes we currently
have in the spec, in that they go up instead of down.

There are two main benefits of this scheme:

1. It reduces the number of signatures that need to be verified by a factor
of 2.

2. It's compatible with approaches for deniability, since the information
that each member is signing doesn't bind them to the other members of the