深入理解 IM 系统

旁支 W4

群组端到端加密

一个 100 人的群,每人 3 台设备,端到端加密。一条消息要加密几次?有人退群,又要做多少事?

这一章是初稿:作者还在逐章校对,内容和数字可能会改。

第 6 章定下:群消息在会话里只存一份,成员各自来拉,这是读扩散读扩散read fan-out消息只在会话的时间线里存一份,每个人读的时候自己去取。写得少、读得多,适合大群。v1、v2 的消息都这样存(第 6、10 章);它要求会话由服务端建、设备去同步。在术语表里查看。这件事有个前提:服务器读得懂这条消息。

端到端加密端到端加密end-to-end encryption消息在发送的设备上加密,只有收件人的设备能解开,服务器只转交它读不懂的字节。钥匙在每台设备上,所以加密的单位是设备,不是人。在术语表里查看(end-to-end encryption,E2EE)把这个前提拿掉了:消息在发送的设备上加密,只有收件人的设备能解开,服务器只是转交一串它解不开的字节。钥匙在哪,就在哪加密。一个人的手机、电脑、平板各有各的钥匙(一台设备丢了,别的设备不受牵连),所以加密的单位是设备,不是人。

这一篇用一个群算账:100 个成员,每人 3 台设备(手机、电脑、平板;全书平均每人 1.5 台,这里取 3,让多设备看得清楚),一共 300 台。Ana 用手机发一句话,要送到另外 299 台:其他 99 人的 297 台,加上 Ana 自己的电脑和平板。

先说清楚:这一篇里没有东西会坏。 下面三种做法都有大产品在用,要看的是每种做法把代价放在哪:每条消息上、发第一条消息前,还是有人退群时。

先交代两个词。对称密钥:一把钥匙,加密和解密用同一把,又快又短(32 字节)。两两会话:两台设备之间先用双方的公钥(一对钥匙里可以公开给任何人的那一半:谁都能用它加密,只有握着配对私钥的设备解得开;私钥从不离开设备)商量出一把只有它俩知道的钥匙,以后每条消息都从它派生出一把新的。Signal 的协议就是这样做的,WhatsApp 也用它。建这种会话要先从服务器取对方的公钥,第一次稍慢,之后每条消息只是几次哈希和一次对称加密。

1. 两两加密:一条消息 299 份

最直接的做法:Ana 的手机和每台设备各有一条两两会话,一条消息加密 299 次,每份都不一样。Signal 2014 年的群聊就是这样:发群消息时,给每个成员发一条两两加密的消息;服务器甚至不知道“群”这回事。WhatsApp 给单聊和自己的其他设备发消息也是这样,白皮书叫它 client-fanout:发给 N 台设备,就传 N 次,每次用那台设备的会话单独加密。

一条消息 200 字节,加密后带上钥匙编号、计数器、校验码和收件地址,按每份 300 字节算(取整的假设):

  • 上传:299 × 300 B = 89.7 KB。在 2 Mbit/s 的弱网上(第 8 章的假设)要 0.36 秒,而且每发一条都这样。
  • 服务器:299 份互不相同,只能一份一份存、一份一份发。第 6 章“只存一份”没了,回到了按设备的写扩散写扩散write fan-out发消息时给每个接收人的信箱各写一条,读的时候只看自己的信箱。写得多、读得快,适合人数不多的会话。第 6 章拿它做比较;第 10 章说明它和端上建会话连在一起:手机要从信箱里拼出会话。v1、v2 都没有用它。在术语表里查看:群里一天 1,000 条消息,就是 299,000 份、89.7 MB。

图片倒不贵。按 WhatsApp 白皮书的做法,附件用一把随机的钥匙加密一次,传一次;发给每台设备的只是一条小消息,里面是这把钥匙和附件的位置。一张 200 KB 的图,总共 200 KB + 299 × 300 B = 289.7 KB,而不是 299 × 200 KB = 59.8 MB。

两两加密的好处是简单:有人退群,下一条消息不再加密给他的 3 台设备就行,什么都不用重做。

2. 发送者密钥:每台设备一把钥匙

发送者密钥发送者密钥sender keys端到端加密的群里,每台设备生成一把自己的链钥匙,先经两两会话发给群里每台设备;以后每条消息只加密一次、上传一份。代价是有人退群时,每台设备都要换一把新的,再发一遍。在术语表里查看(sender key)把“加密 299 次”挪到了前面,只做一次。WhatsApp 的群聊就是这样,白皮书写了步骤:

  1. 一台设备第一次在群里发消息时,生成一个随机的 32 字节链钥匙和一对签名用的钥匙。
  2. 把链钥匙和签名公钥打成一条“发送者密钥”消息,用两两会话分别发给群里每台设备。
  3. 以后每条消息:从链钥匙派生一把消息钥匙,链钥匙往前走一步;用消息钥匙加密一次,再签名;只上传一份,由服务器发给全群。

“往前走一步”是一次单向的哈希:拿到今天的链钥匙,算得出以后的,算不出以前的。所以新人拿到钥匙,也解不开他来之前的消息。

签名是用私钥给消息盖的章,拿着公钥的人都能验证它出自谁。它是必要的:链钥匙群里人人都有,没有签名的话,任何成员都能冒充 Ana 发消息。

算账:

  • 每条消息:加密 1 次,上传 300 B。服务器手里的 299 份是同一串字节,又可以只存一份了,第 6 章的读扩散回来了。
  • 分钥匙:每台设备在发第一条消息前,要先发出 299 份钥匙(89.7 KB),就是一次两两加密的量。所以发两条消息时,两两加密是 598 份,发送者密钥是 299 + 2 = 301 份,从第二条起就划算。
  • 全群都说过话:300 台设备各分一次,300 × 299 = 89,700 份、26.9 MB,每台设备收 299 把钥匙(89.7 KB)。这笔账是懒的:只有说话的设备才分钥匙。只有 10 个人在 3 台设备上说话时,是 8,970 份、2.7 MB。

Signal 现在也用发送者密钥:Signal-Android 的发群消息代码按收件人分两拨,支持发送者密钥的走发送者密钥,其余的仍然两两发(能用发送者密钥的不到 2 个时,全部两两发)。加密本身在 libsignal 里。

3. 有人退群:每个人都要换钥匙

Ben 退群了,他的 3 台设备离开,剩 297 台。

Ben 手里有群里每台设备的链钥匙,而且能一直往前算。只要别人还用旧钥匙,他就能继续解开群消息(加密后的字节,即密文,他照样拿得到:服务器、网络上都有)。所以 WhatsApp 的规矩是:有成员离开,所有人清掉发送者密钥,从头再来。Signal-Android 也一样,群里有人被移出,就扔掉自己的钥匙,下次发消息时重新生成;钥匙用得太久也会换。

算账:

  • 每台留下的设备,下次说话前要发 296 份新钥匙(88.8 KB)。
  • 297 台都再说话:297 × 296 = 87,912 份、26.4 MB;每台设备要收最多 296 把新钥匙。
  • 这又是一笔懒账:只有 10 个人在 3 台设备上再说话,是 8,880 份、2.7 MB。

账是平方的:设备数翻一倍,换一轮钥匙的总量翻四倍。1,500 台设备(500 人)的群,换一轮是 224 万份;3,000 台是 898 万份。MLS 的标准 RFC 9420 开头就讲了这一点:用发送者密钥,要在钥匙泄露后恢复安全,换钥匙的消息数随群大小的平方增长。

进群便宜得多:新人的 3 台设备进来,现有设备把自己当前的钥匙发给它们,最多 300 × 3 = 900 份,不用换钥匙。上面说过,新人拿到的是今天的链钥匙,以前的消息解不开。

4. MLS:一棵树

MLS(Messaging Layer Security,RFC 9420,2023 年 7 月)换了一个思路:全群在一段时间里共用一个群秘密,每条消息的钥匙都从它派生;这一段时间叫一个 epoch(纪元),成员一变,就换一个新的群秘密,进入下一个 epoch。难的是换的时候怎么把新秘密只告诉留下的人。

办法是一棵二叉树。每台设备是一片叶子;树总是“满”的(RFC 9420 的说法:叶子位数是 2 的幂),300 台设备放在 512 个叶子位上(512 = 2⁹),叶子往上 9 层。每个上层节点可以有一对钥匙,它下面的叶子都知道这对钥匙的私钥;根节点派生出群秘密。所以“加密给一个节点”,就是用它的公钥加密一次,它下面的每台设备都解得开。

换钥匙时具体发生什么

改动群的那条消息叫 Commit(提交):谁进、谁出、换了哪些钥匙都写在里面,全群收到后一起进入下一个 epoch。发 Commit 的设备从自己的叶子往根走,路上每个节点都换成新的钥匙对。每个节点下面有两棵子树:自己这一侧知道新钥匙,旁边那一棵还不知道,得告诉它。如果旁边那棵子树顶上的节点有钥匙,用它加密一次就够了,子树里所有叶子都解得开。每层一次,往上 9 层就是 9 次。RFC 第 4 节的说法:加密给除一人以外的全组,只要 log(N) 次加密,而不是逐个加密的 N − 1 次。

节点也可能是空的:有人离开,他的叶子和他往上的节点都清空。空节点没有钥匙,就只能拆开,加密给它下面每个有钥匙的节点。所以空节点越少越便宜,越多越贵。

demo.py 按 RFC 附录 C 的数组树模拟了 300 台设备,数一条 Commit 要加密几次(每次 82 字节,路上每个节点再带一个 33 字节的公钥):

情形 加密几次 Commit 大小(不算签名等)
没有空节点的树,一台设备只是换自己的钥匙 9
没有空节点的树,移出 Ben 的 3 台设备 14 9 × 33 + 14 × 82 B = 1.4 KB
刚建的群(只有建群那台设备的路径有钥匙),移出 Ben 233 19.4 KB

移出 Ben 比只换自己的钥匙多 5 次:他的 3 片叶子(demo.py 里是 100–102 号)和它们往上直到根的节点都清空了。200 号往上走到第 8 步,旁边那棵子树装着 0–127 号设备,它的顶点正在 Ben 往上的路上,没有钥匙了;只好拆开,加密给下面 6 个还有钥匙的节点(0–63、64–95、96–99、103、104–111、112–127 号),一次变成六次。在没有空节点的树里,移出 Ben 只要留下的一台设备(demo.py 里是 200 号)发一条 1.4 KB 的 Commit,服务器发给另外 296 台,一共 427.7 KB;发送者密钥要 26.4 MB。每台设备只收一条,而不是 296 把钥匙。

刚建的群就差多了:除了建群那台设备的路径,上层节点全是空的,几乎要一台台加密,233 次。成员各自发过 Commit 以后,空节点才慢慢填上。

群再大一些(每人 3 台设备,移出一个人):

成员 设备 两两:每条消息 发送者密钥:换一轮(都再说话) MLS:没有空节点 MLS:刚建的群
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

平常发消息,MLS 和发送者密钥一样:每条加密一次,服务器发给全群同一串字节。

5. 代价

  • 发送者密钥:退群贵,钥匙被偷了也难补救。 换一轮是平方的。另一面是:一把发送者密钥要是从某台设备上被偷走,在下次换钥匙之前,偷到的人能一直往前算、一直解开这个人的消息。RFC 9420 开头也指出了这一点。所以除了退群,还要定期换(Signal-Android 按钥匙的年龄换,Matrix 推荐每周或每 100 条换),每换一次,又是 299 份。
  • MLS:改动必须排成一个顺序。 每条 Commit 都基于某个 epoch;两个人同时基于同一个 epoch 发 Commit,只能有一个生效。RFC 第 14 节要求应用必须有办法处理冲突的 Commit。这一点正好对上主线:第 5 章给每个会话的消息排了序号(seq)序号(seq)会话里每条消息的编号,由负责这个会话的消息服务连续分配。它决定会话里的顺序,也让客户端发现缺了哪一条;手机回来时,也按它判断哪个会话落后了。在术语表里查看,第 12 章让入群、退群也占一个 seq。服务器可以像排消息一样给 Commit 排序:同一个 epoch 先到的那条生效,后到的基于新 epoch 重做。服务器看不懂内容,但排序还是它的事。
  • MLS:更复杂。 树、epoch、新成员的 Welcome(欢迎消息,把当前的群秘密交给新人)、各种提案(Proposal:先提出“加谁、移谁”,再由一条 Commit 一起生效),客户端要实现的东西比发送者密钥多得多,出了错也更难查。
  • 三种都一样:新设备看不到旧消息。 服务器上只有新设备解不开的密文,第 16 章“多端同步”里新设备从服务器拉历史的路走不通了。历史怎么在自己的设备之间搬,是第 42 章“隐私通讯”的事。

6. 其他答案

  • Matrix 的加密群用 Megolm,和发送者密钥是一个思路:每个人用自己的出站会话(outbound session,相当于自己的发送者密钥)加密,会话的钥匙通过两两会话分给其他人。规范要求有人离开就换会话,此外推荐每周、或每 100 条消息换一次。
  • Signal 的 sealed sender v2:为了不让服务器知道是谁发的,一条消息在 libsignal 里只加密一份正文,再给每个收件人附 48 字节(32 字节加密过的随机数和 16 字节校验),外加收件人地址,服务器按人拆开转发。
  • Discord 的 DAVE(2024 年 9 月)用 MLS 给语音和视频通话交换群钥匙;文字消息不做端到端加密。
  • Telegram 干脆不给群做端到端加密:FAQ 说群聊和普通私聊是“云聊天”,只在客户端和服务器之间加密;端到端加密的“秘密聊天”只能一对一,而且只在建立它的两台设备上,换了设备、退出登录就没了。这样既没有群的账,也没有多设备的账,代价是这两样功能都不加密。
  • RCS:GSMA 的 Universal Profile 3.0(2025 年 3 月)给 RCS 消息加上端到端加密,基于 MLS。

7. 这一篇的决定

加密的账算完了。主线回到第 11 章“会话同步”;整个隐私通讯产品(服务器尽量少存、历史在设备间搬)在第 42 章。

评论

评论存在 GitHub Discussions,需要 GitHub 账号。