Re: [MLS] Weak vs. Strong Tree Authentication

[Brendan McMillion <[e-mail]>]

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=
[e-mail]> wrote:

> 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 <[e-mail]> 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
> > [e-mail]
> > https://www.ietf.org/mailman/listinfo/mls
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>