Re: [MLS] Weak vs. Strong Tree Authentication

Joel Alwen <> Sat, 24 October 2020 14:39 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 37F923A0C1F for <>; Sat, 24 Oct 2020 07:39:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.146
X-Spam-Status: No, score=-2.146 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, NICE_REPLY_A=-0.247, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id ic0AI38lXbvd for <>; Sat, 24 Oct 2020 07:39:15 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::434]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E89153A0C1B for <>; Sat, 24 Oct 2020 07:39:14 -0700 (PDT)
Received: by with SMTP id g12so6161465wrp.10 for <>; Sat, 24 Oct 2020 07:39:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=subject:to:cc:references:from:autocrypt:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=ZeIYmDJ+iVcDiMyTMFWk1dhf17q0CxKJZvdGQp4xzHI=; b=Ryq4/+ZwUEz2lLfl/iFCM94clI9et6z+ularuYig6+2K7+MIn+SzjkV0CTHK7OxLgE fsQqOH+CznOSNsfFNVw/vwVjsE1eFLy4lBFKq85GGAI72vlSfKokmKqwXaWTpFS38766 xLr1rew2bfsB1cQh0hjC5pFVxM9yLs0ktwa+tqdhxDpk2MhSPlBYmFjWHu84V0uZVGTH aFnhkmzt8Udx/JuYGoVB72KgJ++88FC9rCt6iwl5H56gIIXHpwJmKl75zLjSMXMxEM6V 9nvWtL05bhMtW8pxfp7CcWzR1u99vQRDQgEckwmBYYeBq/Oi3T49DQG+zXEPoEnfP67+ rLIA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=ZeIYmDJ+iVcDiMyTMFWk1dhf17q0CxKJZvdGQp4xzHI=; b=LKPAWqdvE+91WV6AOEcYaW9Grp8QTt7PGu1caC9f++IoVmi8eSyPzTL3VCEHBo22Ff KpW3vjHz2Jbtt6ySyXGpctSOxsFrOY4LhqeIgkcA+aLa1YPZSZ8YTSJgmUzw3twKbSv6 iVQtx8vcJpijmLzd6f6Iicm4fIFUZ3WoJytUNluuDP6R0JQz9wqQ+t8I5aulipSgMPke 8+zpTLSkay1q19PaePW+Zp1ELtDIHzTgXONk290c2IcgRLby3Ld5xz6bq3lNZfowexKZ QcI/mCi6KjPBKw/ekqeASYZhyQUliU9Hsm+R+76NuBFbn/aUt4sDHT2KeJ2edBQuHhei Aatw==
X-Gm-Message-State: AOAM533sU7JcXohqsRdHndr7gjeNPtK/1EbeAPhdmPJ618Sjo6NIZLHo GJazzMsAeqrudMrfcpV31nxR1A==
X-Google-Smtp-Source: ABdhPJz5t5g1QAebUy9tf9VHijmCOsdqRIUUW8XgNwab0jawr4PL3riy/Eu88hGsT7jYqsNOmQpPVg==
X-Received: by 2002:adf:9507:: with SMTP id 7mr7912519wrs.365.1603550352932; Sat, 24 Oct 2020 07:39:12 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id m14sm11470306wro.43.2020. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 24 Oct 2020 07:39:12 -0700 (PDT)
To: Raphael Robert <>
Cc: Messaging Layer Security WG <>, Jost Daniel <>, Marta Mularczyk <>
References: <> <>
From: Joel Alwen <>
Autocrypt:; 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: <>
Date: Sat, 24 Oct 2020 16:39:10 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.12.1
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [MLS] Weak vs. Strong Tree Authentication
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 24 Oct 2020 14:39:17 -0000

Responding inline...

On 23/10/2020 20:23, Raphael Robert wrote:
> What’s maybe worth clarifying is that Alice and Charlie are no longer able to
participate in G2

Yup, "fake" groups remain a possibility also using strong parent_hashes. Seems
kinda unavoidable since we want MLS to support adding contacts to groups before
the contact comes online. So an attacker can make a "fake" group using that
feature of the protocol.

What I do find kinda cool though is that even for arbitrary "fake" group
(states) we still get the assurance that if your MLS client thinks you’re in a
group with members you believe are honest (and didn't suffer state leakage) then
you can conclude that at least have privacy, though not necessarily liveness.

The possibility remains that some members may be "artificial" not even being
aware of the session. What you get with strong (but not weak) parent_hashes is
that u at least know *at most* those people can read your messages. (With the
usual "in the adversarial model we analyzed" disclaimer.)

> Or in other words, we can conclude that the current parent hash does not fully
protect the tree invariant, only one aspect of it

I think this is kinda the gist of the attack. Using weak parent_hashes lets an
insider create a ratchet tree that passes verification by new members yet breaks
the tree invariant.

All the joiner really needs to verify about a ratchet tree is that for each node
v some leaf L in v's subtree attests to having generated the v's HPKE keys and
to whom it sent the sk.

In order to decide which secrets in the group state need deprecating when we
remove (or update) a member, we need to know who learnt each secret; that is who
either chose or was told the secret. The "tree invariant" is a short description
of that info. Reformulated, it says a key assigned to a node v is known to all
users at merged leaves in v's sub-tree. Having that info in parent_hash is
sufficient to make removes (and updates) work. So really, tree_hash has a ton of
redundant info in it and who has which leaf doesn't matter); at least for doing
removes and updates.

> - Regarding External Commits: Did I get this right that your point is that
just signing GroupPublicState isn’t enough and that you’d need the strong tree
hash construction instead?

Yeah, having the sender of the commit/welcome msg sign the new epoch's
GroupPublicSate wouldn't stop the attack I outlined. But it may well stop other
attacks and using a parent_hash committing to the full tree invariant would
prevent the attack.

>  Maybe there is a more lightweight approach that would yield the same result
without “provid[ing] irrefutable evidence that the signing key's owner was in a
group with (at least some) of the other members in the group”, but I can’t think
of anything right now.

Maybe like this.
- ML(node) = all leaves below node *not* in node.unmerged_leaves.
- PK(node) = list of all HPKE pks at ML(node).
- root.parent_hash = 0
- node.parent_hash = (, PK(node.parent), node.parent.parent_hash)

We use the HPKE pk of a leaf as a proxy for the identity at the leaf. Here's the
rationale for this.

Recall "Property 1" which should suffice to ensure privacy; namely there is no
leaf with an exposed signing key pair. So thats our assumption.

Suppose a joiner to accept a ratchet tree T and consider some non-blank node in
v in T. The joiner must have computed the same value for PK(v) as did is
authenticated via the parent_hash at a leaf bellow v. We've assumed the sig key
at that leaf isn't exposed so the party at that leaf is honest (and didn't
suffer state leakage). So they really sampled key pair (, and sent it
to exactly the set of HPKE keys PK(v). After that it wasn't leaked from their
state and they only ever used to decrypt stuff. So, there's no way for the
adv. to learn from that party. That leaves one of 3 ways for the adv. to
still learn 1) by knowing an sk for a pk \in PK(v) 2) by corrupting
someone who knows 3) by having some one send them somehow.

But none of those can happen. By having the joiner recompute PK(node) when
verifying T we get that each pk \in PK(v) must appear in a leaf of T. By
assumption that leaf is signed by an unexposed sig key, i.e. by an honest party
(that hasn't suffered from state leakage). Honest parties dont send and
only use it to decrypt stuff. Since there sig key is unexposed they also didnt
suff from state leakage. Thus, none of the three remaining options for the adv.
to learn works.

Summing up, there's no way the adv. can learn As this holds for all nodes
in the tree we get that the entire ratchet tree has secure secrets which is
enough to argue security for the epoch.

Does that make sense? :-)

As for deniability... well maybe it’s a little better to only sign the
(parent_hash covering) the HPKE pk keys of the leaves in node's subtree... I
dunno. I guess I can deny a ratchet tree that shows me as, say, having sent to some parties (rather the HPKE leaks at their leaves). But to deny it
I have to claim the signature key at the receiving leaf was used to try and
incriminate me. (Same thing if the tree shows me having received a key from
someone.) So it's only "deniable" if I can plausibly argue that other sig keys
in the group were used to try and frame me. Better than nothing maybe?

- Joël