41

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.

Improve this question
15
  • 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
    Commented Jun 12, 2016 at 2: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
    Commented Jun 12, 2016 at 8:47
  • 1
    @Luc here is some worthwhile reading I hope it helps. blog.cryptographyengineering.com/2014/07/…
    – munkeyoto
    Commented Jun 14, 2016 at 19:21
  • 1
    @Luc Perhaps SafeSlinger is the group messaging implementation that you read about, where keys are established on membership. This thesis describes an early version of their implementation.
    – Jedi
    Commented Jun 15, 2016 at 20:56
  • 1
    Also, I found this paper 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
    Commented Jun 17, 2016 at 6:57

2 Answers 2

Reset to default
47
+100

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.

Improve this answer
5
  • 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
    Commented Jun 17, 2016 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
    Commented Jun 17, 2016 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
    Commented Jun 17, 2016 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
    Commented Jan 11, 2020 at 5:43
  • also you should edit your answer with MLS now :)
    – David 天宇 Wong
    Commented Jan 11, 2020 at 5: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.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .