[MLS] Improving client authentication

[Raphael Robert <[e-mail]>]

Hi all,

Recently there was some discussion about identities and credentials in MLS [1][2], in particular whether identities and signatures should be unique per group. The architecture draft defines things as follows:

"Formally, a Client is a set of cryptographic objects composed by public values such as a name (an identity), a public encryption key and a public signature key. Ownership of a Client by a user is determined by the fact that the user has knowledge of the associated secret values. When a Client is part of a Group, it is called a Member and its signature key pair uniquely defines its identity to other clients or members in the Group. In some messaging systems, clients belonging to the same user must all share the same identity key pair, but MLS does not assume this.

Users will typically own multiple Clients, potentially one or more per end-user devices (phones, web clients or other devices...) and may choose to authenticate using the same signature key across devices, using one signature key per device or even one signature key per group.”

In other words: while not encouraged, clients can have the same identity and the same signature key. As such, they become mostly indistinguishable from each other, except for their index in the tree. This was initially worded that way to clearly support real-world use cases where clients indeed have the same credential and MLS can just be used as a key negotiation protocol that builds on top of that. So far this has not received a lot of scrutiny, but I can see scenarios where this can clearly lead to attacks. A first scenario is described by Britta in [2]. Another attack – where attackers use said indistinguishability for impersonation – could go as follows:

 - Alice has two devices, A1 and A2. Both devices use the same credential, meaning they have the same identity and signature key.
 - An attacker briefly compromises A2 and creates a legitimate key package.
 - The attacker then creates an UpdateProposal with that key package and uses the index of A1 as the sender in the MLSPlaintext framing, as well as a RemoveProposal for A2.
 - Other members receive and process these proposals, and to them the UpdateProposal looks like it was issued by A1 (since the index is the one from A1 and the signature key is shared between A1 and A2).
 - Finally one of the other members sends a Commit referencing the proposals, seemingly evicting A2 from the group.
 - The attacker however still knows the HPKE private leaf key of A1 and is therefore still part of the group and can act as a passive attacker until A1 is evicted.
 - Incoming messages will look broken for A1, but it might take a while before A1 notices, if ever.

Besides UpdateProposals, A2 could also send a full Commit or application messages in the name of A1. Maybe other attacks could be mounted that way.

I think these kind of attacks are bad enough to look at things again. I propose the following:

1. Restrict the sharing of credentials: Identities and signature keys MUST each be unique per group.
2. Solve the use case of per-user devices differently.

Regarding the latter, I think we already have all the ingredients we need. The protocol spec has the following definition of credentials:

struct {
    CredentialType credential_type;
    select (Credential.credential_type) {
        case basic:
            BasicCredential;

        case x509:
            Certificate chain<1..2^32-1>;
    };
} Credential;

We can use the fact that a whole chain can be provided for the X509 type. So in case an application wants to use a per-user certificate, this certificate could just move up in the chain and sign a per-device certificate that has a unique identity and signature key. And btw, the same chain could also be allowed for the BasicCredential type with a small spec change.

Why is this better than before? Isn’t this just shifting the problem, because the per-user certificate could still issue an arbitrary number of per-device certificates? 

Firstly, impersonation attacks become harder (if not impossible) because the signature keys used to sign handshake & application messages are no longer shared across multiple devices. 

Secondly, the (private) signature key of the per-user certificate is now only used very rarely, namely in the situation where a new per-device certificate needs to be issued. This opens up new possibilities to better protect that key: it doesn’t have to be on the device necessarily, or it could be stored in a secure enclave, or it could be encrypted with a passphrase the user needs to provide, etc. None of these protection mechanisms could be applied to the per-device certificate, because its signing key needs to be readily available at all times (e.g. mobile messaging apps typically do operations in the background without requiring any action from the user, like sending end-to-end encrypted delivery receipts).

Thirdly, we could limit the validity of the per-device certificate. As mentioned above, that signature key is still relatively exposed and might as accessible to an attacker as the rest of the group state during a brief compromise. Limiting for how much time a per-device certificate is valid, would at least mitigate the risk a bit. We could allow updates to the per-device certificate under the condition that a) the UpdateProposal is signed with the old certificate, b) that the identity doesn’t change and c) that the per-user certificate is still the same.

I think the above proposal would make authentication in MLS better while still catering for the initial use cases.

Raphael


[1] https://github.com/mlswg/mls-protocol/pull/439 <https://github.com/mlswg/mls-protocol/pull/439>
[2] https://mailarchive.ietf.org/arch/msg/mls/6tjSWyAesfU125IFRDfMhRLtsPM/ <https://mailarchive.ietf.org/arch/msg/mls/6tjSWyAesfU125IFRDfMhRLtsPM/>