cover_image

为什么Signal的后量子改造是一项了不起的工程成就

Kurt Pan XPTY
2025年10月14日 14:48

新设计为后量子就绪树立了高标准。

原文：https://arstechnica.com/security/2025/10/why-signals-post-quantum-makeover-is-an-amazing-engineering-achievement/

作者：Dan Goodin

译者：Kurt Pan

保护通信免受犯罪和国家级监控的加密技术正面临威胁。随着私营企业和政府越来越接近构建有用的量子计算机,保护比特币钱包、加密网页访问和其他敏感秘密的算法将变得毫无用处。没有人怀疑这一天会到来,但正如现在密码学圈子里流行的笑话所说,专家们在过去30年里一直预测这场密码学末日将在未来15到30年内到来。

这种不确定性造成了某种生存困境:网络架构师是否应该现在就花费数十亿美元摆脱易受量子攻击的算法,还是应该优先将有限的安全预算用于对抗更紧迫的威胁,如勒索软件和间谍攻击?考虑到成本和没有明确的截止日期,难怪在Cloudflare网络内建立的TLS连接中只有不到一半支持抗量子TLS连接,而财富500强网络中只有18%支持。几乎可以肯定的是,在不太著名的协议中支持量子就绪加密的组织还要少得多。

密码朋克的胜利

行业普遍懈怠的一个例外是设计Signal Protocol的工程团队,这是一个开源引擎,为多个私密聊天应用程序提供世界上最强大、最有韧性的端到端加密形式,最著名的是Signal Messenger。11天前,开发该协议的非营利实体Signal Messenger LLC发布了一篇5900字的文章,描述了其最新更新,使Signal在实现完全抗量子方面迈出了重要一步。

  • https://signal.org/blog/spqr/

使Signal Protocol量子安全所需的复杂性和问题解决能力与现代工程中的任何挑战一样艰巨。原始的Signal Protocol已经类似于精密瑞士钟表的内部,有无数的齿轮、轮子、弹簧、指针和其他部件都以复杂的方式相互操作。在不那么熟练的手中,摆弄像Signal协议这样复杂的工具可能会导致短路或意外后果,损害性能,破坏原本完美运行的手表。然而,这次最新的后量子升级(第一次是在2023年)不啻为一次重大胜利。

  • https://arstechnica.com/security/2023/09/signal-preps-its-encryption-engine-for-the-quantum-doomsday-inevitability/

"这似乎是对现有Signal Protocol的一个可靠、深思熟虑的改进,"Brian LaMacchia说,他是一位密码工程师,曾在2015年至2022年期间监督微软的后量子转型,现在在Farcaster Consulting Group工作。"作为这项工作的一部分,Signal在底层进行了一些有趣的优化,以最大限度地减少添加后量子功能对网络性能的影响。"

在需要克服的多个障碍中,最具挑战性的是考虑抗量子算法所需的更大密钥大小。这里的改造增加了基于ML-KEM-768的保护,这是CRYSTALS-Kyber算法的一个实现,该算法于2022年被选中,并于去年由美国国家标准与技术研究院正式确定为标准。ML-KEM是Module-Lattice-Based Key-Encapsulation Mechanism(基于模格的密钥封装机制)的缩写,但大多数时候,密码学家简称其为KEM。

  • https://arstechnica.com/information-technology/2022/07/nist-selects-quantum-proof-algorithms-to-head-off-the-coming-cryptopocalypse/
  • https://csrc.nist.gov/pubs/fips/203/ipd

棘轮、乒乓和异步性

与Signal自启动以来一直使用的ECDH协议一样,KEM是一种密钥封装机制。也称为密钥协商机制,它为从未见过面的双方提供了一种手段,可以在监控双方连接的敌手在场的情况下安全地就一个或多个共享秘密达成一致。RSA、ECDH和其他封装算法长期以来一直用于在包括TLS、SSH和IKE在内的协议中协商对称密钥(几乎总是AES密钥)。然而,与ECDH和RSA不同,这个更新的KEM是量子安全的。

在TLS这样的协议中,密钥协商相对简单。这是因为通过TLS连接的设备在会话开始时通过单次握手协商密钥。然后在整个会话中使用商定的AES密钥。Signal Protocol则不同。与TLS会话不同,Signal会话受前向保密保护,这是一种密码学特性,确保用于加密最近一组消息的密钥的泄露不能用于解密较早的一组消息。该协议还提供后泄露安全性（Post-Compromise Security）,保护未来的消息免受过去密钥泄露的影响。TLS在整个会话中使用相同的密钥,而Signal会话中的密钥会不断演变。

  • https://en.wikipedia.org/wiki/Forward_secrecy

为了提供这些保密性保证,Signal Protocol在消息方每次点击发送按钮或接收消息时更新密钥材料,以及在其他时间点,例如在显示某一方当前正在输入的图形指示器中以及在发送已读回执时。在过去十年中使Signal能够实现这种持续密钥演变的机制是协议开发人员所说的"双棘轮"。就像传统棘轮允许齿轮在一个方向旋转但不能在另一个方向旋转一样,Signal棘轮允许消息方基于先前和新商定的秘密的组合创建新密钥。棘轮在单一方向上工作,即发送和接收未来的消息。即使对手泄露了新创建的秘密,使用较旧秘密加密的消息也无法解密。

  • https://signal.org/docs/specifications/doubleratchet/

起点是执行三到四次ECDH协商的握手,混合长期和短期秘密以建立共享秘密。这个"根密钥"的创建允许双棘轮开始。直到2023年,密钥协商使用X3DH。握手现在使用PQXDH使握手具有抗量子性。

双棘轮的第一层,对称棘轮,从根密钥派生出AES密钥,并为发送的每条消息推进它。这允许每条消息都用新的密钥加密。因此,如果攻击者泄露了一方的设备,他们将无法了解之前密钥的任何信息。但即便如此,攻击者仍然能够计算未来消息中使用的密钥。这就是第二个"Diffie-Hellman棘轮"发挥作用的地方。

Diffie-Hellman棘轮在发送的每条消息中合并一个新的ECDH公钥。使用Alice和Bob——解释非对称加密时经常提到的虚构角色——当Alice向Bob发送消息时,她创建一个新的棘轮密钥对,并计算此密钥与Bob发送的最后一个棘轮公钥之间的ECDH协议。这给了她一个新的秘密,她知道一旦Bob得到她的新公钥,他也会知道这个秘密(因为如前所述,Bob之前发送了另一个密钥)。有了这个,Alice可以将新秘密与她的旧根密钥混合以获得新的根密钥并重新开始。结果是:了解她旧秘密的攻击者将无法区分她的新棘轮密钥和随机噪声。

结果就是Signal开发人员所描述的"乒乓"行为,因为讨论的各方轮流一次替换一个棘轮密钥对。效果是:泄露其中一方的窃听者可能会恢复当前的棘轮私钥,但很快,该私钥将被一个新的、未泄露的私钥替换,并且以一种使其免受攻击者窥探的方式。

新生成密钥的目标是限制在正在进行的聊天中的某个时刻,如果对手恢复了密钥材料,可以解密的消息数量。在泄露之前和之后发送的消息将保持无法访问。

Signal Protocol设计者面临的一个主要挑战是需要使棘轮在异步环境中工作。异步消息发生在各方在不同时间发送或接收消息时——例如当一方离线而另一方活跃时,或者反之——而不需要任何一方立即在场或响应。整个Signal Protocol必须在这个异步环境中工作。更重要的是,它必须在不稳定的网络和由敌手控制的网络上可靠工作,例如强制电信或云服务监视流量的政府。

阴影中的Shor算法

无疑Signal的双棘轮设计是最先进的。但它依然对一个不可避免(如果不是立即的)的威胁无能为力:量子计算。这是因为能够监控从两个或更多信使用户传递的流量的敌手可以捕获该数据并将其输入量子计算机——一旦有足够功率的量子计算机可行——并计算第二个棘轮中生成的临时密钥。

在经典计算中,这样的敌手计算密钥是不可行的,如果不是不可能的话。像所有非对称加密算法一样,ECDH基于数学单向函数。也称为陷门函数,这些问题在一个方向上计算起来很简单,而反向计算则要困难得多。在椭圆曲线密码学中,这个单向函数基于数学中的离散对数问题。关键参数基于某个素数模整数域上椭圆曲线中的特定点。

平均而言,仅配备经典计算机的敌手需要花费数十亿年猜测整数才能得到正确的整数。相比之下,量子计算机能够在几小时或几天内计算出正确的整数。一个名为Shor算法的公式——仅在量子计算机上运行——将这个单向离散对数方程恢复为双向方程。Shor算法同样可以快速解决作为RSA算法基础的单向函数。

如前所述,Signal Protocol于2023年首次进行了后量子改造。这次更新在初始协议握手中添加了PQXDH——一个Signal特定的实现,结合了X3DH中使用的椭圆曲线密钥协议(特别是X25519)和量子安全的KEM。(然后X3DH作为独立实现被淘汰。)

  • https://signal.org/blog/pqxdh/

此举排除了量子攻击能够恢复用于启动棘轮的对称密钥的可能性,但在乒乓式第二棘轮中建立的临时密钥仍然容易受到量子攻击。Signal的最新更新为这些密钥增加了量子抗性,确保前向保密和后泄露安全性也免受Shor算法的影响。

尽管乒乓密钥容易受到未来量子攻击,但人们普遍认为它们对今天来自经典计算机的攻击是安全的。Signal Protocol开发人员不想删除它们或产生它们的经过实战检验的代码。这导致他们决定通过添加第三个棘轮来增加量子抗性。这个棘轮使用量子安全的KEM来产生新的秘密,就像之前的Diffie-Hellman棘轮一样,确保量子安全的后泄露安全性。

技术挑战绝非易事。在X25519实现中生成的椭圆曲线密钥大约32字节长,足够小,可以添加到每条消息中,而不会对已经受限的带宽或计算资源造成负担。相比之下,ML-KEM 768密钥是1000字节。此外,Signal的设计需要发送加密密钥和密文,使总大小达到2272字节。

然后变成了三个

为了处理71倍的增长,Signal开发人员考虑了各种选择。一个是更少地发送2272字节的KEM密钥——比如每50条消息一次或每周一次——而不是每条消息。这个想法被否决了,因为它在异步或对抗性消息环境中效果不佳。Signal Protocol开发人员Graeme Connell和Rolfe Schmidt解释说:

考虑"如果你一周内没有发送密钥就发送密钥"的情况。如果Bob已经离线2周,当Alice想发送消息时她该怎么办?如果我们可能丢失消息,而我们丢失了包含新密钥的五十分之一的消息会怎样?或者,如果中间有一个攻击者想要阻止我们生成新的秘密,并且可以寻找比其他消息大[许多]字节的消息并丢弃它们,只允许无密钥消息通过会怎样?

Signal工程师考虑的另一个选择是将2272字节的密钥分解为更小的块,比如71个32字节的块。将KEM密钥分解为更小的块并将一个放在每条消息中,乍一看似乎是一种可行的方法,但再一次,消息传递的异步环境使其不可行。例如,当数据丢失导致其中一个块被丢弃时会发生什么?协议可以通过在发送完所有71个之前的块后再次重复发送块来处理这种情况。但是,监控流量的对手可以简单地每次都导致数据包3被丢弃,从而阻止Alice和Bob完成密钥交换。

Signal开发人员最终采用了使用这种多块方法的解决方案。

让大象偷偷穿过猫门

为了对付异步挑战,开发人员转向"纠删码",这是一种将较大数据分解为较小块的方法,使得可以使用任何足够大的块子集重建原始数据。

Charlie Jacomme是INRIA Nancy Pesto团队的研究员,专注于形式化验证和安全消息传递,他说这种设计通过在分块材料中构建冗余来解决数据包丢失问题。不是所有个块都必须成功接收才能重建密钥,该模型只需要接收个块,其中是可接受的丢失数据包数量。只要达到该阈值,即使发生数据包丢失,也可以建立新密钥。

设计的另一部分是将KEM计算分解为更小的步骤。这些KEM计算与KEM密钥材料不同。

正如Jacomme所解释的:

本质上,公钥的一小部分足以开始计算和发送密文的更大部分,因此你可以快速并行发送公钥的其余部分和密文的开头。本质上,最终计算等于标准,但一些东西被并行化了。

所有这些实际上在最终的安全保证中发挥了作用,因为通过优化KEM计算完成得更快的事实,你更频繁地在密钥派生中引入新的秘密。

Signal在10天前的帖子中包含了几张说明这种设计的图片:

虽然该设计解决了异步消息传递问题,但它本身又带来了一个新的复杂问题:这个新的量子安全棘轮推进得如此之快,以至于无法与Diffie-Hellman棘轮保持同步。最终,架构师们采用了一个创造性的解决方案。他们没有将KEM添加到现有的双棘轮上,而是让它保持或多或少与以前相同。然后他们使用新的量子安全棘轮实现了一个并行的安全消息系统。

现在,当协议加密消息时,它从经典的双棘轮和新棘轮中获取加密密钥。然后它将两个密钥混合在一起(使用密码学密钥派生函数)以获得一个新的加密密钥,该密钥具有经典双棘轮的所有安全性,但现在也具有量子安全性。

Signal工程师给这个第三棘轮起了正式名称:Sparse Post Quantum Ratchet,简称SPQR。第三棘轮是与PQShield、AIST和纽约大学合作设计的。开发人员在Eurocrypt 2025会议上展示了基于纠删码的分块和高级三棘轮设计。在Usenix 25会议上,他们讨论了他们考虑添加量子安全前向保密和后泄露安全性的六个选项,以及为什么SPQR和另一个选项脱颖而出。在NIST PQC标准化会议和密码应用研讨会上的演示解释了分块的细节、设计挑战以及协议如何必须适应使用标准化的ML-KEM。

  • https://eprint.iacr.org/2025/078
  • https://www.usenix.org/system/files/usenixsecurity25-auerbach.pdf
  • https://csrc.nist.gov/Presentations/2025/post-quantum-ratcheting-for-signal
  • https://youtu.be/WhTLjKzkK9c

Jacomme进一步观察到:

三棘轮最后有趣的地方在于它很好地结合了两个世界的优点。在两个用户之间,你有一个基于经典DH的棘轮在一边进行,完全独立地,一个基于KEM的棘轮在另一边进行。然后,每当你需要加密某些东西时,你从两者中获取一个密钥,并将其混合起来以获得实际的加密密钥。因此,即使一个棘轮被完全破解,无论是因为现在有了量子计算机,还是因为有人设法破解椭圆曲线或ML-KEM,或者因为其中一个的实现有缺陷,或者......,Signal消息仍将受到第二棘轮的保护。从某种意义上说,这次更新可以被视为,当然是简化了,使Signal的棘轮部分的安全性翻倍,即使对于不关心量子计算机的人来说,这也是一件很酷的事情。

正如Signal和Jacomme所指出的,Signal和其他依赖Signal Protocol的消息应用的用户无需关心任何这些新设计。套用某个设备制造商的话,它就是能用。

在未来几周或几个月内,各种消息应用程序版本将更新以添加三棘轮。在那之前,应用程序将像往常一样简单地依赖双棘轮。一旦应用程序收到更新,它们的行为将与升级前完全一样。

然而,对于那些关心基于Signal的应用程序内部工作原理的人,架构师已经非常详细地记录了这个新棘轮的设计及其行为方式。除其他事项外,该工作包括验证更新的Signal协议提供声称的安全性质的数学证明。

外部研究人员亦对这项工作表示赞赏。

"如果我们使用的正常加密消息是猫,那么后量子密文就是大象,"约翰霍普金斯大学的密码学专家Matt Green在一次采访中写道。"所以这里的问题是让一头大象偷偷穿过为猫设计的隧道。这是一项了不起的工程成就。但这也让我去希望一下我们可以不必处理大象。"


修改于