更优加密群聊 - Trail of Bits博客
Trail of Bits博客
更优加密群聊
Trail of Bits
2019年8月6日
密码学, 实习项目
广义而言，端到端加密消息协议确保只有会话参与者（而非中间服务器、路由器或中继系统）能够读写消息。端到端加密群组消息协议则确保三人及以上会话中的所有参与者均满足此条件。
端到端加密群组消息是一个必须解决的问题。无论是为了限制责任、提供可验证的客户端安全性，还是消除单点故障，群组消息托管方都有充分理由采用端到端加密协议。
端到端加密群组消息也是一个难题。现有解决方案如Signal、WhatsApp和iMessage存在固有的扩展性问题（后续将详细讨论），导致无法支持超过几百人的群聊。消息层安全（MLS）协议旨在提高端到端加密群聊的效率，同时提供前向保密和入侵后安全等安全保证¹。
为此，我开发了molasses——一个基于Rust的MLS实现，注重安全性、易用性和防误用设计。
Molasses助力完善MLS规范
molasses的主要贡献是通过单元和互操作性测试发现规范及其他实现中的错误。molasses实现了MLS第六版草案的大部分内容。为何未完全实现？因为规范中存在一个错误，导致无法向任何群组添加成员。这破坏了所有创建非平凡群组的单元测试。此类错误仅通过阅读规范难以发现，需要一定程度的自动化挖掘。一旦发现，必要的修订往往显而易见，并会迅速纳入后续草案。
通过molasses迭代发现/修补过程，我有机会全面测试规范并帮助澄清细节。这个冬季实习项目是一次宝贵的经历，尤其作为首次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： pairwise通道
假设Wilna、Xavier、Yolanda和Zayne都知晓彼此的数字签名公钥。这意味着每对人可通过一些辅助消息进行认证Diffie-Hellman密钥交换，并派生称为对密钥的共享对称密钥。此过程产生六个独立的成对通道，如下所示：
[图示：四人之间的成对连接图]
若Wilna想向群组发送应用消息m，她必须加密三次（对每个成员一次）并发送所有密文：
[图示：Wilna向其他三人分别发送加密消息]
灰色箭头表示使用对称密钥加密的应用消息。
注意，Wilna未利用服务器的广播能力，因为群组中每个成员只能解密使用自身对密钥加密的消息。推广而言，若群组大小为N，发送应用消息需要成员加密并发送N-1次。粗略来说，iMessage的群聊即如此实现²。
很好，每人仅需三次加密。这在手机上最多可能耗时几毫秒。问题何在？问题在于：当WhatsApp群组有超过10,000名成员（我姨妈们讨论谁将结婚）时呢？你希望她们每次发送内容时执行9,999次加密吗？我希望，但她们可能不乐意。为照顾我姨妈们，我们需要更聪明的方法。
解决方案#2：发送者密钥
不为群组中每对用户设置密钥，而是给每个用户一个发送者密钥用于加密应用消息。这大致是Signal²、WhatsApp²和Keybase的做法。若你是群组成员，必须完成以下设置：
- 随机生成你的发送者密钥
- 对群组中每个用户，使用你与该用户共享的对密钥加密你的发送者密钥
- 作为辅助消息，向每个用户发送其加密版本的发送者密钥
设置完成后（在大小为N的群组中，每个用户需要N-1次加密，即总计Θ(N²)条辅助消息），我们终于看到一些高效行为。为发送应用消息m，Wilna：
- 使用她的发送者密钥精确加密
m一次 - 向群组广播密文
[图示：Wilna广播单一加密消息至所有成员]
灰色箭头表示使用对称密钥加密的应用消息。
尽管此处有三个箭头，但它们都是相同密文，因此应用消息仅需加密和广播一次。于是，在设置阶段后，每个传出应用消息仅需一次加密。这样就完事了，对吗？错误，当然错误。因为……
移除怎么办？
此处的谬误在于设置阶段仅运行一次。实际上，它每次群组修改时都会运行。假设在策划此“退休派对”过程中，群组发现Zayne一直向Vince泄露细节。自然，他们踢出Zayne。现在Zayne仍知晓所有发送者密钥，因此若他与Vince交谈并获取离开后群组对话的加密记录，他仍能解密。这是禁忌，因为Zayne已叛变。为防止此事发生，群组中每个剩余用户必须创建新发送者密钥，并通过其成对通道与其他人共享。再次，这是Θ(N²)条总辅助消息，可能很多。因此，若想容忍大量群组修改³，我们必须找到减少设置阶段发送的辅助消息数量的方法，同时仍能使用发送者密钥处理应用消息。计算机科学中一个众所周知的秘密是：当成对和列表的朴素解决方案无效时，下一个逻辑步骤是：
解决方案#3：树
我们希望拥有发送者密钥（因为它们使应用消息高效）。我们还希望能够向群组子集传输新发送者密钥而无需太多辅助消息。此处的关键洞察是：移除成员时，我们不应像先前解决方案那样需要单独向每个剩余成员发送新密钥信息。毕竟，我们只需向整个群组减去一人发送。因此，为何不拥有覆盖群组大子集的公钥，并用它们发送辅助消息？这正是MLS ratchet树（又名TreeKEM）提供给我们的。
MLS ratchet树是二叉树⁴，其中叶子对应群组成员，非叶节点（称为中间节点）携带Diffie-Hellman公钥和私钥。中间节点不代表人员、计算机或网络位置；它们只是促进辅助消息发送的数据片段。我们还允许节点为空白，意味着它们没有关联的密钥对。有关联密钥对的节点称为已填充。群组中每个成员保留ratchet树的副本（不含私钥）。私钥的知晓遵循ratchet树属性：
Ratchet树属性 若成员M是中间节点N的后代，则M知晓N的私钥。
深呼吸
发送者密钥通过密钥派生函数（KDF）从根节点的私钥派生，而私钥通过KDF从其最近更新的子节点的私钥派生⁵。移除用户时，新私钥被分发给copath节点的解析，即更新节点的兄弟节点的子树的最大非空白节点。
仅此段落的撰写就耗时约10分钟，因此让我们直接看……
一个小例子
我们从如下群组开始：
[图示：包含Wilna、Xavier、Yolanda、Zayne的树]
Zayne想退出，因此Yolanda移除他⁶。为移除他，Yolanda将首先空白化Zayne及其所有祖先：
[图示：Zayne及其祖先被标记为空白节点]
带红色斜线的框表示空白节点。
Yolanda需要向新群组提供新密钥信息，以便新发送者密钥可从新根的私钥派生。为此，她生成新个人密钥对pubY’和privY’，并通过迭代应用KDF到私钥并计算其对应公钥（称为“ratcheting”，故名“ratchet tree”）派生所有祖先的密钥对。
[图示：Yolanda及其祖先节点更新为新密钥]
绿色圆圈指示最近更新的节点。
但Yolanda未完成。Wilna和Xavier需要以某种方式被告知这些新密钥。Yolanda的职责是共享此信息。具体而言：
- 每个成员需要获取所有更新节点（即Yolanda自身的公钥及其所有祖先的公钥）的副本。这很重要。公钥是共享群组状态的一部分，而共享群组状态是MLS协议中许多值的派生方式。
- 每个成员需要获取其最近修改祖先的私钥副本。这是为了保持ratchet树属性。
记住最终目标仍是派生发送者密钥，这意味着Wilna和Xavier需要被告知根私钥privY”’的值。这将是上述第二项的结果。
由于每个人都需要公钥且公钥非秘密，Yolanda可仅以未加密辅助消息广播它们。但私钥更敏感。她需要仅加密给需要它们的成员。此处我们使用ratchet树属性。若她希望Wilna和Xavier能读取包含privY”’的辅助消息，她只需使用pubWX加密消息，因为Wilna和Xavier是WX中间节点的后代，因此将能解密使用pubWX加密的任何内容⁷。这描述了辅助消息如何发送至群组其他成员：
[图示：Yolanda向Wilna和Xavier加密发送私钥，广播公钥]
实心黑箭头表示公钥加密消息。虚线箭头表示纯文本消息。箭头不指示谁在发送（因为全是Yolanda）。它们仅旨在说明值在树中的来源及目标对象。
现在Wilna和Xavier将通过保存公钥和解密根私钥来更新其树视图。于是，每个人同步且ratchet树属性得以保持。最后，每个人重新派生其发送者密钥，移除完成：
[图示：移除后树状态，Zayne位置保持空白]
注意Zayne的位置在移除后保持空白。这使成员免于重新排列自身和重新计算祖先密钥对的计算开销。MLS定义了两种防止被移除成员过度拥挤树的方法：允许在移除后从树右端移除空白节点（上述示例中不适用），并允许新成员添加到先前被移除成员的位置。因此，若上述“派对策划者”想替换Zayne，他们可在不增大树的情况下完成。
此示例说明了更新密钥的较小细节，但未特别好地说明哪些节点秘密被发送至copath节点解析中的哪些其他节点。为给出概念，这里是……
一个更大的例子
假设Zayne想单飞，但仍渴望加入男孩乐队。克隆自己15次后，Zayne #1注意到其中一个克隆人Zayne #11一直暗示要分离并开展个人独唱生涯。Zayne #1默许并将他从群组中移除。他看到了自己的创造物。Zayne #1仰望星空。战争将至。
让我们看看当Zayne #11被踢出时发送了哪些辅助消息。在此移除过程中，Zayne #1生成新秘密，将它们一直ratchet至树顶，并与适当子树共享：
[图示：Zayne #1更新树并加密共享私钥]
绿色圆圈仍表示更新节点。实心箭头表示其尾部的私钥使用其头部的公钥加密。
注意树右侧，由于无法加密至空白节点，根私钥需要使用三个独立公钥加密。为清晰省略虚线箭头，但所有圆圈节点的公钥在此步骤中被广播仍成立。
通过此更大示例，你可能开始看到每次树更新发送的辅助消息数量的某种模式。让我们玩
你能目测渐近行为吗？
我们通过发送者密钥获得了高效应用消息，并且我们希望说通过TreeKEM获得了高效辅助消息，从而可以收工。这是真的吗？绝对不，至少不完全。让我们首先讨论上述示例，其中我们从一个所有节点已填充的树开始。
已填充树中的移除
Zayne示例在已填充树中实际上是辅助消息数量方面的最坏情况移除行为（你应自证：若Zayne #1移除Zayne #6会发生什么？）。若群组中有N个成员，最多有log(N)-1条加密辅助消息无需处理空白节点，另有log(N)-1条需要。此外，有log(N)个公钥需共享。因此，完成过去计算机科学家的明智智慧：若使用树，你获得O(log(N))行为。这远优于我们在解决方案#2中看到的二次方数量的辅助消息。相同的WhatsApp唠叨姨妈群现在仅需约3log₂(10,000) ≈ 40条总辅助消息即可建立新发送者密钥集（假设已填充树），而非先前所需的N(N-1) ≈ 9900万条总辅助消息。
含空白树中的移除
此对数行为非常棒，但我们仅检查了从完整群组开始然后移除一人的非常特定情况。当从已有一些空白的群组中移除单人时，其效率如何？好消息是它仍优于Θ(N²)。坏消息是最坏情况是……嗯，让我展示给你。
假设每个奇数编号Zayne已被从群组中移除，除了Zayne #1。最后，Zayne #2给予最后一击，移除Zayne #1并恢复和平。以下是更新看起来的样子：
[图示：最坏情况移除，需要N-1条消息]
这是移除单人所需的N-1条消息！如前所述，对于大N，这可能是禁止性的大量辅助消息。更糟的是，恶意群组成员可能策略性地移除人员直至树达到最坏状态，从而减慢群组中每个人的群组操作。
处理此情况是一个开放问题，人们正积极工作以解决或至少缓解它。截至撰写时，尚无提议的解决方案能实质改进最坏情况行为。
结论与更多信息
以开放问题结束令人失望，但这是协议当前的状况。高效更新密钥是端到端群组消息的核心。TreeKEM方法及其边界情况是MLS做出的最重要单一贡献之一。鉴于规范中至少仍有一个开放问题，你可能想知道
协议离完成有多近？
毫无头绪。MLS有许多开放问题（截至撰写时九个）并在不断调整。第七版草案本月刚落地，它彻底改革了对称密钥计划。随着真实性、机密性、可否认性等问题被修补，低效正被削减。
其他实现有哪些？
非官方参考实现mlspp用于创建测试向量，我们实现者都针对其测试。还有MLS*，Inria的一个项目，在F*中实现并形式化建模协议。甚至还有另一个Rust实现melissa，正在Wire编写。
提醒我为何你还要写另一个Rust实现？
实现越多越好。编写此实现有助于发现mlspp和规范本身的错误。
在mlspp中发现的错误包括缺少重要字段（缺少协议版本和缺少WelcomeInfo哈希，后者强制执行排序）、不正确的树寻址（使用叶索引而非节点索引，反之亦然）以及错误生成的测试向量。我们在规范中发现的错误包括歧义（如何从ratchet树中修剪移除节点？）、逻辑不可能（若WelcomeInfo不包括当前解密密钥，如何向群组添加用户？）和义务遗漏（用户SHOULD⁸验证广播公钥与其派生公钥吗？）。
很好，但为何用Rust？
掰指关节
我认为拥有一个具有清晰API（得益于molasses的精心设计和Rust的强类型）、内存安全语义（得益于Rust借用检查器）、全面文档（得益于cargo doc和molasses当前43%的注释代码比）和良好性能（得益于零成本抽象）的MLS实现会很好。当然，这些特性都无法弥补molasses不像MLS*那样经过形式化验证且可能永远不会的事实，但嘿，没人抱怨棉花不如凯夫拉防弹，因为它们用途不同。
我如何帮助？
我尚不建议向molasses提交问题。规范变动太快，库每次都必须相应重新设计。若你想贡献，MLS IETF页面有一个邮件列表，你可在其中阅读并参与讨论。组织者乐于助人且耐心，我无比感激他们。若你想编写自己的实现，请参阅实现者的Github仓库以获取组织信息和测试向量。
若你有兴趣阅读更多关于协议的内容并查看其他开放问题，你应该阅读规范⁹。
“我想要你的专业知识”
那将花费你。我们提供端到端协议设计、工程和审计的咨询服务。若有兴趣，请通过我们的联系页面致信。
感谢阅读！如有问题或更正，请随时发送电子邮件至michael.rosenberg@trailofbits.com。
脚注
- 完全入侵后安全，即非确定性派生所有新共享数据以使排除方无法参与的问题，在此方案中实际上不易实现。关于表征一定数量群组更新后MLS的入侵后安全程度，正在进行研究。
- 来源。这是一篇杰出论文，为本文提供了大量背景。说真的，若你想更好理解此主题，你应该阅读MLS规范和此论文并比较两者，因为它们存在相当微妙但显著的差异。例如，论文中使用的ART方案不允许中间节点空白，这影响了发送给离线成员的消息的机密性。
- 本文中的“移除”问题是（较弱形式的）入侵后安全的占位符。此处“群组修改”包括更新密钥材料而不更改群组成员