构建更高效的端到端加密群聊

端到端加密群聊的必要性与挑战

端到端加密消息协议确保只有会话参与者（而非中间服务器、路由器或中继系统）能够读写消息。当会话参与人数达到三人或以上时，端到端加密群聊协议需为所有参与者提供同等保障。

解决端到端加密群聊问题具有必要性：无论是为了限制责任、提供可验证的客户端安全性，还是消除单点故障，群聊服务都有充分理由采用端到端加密协议。但这也是个难题——现有解决方案（如Signal、WhatsApp和iMessage）存在固有的扩展性问题，使得支持数百人以上的群聊变得不可行。

消息层安全（MLS）协议旨在提高端到端加密群聊的效率，同时提供前向保密和入侵后安全等安全保证。

molasses：MLS的Rust实现

为此，我开发了molasses——一个基于Rust的MLS实现，其设计注重安全性、易用性和防误用性。

molasses对MLS规范的改进

molasses的主要贡献在于通过单元测试和互操作性测试发现了规范和其他实现中的错误。该实现基于MLS第六草案，但未完全实现——因为规范中存在一个错误导致无法向任何群组添加成员，这破坏了所有创建非平凡群组的单元测试。

此类错误仅通过阅读规范难以发现，需要一定程度的自动化挖掘。一旦发现，必要的修订往往很明显，并会迅速纳入后续草案。通过molasses迭代这个发现/修补过程，使我能够全面测试规范并帮助使其更加清晰。

加密群聊的构建原理

本节将推导MLS的设计原理（提示：出于效率考虑），并与其他解决方案进行比较（提示：它更优秀）。

首先，MLS比大多数聊天应用工作在更底层。它是构建应用的基础协议。例如，MLS不管理群组权限（如谁可以添加人员到聊天中）——这将由使用MLS的应用程序处理。因此，在分析协议时，我们可以完全忽略形式化规则系统等问题，只关注消息发送和成员移除。

密码学原语

以下部分使用数字签名、Diffie-Hellman密钥交换、（非）对称加密和密钥派生函数等密码学原语。如果读者在这些领域准备不足，快速浏览《Serious Cryptography》中关于ECIES和认证Diffie-Hellman的部分应该足够。

问题场景

Wilna正在为熟人Vince策划退休派对。后勤工作十分棘手，因此她邀请朋友Xavier、Yolanda和Zayne帮忙策划。他们想在Slack上创建群聊以保持同步，但想起Vince是Slack的基础设施经理——他可以查看世界上任何Slack服务器上的所有消息。这是个问题，因为他们想给Vince一个惊喜的长假。

Vince的职位带来了更多问题：他恰好管理镇上的所有服务器。即使Wilna购买自己的服务器来协调群聊，Vince也会被指派管理它，这意味着他可以读取服务器存储的所有内容。

Wilna需要的是集中式端到端加密群聊，即每个成员都可以广播消息并读取所有传入消息，但协调这些消息的单个服务器无法读取任何内容。

为清晰起见，我们将区分应用消息（携带群组成员想对组内其他人说的文本内容）和辅助消息（在MLS中称为"握手消息"），成员使用后者管理群组成员身份和密码秘密。由于这一切都通过一个服务器协调，成员可以依赖服务器将消息广播给组内其他成员。

解决方案一： pairwise通道

假设Wilna、Xavier、Yolanda和Zayne都知道彼此的数字签名公钥。这意味着每对人可以通过一些辅助消息进行认证的Diffie-Hellman密钥交换，并派生称为对密钥的共享对称密钥。此过程产生六个独立的成对通道。

如果Wilna想向群组发送应用消息m，她必须分别加密三次（对每个组成员一次）并发送所有密文：

灰色箭头表示使用对称密钥加密的应用消息。

注意，Wilna没有利用服务器的广播能力，因为组中的每个成员只能解密使用自己的对密钥加密的消息。推广来说，如果组大小为N，发送应用消息需要成员加密并发送N-1次。粗略来说，这就是iMessage进行群聊的方式。

解决方案二：发送者密钥

不为组中每个用户设置密钥，而是给每个用户一个发送者密钥用于加密应用消息。这大致是Signal、WhatsApp和Keybase的做法。

如果你是组成员，必须完成以下设置：

随机生成发送者密钥
对组中每个用户，使用与该用户共享的对密钥加密你的发送者密钥
将加密的发送者密钥副本作为辅助消息发送给每个用户

设置完成后（在大小为N的组中，每个用户需要N-1次加密，总共Θ(N²)条辅助消息），我们终于看到了一些高效行为。要发送应用消息m，Wilna：

使用她的发送者密钥精确加密m一次
将密文广播到组中

灰色箭头表示使用对称密钥加密的应用消息。

虽然这里有三个箭头，但它们都是相同的密文，因此应用消息只需要加密和广播一次。这样，在设置阶段之后，每个传出应用消息只需要一次加密。那么问题解决了吗？当然没有。

关于移除的问题

这里的误区是设置阶段只运行一次。实际上，每次修改组时它都会运行。假设在策划这个"退休派对"的过程中，组发现Zayne一直在向Vince泄露细节。自然，他们踢出了Zayne。

现在Zayne仍然知道所有发送者密钥，因此如果他与Vince交谈并获得他离开后群组对话的加密记录，他仍然能够解密。这是不允许的，因为Zayne已经叛变。

为防止这种情况，组中每个剩余用户必须创建新的发送者密钥，并通过他们的成对通道与其他人共享。同样，这是Θ(N²)条总辅助消息，可能很多。因此，如果我们想要容忍大量组修改，就需要找到一种方法减少设置阶段发送的辅助消息数量，同时仍能使用发送者密钥进行应用消息。

计算机科学中的一个众所周知的秘密是：当成对和列表的简单解决方案不起作用时，下一个逻辑步骤是：

解决方案三：树结构

我们希望拥有发送者密钥（因为它们使应用消息高效）。我们还希望能够向组子集传输新的发送者密钥，而无需使用太多辅助消息。

这里的重要见解是：当我们移除成员时，不应该像前一个解决方案那样需要单独向每个剩余成员发送新的密钥信息。毕竟，我们只需要将这个消息发送给整个组减去一个人。那么为什么不使用覆盖组大子集的公钥，并用它们发送辅助消息呢？这正是MLS棘轮树（又名TreeKEM）提供给我们的。

MLS棘轮树是一种二叉树，其叶子对应组成员，非叶子节点（称为中间节点）携带Diffie-Hellman公钥和私钥。中间节点不代表人、计算机或网络位置；它们只是促进辅助消息发送的数据片段。我们还允许节点为空白，意味着它们没有关联的密钥对。有关联密钥对的节点被称为已填充。

组中每个成员保留棘轮树的副本（不包括私钥）。私钥的知识遵循棘轮树属性：

棘轮树属性 如果成员M是中间节点N的后代，那么M知道N的私钥。

深呼吸

发送者密钥通过密钥派生函数（KDF）从根节点的私钥派生，而私钥通过KDF从其最近更新的子节点的私钥派生。在移除用户时，新的私钥被分发给共路径节点的解析，即更新节点的兄弟节点的子树的最大非空白节点。

小型示例

我们从这样一个组开始：

Zayne想退出，所以Yolanda移除了他。为了移除他，Yolanda首先将Zayne及其所有祖先置空：

带红色斜线的框表示空白节点。

Yolanda需要向新组提供新的密钥信息，以便新的发送者密钥可以从新根的私钥派生。为此，她生成新的个人密钥对pubY’和privY’，并通过迭代对私钥应用KDF并计算其对应的公钥（这称为"棘轮"，因此得名"棘轮树"）来派生所有祖先的密钥对。

绿色圆圈表示最近更新的节点。

但Yolanda还没有完成。Wilna和Xavier需要以某种方式被告知这些新密钥。分享这些信息是Yolanda的工作。具体来说：

每个成员都需要获取所有更新节点（即Yolanda自己的公钥及其所有祖先的公钥）的副本。这很重要。公钥是共享组状态的一部分，共享组状态是MLS协议中许多值的派生方式。
每个成员都需要获取其最近修改祖先的私钥副本。这是为了保持棘轮树属性。

记住最终目标仍然是派生发送者密钥，这意味着Wilna和Xavier需要被告知根私钥privY’‘‘的值。这将是上述第二项的结果。

由于每个人都需要公钥且公钥不是秘密，Yolanda可以将它们作为未加密的辅助消息广播。但私钥更敏感。她需要只为需要它们的成员加密它们。这就是我们使用棘轮树属性的地方。

如果她希望Wilna和Xavier能够读取包含privY’‘‘的辅助消息，她只需要使用pubWX加密消息，因为Wilna和Xavier是WX中间节点的后代，因此将能够解密使用pubWX加密的任何内容。这描述了辅助消息如何发送给组中其他成员：

上面的实心黑色箭头表示公钥加密的消息。虚线箭头表示纯文本消息。箭头不表示谁在发送（因为都是Yolanda）。它们只是为了说明值在树中的来源以及它们 intended 给谁。

现在Wilna和Xavier将通过保存公钥和解密根私钥来更新他们对树的视图。这样，每个人都保持一致，棘轮树属性得以保留。最后，每个人重新派生他们的发送者密钥，移除完成：

注意Zayne的位置在移除后保持空白。这使成员免于重新排列自己和重新计算祖先密钥对的计算开销。MLS定义了两种防止被移除成员使树过度拥挤的方法：它允许在移除后从树的右端移除空白节点（在上面的示例中不适用），并且允许新成员添加到先前移除成员的位置。因此，如果上面的"派对策划者"想要替换Zayne，他们可以在不使树变大的情况下这样做。

渐进行为分析

我们通过发送者密钥获得了高效的应用消息，并且我们希望说通过TreeKEM获得了高效的辅助消息，这样我们就可以收工了。这是真的吗？绝对不是，至少不完全是这样。

填充树中的移除

Zayne示例实际上是填充树中移除的最坏情况行为（就辅助消息数量而言）。如果组中有N个成员，最多有log(N)-1个不需要处理空白节点的加密辅助消息，还有log(N)-1个需要处理空白节点的。另外，有log(N)个公钥要共享。

因此，为了完成过去计算机科学家的明智智慧：如果使用树，你会得到O(log(N))行为。这比我们在解决方案二中看到的二次辅助消息数量要好得多。同样的WhatsApp群现在只需要大约3log₂(10,000) ≈ 40条总辅助消息来建立一组新的发送者密钥（假设是填充树），而不是之前需要的N(N-1) ≈ 9900万条总辅助消息。

带空白树中的移除

这种对数行为非常棒，但我们只检查了从完整组开始然后移除一个人的非常具体情况。当从已经有