Re: [MLS] All commits = external commit?

Brendan McMillion <brendan@cloudflare.com> Tue, 13 October 2020 16:40 UTC

Return-Path: <brendan@cloudflare.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 8E0A63A09D6 for <mls@ietfa.amsl.com>; Tue, 13 Oct 2020 09:40:05 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.298
X-Spam-Level:
X-Spam-Status: No, score=-3.298 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-1.2, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.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 loMsoMauquRm for <mls@ietfa.amsl.com>; Tue, 13 Oct 2020 09:40:02 -0700 (PDT)
Received: from mail-qk1-x730.google.com (mail-qk1-x730.google.com [IPv6:2607:f8b0:4864:20::730]) (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 61BC93A09CC for <mls@ietf.org>; Tue, 13 Oct 2020 09:40:02 -0700 (PDT)
Received: by mail-qk1-x730.google.com with SMTP id x20so382158qkn.1 for <mls@ietf.org>; Tue, 13 Oct 2020 09:40:02 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Q7SUQvkUvh6U1vR1+i3gJ4AS5RL4zsHqyuS4J5ygQ54=; b=I0xWNIRb2zO/6DT12zAa7IWENVlVADR25m8TY1VNozfFCw3UzKzqtuI5DmQ1ol/kLn ark0FId2n4uPJdWV3cBlAKJ9Ngm+GXUtLPC+f7pcUf0Axy1/FWVHAstsuTqFMEo+gVlL v7wFUkyi5kSlDFpjItYGCefRpU8mF3kKT15BU=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=Q7SUQvkUvh6U1vR1+i3gJ4AS5RL4zsHqyuS4J5ygQ54=; b=HzzrIibgzbNIKUW7cvEdrua9MjYfByk+kNCPWjSj7EJNiJg8iPP5s/lldQZdli4J+T 3Uav9qXWz/FDZhtDc4O6jlcwpsIiPMjrzH3f5tWHMfMoEzKRb6o93e/D1kbTYIsX7rgv LT+lxibPLz2enoDCcAFOZt7mFii7QZrzEhaYuAmzhE6wArgHywicVryGbqsGuz2t1EPC IuX2pdsWaxu7iXc6RnAYioWMQ29nJ6WOa4EqW0Kizt8OoCvTGq/5GW/82AzkCvCE2xbt ov2pBe29NpwT45t7ZrTLqFAlWjTQd34FgzIa1HRKxhcqzC25stnYeQtEm+iGSihVymKx 8eaA==
X-Gm-Message-State: AOAM530RVURWnP0gAgTCSLz2mzazo+xd45IkygTf14ysEOrN2C/ZjDsR naqvSnG6vSP338dqV4ybJijItrnIdCSfY4s6CxVQPA==
X-Google-Smtp-Source: ABdhPJw2ZN/RArA8Ys51YSZOdO28F0Lt+Srl+LCXzVwQkFUYr63byEdcbguwsPmbJx9Hw1af1q3yZmSi17lWhfclF4w=
X-Received: by 2002:a37:d55:: with SMTP id 82mr826320qkn.227.1602607201114; Tue, 13 Oct 2020 09:40:01 -0700 (PDT)
MIME-Version: 1.0
References: <ceb4e95a-09b7-c4cb-cd8f-50641b605fbf@wickr.com> <7E1C8351-0C05-40F7-86D2-803AFFE5554E@wire.com> <CAL02cgRKF4pfsovTUYRJAO7Of8sDYWEFNjzMdkPq8b0-t_feuw@mail.gmail.com> <CABP-pSSM14WsC-zX41o9Yp76ne_8B1diSfoRjNs2RFbvwV6QCA@mail.gmail.com> <CAL02cgRKMx3WPvj-urR_saQy41Z+x=8-mjx=1Qug06BhK+u8Bw@mail.gmail.com> <4ebdc134-59f5-8331-e9c8-ac3c9f343320@wickr.com>
In-Reply-To: <4ebdc134-59f5-8331-e9c8-ac3c9f343320@wickr.com>
From: Brendan McMillion <brendan@cloudflare.com>
Date: Tue, 13 Oct 2020 09:39:50 -0700
Message-ID: <CABP-pSToBCT8yhY6ff5-CVwpq3ypi=+AhcQRJGxNcSDx=Ef5bQ@mail.gmail.com>
To: Joel Alwen <jalwen@wickr.com>
Cc: Richard Barnes <rlb@ipv.sx>, Raphael Robert <raphael=40wire.com@dmarc.ietf.org>, Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000f00b1405b1901084"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/1yI3OzB733FEzrxXJRavScP3nvk>
Subject: Re: [MLS] All commits = external commit?
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: Tue, 13 Oct 2020 16:40:06 -0000

>
> So, the attacks I describe do work for the construction I had outlined at
> the
> start of this thread. So maybe you are (implicitly) thinking about a
> different
> construction?


It doesn't work because MLSPlaintext messages from internal sender types
are authenticated with a MAC, derived from the key schedule. An outsider
can form a valid asymmetric Commit, but since they don't have the MAC key
they'd have to mark the message as being from a new_member sender type.

Moreover, when an internal commitor uses bad randomness the security we get
> from
> AEC+SIC is strictly worse than what SIC gives us. Bad randomness ==>
> secrets
> chosen by commitor during the commit are known to (or at least easier to
> guess)
> by the adversary.
>

Hardening the protocol against bad randomness is too severe of a design
constraint, especially given how big the protocol is and that this problem
is best solved by using a better-implemented RNG. Even if bad randomness
doesn't directly compromise the group, it interferes with the PCS of the
ratchet tree. It causes nonce reuse. It breaks the confidentiality of
Welcome messages sent to that peer.

In the external-join case, you need this independent variable, so that the
> new joiner can join the key schedule.  In the internal-commit case, you
> don't need it, so it's purely a source of potential mischief.
>

We already have one joint for handling messages from external senders: the
new_member sender type. By always using asymmetric commits, we rely on this
one joint working like it always has. In the approach that you've been
working on in the other thread, we have a lot more moving parts and need to
coordinate between three different protocol messages. A subset of the
Commit validation logic is:

if Commit is from new_member SenderType:
  - It must contain at least one Add from a new_member SenderType
  - The identities in the Adds from new_member SenderTypes can't correspond
to any existing group members
  - It must contain exactly one ExternalInit from an external SenderType,
signed by one of the keys in an Add that's also from a new_member SenderType
  - The Commit itself must be signed by the same key the ExternalInit
proposal is
if Commit is from internal SenderType:
  - It can't contain any ExternalInit proposals

Note that Commits are no longer valid if all their individual proposals are
valid, they need an interaction between several proposals and the Commit
itself to succeed.


On Tue, Oct 13, 2020 at 7:58 AM Joel Alwen <jalwen@wickr.com> wrote:

> On 08/10/2020 02:25, Brendan McMillion wrote:
> > Unfortunately the attack outlined above doesn't work
>
> So, the attacks I describe do work for the construction I had outlined at
> the
> start of this thread. So maybe you are (implicitly) thinking about a
> different
> construction?
>
> Put simply, AEC is explicitly designed to allow a non-group member to
> produce a
> valid commit. I.e. given a signing key certified to Alice and the public
> group
> state one can always produce a valid AEC commit from Alice to the group.
> (This
> includes any and all AEAD keys, MACs, etc. needed for the commit packet.
> Otherwise AEC wouldn't full-fill its stated purpose.)
>
> Ergo if we use AEC for internal commits too then, to commit on behalf of
> Alice
> (who is already in the group), all I need again is her signing key and the
> public group state all of which is available to the adv in the attacks
> outlined
> at the start of the thread.
>
> So trying to read between the lines, my guess is that you are actually
> thinking
> of a hybrid between AEC+SIC for internal commits? Basically, the
> init_secret is
> derived as in AEC (by KEMing to the group) but the current key schedule is
> also
> used to derive a secret used for authenticating group membership of the
> commitor
> (e.g. AEAD encryption key for an MLSCiphertext, or membersip_key for
> MACing the
> MLSPlaintext).
>
> If that's the case, we're back to authenticating group membership for
> internal
> commits which is an absoluately crucial property IMO. But we're also back
> to not
> having full code reuse between external vs. internal commits. And we're
> definitely paying a price: internal commits require otherwise needles
> asymmetric
> crypto operations and commits take more bandwidth. Is their any point
> beyond a
> bit (but not full) code reuse between int/ext commits?
>
>
>
> On 12/10/2020 22:58, Richard Barnes wrote:
> > Sorry that's not super concrete.  Maybe some of the folks doing proofs
> here
> > have thoughts?
>
> So pure AEC for internal commits is definitely much worse in terms of
> security.
> We need internal commitors to prove they know the old epochs key schedule.
> This
> plays a central role in the general security guarantees provided by MLS.
>
> Moreover, when an internal commitor uses bad randomness the security we
> get from
> AEC+SIC is strictly worse than what SIC gives us. Bad randomness ==>
> secrets
> chosen by commitor during the commit are known to (or at least easier to
> guess)
> by the adversary. In this case, for the new epoch_secret[n] to be secure we
> can't rely on entropy coming from commit_secret. Instead, we need
> init_secret[n-1] to have entropy. For SIC that can be the case (depending
> on
> past corruptions of course) so we're (potentially) good. But for AEC+SIC
> we're
> *always* screwed coz knowing the KEM secret chosen by the commitor lets you
> compute init_secret[n-1].
>
>
>
> IMO this is all a bit moot anyway. Some limited code reuse is just not
> worth
> extra asymmetric crypto ops. & extra bandwidth. Even with identical
> security
> guarantees I'd say its a bad idea to KEM init_secrets to the group.
>
> - Joël
>
> On 12/10/2020 22:58, Richard Barnes wrote:
> > That's a fair point, Brendan.  The thing that still worries me, though,
> is that
> > the KEM operation in an AEC effectively introduces a new independent
> variable --
> > who is the sender for purposes of the KEM operation?  In the DHKEM case,
> who
> > holds the private key corresponding to the ephemeral public key?
> >
> > In the external-join case, you need this independent variable, so that
> the new
> > joiner can join the key schedule.  In the internal-commit case, you
> don't need
> > it, so it's purely a source of potential mischief.  It's possible that
> other
> > mechanisms protect against such mischief, but (a) we would need more than
> > mailing-list proofs that that was the case, and (b) we would need to
> somehow
> > assure that future extensions to the protocol would interact badly with
> this
> > mechanism.  It seems more conservative to not have the additional choice.
> >
> > Sorry that's not super concrete.  Maybe some of the folks doing proofs
> here have
> > thoughts?
> >
> > --Richard
> >
> >
> > On Wed, Oct 7, 2020 at 8:24 PM Brendan McMillion <brendan@cloudflare.com
> > <mailto:brendan@cloudflare.com>> wrote:
> >
> >     Unfortunately the attack outlined above doesn't work because if an
> attacker
> >     has Alice's state from a previous epoch and Alice has since Updated,
> they're
> >     unable to encrypt MLSCiphertext or authenticate MLSPlaintext
> messages. The
> >     attacker could use Alice's signing private key to send an Add
> proposal and
> >     Commit, but they'd be marked as being from an external sender.
> There's no
> >     distinction between Alice being in the group already or the attacker
> adding
> >     Alice to groups she was never in to begin with -- this is a risk
> inherent
> >     with allowing external joiners, not the asymmetric Commit mechanism
> itself.
> >
> >     On Wed, Oct 7, 2020 at 8:49 AM Richard Barnes <rlb@ipv.sx
> >     <mailto:rlb@ipv.sx>> wrote:
> >
> >         Thanks for this analysis, Joël.  This aligns with my intuition
> as well,
> >         and seems like a good rationale for a hard prohibition on AEC /
> >         ExternalCommit from group members.  (Something about which I had
> waffled
> >         in a previous email.)
> >
> >         Another way to think about this: PCS with regard to a member is
> about
> >         removing an old version of that member (as represented by an
> HPKE key
> >         and signing key).  AEC is designed to allow joins, which means
> that
> >         AEC-from-inside allows the old, compromised version of the
> member to
> >         rejoin, which kills PCS.
> >
> >         --Richard
> >
> >         On Tue, Oct 6, 2020 at 12:55 PM Raphael Robert
> >         <raphael=40wire.com@dmarc.ietf.org <mailto:
> 40wire.com@dmarc.ietf.org>>
> >         wrote:
> >
> >             I second that assessment, my idea behind External Commits
> was to
> >             offer a mechanism where internal Commits couldn’t be used.
> External
> >             Commits should remain optional (this can easily be achieved
> by not
> >             providing the ExternalCommitInfo package to new members) and
> when
> >             they are used they should be used as a last resort mechanism
> >             (meaning there really is no way to add a member with an
> internal
> >             Commit).
> >
> >             I also think MLS should should remain in the position to
> cover most
> >             scenarios from mainstream consumer messaging to messaging in
> high
> >             security environments. External Commits make the former much
> more
> >             accessible but shouldn’t jeopardise the latter.
> >
> >             Raphael
> >
> >             > On 6 Oct 2020, at 18:38, Joel Alwen <jalwen@wickr.com
> >             <mailto:jalwen@wickr.com>> wrote:
> >             >
> >             > Hey people,
> >             >
> >             > To follow up on the discussion at the end of the Interim
> about
> >             whether to use
> >             > the new "asymmetric external commit" (AEC) mechanism for
> internal
> >             commits I
> >             > wanted to summarize my thoughts here. For brevity let SIC
> be our
> >             current
> >             > "symmetric internal commit" mechanism.
> >             >
> >             > - AEC requires extra asymmetric crypto operations (both for
> >             committer and
> >             > receiver) compared to SIC which I think we should avoid if
> we can,
> >             even at the
> >             > cost of some code complexity.
> >             >
> >             > - AEC doesn't ensure the committer knows the old epoch's
> key
> >             schedule. This can
> >             > play a deciding role in several types of attacks.
> >             >
> >             > Consider this execution:
> >             >
> >             > 1. Alice is in a group. Her state leaks (including her
> signining key).
> >             > 2. Alice commits (to arbitrary propal).
> >             >
> >             > At this point, the adversary can still forge a new AEC
> from Alice
> >             but not an SIC.
> >             >
> >             > Worse, step 2 could have instead been "Alice sends an
> update
> >             proposal replacing
> >             > her leaf HPKE but keeping the her sig keys (e.g. because
> new
> >             credentials are
> >             > costly to come by). Someone commits to the new proposal."
> At this
> >             point I'd
> >             > expect PCS to have kicked in for Alice (as it does when
> using
> >             SIC). But not for
> >             > AECs since Alice's signing key is all thats needed to
> forge a new AEC.
> >             >
> >             > I think it is not worth weakening security this way if we
> dont
> >             have to.
> >             > (Especially, since in some deployments external commits
> may not be
> >             a supported
> >             > feature at all.)
> >             >
> >             > - As for what may or may not be displaid to users, that's
> really
> >             up to the
> >             > implementation. IMO our goal should be to make the
> protocol as
> >             secure as we can
> >             > subject to reasonable costs. Which aspects of the resulting
> >             security properties
> >             > are ultimately communicated to users should, in principle,
> be left
> >             up to
> >             > implementations. That means we shouldn't be designing away
> >             security features
> >             > only because we think they might be hard to communicate.
> (Nor does
> >             it seem that
> >             > inconceivable to me that some implementation may end up
> explicitly
> >             signaling
> >             > whether a commit was external vs internal.)
> >             >
> >             > - Joël
> >             >
> >             > _______________________________________________
> >             > MLS mailing list
> >             > MLS@ietf.org <mailto:MLS@ietf.org>
> >             > https://www.ietf.org/mailman/listinfo/mls
> >
> >             _______________________________________________
> >             MLS mailing list
> >             MLS@ietf.org <mailto:MLS@ietf.org>
> >             https://www.ietf.org/mailman/listinfo/mls
> >
> >         _______________________________________________
> >         MLS mailing list
> >         MLS@ietf.org <mailto:MLS@ietf.org>
> >         https://www.ietf.org/mailman/listinfo/mls
> >
>