构建更高效的端到端加密群聊
端到端加密群聊的必要性与挑战
端到端加密消息协议确保只有对话参与者（而非中间服务器、路由器或中继系统）能读写消息。端到端加密群聊协议则将这一保障扩展至三人及以上对话场景。
解决端到端加密群聊问题具有必要性：无论是为了限制责任、提供可验证的客户端安全性，还是消除单点故障，群聊服务都有充分理由采用此类协议。但与此同时，这也是一个难题。现有解决方案（如Signal、WhatsApp和iMessage）存在扩展性缺陷，导致无法支持数百人以上的群聊。消息层安全（MLS）协议旨在提高端到端加密群聊效率，同时提供前向安全性和后泄密安全性等保障。
为此，我开发了molasses——一个基于Rust的MLS实现，注重安全性、易用性和防误用设计。
Molasses对MLS规范的改进作用
Molasses的主要贡献是通过单元和互操作性测试发现规范及其他实现中的错误。它实现了MLS草案6的大部分内容（未完全实现的原因在于规范中存在错误：无法向任何群组添加成员，这破坏了所有创建非平凡群组的单元测试）。此类错误仅通过阅读规范难以发现，需要自动化挖掘。一旦发现，必要的修订往往显而易见，并会迅速纳入后续草案。
通过molasses迭代发现/修补过程，我有机会全面测试规范并帮助澄清细节。这个冬季实习项目（“winternship”）是一次宝贵经历，尤其作为首次IETF贡献者。
如何构建加密群聊
本节探讨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中称为“握手消息”，用于管理群组成员和密码秘密）。由于这一切通过一个服务器中介，成员可依赖服务器向群组广播消息。
明确了设置，有哪些方案可选？
方案一：配对通道
假设Wilna、Xavier、Yolanda和Zayne都彼此知道数字签名的公钥。这意味着每对人可通过一些辅助消息进行认证Diffie-Hellman密钥交换，并派生称为配对密钥的共享对称密钥。此过程产生六个独立的配对通道，如下图所示：
如果Wilna想向群组发送应用消息m，她必须加密三次（对每个成员一次）并发送所有密文：
灰色箭头表示在对称密钥下加密的应用消息。
注意，Wilna未利用服务器的广播能力，因为每个成员只能解密用自己配对密钥加密的消息。推广而言，对于大小为N的群组，发送应用消息需要成员加密并发送N-1次。粗略来说，这是iMessage处理群聊的方式。
很好，每人只需三次加密。这在手机上最多几毫秒。问题在哪？问题在于：如果WhatsApp群组有超过10,000名成员（比如我的阿姨们讨论谁要结婚），你希望她们每次发送内容时都执行9,999次加密吗？我希望，但她们可能不乐意。为满足阿姨们，我们需要更聪明的方案。
方案二：发送者密钥
不为每对用户设置密钥，而是给每个用户一个发送者密钥用于加密应用消息。这大致是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从其最近更新的子节点的私钥派生。移除用户时，新私钥被分发给共路径节点的解析，即更新节点的兄弟节点的子树的最大非空白节点。
仅这一段就花了约10分钟编写，所以我们直接看……
一个小例子
我们从这样一个群组开始：
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），仅说明值在树中的来源及目标对象。
现在Wilna和Xavier将通过保存公钥并解密密根私钥来更新他们的树视图。因此，每个人都在同一页面，棘轮树属性得以保留。最后，每个人重新派生发送者密钥，移除完成：
注意Zayne的位置在移除后保持空白。这节省了成员重新排列自身和重新计算祖先密钥对的计算开销。MLS定义了两种防止被移除成员过度拥挤树的方法：允许在移除后从树右端移除空白节点（上述示例不适用），并允许新成员添加到先前被移除成员的位置。因此，如果上述“派对策划者”想替换Zayne，他们可在不增大树的情况下完成。
此示例说明了更新密钥的较小细节，但未很好展示哪些节点秘密被发送到共路径节点解析中的其他节点。为给出概念，这里是……
一个更大的例子
假设Zayne想单飞，但仍渴望加入男孩乐队。克隆自己15次后，Zayne #1注意到其中一个克隆Zayne #11一直暗示要分离并独自开展个人事业。Zayne #1默许并将他从群组中移除。他看到了自己的创造。Zayne #1仰望星空。战争即将来临。
让我们看看Zayne #11被踢出时发送了哪些辅助消息。在此移除过程中，Zayne #1生成新秘密，将它们一直棘轮到树顶，并与适当子树共享：
绿色圆圈仍表示更新节点。实线箭头表示其尾部的私钥用其头部的公钥加密。
注意树右侧，由于无法加密到空白节点，根私钥需要用三个独立公钥加密。为清晰省略虚线箭头，但所有圆圈节点的公钥在此步骤中广播仍成立。
通过这个更大的例子，你可能开始看到每次树更新发送多少辅助消息的一些模式。让我们玩
你能看出渐进行为吗？
我们通过发送者密钥获得了高效的应用消息，并且想说通过TreeKEM获得了高效的辅助消息，从而可以收工。这是真的吗？绝对不，至少不完全。首先讨论上述示例，其中我们从一个所有节点已填充的树开始。
填充树中的移除
Zayne示例实际上是填充树中移除的最坏情况行为（就辅助消息数量而言）。如果群组中有N个成员，最多有log(N)-1条加密辅助消息不需要处理空白节点，另有log(N)-1条需要。此外，还有log(N)个公钥要共享。因此，完成过去计算机科学家的智慧，如果使用树，你会得到O(log(N))行为。这比方案#2中二次数量的辅助消息好得多。同样的WhatsApp群组现在只需约3log2(10,000) ≈ 40条总辅助消息来建立新发送者密钥集（假设填充树），而不是之前需要的N(N-1) ≈ 9900万条总辅助消息。
带空白树中的移除
这种对数行为非常棒，但我们只检查了从完整群组开始然后移除一个人的非常具体情况。从已有一些空白的群组中移除单个人时，效率如何？好消息是它仍然比Θ(N²)好。坏消息是最坏情况是……嗯，让我展示给你。
假设每个奇数编号的Zayne已被从群组中移除，除了Zayne #1。最后，Zayne #2给出致命一击，移除Zayne #1并恢复和平。更新如下：
移除一个人需要N-1条消息！如前所述，对于大N，这可能是禁止性的大量辅助消息。更糟的是，恶意群组成员可能策略性地移除人员直到树达到最坏状态，从而减慢群组中每个人的操作速度。
处理这种情况是一个未解决的问题，人们正在积极研究解决或至少缓解它。截至本文撰写时，尚无提出实质性改进最坏情况行为的解决方案。
结论与更多信息
以未解决的问题结束令人失望，但这是协议目前的现状。高效更新密钥是端到端群组消息传递的核心。TreeKEM方法及其边缘情况是MLS做出的最重要单一贡献之一。鉴于规范中至少还有一个未解决问题，你可能想知道
协议接近完成了吗？
不知道。MLS有许多未解决问题（本文撰写时为九个）并在不断调整。草案7刚于本月落地，它彻底改革了对称密钥计划。随着真实性、机密性、不可否认性等问题的修补，低效正被削减。
其他实现有哪些？
非官方参考实现mlspp用于创建测试向量，我们实现者都针对其测试。还有MLS*，Inria的一个项目，用F*实现和形式化建模协议。甚至还有另一个Rust实现melissa，正在Wire编写。
提醒我为什么你还要写另一个Rust实现？
实现越多越好。编写此实现有助于发现mlspp和规范本身的错误。
在mlspp中发现的错误包括缺少重要字段（缺少协议版本和缺少WelcomeInfo哈希，这强制执行排序）、不正确的树寻址（使用叶子索引而非节点索引，反之亦然）以及错误生成的测试向量。在规范中发现的错误包括歧义（如何从棘轮树中修剪移除的节点？）、逻辑不可能（如果WelcomeInfo不包括当前解密密钥，如何向群组添加用户？）和义务遗漏（用户是否应该验证广播公钥与其派生公钥？）。
好的，但为什么用Rust？
掰指关节
我认为拥有一个具有清晰API（得益于molasses的精心设计和Rust的强类型）、内存安全语义（得益于Rust借用检查器）、全面文档（得益于cargo doc和molasses当前43%的注释代码比）和良好性能（得益于零成本抽象）的MLS实现会很好。当然，这些功能无法弥补molasses不像MLS*那样经过形式化验证且可能永远不会的事实，但嘿，没人抱怨棉花不如凯夫拉防弹，因为它们用途不同。
我如何帮忙？
我还不建议提交molasses的问题。规范变动太快，每次都必须相应重新设计库。如果你想贡献，MLS IETF页面有一个邮件列表，你可在其中阅读和参与讨论。组织者有帮助和耐心，我非常感激他们。如果你想编写自己的实现，请参阅实现者的Github仓库以获取组织信息和测试向量。
如果你有兴趣阅读更多关于协议的内容并查看其他未解决问题，你应该阅读规范。
“我想要你的专业知识”
那要收费了。我们提供端到端协议设计、工程和审计的咨询服务。如果有兴趣，请通过我们的联系页面给我们留言。
感谢阅读！如有问题或更正，请随时发送电子邮件至michael.rosenberg@trailofbits.com。
脚注
- 完全后泄密安全性，即非确定性地派生所有新共享数据以使排除方无法参与的问题，在此方案中实际上不易实现。正在进行的研