Mitigating the effects of server-compromise in an end-to-end encrypted system

Question

I'm working on a chat system that will be end-to-end encrypted, and I've run into a problem. As you know, in end-to-end encrypted chats, the server isn't trusted at all; it's why we have fingerprint checking etc.

The problem came about when I was considering group chats. If Alice, Bob, and Eve are communicating, and Jill decides to join the server, we'll have to re-do the key exchange for her. But what if Jill is a malicious attacker? We'll be giving her the encryption keys! The solution I had in mind was to place each "trustworthy" client's public key in a file on the server, just like SSH does, and then the clients can identify themselves with a digital signature on connection. Now, as D.W. pointed out, this requires trusting the server, which is against standard end-to-end spec. In fact, any solution that allows the server to choose who is in the chat requires trust in the server.

Because what if the server is compromised or dishonest, and instead of attempting an MITM attack, it decides to add his own public key to the authorised_keys file? Then he can connect as a legitimate user and steal the session key. (This is how SSH does it, and I'm not sure how it mitigates this possibility, so as a side-question, clearing this up would be helpful.)

In an end-to-end encrypted system, what degree of control does the server usually have? I mean Signal Messenger has to have thought about this scenario and mitigated it.

Let me direct my question like so: what is the recommended practice for deciding who is a part of an end-to-end encrypted group chat? By recommended practice, I mean to communicate that an answer that draws from a well known and trusted protocol, or thing, like the signal protocol, would be optimal. The requirements are that the server should not be trusted and confidentiality and security for the clients should hold up in the adversarial model. They should also hold up if the server is compromised.

Obviously if the server cannot decide who is in the group, then the clients would somehow have to authorise each additional member, but seamlessly. How should I handle this? The idea is that the server is always up and clients can join and disconnect at any time, like a chat room.

Answer 1

Trusted server

That's right. There are several standard approaches to handling group key management with a trusted server:

• Group key: Use a single group key known to everyone in the group. Anytime someone is removed from the group, change the group key and update everyone who is supposed to still have access. Use a symmetric key for the group key; this makes encryption and decryption efficient.

• Individual keying, with server proxying: Give each person their own individual symmetric key, which is shared only with the server. Each person has a secure connection with the server, secured with this key, and the server forwards messages (decrypting and re-encrypting). This is a hub-and-spoke model, with the server responsible for determining who is allowed to see the messages. When someone is removed from the group, the server will stop forward messages to them.

• Signed list of group members: Have the server sign a list of group members, along with a timestamp. For instance, each group member could be indicated by its public key. It's important to include a way for the server to prove freshness of the signed list (e.g., include a timestamp in the signed data). This solution is vaguely similar to what you sketched in your question, except you seem to have overlooked the need for a timestamp and a signature. Clients will have to periodically poll the server to check for updates to the list of group members.

  If you use public-key encryption to encrypt all messages between group membesr, this will be unnecessarily expensive/slow, because it would require all clients to use public-key encryption to encrypt each message, and require $O(n)$ public-key encryptions per message sent. However, each client could exchange a symmetric key with every other authorized member of the group (using the public key provided by the server), cache this symmetric key, and use it for all subsequent messages, which will be more efficient.

Yes, this is a pain, but it's a necessary pain.

No, your solution isn't secure, for exactly the reason you mentioned: because the list of group members is unsigned, it can be modified by a man-in-the-middle.

All of these solutions require trust in the server. That is unavoidable: it's part of your problem specification that the server determines who is authorized to be in the group. Thus, a malicious server can just add himself to the group and read/modify all the traffic. Once you start from a world where the server is empowered to decide group membership, you must trust the server. There's no way to avoid trusting the server, if the server is empowered to decide who is part of the group -- in that model, there's no way to build a solution that doesn't involve trust in the server.

Untrusted server

The simplest approach is to have a single group leader who is in charge of group membership, and who has complete control over the list of people in th group. The most natural model is that the group leader be the first person to create the group -- so the group owner is one of the members of the group, and controls who the other members are.

You can easily support that model, without trust in the server. Simply take any of the three solutions above, but replace "server" with "the group owner's machine".

There are other approaches one could imagine -- e.g., once someone is in the group they can never be removed (revocation is impossible); or, all members must approve each group member and any member can kick anyone out of the group at any time -- but the usability consequences of those seem horrible, so I can't imagine they are going to be attractive.