Subject: [MLS] Weak vs. Strong Tree Authentication

From: Joel Alwen <[email-masked]>
Date: Fri, 23 Oct 2020 12:00:00 +0200

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.

---

From: Raphael Robert <[email-masked]>
Date: Fri, 23 Oct 2020 20:23:47 +0200

Thanks for the detailed write-up! A few thoughts that came to mind when I read it:

 - When we discussed the weak parent hash construction vs strong tree hash, it was obvious that a malicious insider could create fake trees and trick new joiners. Creating fake trees is a possibility that’s always been there (and still is) in MLS: the attacker places a bunch of KeyPackages in leaves, the attacker commits (thus populating their direct path) and invites a new member at the same time. The new member can only verify a parent hash/tree hash that the attacker created. The group looks valid to the new member, but in fact all other members of the group could be fake until we’ve seen an update from them. What you now describe has a new quality (at least to me): the impossibility evict the malicious insider from a group.

 - In the example you describe, it is clear that Dave did not manage to cryptographically evict Bob from the group. What’s maybe worth clarifying is that Alice and Charlie are no longer able to participate in G2, since Bob swapped his position with Charlie. This would lead to a different tree hash for Alice and Charlie, hence the group context would be a different one, hence they would have different inputs to the key schedule. They would detect that when Bob Commits (from his fake position in the tree) to add Dave, because Bob would produce a confirmation_tag that would look wrong to Alice and Charlie. In the end this means that Dave thinks he ist talking to to whoever is left in the group after he evicted Bob (in this case Alice & Charlie), while in fact only Bob can decrypt his messages. At some point Dave might notice that nobody else interacts with the group anymore, but the damage might already be done if he sent messages to the group in the meantime.

- 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?

 - The reason why Bob couldn’t be evicted by Dave is because Bob had the liberty of reshuffling the leaves. Or in other words, we can conclude that the current parent hash does not fully protect the tree invariant, only one aspect of it. Going for fully hashing the tree nodes as described locks down the whole tree structure, making any reshuffling impossible. 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.

 - To follow up on the last point, what the current parent hash scheme is missing, is that it doesn’t convey to whom the secrets in a direct path of a member were made available. The only way to convey this is to show who was below the heads of the copath nodes when the new node secrets were KEMed to the copath during Commit. The full tree hash provides that information. The unwanted side-effect is that it fully reveals the identity of the leaves, especially their long-term identity. If there was a way to dissociate the identity from the position of the leaves in the tree, the side-effect might be alleviated. But again, I don’t see how to achieve that right now.

That’s all for now, I’ll think about this some more.

Raphael

> On 23 Oct 2020, at 12:00, Joel Alwen <[email-masked]> wrote:
> 
> Hey everyone,
> 
> <attack on weak parent hashing.png>_______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Brendan McMillion <[email-masked]>
Date: Fri, 23 Oct 2020 13:01:00 -0700

Hey Joel,

Thanks as well. The bar we were having trouble meeting at the interim in NY
was finding a meaningful attack that distinguished the two constructions.
But since you've now done that, I definitely agree we should move to the
stronger one.

On Fri, Oct 23, 2020 at 11:24 AM Raphael Robert <raphael=
[email-masked]> wrote:

>  - When we discussed the weak parent hash construction vs strong tree
> hash, it was obvious that a malicious insider could create fake trees and
> trick new joiners. Creating fake trees is a possibility that’s always been
> there (and still is) in MLS: the attacker places a bunch of KeyPackages in
> leaves, the attacker commits (thus populating their direct path) and
> invites a new member at the same time. The new member can only verify a
> parent hash/tree hash that the attacker created. The group looks valid to
> the new member, but in fact all other members of the group could be fake
> until we’ve seen an update from them. What you now describe has a new
> quality (at least to me): the impossibility evict the malicious insider
> from a group.
>
>  - In the example you describe, it is clear that Dave did not manage to
> cryptographically evict Bob from the group. What’s maybe worth clarifying
> is that Alice and Charlie are no longer able to participate in G2, since
> Bob swapped his position with Charlie. This would lead to a different tree
> hash for Alice and Charlie, hence the group context would be a different
> one, hence they would have different inputs to the key schedule. They would
> detect that when Bob Commits (from his fake position in the tree) to add
> Dave, because Bob would produce a confirmation_tag that would look wrong to
> Alice and Charlie. In the end this means that Dave thinks he ist talking to
> to whoever is left in the group after he evicted Bob (in this case Alice &
> Charlie), while in fact only Bob can decrypt his messages. At some point
> Dave might notice that nobody else interacts with the group anymore, but
> the damage might already be done if he sent messages to the group in the
> meantime.
>
> - 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?
>
>  - The reason why Bob couldn’t be evicted by Dave is because Bob had the
> liberty of reshuffling the leaves. Or in other words, we can conclude that
> the current parent hash does not fully protect the tree invariant, only one
> aspect of it. Going for fully hashing the tree nodes as described locks
> down the whole tree structure, making any reshuffling impossible. 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.
>
>  - To follow up on the last point, what the current parent hash scheme is
> missing, is that it doesn’t convey to whom the secrets in a direct path of
> a member were made available. The only way to convey this is to show who
> was below the heads of the copath nodes when the new node secrets were
> KEMed to the copath during Commit. The full tree hash provides that
> information. The unwanted side-effect is that it fully reveals the identity
> of the leaves, especially their long-term identity. If there was a way to
> dissociate the identity from the position of the leaves in the tree, the
> side-effect might be alleviated. But again, I don’t see how to achieve that
> right now.
>
> > <attack on weak parent
> hashing.png>_______________________________________________
> > MLS mailing list
> > [email-masked]
> _______________________________________________
> MLS mailing list
> [email-masked]

---

From: Joel Alwen <[email-masked]>
Date: Sat, 24 Oct 2020 16:39:10 +0200

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 = (node.parent.pk, 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 (v.pk, v.sk) 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 v.sk to decrypt stuff. So, there's no way for the
adv. to learn v.sk from that party. That leaves one of 3 ways for the adv. to
still learn v.sk: 1) by knowing an sk for a pk \in PK(v) 2) by corrupting
someone who knows v.sk 3) by having some one send them v.sk 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 v.sk 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 v.sk works.

Summing up, there's no way the adv. can learn v.sk. 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
node.pk 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