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