IM Systems in Depth

Side trip W4

Group encryption

A group of 100 people, 3 devices each, end-to-end encrypted. How many times is one message encrypted? And when someone leaves, how much work is that?

This chapter is a first draft. The author is still checking it, and its text and numbers may change.

Chapter 6 decided that a group message is stored once in the conversation and each member comes to read it: read fan-outread fan-out读扩散Keep one copy in the conversation’s timeline, and each reader fetches it from there. Few writes, more reads; suits big groups. All of v1’s and v2’s messages are kept this way (chapters 6, 10); it needs the server to build the chat list and devices to sync it.See the glossary. That assumes one thing: the server can read the message.

End-to-end encryptionend-to-end encryption端到端加密A message is encrypted on the sending device and only the recipients’ devices can open it; the server passes on bytes it cannot read. Each device has its own keys, so the unit of encryption is the device, not the person.See the glossary (E2EE) takes that away. A message is encrypted on the sending device and only the recipients’ devices can open it; the server passes on bytes it cannot read. Encryption happens wherever the keys are. A person’s phone, laptop and tablet each have their own keys (losing one device does not expose the others), so the unit of encryption is the device, not the person.

This side trip does the sums for one group: 100 members, 3 devices each (phone, laptop, tablet; the book’s average is 1.5 per person, but 3 makes the cost of many devices easy to see), 300 devices in all. Ana sends a line from her phone, and it has to reach 299 devices: the 297 of the other 99 people, plus Ana’s own laptop and tablet.

To be clear: nothing breaks in this side trip. Each of the three designs below runs in large products. The question is where each one puts its cost: on every message, before the first message, or when someone leaves.

Two terms first. A symmetric key is one key that both encrypts and decrypts; it is fast and short (32 bytes). A pairwise session is a channel between two devices: they use each other’s public keys (the half of a key pair anyone may see: anyone can encrypt with it, and only the device holding the matching private key can decrypt; private keys never leave the device) to agree on a key only they know, and derive a fresh key from it for every message. Signal’s protocol works this way, and WhatsApp uses it too. Setting one up means fetching the other device’s public keys from the server, so the first message is a little slower; after that each message costs a few hashes and one symmetric encryption.

1. Pairwise: 299 copies of one message

The direct way: Ana’s phone has a pairwise session with every device and encrypts each message 299 times, every copy different. Signal’s group chat in 2014 worked like this: a group message went to each member as a pairwise encrypted message, and the server did not even know what a group was. WhatsApp does the same for one-to-one chats and for a user’s own other devices; its white paper calls it client-fanout: to reach N devices, the message is sent N times, each copy encrypted with that device’s session.

A message is 200 bytes. Add what encryption attaches (a key number, a counter, a check code) and the recipient’s address, and call each copy 300 bytes (a round assumption):

  • Upload: 299 × 300 B = 89.7 KB. On a weak 2 Mbit/s uplink (chapter 8’s assumption) that is 0.36 s, for every message.
  • Server: 299 different copies, stored and delivered one by one. Chapter 6’s “store once” is gone; we are back to write fan-outwrite fan-out写扩散When a message is sent, write one entry into each recipient’s inbox; reading means reading your own inbox. More writes, fast reads; suits conversations with few members. Chapter 6 weighs it; chapter 10 shows it goes with client-built chat lists, where the phone builds its chats from the inbox. Neither v1 nor v2 uses it.See the glossary, now per device. At 1,000 messages a day the group makes 299,000 copies, 89.7 MB.

Photos stay cheap. In WhatsApp’s white paper an attachment is encrypted once with a random key and uploaded once; what goes to each device is a small message with that key and where the file is. A 200 KB photo costs 200 KB + 299 × 300 B = 289.7 KB in all, not 299 × 200 KB = 59.8 MB.

What pairwise gets right is simplicity: when someone leaves, the next message just isn’t encrypted to their 3 devices. Nothing has to be redone.

2. Sender keys: one key per device

Sender keyssender keys发送者密钥In an end-to-end encrypted group, each device makes a chain key of its own and first sends it to every device in the group over pairwise sessions; after that each message is encrypted once and uploaded once. The cost: when someone leaves, every device makes a new key and sends it out again.See the glossary move the 299 encryptions to the front and do them once. WhatsApp’s groups work this way, and the white paper lists the steps:

  1. The first time a device sends to a group, it generates a random 32-byte chain key and a key pair for signing.
  2. It puts the chain key and the public signing key into a “sender key” message and sends it to each device in the group over the pairwise sessions.
  3. For every later message: derive a message key from the chain key and move the chain key one step forward; encrypt once with the message key, sign it, upload one copy, and the server fans it out to the group.

“One step forward” is a one-way hash: from today’s chain key you can compute the later ones, never the earlier ones. So a newcomer who is given the key still cannot open messages from before they arrived.

A signature is a stamp made with a private key; anyone with the public key can check who made it. It is needed because everyone in the group holds the chain key. Without it, any member could send messages as Ana.

The sums:

  • Each message: 1 encryption, 300 B uploaded. The 299 copies on the server are the same bytes, so it can store one again: chapter 6’s read fan-out is back.
  • Handing out the key: before its first message a device sends 299 copies of its key (89.7 KB), the same as one pairwise message. For two messages, pairwise is 598 copies and sender keys 299 + 2 = 301: ahead from the second message on.
  • Once everyone has spoken: 300 devices × 299 = 89,700 copies, 26.9 MB, and each device receives 299 keys (89.7 KB). The bill is lazy: only devices that speak hand out keys. If only 10 people speak, on all 3 devices, it is 8,970 copies, 2.7 MB.

Signal uses sender keys now as well. Signal-Android’s group sending code splits the recipients in two: those that support sender keys get a sender-key message, the rest still get pairwise copies (and with fewer than 2 sender-key recipients, all go pairwise). The encryption itself is in libsignal.

3. Someone leaves: everyone changes keys

Ben leaves. His 3 devices go; 297 stay.

Ben holds the chain key of every device in the group and can keep stepping it forward. As long as the others keep using their old keys, he can keep reading the group (he can still get the encrypted bytes, the ciphertext: they pass through the server and the network). So WhatsApp’s rule is: whenever a member leaves, everyone clears their sender key and starts over. Signal-Android does the same: when members are removed, it throws away its own key and makes a new one at the next send; it also replaces keys that have grown too old.

The sums:

  • Each staying device sends 296 new key copies (88.8 KB) before it next speaks.
  • If all 297 speak again: 297 × 296 = 87,912 copies, 26.4 MB; each device receives up to 296 new keys.
  • Lazy again: if only 10 people speak again, on all 3 devices, it is 8,880 copies, 2.7 MB.

The bill is quadratic: double the devices and one round of new keys costs four times as much. A group with 1,500 devices (500 people) needs 2.24 million copies for a round; 3,000 devices, 8.98 million. The MLS standard, RFC 9420, says as much in its introduction: with sender keys, recovering after a key is exposed takes a number of key update messages that grows with the square of the group size.

Joining is much cheaper. When a newcomer’s 3 devices arrive, existing devices send them their current keys, at most 300 × 3 = 900 copies, and nobody changes keys. As above, the newcomer gets today’s chain key and cannot open earlier messages.

4. MLS: a tree

MLS (Messaging Layer Security, RFC 9420, July 2023) takes another route. The whole group shares one group secret for a stretch of time, and every message key is derived from it; that stretch is called an epoch. When membership changes, the group moves to a new secret and the next epoch. The hard part is telling the new secret only to those who stay.

The answer is a binary tree. Each device is a leaf. The tree is always full (RFC 9420’s term: the number of leaf slots is a power of two): 300 devices sit in 512 leaf slots (512 = 2⁹), with 9 levels above the leaves. Every node above the leaves can hold a key pair, and every leaf below it knows its private key; the group secret is derived from the root. So “encrypting to a node” means one encryption with its public key, and every device below it can open it.

What happens in a key change

The message that changes the group is called a Commit: it says who joins, who leaves and which keys changed, and on receiving it the whole group moves to the next epoch together. The device sending it walks from its leaf up to the root, and every node on the way gets a new key pair. Each node has two subtrees below it: the device’s own side knows the new key, the other side does not yet and must be told. If the other subtree’s top node has a key, one encryption to it reaches every leaf in that subtree. One per level: 9 levels, 9 encryptions. Section 4 of the RFC puts it this way: encrypting to all but one member takes log(N) encryptions instead of the N − 1 needed to encrypt to each one.

Nodes can also be blank: when someone leaves, their leaf and the nodes above it are cleared. A blank node has no key, so it has to be split, encrypting to each node below it that has one. The fewer blank nodes, the cheaper; the more, the dearer.

demo.py builds the RFC’s array-based tree (Appendix C) for 300 devices and counts how many encryptions one Commit takes (82 bytes each, plus a 33-byte public key for each node on the path):

Case Encryptions Commit size (without signatures etc.)
No blank nodes, a device only changes its own key 9
No blank nodes, removing Ben’s 3 devices 14 9 × 33 + 14 × 82 B = 1.4 KB
New group (only the creator’s path has keys), removing Ben 233 19.4 KB

Removing Ben costs 5 more than a plain key change: his 3 leaves (devices 100–102 in demo.py) and every node above them up to the root are cleared. At the 8th step up from device 200, the subtree alongside holds devices 0–127, and its top node lies on Ben’s path, so it has no key any more; it has to be split into the 6 nodes below it that still have keys (devices 0–63, 64–95, 96–99, 103, 104–111, 112–127), so one encryption becomes six. In a tree with no blank nodes, removing Ben takes one 1.4 KB Commit from a staying device (device 200 in demo.py), which the server delivers to the other 296 devices, 427.7 KB in all; sender keys take 26.4 MB. Each device receives one message instead of 296 keys.

A new group is different: apart from the creator’s path, every node above the leaves is blank, so the Commit has to encrypt nearly device by device, 233 times. The blank nodes fill in as members send Commits of their own.

Bigger groups (3 devices each, one member removed):

Members Devices Pairwise: each message Sender keys: one round (all speak again) MLS: no blank nodes MLS: new group
10 30 29 702 8 19
100 300 299 87,912 14 233
500 1,500 1,499 2,239,512 18 1,241
1,000 3,000 2,999 8,979,012 20 2,485
10,000 30,000 29,999 899,790,012 27 21,805

For ordinary messages MLS is the same as sender keys: one encryption each, and the server sends the same bytes to the whole group.

5. The cost

  • Sender keys: leaving is expensive, and a stolen key is hard to recover from. One round of new keys is quadratic. The other side: if a sender key is stolen from a device, whoever holds it can keep stepping it forward and reading that person’s messages until the next key change. The introduction of RFC 9420 points this out too. So besides changing them when someone leaves, groups change keys on a schedule (Signal-Android by the key’s age; Matrix recommends weekly or every 100 messages), and every change is another 299 copies.
  • MLS: changes must happen in one order. Every Commit is based on one epoch; if two members send a Commit on the same epoch at the same time, only one can take effect. Section 14 of the RFC says applications must have a way to resolve conflicting Commits. This fits the trunk: chapter 5 gave each conversation’s messages a seqseq序号(seq)The number of each message in a conversation, assigned in order by the message service that owns it. It sets the order, lets a client see which message is missing, and tells a returning phone which conversations it is behind on.See the glossary, and chapter 12 made joins and leaves take a seq too. The server can order Commits the way it orders messages: for each epoch the first to arrive wins, and the others are redone on the new epoch. The server cannot read them, but ordering is still its job.
  • MLS: more complex. Trees, epochs, the Welcome message that hands a newcomer the current group secret, the various Proposals (first propose “add this one, remove that one”, then one Commit applies them together): a client implements much more than with sender keys, and mistakes are harder to trace.
  • All three: a new device cannot see old messages. The server holds only ciphertext the new device cannot open, so chapter 16’s path, where a new device pulls history from the server, is closed. How history moves between one’s own devices belongs to chapter 42, “Private messenger”.

6. Other answers

  • Matrix encrypts groups with Megolm, the same idea as sender keys: each participant encrypts with their own outbound session (in effect, their sender key), whose keys go to the others over pairwise sessions. The spec requires a new session whenever someone leaves, and recommends a new one every week or every 100 messages besides.
  • Signal’s sealed sender v2: so that the server doesn’t learn who sent a message, libsignal encrypts the body once and attaches 48 bytes per recipient (a 32-byte encrypted random value and a 16-byte tag), besides each recipient’s address; the server splits it up and routes each part.
  • Discord’s DAVE (September 2024) uses MLS to exchange group keys for voice and video calls; text messages are not end-to-end encrypted.
  • Telegram simply doesn’t encrypt groups end to end: its FAQ says group chats and ordinary private chats are “cloud chats”, encrypted only between client and server; its end-to-end “secret chats” are one-on-one only and live only on the two devices that set them up, so a new device or a logout loses them. That avoids both the group bill and the multi-device bill, at the price of neither being encrypted.
  • RCS: the GSMA’s Universal Profile 3.0 (March 2025) adds end-to-end encryption to RCS messaging, based on MLS.

7. This side trip’s decision

That is the encryption bill. The trunk goes on at chapter 11, “Syncing the conversation list”; the private messenger as a whole product (a server that keeps as little as possible, history moving between devices) is chapter 42.

Comments

Comments live in GitHub Discussions and need a GitHub account.