量子对后量子无关紧要 - Trail of Bits 博客

Opal Wright
2024年7月1日
密码学

最近你可能经常听到后量子（PQ）密码学的消息，很容易好奇为什么在没人真正见过量子计算机的情况下，它如此重要。但即使量子计算机从未建成，新的 PQ 标准也比其经典对应物更安全、更具弹性和更灵活。

量子计算机是个大问题；随便问问，你会得到很多意见。也许量子计算机即将摧毁我们所知的公钥密码学。或者也许具有密码学意义的量子计算机是一个不可能的白日梦。也许公钥密码学的终结不是现在，而是只有二十年之遥。或者也许我们还有五六十年的时间，因为有用的量子计算机已经“还有二十年”三十年了，我们不期望很快改变。

这些关于量子计算机的意见和预测也导致了对后量子密码学的许多不同观点。也许我们需要尽快过渡到后量子密码学。也许后量子密码学是白日梦，因为有人会找到方法使用量子计算机来破解新算法。也许某个世界大国已经拥有量子计算机，但将其保密。

事实是，在我们看到之前，很难知道具有密码学意义的量子计算机何时会存在。我们可以猜测，可以尝试根据我们目前有限的数据进行推断，可以希望某种结果。但我们无法确定。

不过这没关系，因为抗量子性并不是后量子密码学的主要好处。

当前的研究和标准工作将基于多样化的密码学问题，产生更安全、更具弹性的密码算法。这些算法受益于过去40年的实践经验，并提供用例灵活性。末日预言者和量子怀疑论者都应该庆祝。

一篮子鸡蛋

担心量子计算机的人通常关注一点，他们绝对正确：目前广泛使用的几乎所有公钥密码学，只需量子计算的一些不确定但可能的进步就可以被破解。

粗略地说，最常用的公钥算法基于三个问题：因式分解（RSA）、有限域离散对数（Diffie-Hellman）和椭圆曲线离散对数（ECDH 和 ECDSA）。这些都是更一般的计算问题（称为隐藏子群问题）的特殊实例。而量子计算机擅长解决隐藏子群问题。它们非常擅长。如此擅长，以至于如果有人建造一个许多研究人员认为合理大小的量子计算机，他们可以做各种坏事。他们可以读取加密消息。他们可以在线冒充受信任的组织。他们甚至可以用它来构建工具，在没有量子计算机的情况下破解某些形式的加密。

但即使量子计算从未变得足够强大以破解当前的公钥，量子末日预言者的恐惧基于一个完全有效的观察：互联网几乎将其所有密码学鸡蛋都放在了隐藏子群问题这一个篮子里。如果有人能高效解决隐藏子群问题，无论是用量子计算机还是经典计算机，他们将能够破解互联网上使用的大多数公钥密码学。

经常被忽视的是，在过去的40年里，隐藏子群篮子一直被证明比我们预期的更不安全。

因式分解和离散对数的进展

在1987年的演讲“从弩到密码学：技术挫败国家”中，Chuck Hammill 讨论了200位（约664位）的 RSA 密钥，说地球上最强大的超级计算机在100年内也无法分解这样的数字。PGP 1.0 的 Unix 版本支持992位 RSA 密钥作为其最高安全级别，称该密钥大小为“军事级”。

如今，美国国家标准与技术研究院（NIST）提供的公式表明，664位密钥仅提供约65位的安全性，并且完全在有意愿的学术研究人员的能力范围内。992位密钥仅提供约78位的安全性，据推测在情报机构的能力范围内。

（PGP 1.0 支持的最小密钥大小288位，在现代台式计算机上使用现成软件如 msieve 可以在约10分钟内破解。“商业级”密钥为512位，可以使用 AWS 在不到一天的时间内以低于100美元的成本分解。）

不断增加的密钥大小

为了应对多年来因式分解和离散对数算法的进步，我们做了唯一真正知道如何做的事情：增加密钥大小。如今典型的 RSA 密钥大小为2048到4096位，大约是 Chuck Hammill 建议的三到六倍，是早期 PGP 版本称为“军事级”RSA 密钥长度的两到四倍。国家安全局要求机密数据的 RSA 密钥长度不低于3072位。NIST 公式表明，密钥需要长达15,360位才能匹配256位 AES 密钥的安全性。

多年来，有限域离散对数密钥大小很大程度上跟随 RSA 密钥大小。这是因为解决这两个问题的最佳算法相同：使用一般数域筛法（GNFS）的指数积分。在边缘有一些差异，但大部分艰苦工作是相同的。值得指出的是，有限域离散对数密码系统有一个额外的缺点：在有限域中计算一个离散对数的成本与计算许多离散对数的成本大致相同。

在过去15年左右变得流行的椭圆曲线，没有经历因式分解和离散对数系统那种密钥大小的变化。指数积分不适用于椭圆曲线，谢天谢地，但椭圆曲线离散对数是一个开放的研究领域。

实现危险

除了缺乏问题多样性之外，另一个担忧是当前算法很挑剔，容易受到细微实现失败的影响。

瞧，我们是 Trail of Bits。我们以说“去他妈的 RSA”而有点出名，我们这么说主要是因为 RSA 充满了地雷。有限域 Diffie-Hellman 在参数选择和弱子群攻击方面有细微问题。椭圆曲线密码系统容易受到离曲线攻击、弱子群攻击以及与不良参数选择相关的攻击。

更糟糕的是，每个这些算法都需要仔细注意以避免时序侧信道攻击！

总之，这些陷阱和细微的失败模式将当前的公钥原语变成了开发人员的绝对雷区。密码库将其低级功能称为“危险材料”并不罕见。这都是在进入更高级协议之前！

许多实现问题至少部分通过使用良好标准得到缓解。例如，Curve25519 专门设计用于快速、恒定时间实现，以及防止离曲线和弱子群攻击的安全性。用于网络流量的大多数有限域 Diffie-Hellman 密钥交换是使用少量标准化参数集完成的，这些参数集旨在减轻弱子群攻击。与加密和签名相关的已知 RSA 攻击的不断增长的动物园通常可以通过使用经过良好测试和审计的实现最新标准的 RSA 库来缓解。

良好标准有很大帮助，但它们实际上只是掩盖了这些密码系统的一些深层次属性，这些属性使它们难以使用且出错危险。尽管如此，尽管有错误的后果和高质量开源库的可用性，Trail of Bits 在我们的代码审查中经常发现这些算法的危险有缺陷的实现。

后量子密码学提供什么

那么为什么后量子密码学好得多？看看正在进行的 NIST 后量子密码学标准化工作是有启发性的。

问题多样性

首先，即将推出的 NIST 标准基于多个数学问题：

• CRYSTALS-KYBER、CRYSTALS-DILITHIUM 和 Falcon 基于格问题：各种环上的短整数解（SIS）和带错误学习（LWE）。
• SPHINCS+ 基于 SHA-256 和 SHA-3 哈希函数的第二原像攻击的难度。

此外，NIST 正试图标准化一个或多个额外的签名算法，可能基于不同问题。提交内容包括基于椭圆曲线同源、纠错码和多变量二次问题相关问题的签名算法。

到标准化下一阶段结束时，我们可以期望拥有基于至少三四个不同数学问题的算法。如果选定的问题之一因量子或经典算法的进步而失效，有现成的替代方案，极不可能受到对失效密码系统攻击的影响。

现代设计

我们今天看到的后量子提案是在有后见之明优势的情况下开发的。现代密码系统设计者已经看到当前公钥密码学在实践中失败的无数方式，这些教训正被整合到最终设计的结构中。

以下是一些例子：

• 许多后量子算法设计使恒定时间实现容易，降低时序攻击风险。
• 许多算法通过使用确定性函数如 SHAKE 扩展随机数值，减少对随机数生成器（RNG）的依赖，防止依赖不安全的 RNG。
• NIST 决赛中非均匀分布的随机抽样技术完全指定，并作为标准化工作的一部分进行了分析，降低了依赖有偏抽样的攻击风险。
• 许多后量子算法在其输入上完全确定性（意味着用相同随机数加密或签名相同值总是产生相同结果），减少随机数重用问题和值重用时的信息泄漏风险。
• 许多算法设计允许快速轻松生成新密钥，使提供前向保密更容易。
• 不是邀请开发人员梦想自己的参数，每个严肃的后量子密码系统提案都列出一小套安全参数化。

这些是故意、精心做出的决定。每个都基于过去40年左右出现的真实世界失败。在密码学中，我们经常称这些失败场景为“footguns”，因为它们使