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

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.

• Please try to ask only one question per question -- our site format doesn't work so well when you have multiple questions in the same post. You have four questions in there, which is too many. Also, "should" questions are subjective/a matter of opinion and probably aren't a good fit here; see our help center. Thank you!
– D.W.
Aug 19, 2016 at 19:56
• Rather than "stuff EDIT: more stuff", it's better to edit your question to a cohesive whole that reads well for someone who sees it for the first time (i.e., to take the form it should have been from the start). Don't use "EDIT:"; we have revision history, so you don't need to mark what has changed. Also, if some material is no longer relevant, remove it, rather than writing "(stuff) EDIT: never mind, I actually meant (other stuff)". I suggest you ask a new question, informed by what you have learned here, rather than changing the question so radically (and invalidating an existing answer).
– D.W.
Aug 19, 2016 at 21:52
• "What is the recommended practice?" is subjective. There is no single recommended practice. Everyone might recommend something different; that's too subjective, so it's better not to ask that kind of question -- see our help center. Instead, it's better to describe the problem you are trying to solve -- e.g., what the security requirements are, what kind of user-visible functionality you want to support, what you want the user experience to look like.
– D.W.
Aug 19, 2016 at 21:55
• Edited it, but I'm not really sure how to phrase it differently to avoid asking for the recommended practice. I'm trying to convey that a solution that is being used by a trusted protocol like the Signal Protocol would be optimal.
– Awn
Aug 19, 2016 at 22:09
• "Usually" is unanswerable, but asking what Signal does would be a perfectly fine question, if that's what you want to ask.
– D.W.
Aug 19, 2016 at 23:10

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.

• Using a server key,or a group key as you put it, comes with challenges of its own. If it's compromised, then the encryption means nothing. The second solution you put forward gives the server some control over encryption and decryption, however, this isn't an end-to-end system. The signing is a good point, and I was trying to come up with some kind of protocol whereby the authorised keys are signed by a trusted or admin client but then how does the server remember which the admin client is? Can I sign with any existing key? What about the first key? How does SSH handle the problem in the OP?
– Awn
Aug 19, 2016 at 19:53
• @Eclipse, I think I've answered the question you asked. If your actual question was different (how do I build a system that meets such-and-such requirements?), well, that wasn't in the question you asked above, so I suggest you ask a new question. This is a question-and-answer site, so we can only answer the question that was asked. This isn't the place for extended discussion or back-and-forths.
– D.W.
Aug 19, 2016 at 19:55
• I don't feel that my main points have been answered. A server key is really not a good solution, and your other solution is not an end-to-end encryption system, as mentioned in the title of the question.
– Awn
Aug 19, 2016 at 20:15
• @Eclipse, you might want to edit the question, then. Note that both my first solution (group key) and third solution (signed list of group members) do involve end-to-end encryption.
– D.W.
Aug 19, 2016 at 21:28
• With the signing, the server would have to store a private key somewhere, which means that a server compromise would be detrimental. The most important principle is that even if the server is dishonest, according to the adversarial model, confidentiality and security are not compromised.
– Awn
Aug 19, 2016 at 21:32