Re: [MLS] Improving client authentication

[Benjamin Beurdouche <[e-mail]>]

Hi Raphael, Hi all,

I finally had time to have a look at your proposal and I agree with it. I think this is a nice improvement.

See more inline:

> On 29 Nov 2020, at 18:13, Raphael Robert <raphael=[e-mail]> wrote:
> 
> 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.

To start with, I agree this is a valid threat that we should consider.

This attack is something that we have known for a while and is part of multiple variants of
this problem, but there are no clear solutions in the context of a strong threat model.
This is simply because for MLS we have a significantly stronger threat model than all other
messaging systems have as we often consider active malicious insider and full state device
compromises which lead to many-group compromises.

For instance, if I am correct, the attack you mentioned is valid because it works across devices,
so the natural solution is key separation. But this solution would not work - even if there were
one signature key per group on the device - in the case where you consider that compromising
the device will lead to a compromise of all signature keys on the device (of all groups).

Is this a reason for not doing anything here? No. Even though we can’t achieve perfect security,
especially in the context of strong attackers performing targeted attacks, **I am very inclined
to agree with you and force requiring the signature key to be unique per group** as it provides
better defense in depth. This makes me immediately think about the problem of detecting the key-reuse 
which is not an easy task to handle. An honest DS would be helpful as it could help check that all
the stored key packages for a user have different signature public keys, but that’s not perfect
and my intuition is that the best case is a situation where we can prove some security only in
the absence of an attack and not in cases of compromise. Note that this problem of key reuse
detection already exists and is not new, so that can’t be an argument against *requiring* unique keys.

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

I am in favor of doing this. As you note below, we can also leverage OS keystores and 
hardware features to limit the ability of the attacker to compromise all keys (including across groups) at once.
In that situation we can reduce the risk to an attacker being able to sign arbitrary things
without having access to the actual key, which is good for both FS and PCS.

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

I also agree with this, intermediates can be used in a very efficient way.

Something less relevant to this discussion but I want to mention it here...
This raises an issue that I have seen a lot over the last few years: we need something
which performs a similar role to the WebPKI but doesn’t have the complexity of X.509.
Note that half of the attacks against TLS implementations are actually attacks against
ASN1/X.509 parsers, and we don’t really need this complexity for MLS.

We should probably use X.509 in many cases because it is well supported by HSMs
but in the long run, I think we should create WG and start thinking of a replacement to 
X.509 for places (not the Web) that don’t need the complexity.


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

Overall, I think these proposals are good and we I suggest we do this !
Thanks for looking into it.

Ben.

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