Re: [MLS] On the Insider Security of MLS

Raphael Robert <raphael@wire.com> Fri, 23 October 2020 11:03 UTC

Return-Path: <raphael@wire.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5329E3A0BA5 for <mls@ietfa.amsl.com>; Fri, 23 Oct 2020 04:03:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_BLOCKED=0.001, 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=wire-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id DoEkOxRi5yUM for <mls@ietfa.amsl.com>; Fri, 23 Oct 2020 04:03:49 -0700 (PDT)
Received: from mail-ej1-x630.google.com (mail-ej1-x630.google.com [IPv6:2a00:1450:4864:20::630]) (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 3060F3A0BA4 for <mls@ietf.org>; Fri, 23 Oct 2020 04:03:49 -0700 (PDT)
Received: by mail-ej1-x630.google.com with SMTP id ce10so1791626ejc.5 for <mls@ietf.org>; Fri, 23 Oct 2020 04:03:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wire-com.20150623.gappssmtp.com; s=20150623; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=r0L/i8aJR9odIWatHmAEwrSc+kUxie7xkoDS6AwYi3c=; b=EUzfRMiQHb3RYQ7cE98F//XM7e7JNj6HrZiR3bbjXdeh1UinfTHfeSJ118YP7bWcsN pm1WRzw7ZCGZfOj6KuPgLqUjLhuVWDUXfIMoSVEeMoZPv6VR40wuQS+swig1FfgKQF3O SBBFLRTHpKX4mr3LjTu39q6G5uFxQ4S34dw6UJQqfT/sSpilk+oNG9ZZhd6D8P2ycaEi O8U1oeU7JHVNxSC7RzA6gYA4J2xetC68DXVkNsEOm0gF0V9CJLGu+adXW5RCE5KmNPKi 8n6WJns2uyfay9t92ZNcjpAS/0qduMTdPRJg/Twp3kA5U0DIy/1xsXzSZmMLQJc4uXzv JcKA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=r0L/i8aJR9odIWatHmAEwrSc+kUxie7xkoDS6AwYi3c=; b=HTV721OsVBG+RmYsVvYWkq4GuPAnkm5g1n5EKc7RZShle5M2vC1IaUpXDtv0SaW5E6 02WoFfuY4UCzkX/EIvqia7f9VUxg0iVJncBewpWvzZbk8ugHjSVAF3JWUDf55Ousrbfq aU+7OXWcnSFDVOr6G/U1GDn6R0UxwHncmuqmuG6I4XEyDzopli5u4mmZ6SKOVe2SSv3B WxhSEKj3e239bsDd06yVNENECGc2gKatC2mMwVHFFgPdAi2HbSmzMxmdOlFTJwKw6uQs Hvt7u1+2n6zr5bj5Iuiw8ihL2QGal5xkB9nEUO8jfo8UdKi2FJYa6YUgJEOdmfQhpJDK 7i3A==
X-Gm-Message-State: AOAM533dIaR/bva+hSwiUKoBn3w+B6w5+ZTqYdkHun5PJfr3Y42j/OsU odg5NSlLKm8Ji64pYz1XrSzBZA==
X-Google-Smtp-Source: ABdhPJyl1YOLFx3t1hxgAORmIUxvcI/HlJkkEqHSz69HFHvhIlwqnScgdGnotarucIcdK7wezUhV+A==
X-Received: by 2002:a17:906:138a:: with SMTP id f10mr1436360ejc.360.1603451027232; Fri, 23 Oct 2020 04:03:47 -0700 (PDT)
Received: from rmbp.wire.local (h-62.96.148.44.host.de.colt.net. [62.96.148.44]) by smtp.gmail.com with ESMTPSA id g23sm586966edp.33.2020.10.23.04.03.45 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Fri, 23 Oct 2020 04:03:45 -0700 (PDT)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\))
From: Raphael Robert <raphael@wire.com>
In-Reply-To: <7b86078a-55dc-7d80-0a75-e900bed61694@wickr.com>
Date: Fri, 23 Oct 2020 13:03:44 +0200
Cc: Messaging Layer Security WG <mls@ietf.org>, Jost Daniel <dajost@inf.ethz.ch>, Marta Mularczyk <mumarta@ethz.ch>
Content-Transfer-Encoding: quoted-printable
Message-Id: <ED33228D-14E3-4885-85BB-CC77E908AA41@wire.com>
References: <7b86078a-55dc-7d80-0a75-e900bed61694@wickr.com>
To: Joel Alwen <jalwen@wickr.com>
X-Mailer: Apple Mail (2.3608.120.23.2.4)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/Yug4BSRCH0XvIhQ-4EHlidvejEs>
Subject: Re: [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 11:03:51 -0000

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 <jalwen@wickr.com> wrote:
> 
> 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).
> 
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls