[MLS] Weak vs. Strong Tree Authentication

Joel Alwen <jalwen@wickr.com> Fri, 23 October 2020 10:00 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 80D1A3A0B45 for <mls@ietfa.amsl.com>; Fri, 23 Oct 2020 03:00:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_BLOCKED=0.001, 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=wickr-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id oRU_98RfdVbz for <mls@ietfa.amsl.com>; Fri, 23 Oct 2020 03:00:05 -0700 (PDT)
Received: from mail-wm1-x32a.google.com (mail-wm1-x32a.google.com [IPv6:2a00:1450:4864:20::32a]) (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 071723A0B62 for <mls@ietf.org>; Fri, 23 Oct 2020 03:00:05 -0700 (PDT)
Received: by mail-wm1-x32a.google.com with SMTP id l20so227555wme.0 for <mls@ietf.org>; Fri, 23 Oct 2020 03:00:04 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=to:cc:from:subject:autocrypt:message-id:date:user-agent :mime-version:content-language; bh=+2uFyL6V48crF8rpmhqpJNu+bcYYExBjO9Ie04sKHLQ=; b=rQu3WeOOwrLcqcRIqoh/qCaZ10NVsicGTZtqDRTdrqRiDrJcr6MccpUIBax4AWA05m eN+jbhIKbTe7kmbkFri0TxyfvKXWepKYHvCJK5VYPjAm816MdWWIYRm743r9BUATgCNO vVOWzt9zkPthVqu50V35pmsDkpQdbyQT6T/X0IL1Wrk/WVnVSx9rqtMu/4kHSCk9UA2S sh9fp+wK7hS1RhuHj0eBgFQhshNfQAaXgdFVmYbS4TWD1demvI2zaxnRuhjZDNgNMoYH u+kFrg1m4I1SBTiMOvwSigk4tf+KHla4ofOgR4BrjKZl1/RP7xYr8z8eVwOERCbgkUl7 6OZg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:from:subject:autocrypt:message-id:date :user-agent:mime-version:content-language; bh=+2uFyL6V48crF8rpmhqpJNu+bcYYExBjO9Ie04sKHLQ=; b=oxkUK3MIdfW2mkyQJ1xBNIpBl62AYBIBvc8Xq9apfFv9Bm2OiV3v3XPivhaUtcerIm Skg42KaLzmPxRtFBe8UJEQforpDSfABQZ0kbetYR0DoY6u6/ulglbSOgEA0lImfYeR2V EdM80TXTFLadlpfCPfxDwbnv5oe6LoDHDzWfyploabCsGUatJRgLWxo/itLF90BCf3oM /Zq7dfw1RO8SI2SFKiQl5wW8g1soCf0WWS6rJdIq3uzZnyDZy1cWe3Xh9wYwDPYIM8Bx 75nJViWsSsQ4pjIdP91cuYPbDO659gTONXtg3+OrCA5ijsn29s/fSQLvOETjMDX/1yry 7K9Q==
X-Gm-Message-State: AOAM530suw1Jkrjrgu3PkyjbVLj1/PHr8e+vz8S/4mRdlP9F9QNbGIxE Dik/1nNKnGcMZoVCH93Q+1xEyw==
X-Google-Smtp-Source: ABdhPJxDx357JXocNXQYHlseq1j+YTAjWolrxNapyXmnvbBLJWijZlvWSGMNlkJVgeVOPyA7KPfSzw==
X-Received: by 2002:a7b:cd96:: with SMTP id y22mr1533103wmj.126.1603447203281; Fri, 23 Oct 2020 03:00:03 -0700 (PDT)
Received: from [] (84-114-27-5.cable.dynamic.surfer.at. []) by smtp.gmail.com with ESMTPSA id y4sm2299225wrp.74.2020. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 23 Oct 2020 03:00:02 -0700 (PDT)
To: Messaging Layer Security WG <mls@ietf.org>
Cc: Jost Daniel <dajost@inf.ethz.ch>, Marta Mularczyk <mumarta@ethz.ch>
From: Joel Alwen <jalwen@wickr.com>
Autocrypt: addr=jalwen@wickr.com; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0Lw==
Message-ID: <fdad0840-6396-341b-b646-7bee23e2d5d8@wickr.com>
Date: Fri, 23 Oct 2020 12:00:00 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.12.1
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------D327DA4C35DE5DCC6429AFEE"
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/y7AUyHjGLax2oIBMSDzi9KDysnM>
Subject: [MLS] Weak vs. Strong Tree Authentication
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: Fri, 23 Oct 2020 10:00:09 -0000

Hey everyone,

In the course of our insider security analysis of MLS (detailed in our previous
email titled “On the Insider Security of MLS” on the list today and available
here [1]) we noticed a trade-off MLS is making between deniability and security
that we believe merits extra attention.

MLS initially considered two "tree-signing" methods (see below), where method 1
seemed more secure but was less deniable than method 2. MLS went with method 2,
since at the time additional security of method 1 was unclear.  We now have a
much clearer understanding of what we’re giving up by opting for method 2 so we
wanted to share that with everyone. Put simply, method 2 provides a fair bit
weaker security guarantees for people joining a new (possibly adversarially
generated) group than does method 1.

[1] Alwen, Jost, Mularczyk - On the Insider Security of MLS. https://ia.cr/2020/1327

Two Constructions
In more detail, the issue centers on how the parent_hash is defined. A party
joining a group authenticates the group’s ratchet tree by verifying the sigs at
each leaf. Some of those leaves include a parent_hash value which, in turn,
fixes values stored higher up in the ratchet tree. Intuitively, this is meant to
provide some security guarantees to the new member. Basically, the hope was that
if all keys in a ratchet tree are signed by group members and you trust all the
group members you should be in a secure group.

It turns out though that exactly how parent_hash is defined is critical to
whether we really achieve this intuition or not. We are aware of 2 definitions
considered in the past. For lack of better terminology we'll call them:

"weak parent_hash"   : What MLS does now. parent_hash of a node only covers the
HPKE pks on the path from root to the node. Roughly speaking, we have that:
	- root.parent_hash := 0
	- node.parent_hash := H(node.parent.pk, node.parent.parent_hash).

"strong parent_hash" : Define parent_hash to include tree_hash (and tree_hash to
*not* include parent_hash). The tree_hash of a node covers all values in the
subtree rooted at that node  (except the parent_hashes and signatures). So
basically something like this:
	- leaf.tree_hash := H(leaf.data)
	- node.tree_hash := H(node.data, node.lchild.tree_hash, node.rchild.tree_hash)
	- root.parent_hash := 0
	- node.parent_hash := H(node.parent.tree_hash, node.parent.parent_hash).

In an effort to preserve a modicum of deniability, the working group opted for
the "weak" approach. It was felt that this way a signature at a leaf would only
weakly bind the signing party to the session it was signing in. Conversely,
signing a strong parent_hash would provide irrefutable evidence that the signing
key's owner was in a group with (at least some) of the other members in the
group. As far as we know, at the time the security implications of this decision
(beyond deniability), were not well understood.

Different Security Guarantees
Here's what we found about these 2 variants. Consider an MLS execution where
Alice joins a session using a valid looking welcome message and ratchet tree
*possibly produced somehow by a malicious insider*. (Think of an “insider” as an
attacker that can participate as a group member in MLS sessions, can leak honest
parties states at will, and that can completely control the DS and the AS. For a
more complete explanation of their capabilities see the email with subject “On
the Insider Security of MLS” in this mailinglist.) Alice's session continues,
e.g. parties issue proposals, commit and send application messages.

We asked ourselves: When (if ever) does the session Alice joined become
“secure”? A bit more precisely, when can we prove that (in our adversarial
model) the epoch_secret of a given epoch E looks random to the adversary?

We answered this by defining 2 properties of the execution that suffice for us
to prove such a claim for any given epoch E.

Call a signature key pair "leaked" if it's secret key was either chosen by the
adversary or explicitly revealed to the adversary in the course of a leaking the
key’s owner’s local state. We call a ratchet tree "bad" if at least one leaf is
assigned a leaked key pair.

 - Property 1: The ratchet tree for epoch E is not bad. (When MLS uses strong
parent_hashes then this property suffices to prove security for E.)

 - Property 2: No key pair at a leaf of E was ever part of a bad ratchet tree.
This includes ratchet tree's for other epochs in other sessions. (When MLS uses
weak parent_hashes  then this property suffices to prove security for E.)

This difference in what we need to prove security for strong and weak hashes is
not just a limit of our proof techniques. In fact, we can build concrete attacks
that demonstrate the different guarantees. The attacks succeed against weak
parent_hashes but fails against strong parent_hashes. See the end of this email
for an example.

The Argument for Strong parent_hashes
In our opinion the difference between the 2 properties is big. Suppose you find
yourself in an epoch E and are trying to decide if it’s secure. Property 1 means
that E’s security depends only on the security of the keys involved in that
epoch; that is keys  you can see belonging to parties you are aware of. So if
you believe that everyone in E is honest and is using an unleaked key you can
already conclude you're getting privacy.

But Property 2 means that to reach the same conclusion about E you'd further
have to assume the same thing about all sorts of other epochs (of other groups!)
which just happen to involve a key pair also used in E. That seems like a *much*
worse guarantee. In particular, there's no reason to believe you'd even be aware
of all those other groups, let alone who was in them and what keys everyone was
using. To us, this motivates switching over to strong parent_hashing.

On the flip side we would lose the deniability benefits that the weak
parent_hashes give us now. We believe this "loss" to be worth it though. First,
our (Joël and Marta) take is that deniability is at most "nice to have" but
nowhere near as crucial as privacy and authenticity are. Second, we don't think
that even with weak parent_hashes we could make any claims that MLS is deniable
in some reasonable and holistic sense. So by giving up this particular mechanism
it doesn't look like we're really losing any general deniability feature of the
entire protocol. If we want deniability in some form for MLS then we believe
we'll have to revisit much of what MLS does anyway.

Thus, our take is that we'd rather have a stronger, (in particular more locally
based) privacy guarantee when joining a new group than the incomplete
deniability guarantee we have now.

- Daniel, Joël, Marta

An Attack Separating Strong from Weak parent_hashs
The basic vulnerability exploited by this attack is that signing a weak
parent_hash only authenticates the HPKE keys on a direct path but not which
parties were then told each of the secret keys on that path. This lets an
insider that knows many keys on a path construct a new ratchet tree where they
seem to only know fewer of the keys (near the root). So when the party is then
removed from this fake group some of the secrets they know will remain part of
the group state. That in turn lets them compute epoch_secrets even after being
removed from the group thus breaking privacy. The attack is described bellow and
depicted in the figure attached to this email.

Suppose MLS uses weak parent_hashes.
 1) Bob is an insider attacker. He's in a group G1 with 3 leaves. From left to
right they are assigned to Alice, Bob and Charlie. Alice performs a commit in G1
resulting in ratchet tree T1. (Notice Bob now knows the HPKE sk at the parent of
Alice and Bob.)

 2) Bob creates a fake ratchet tree T2 with 3 leaves as follows. He copies all
nodes from Alice’s leaf to the root from T1 to T2. Next he places a fresh key
package for Charlie the sibling leaf to Alice (i.e. Bob’s former leaf in T1).
Finally he places himself in the rightmost leaf. He also samples any values he
needs for the new groups application key schedule (e.g. an init_secret from a
fake previous epoch). Call the resulting group G2.

 3) Next Bob creates a proposal to add Dave to G2 and commits to it initiating a
new epoch E’. He produces a corresponding welcome message which he sends to Dave.

 4) Once Dave joins, Bob proposes to remove himself from the group. Dave commits
to the proposal which initiates epoch E.

At this point Property 1 for E is satisfied (as T2 only has Alice, Charlie and
Dave at the leaves). But in reality, Bob still knows the HPKE sk at the parent
of Alice and Charlie as that wasn’t blanked out or overwritten when Dave did his
commit removing Bob from T2. Worse, that commit by Dave includes a ciphertext
encrypting a secret to the sk which is intended to let Alice and Charlie compute
the commit_secret. That lets Bob compute the commit_secret and thus too the
epoch_secret for E. So E isn't secure.

Notice the above attack fails when MLS uses strong parent_hashes. Copying
Alice’s leaf and parent node from T1 to T2 forces Bob to also copy her sibling
leaf from T1 to T2. Bob can no longer pretend he is not the sibling of Alice.
Thus, when Bob is removed from G2 by Dave the parent node of Alice will be
blanked and so Dave will encrypt the secret for the grandparent straight to
Alice’s leaf. In other words, Bob can no longer process the commit and he is
truly out of G2 as intended leaving E in a secure state.

Finally, to add to the discussion in the “Overflow from discussion on #406”
email thread, it looks like this attack is *not* prevented by having the
GroupKeyPackage signed (e.g. by the sender of a welcome packet = the most recent
group member to commit). Dave gets the GroupKeyPackage for G2 from Bob and Bob
can create and sign it no problem as he is in G2, knows its key schedule and the
whole public part of T2. So everything  would check out just fine for Dave.