Re: [MLS] All commits = external commit?

[Richard Barnes <[e-mail]>]

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 <[e-mail]>
wrote:

> 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 <[e-mail]> 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 <
>> [e-mail]
>> > <mailto:[e-mail]>> 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 <[e-mail]
>> >     <mailto:[e-mail]>> 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=[e-mail] <mailto:
>> [e-mail]>>
>> >         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 <[e-mail]
>> >             <mailto:[e-mail]>> 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
>> >             > [e-mail] <mailto:[e-mail]>
>> >             > https://www.ietf.org/mailman/listinfo/mls
>> >
>> >             _______________________________________________
>> >             MLS mailing list
>> >             [e-mail] <mailto:[e-mail]>
>> >             https://www.ietf.org/mailman/listinfo/mls
>> >
>> >         _______________________________________________
>> >         MLS mailing list
>> >         [e-mail] <mailto:[e-mail]>
>> >         https://www.ietf.org/mailman/listinfo/mls
>> >
>>
>