38

I am looking for existing protocols for a group chat with two things:

  1. End to end encrypted. Just what you would expect: messages are only decipherable by the chat members and message tampering is detected.

  2. It should not encrypt each message for each member individually. The Signal Protocol does this, turning group chats into many one-on-one chats, which is not a proper, scalable solution to the problem. With potentially hundreds of members in a group, even encrypting an encryption key for each member is a considerable downside.

Every new member may receive everyone's public key upon joining, and any group key(s) must be rotated when a member leaves. This scales reasonably enough, and there might not be a way around it without compromising security, so this is allowed and does not count as 'encrypting every message for everyone'.

I've looked for existing protocols, but came up with zero results that meet these requirements. I thought I read about something a few years ago where the group derived a common key and used that or something, but I cannot find anything like that.

Community
  • 1
Luc
  • 31,973
  • 8
  • 71
  • 135
  • 3
    if you don't want to encrypt a given message more than once, you'll need to make the group like a person, and give everyone a copy of the private key. that increases the chances of whoops/darn, which is why most services use per-user keys for group message. – dandavis Jun 12 '16 at 02:52
  • @dandavis I disagree. I understand that losing private or symmetric key creates a bigger problem when it was shared by many members, but you could argue the same for not using an uncrackable OTP scheme: "if you don't want to use a new OTP for every message [but rather want to use a long(er)-lived symmetric key], you increase the chances of [data being leaked]". Moreover you say *"which is why most services use per-user keys for group message"* but there is no *most services* here: there's only the Signal Protocol and no-one else. [1/2] – Luc Jun 12 '16 at 08:47
  • @dandavis [2/2] There seems to be no standard, so why would a shared key be wrong? Also a group doesn't need to have only one private or symmetric key, I was actually thinking it would be good practice to rotate the key for forward secrecy, but I couldn't check whether that's a good idea because there are exactly zero schemes out there. That is ignoring the Signal Protocol, but they didn't even attempt to solve the problem (which is reasonably fair game if you just try to bring encryption to the masses and don't care about improving the algorithms themselves, but not what I am looking for). – Luc Jun 12 '16 at 08:49
  • well to me, "end to end" basically implies 2 ends, but if you know 5 ways to solve this long-standing problem, i encourage you to get them out there so they can start standing the test of time. – dandavis Jun 13 '16 at 08:11
  • @dandavis I don't exactly own a chat network -- and if I did, I wouldn't want to put my users at risk by rolling my own crypto. I can hardly imagine there is is no existing solution other than turning them into one on one chats. (And maybe it's a language thing, I'm not natively English, but for me nothing in "end to end" implies the number of endpoints.) – Luc Jun 13 '16 at 08:19
  • the tools we commonly use to encrypt are either one-to-one (ala rsa/ecc) or rely on shared secrets and key managment (ala aes). there might be ways to do e2e group chat as you describe, but don't you think you would have found it by now? so , i don't think they can be common... the fact that nobody is commenting "hey, just use XXX" says a lot to me. – dandavis Jun 13 '16 at 08:38
  • @dandavis "the fact that nobody is commenting "hey, just use XXX" says a lot to me." Looks like you're right. Not sure whether it's worth starting a bounty, if someone knew of something it's not exactly a hard question that involves much research. Too bad... and still strange I think. – Luc Jun 14 '16 at 06:44
  • A bounty might help, i'd be interested in a solution if there is one... – dandavis Jun 14 '16 at 08:03
  • 1
    @Luc here is some worthwhile reading I hope it helps. http://blog.cryptographyengineering.com/2014/07/noodling-about-im-protocols.html – munkeyoto Jun 14 '16 at 19:21
  • 1
    [@Luc](https://security.stackexchange.com/users/10863/luc) Perhaps [SafeSlinger](https://www.cylab.cmu.edu/safeslinger/) is the group messaging implementation that you read about, where keys are established on membership. [This thesis](http://www.cs.cmu.edu/afs/.cs.cmu.edu/Web/copetas/Posters/JasonLee-Thesis11.pdf) describes an early version of their implementation. – Jedi Jun 15 '16 at 20:56
  • @Luc You sort of inherently have problems in your requirements, especially if you want OTP properties (forward secrecy, plausible deniability) in addition. Even if you drop the privacy requirements, you'd still have a scalability problem to reset the keys repeatedly (because that protocol would be interactive between all members). To be fair, the biggest reason that this isn't the case is probably that one on one crypto is "good enough". The only reason I can think of that you'd want to exchange this is concerns about potential attacks by manipulating key exchange. – Rens van der Heijden Jun 17 '16 at 06:49
  • 1
    Also, I found [this paper](http://ieee-security.org/TC/SP2015/papers-archived/6949a232.pdf) linked from wikipedia while trying to find out how Signal handles groups exactly. It's an impressive overview; on page 11 you'll find a section on group chat, which says that "Multicast encryption is used for performance: a single encrypted message is sent to a central server for relaying to recipients while the decryption key for the message is sent pairwise using TextSecure." It also details which requirements cannot be met by this scheme. Not a lot of info about implementations though. – Rens van der Heijden Jun 17 '16 at 06:57
  • Are you looking for implementations or approaches? – Lie Ryan Jun 17 '16 at 14:26
  • @LieRyan Implementations I think. But from those implementations I'm not particularly interested in the code, I'm interested in the approach they took. However just approaches are usually theoretical, that's why I'd like to see something that has been implemented somewhere. For example "onion routing" is an approach with lots of theory behind it, but the Tor network with 3 hops and layers of encryption can be explained in two or three paragraphs and I could understand most of the considerations involved. – Luc Jun 17 '16 at 17:34
  • Note to self: MLS might turn into an answer if it ever becomes stable (for now it's a draft with open issues, and they're trying to cover (too?) many use-cases (e.g. both non-repudiation and plausible deniability) which sounds like IPsec all over again): https://datatracker.ietf.org/doc/draft-omara-mls-architecture/ / https://datatracker.ietf.org/doc/draft-barnes-mls-protocol/?include_text=1 – Luc Feb 10 '18 at 22:26

2 Answers2

41

Let me try to sum up what the landscape of end-to-end encrypted messaging protocols for group chat looks like:

  • Protocols like PGP have been around for some time and offer "group messaging" by simply encrypting the content with a randomly generated symmetric key and then encrypting that key asymmetrically with the public keys of each of the recipients. These protocols only sends the encrypted content once but encrypts the encryption key to each of the members of the group. Note that similarly to PGP, this approach does not provide any perfect forward secrecy, deniability or conversation integrity (and thus no transcript consistency).

  • OTR was introduced to address some of the shortcomings of PGP, improving on perfect forward secrecy, conversation integrity and deniability. Ian Goldberg, the author of OTR also wrote a paper on a multi-party variant of the protocol, named mpOTR. mpOTR was designed with the XMPP transport in mind and inherently synchronous in its design, meaning that each group member is expected to be online at any time to negotiate new keying material. The described protocol does not provide in-session perfect forward secrecy and has not been largely deployed. N+1Sec is a similar protocol with some improvements. Note that these protocols have a lot of algorithmic complexity and tend to scale badly, especially when you add latency into the mix.

  • Then you have a whole class of protocols, that we simply call N times protocols because they are just sending each message . These protocols have the advantage of reusing an existing one-to-one protocol, which is really convenient when you already have a channel that gives you nice features such as asynchronous perfect forward secrecy. The group structure is not a cryptographic concept in this case, losing on the cryptographic guarantees but lowering algorithmic complexity. The Open Whisper Systems blog has a great post about why Signal does this instead of mpOTR-style messaging. This class of protocols violates your second requirement since they are what we call “client-side fan-out” where the client encrypts and sends out all of the different messages.

  • There exists an optimisation on Signal's which was adopted by WhatsApp and that you can find in their whitepaper called Sender Keys that has “server-side fan-out”. It uses N times on setup, but after the first message, each member of the group can send a single messages to the group. This protocol has perfect forward secrecy by using a hash ratchet (but does not provide perfect future secrecy). Transcript consistency is enforced by the server-side (because server-side fan-out), but not from a cryptographic perspective.

These are the types of protocols that I've seen being implemented. There are challenges, both in usability and crypto research on how to combine asynchronosity with perfect future secrecy and transcript consistency in the group setting.

If you want a protocol that answers both of your requirements, I think something like the Sender Keys variant of the Signal protocol is what you're looking for.

FredericJacobs
  • 626
  • 6
  • 4
  • 1
    Thank you from the answer! I didn't know Whatsapp did something new, I thought it was just implementing an existing protocol so I didn't look into it. Are they really the only one that has end-to-end with "server-side fan-out"? (Server-side fan-out actually sounds like a fancy way of saying "like all other chat software, e.g. MSN, but this time with encrypted instead of plain messages", hope I understand it correctly.) – Luc Jun 17 '16 at 18:00
  • @Luc : With perfect forward secrecy, this is the only large scale deployment I'm aware of. Most of the other ones are using the PGP approach which was my first bullet point where you encrypt the content with a symmetric encryption key that you then encrypt to the recipients public keys. – FredericJacobs Jun 17 '16 at 18:11
  • WhatsApp is as large scale as it gets indeed! It doesn't have to be *that* large-scale though: some service used by 5000 people from a crypto forum would be just as convincing. – Luc Jun 17 '16 at 19:53
  • is this still the case? I just talked to someone at RWC who told me that Signal encrypts the list of recipients and obtains a key to decrypt it and fan-out the message every time a client sends a message to the group – David 天宇 Wong Jan 11 '20 at 05:43
  • also you should edit your answer with MLS now :) – David 天宇 Wong Jan 11 '20 at 05:44
3

Maybe Asynchronous Ratcheting Tree is what you are asking for.

You can also take a look at Messaging Layer Security:

Messaging Layer Security (MLS) is an IETF working group building a modern, efficient, secure group messaging protocol.

sarnold
  • 721
  • 4
  • 7
cbwang
  • 31
  • 1