Re: [MLS] Weak vs. Strong Tree Authentication

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 <jalwen@wickr.com> wrote:
> 
> 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.
> <attack on weak parent hashing.png>_______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls