# 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?

IM Systems in Depth · https://im.liko.page/en/group-encryption/

[Chapter 6](/en/offline-sync/) decided that a group message is stored once in the conversation and each member comes to read it: read fan-out. That assumes one thing: the server can read the message.

**End-to-end encryption** (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](https://signal.org/blog/private-groups/) 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](https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf) 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-out, 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 keys** 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](https://github.com/signalapp/Signal-Android/blob/main/app/src/main/java/org/thoughtcrime/securesms/messages/GroupSendUtil.java) 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](https://github.com/signalapp/libsignal/blob/main/rust/protocol/src/group_cipher.rs).

## 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](https://github.com/signalapp/Signal-Android/blob/main/app/src/main/java/org/thoughtcrime/securesms/database/GroupTable.kt), 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](https://www.rfc-editor.org/rfc/rfc9420.html#section-1), 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](https://www.rfc-editor.org/rfc/rfc9420.html), 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](/en/ordering/) gave each conversation's messages a seq, and [chapter 12](/en/group-membership/) 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](/en/many-devices/)'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"](/en/private-messenger/).

## 6. Other answers

- **Matrix** encrypts groups with [Megolm](https://gitlab.matrix.org/matrix-org/olm/-/blob/master/docs/megolm.md), 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](https://spec.matrix.org/latest/client-server-api/#mroomencryption) 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](https://github.com/signalapp/libsignal/blob/main/rust/protocol/src/sealed_sender.rs) 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](https://discord.com/blog/meet-dave-e2ee-for-audio-video) (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](https://telegram.org/faq#q-so-how-do-you-encrypt-data) 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](https://core.telegram.org/api/end-to-end) 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](https://www.gsma.com/newsroom/article/rcs-encryption-a-leap-towards-secure-and-interoperable-messaging/).

## 7. This side trip's decision

**Decision card**

- Problem: An end-to-end encrypted group, 100 people × 3 devices: pairwise, one message is encrypted 299 times and uploads 89.7 KB, and the server must store a copy per device; chapter 6's “store once” is gone.
- Choice: Sender keys: before it first speaks, each device sends its own key to the other devices over pairwise sessions; after that every message is encrypted once, signed, uploaded once and fanned out by the server. When a member leaves, everyone changes keys. For very large groups or heavy churn, MLS (RFC 9420).
- Cost: 299 key copies before a device's first message; when someone leaves, a round of new keys is up to 87,912 copies, 26.4 MB, growing with the square of the device count. MLS brings it down to one Commit of about 1.4 KB (when no node is blank), at the price of one order for Commits and a complex client; in a new group most nodes are blank and one Commit takes 233 encryptions. In all three, new devices cannot read old messages.
- Revisit when: When groups grow from hundreds of devices to thousands and members come and go daily (move to MLS); when people have more devices (chapter 16); when history must move to a new device (chapter 42).
- Other answers: Pairwise (Signal's groups in 2014); no group encryption, one-on-one secret chats only (Telegram); Matrix's Megolm; Signal's sealed sender v2; MLS (Discord's calls, RCS).

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