Subject: [MLS] On the Insider Security of MLS

From: Joel Alwen <[email-masked]>
Date: Fri, 23 Oct 2020 11:59:47 +0200

Hey Everyone,

Daniel Jost, Marta Mularczyk and I wanted to let you know about the results of
some analysis we've done for MLS. There's a fair bit to unpack here (so please
forgive the long email) and we encourage you to look at the full writeup [1] but
we'll try to summarize the most salient points here. Also at the end we mention
some limitations of our results.

[1] Alwen, Jost, Mularczyk - On the Insider Security of MLS. https://ia.cr/2020/1327
	
What We Analyzed
----------------
We analyzed how the cryptographic core of MLS behaves in the face of insider
attacks. By "core" we mean (a CGKA protocol implicit within MLS which includes)
TreeKEM, signatures, tree hashing, parent hash, confirmation_tag,
membership_tag, transcript hashing and the basic key schedule. We only
considered the MLSPlaintext framing mode.

Insiders
--------
By "insiders" we mean adversaries with all of the following capabilities:
 - participate in groups as a member (including by deviating from the protocol)
 - leak other parties entire local states with all their keys
 - set the output of parties PRNGs (aka. "bad randomness")
 - control the network completely (think: a corrupt DS)
 - register/deliver arbitrary Key Packages (again: corrupt DS)
 - register arbitrary Sig keys with the AS (e.g.: badly generated keys, copied
keys, keys for which they don't know the sk, etc.)
 - the adversary orchestrates the execution as they see fit: e.g. the can tell
Alice to propose adding Bob, Charlie to commit and then have the network deliver
packet P to Dave.
 - the adversary is fully adaptive; at each moment during the execution the adv.
can decide which action to take next based upon their entire view of execution
up to that point.

Security Property
-----------------
Our goal was to determine when a given epoch_secret is secure. In other words,
given a complete execution (in particular, the adversary’s actions) decide if a
particular epoch_secret is guaranteed to be secure. We encoded the security
guarantees we could prove using a "safe predicate" which takes as input an
execution and a particular epoch and returns true/false indicating if that
epoch_secret is secure.

What We Found
-------------
By and large, the privacy and authenticity guarantees are what we hoped for from
MLS (especially with the inclusion of membership_tags for MLSPlaintext
proposals). Still, there were at least 2 surprises for us
 1) "Weak vs. Strong Tree Authentication". See subsequent email with that
subject for more on this as we might consider changing how tree_hash and
parent_hash are computed in light of what we found. But in a nutshell, we show
that MLS has weaker security guarantees than maybe expected for parties joining
a group because of how MLS defines parent_hash. We analyzed security for the
original proposal for parent_hash and the one MLS uses now and found that the
former provides strictly stronger guarantees for new members. Nor is this an
issue with limited proof techniques. We found attacks that work against MLS now
but not if we define parent_hash to include tree_hash as first proposed.

 2) ECDSA vs. EdDSA : We found that we could have proven stronger security if
only EdDSA were used vs. if ECDSA is permitted. ECDSA sigs produced with a bad
PRNG (i.e. not enough entropy) can result in sigs that reveal the signing keys.
EdDSA signatures are deterministic and so aren't susceptible to this. ECDSA can
also be de-randomized (RFC 6979) to avoid the problem.

Other Conclusions
-----------------
We still think that MLS would benefit significantly from:
  1) Better hardening against bad randomness. (This can be done cheaply, simply
& doesn't have to break compatibility, yet has a clear & quantifiable benefit
for security. PR incoming with a generic & protocol specific trick for doing
just that...)

  2) Including a separate HPKE key in KeyPackages in DS for encrypting the
welcome message secrets (rather than using the initial leaf HPKE key for that
purpose as done now).

- Daniel, Joël, Marta

Some Limits Of Our Results
--------------------------
 - We analyzed security of a single honestly generated group, running
concurrently with any number of adversarially generated "fake" groups. But we
didn't analyze how concurrent honestly generated groups might interact. (To be
clear, that's only to keep the results tractable, not because we think there's
some kind of deeper problem precluding meaningful security in the more general
setting.)

 - We didn't consider MLSCiphertext framing. Intuitively, that mode "only" adds
better meta-data protection compared to MLSPLaintexts. Metadata hiding was
outside the scope for us. We focused on privacy and authenticity for
MLSPlaintext for now with the understanding that MLSCiphertext framing provides
at least as good security in those terms. So what we show applies to both types
of framing.

 - We didn't analyze full Secure Group Messaging, only the core CGKA
functionality. (Although we feel it's pretty easy & immediate to extend our CGKA
results to meaningful security statements for the full SGM protocol.) We also
don’t cover any of the “extended features of MLS”: e.g. exporter keys, PSKs,
external proposals & commits, state recovery procedures, protocol
downgrade/upgrades etc. MLS is a beast. Much remains to be covered. (But we do
think that, as with SGM, the core analysis we’re reporting on can reasonably
easily be extended to cover several, if not most, of those features.) For more
on what we left out / simplified see Section 4.5 in the writeup.

 - Our safe predicate isn't tight. But it only errs on the side of caution. I.e.
whenever it says an epoch_secret is secure we have proven this to be the case
(in our adversarial model of course). But sometimes it says an epoch_secret is
*insecure* although it actually still is. This is due to a few things:

   1) The predicate doesn't account for parties’ position in the ratchet trees.
Sometimes, an attack may or may not reveal an epoch_secret depending on the
order of the leaves people are assigned to in the ratchet tree. For simplicity,
our predicate always assumes the worst case ordering (from a security perspective).

   2) The safe predicate pessimistically assumes that just 1 sig produced by an
honest party using bad randomness already leaks the parties signing key. Of
course, that might not really be the case, e.g. (if EdDSA is being used, etc).

---

From: Raphael Robert <[email-masked]>
Date: Fri, 23 Oct 2020 13:03:44 +0200

Joel, Marta, Daniel,

Many thanks for the analysis! I will look at this in more detail, but it sounds we should address these concerns including revisiting past choices.

Raphael

> On 23 Oct 2020, at 11:59, Joel Alwen <[email-masked]> wrote:
> 
> Hey Everyone,
> 
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls