Subject: [MLS] All commits = external commit?

From: Joel Alwen <[email-masked]>
Date: Tue, 6 Oct 2020 18:38:51 +0200

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

---

From: Raphael Robert <[email-masked]>
Date: Tue, 6 Oct 2020 18:55:40 +0200

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 <[email-masked]> wrote:
> 
> Hey people,
> 
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Wed, 7 Oct 2020 11:48:40 -0400

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=
[email-masked]> 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
>

---

From: Brendan McMillion <[email-masked]>
Date: Wed, 7 Oct 2020 17:25:17 -0700

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 <[email-masked]> 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.)
>

---

From: Richard Barnes <[email-masked]>
Date: Mon, 12 Oct 2020 16:58:40 -0400

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 <[email-masked]>
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.
>

---

From: Joel Alwen <[email-masked]>
Date: Tue, 13 Oct 2020 16:58:39 +0200

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?

> Sorry that's not super concrete.  Maybe some of the folks doing proofs here

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 <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>     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 <[email-masked]
>     <mailto:[email-masked]>> wrote:
> 
>         ExternalCommit from group members.  (Something about which I had waffled
>         in a previous email.)
> 
>         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
>         On Tue, Oct 6, 2020 at 12:55 PM Raphael Robert
>         <raphael=[email-masked] <mailto:[email-masked]>>
>         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).
> 
>             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 <[email-masked]
>             <mailto:[email-masked]>> wrote:
>             >
>             > Hey people,
>             >
>             > [email-masked] <mailto:[email-masked]>
>             [email-masked] <mailto:[email-masked]>
>         [email-masked] <mailto:[email-masked]>

---

From: Brendan McMillion <[email-masked]>
Date: Tue, 13 Oct 2020 09:39:50 -0700

> start of this thread. So maybe you are (implicitly) thinking about a

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

> 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 <[email-masked]> wrote:

> attacker
> they're
> >             > 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
> >             > receiver) compared to SIC which I think we should avoid if
> we can,
> >             even at the
> >             > - AEC doesn't ensure the committer knows the old epoch's
> key
> >             schedule. This can
> >             > 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
> >             > 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
> >             > are ultimately communicated to users should, in principle,
> be left
> >             up to
> >             > 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

---

From: Richard Barnes <[email-masked]>
Date: Tue, 13 Oct 2020 18:30:12 -0400

On the complexity point: I think the rules are a bit simpler than what you
describe (added numbering for reference):

1. if Commit is from "new_member" SenderType:
  a. It must have a path
  b. It must contain at least one Add that matches
Commit.path.leaf_key_package [same identity at least; same rules as for
someone in the tree]
  c. It must contain exactly one ExternalInit, provided inline [since
external people can't send Proposals]
  d. The Commit itself must be signed by the key in
Commit.path.leaf_key_package.credential
2. if Commit is from "member" SenderType:
  a. It can't contain any ExternalInit proposals

(Re: "The identities in the Adds from new_member SenderTypes can't
correspond to any existing group members" - This doesn't hold, because the
new joiner might be a new instance of an existing group member.)

Having implemented this, it wasn't that bad.  The checks here align well
with the natural layering.  The worst "layering violation" is the need to
reach into the Commit.path.leaf_key_package to get the public key to verify
the credential, and the signal that this is an external message has to be
passed to Commit processing.  Other than that, it's a few more lines in
Commit handling.

And honestly, you have almost the same amount of complexity if you always
do AEC.  You save steps 1(c) and 2, because the ExternalInit is always
there.  You still need checks 1(a), 1(b), and the layering violations.

--Richard

On Tue, Oct 13, 2020 at 12:40 PM Brendan McMillion <[email-masked]>
wrote:

>   - The identities in the Adds from new_member SenderTypes can't
> correspond to any existing group members
> 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.
>
>
>> >             > - 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
>> >             > subject to reasonable costs. Which aspects of the
>> resulting
>> >             security properties
>> >             > are ultimately communicated to users should, in
>> principle, be left
>> >             up to