[MLS] On the Insider Security of MLS

Joel Alwen <jalwen@wickr.com> Fri, 23 October 2020 09:59 UTC

Return-Path: <jalwen@wickr.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id CF1EF3A0B37 for <mls@ietfa.amsl.com>; Fri, 23 Oct 2020 02:59:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=wickr-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id YZBLrpdoED32 for <mls@ietfa.amsl.com>; Fri, 23 Oct 2020 02:59:53 -0700 (PDT)
Received: from mail-wr1-x431.google.com (mail-wr1-x431.google.com [IPv6:2a00:1450:4864:20::431]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C31EA3A0B36 for <mls@ietf.org>; Fri, 23 Oct 2020 02:59:52 -0700 (PDT)
Received: by mail-wr1-x431.google.com with SMTP id n15so1144457wrq.2 for <mls@ietf.org>; Fri, 23 Oct 2020 02:59:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=to:cc:from:subject:autocrypt:message-id:date:user-agent :mime-version:content-language:content-transfer-encoding; bh=Pso9avB9YvlPPzakSxvJstgBPIgXq9/TxtALwUchJpM=; b=Ne4TeGhLySXzLh/OnmxsSV4sak664BvcSyDJ6tPR7jW4YxPm81bDvBWr+Eil44nxwE 1lVey9RmN1RBS77+DhemOEV34atG7YCBOfy987NQJBRTaBTli378vT0mD58Lg9+qOaah fpgXEN2kIdfMUa3JhK/8d7jxJVSH3/q/s5bWOkLzGOTUwe4SAhAj4nozEN/BAjbz4xrn ooz6KBeqwvgZDRud6QHqp7ed2N7bvWKI/uAkDPvIWpXLmJY7nE1Vx5ntWDjZxggkjgSW qDpT2k2EeUtTgRVs41I5OMT08Xu3YRqmTUHGyZQpB2KgTIw/u/7PiiXAmfNXQZa8zDlg AZNw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:from:subject:autocrypt:message-id:date :user-agent:mime-version:content-language:content-transfer-encoding; bh=Pso9avB9YvlPPzakSxvJstgBPIgXq9/TxtALwUchJpM=; b=jvd6822ZiBnJgmYrhilO797fJ8sotDuScPzf8+nq++2R7z+8/5IV3DVKpT8KuM0DjA DS+e2I7RUs5EtQyUKhTWcif73ubw2EuMTSjlv7+AlK+bMbrBPHLDrb+sQQRDRJ/6Lt/D h4X2o+XnpsJPUnIBFqtl+jxUUaMtHRl/z68Uf1ZXPuUxseOGA+9GRu99QU6y1qs43n6X P6sOHv+IEjNG9oTFLv1GtbfjN6cMTU7fM7vVMamTcyjuDaZkL1UwK1ib1vO8wSSb34Dy +M7ngalMkIFwiixi47XXY06GdiatubTwBvC5KDbK1YjKBn/3oRnS9PRdwldhCgTQP8cr fhHg==
X-Gm-Message-State: AOAM533lHEjXstYVR05hNWxDxOsjuY1Y7T2VVTlfV7SK9GE93qkp15p8 eT9/u8aSCyJhMXTEa4DkoeibjQ==
X-Google-Smtp-Source: ABdhPJzEs8zWd29SoKC3rRh6tlNMKiSCEDps9o3IKCx8pbtlMu0znTuUhDzLfFiizTaceoykSZhoMA==
X-Received: by 2002:a5d:5090:: with SMTP id a16mr1637661wrt.281.1603447191084; Fri, 23 Oct 2020 02:59:51 -0700 (PDT)
Received: from [] (84-114-27-5.cable.dynamic.surfer.at. []) by smtp.gmail.com with ESMTPSA id c14sm2196746wrv.12.2020. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 23 Oct 2020 02:59:50 -0700 (PDT)
To: Messaging Layer Security WG <mls@ietf.org>
Cc: Jost Daniel <dajost@inf.ethz.ch>, Marta Mularczyk <mumarta@ethz.ch>
From: Joel Alwen <jalwen@wickr.com>
Autocrypt: addr=jalwen@wickr.com; 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: <7b86078a-55dc-7d80-0a75-e900bed61694@wickr.com>
Date: Fri, 23 Oct 2020 11:59:47 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.12.1
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/-kOwBDnMwdF5T1i9VWBZ0GWQ6Ko>
Subject: [MLS] On the Insider Security of MLS
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 23 Oct 2020 09:59:55 -0000

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.

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

 - 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).