量子对后量子并不重要
原文：https://blog.trailofbits.com/2024/07/01/quantum-is-unimportant-to-post-quantum/
作者：Opal Wright
译者：Kurt Pan
你最近可能听到过很多关于后量子（PQ）密码学的内容，而且很容易就会去想，在还没有人真正见过量子计算机的时候，这个有那么重要嘛。但是，即使量子计算机永远不会建成，新的后量子标准也要比经典标准更安全、更有适应力、更灵活。
量子计算机是一件大事；只要到处问问，你就会得到很多观点。也许量子计算机已经处于摧毁我们所知的公钥密码学的边缘。亦或者，足以影响密码学的量子计算机也许只是一个不可能实现的白日梦。又也许，公钥密码学的终结还不是现在，但距现在也只有二十年了。也可能我们还有 50 或 60 年的时间，毕竟“量子计算机距离实用还有二十年”这个说法也已经有 30 年的时间了，而且我们预计这种情况不会很快改变。
这些关于量子计算机的观点和预测也导致了对后量子密码学的许多不同观点。也许我们现在就需要尽快过渡到后量子密码。也许后量子密码也只是一个白日梦，因为终究有人会找到一种使用量子计算机来攻破新算法的方法。也许某个世界主要政府已经拥有了量子计算机，但仍将其保密。
事实是，直到我们看到一台具有密码学影响的量子计算机之前，我们都很难知道它何时会存在。我们可以猜测，我们可以试着根据迄今为止所掌握的有限数据进行推断，我们可以希望得到一种结果或另一种结果。但我们无法确定。
不过没关系，因为抗量子性并不是后量子密码的主要好处。
当前的研究和标准工作将基于一系列不同的密码学问题产生出更安全、更有适应力的密码学算法。这些算法受益于过去 40 年的实践经验，并提供用例灵活性。不管是末日论者和还是量子怀疑论者都应该庆祝。
都在一个篮子里
担心量子计算机的人通常只关注一点，他们在这一点上绝对正确：几乎所有目前广泛使用的公钥密码学都会因为量子计算的一些不确定但可能的进展而被攻破。
大致来说，最常用的公钥算法基于三个问题：因子分解（RSA）、有限域离散对数（Diffie-Hellman）和椭圆曲线离散对数（ECDH 和 ECDSA）。这些都是被称为隐藏子群问题的更一般计算问题的特殊实例。而量子计算机擅长解决隐藏子群问题。是真的很擅长。好到如果有人造了一台对许多研究者来说看起来合理大小的量子计算机，那他就可以做各种各样令人讨厌的事情。他可以读取加密的消息。可以在线上冒充受信任的组织。他甚至可以用它来构造工具，在没有量子计算机的情况下破解某些形式的加密。
但即使量子计算永远不会变强大到足以破解当前的公钥，量子末日论者的恐惧也基于一个完全有效的观察：互联网已将几乎所有的密码鸡蛋放入到了隐藏子群问题这一单个篮子中了。如果有人能够高效解决隐藏子群问题，无论是使用量子计算机还是经典计算机，他都将能够破解互联网上使用的绝大多数公钥密码学。
经常被忽视的一点是，在过去 40 年里，这个隐藏子群篮子一直被证明是并不如我们预期的安全。
因子分解和离散对数的进展
在 1987 年的演讲“从弩到密码学：Techno-Thwarting The State”中，Chuck Hammill 讨论了 200 位数字（约 664 比特）的 RSA 密钥，并表示地球上最强大的超级计算机也无法在100年内分解这个数字。 PGP 1.0 的 Unix 版本支持 992 比特的RSA 密钥作为其最高安全级别，并称该密钥大小为“军用级”。
https://nakamotoinstitute.org/from-crossbows-to-cryptography/ https://www.pgpkeys.org/bin/unix_pgp10.tar.gz
如今，美国国家标准与技术研究所 (NIST) 提供的公式表明，一个664 比特的密钥仅提供大约 65 比特的安全性，完全在一个受激励的学术研究者的能力范围之内了。 992 比特的密钥仅提供大约 78 比特的安全性，应该也在情报机构的能力范围之内。
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br2.pdf
（PGP 1.0 支持的最小密钥大小为 288 比特，可以在现代台式计算机上使用 msieve 等现成软件在大约 10 分钟内破解。“商业级”密钥为 512 比特，使用 AWS 可以在不到一天内用不到 100 美元分解。）
https://sourceforge.net/projects/msieve/
不断增加的密钥大小
为了应对多年来因子分解和离散对数算法的进步，我们做出了回应，做了我们唯一真正知道要如何做的事情：增加密钥大小。目前，典型的 RSA 密钥大小为 2048 至 4096 比特，大约比 Chuck Hammill 建议的长度长三到六倍，是 PGP 早期版本所谓的“军用级”RSA 密钥长度的二到四倍。国家安全局要求机密数据的 RSA 密钥不少于 3072 比特。 NIST 公式建议密钥长度需要为 15,360 比特才能匹配 256 比特AES 密钥的安全性。
多年来，有限域离散对数密钥大小在很大程度上跟上了 RSA 密钥大小。这是因为解决这两个问题的最佳算法是相同的：使用广义数域筛法 (GNFS) 的指数演算。虽然边际条件有一些差异，但大部分困难工作都是一样的。值得指出的是，有限域离散对数密码系统还有一个额外的缺点：在有限域中计算一个离散对数的开销与计算大量离散对数的开销大致相同。
https://weakdh.org/imperfect-forward-secrecy.pdf
椭圆曲线在过去 15 年左右的时间里变得越来越流行，密钥大小并未出现因子分解和离散对数系统那样的变化。谢天谢地，指数演算不能很好地转化到椭圆曲线上，但椭圆曲线离散对数依然是一个开放的研究领域。
https://eprint.iacr.org/2015/1022.pdf
实现的危险
除了问题多样性不足之外，另一个令人担忧的问题是现有算法过于复杂挑剔，容易出现细微的实现故障。
我们因说“f*** RSA”而闻名，我们这么说主要是因为 RSA 充满了地雷。有限域 Diffie-Hellman 在参数选择和弱子群攻击方面存在着微妙的问题。椭圆曲线密码系统则容易受到曲线外攻击、弱子群攻击以及与弱参数选择相关的攻击。
https://www.youtube.com/watch?v=lElHzac8DDI https://crypto.stanford.edu/%7Edabo/papers/RSA-survey.pdf
更糟糕的是，这些算法中的每一种都需要仔细注意以避免时序侧信道攻击！
总而言之，这些陷阱和微妙故障的模式将当前的公钥原语变成了开发者的绝对雷区。密码学库将其底层功能称为“危险品”的情况并不罕见。这就是进入更高层协议之前的全部内容！
https://cryptography.io/en/latest/hazmat/primitives/
通过使用良好的标准，许多实现方面的担忧至少可以部分缓解。例如，Curve25519 专为快速、常数时间实现以及针对曲线外和弱子群攻击的安全性而设计。大多数网络流量的有限域 Diffie-Hellman 密钥交换都使用了少数几个标准化的参数集来完成的，这些参数集旨在缓解弱子群攻击。与加密和签名相关的已知 RSA 攻击不断增长，通常也可以通过使用实现最新标准的经过充分测试和审核的 RSA 库来缓解。
好的标准是有很大帮助，但它们实际上也只是掩盖了这些密码系统的一些根深蒂固的性质，这些性质使其难以使用且出错后十分危险。但尽管存在错误的后果以及可用的高质量开源库，我们仍然经常在我们的代码审计中发现这些算法存在危险的漏洞的实现。
后量子密码提供了什么
那么为什么后量子密码要好得多呢？看看正在进行的 NIST 后量子密码标准化的工作可能会有所启发。
问题的多样性
首先，即将推出的 NIST 标准基于多个数学问题：
CRYSTALS-KYBER、CRYSTALS-DILITHIUM 和 Falcon 基于格问题：短整数解 (SIS) 和各种环上的带错误学习 (LWE)。 SPHINCS+ 基于 SHA-256 和 SHA-3 哈希函数的第二原像攻击的困难性。
此外，NIST 正在尝试标准化一种或多种额外的签名算法，可能基于不同的问题。提交的方案包括基于椭圆曲线同源、纠错码和多变量二次方程相关问题的签名算法。
到下一阶段的标准化结束时，我们可以期望拥有基于至少三到四个不同数学问题的算法。如果选定的问题之一失效于量子或经典算法的进步，那么还有现成的替代品，它们极不可能受到对已失效密码系统的攻击的影响。
现代的设计
我们今天看到的后量子提案都是在借鉴以往经验的基础上开发的。现代密码系统的设计者已经充分了解当前公钥密码在实践中失败的多种方式，并将这些经验教训融入到了最终的设计之中。
这里有些例子：
许多后量子算法的设计都使得常数时间的实现变得容易，从而降低了时序攻击的风险。 许多算法通过使用 SHAKE 等确定性函数扩展随机数值来减少对随机数生成器 (RNG) 的依赖，从而防止对不安全的 RNG 的依赖。 NIST 决赛入围者中非均匀分布的随机采样技术已得到充分说明，并已作为标准化工作的一部分进行了分析，从而降低了依赖有偏采样的攻击风险。 许多后量子算法的输入是完全确定性的（这意味着使用相同的随机数对相同的值进行加密或签名将始终产生相同的结果），从而减少了随机数重用问题以及重用值时信息泄漏的风险。 许多算法的设计目的是允许快速、容易地生成新密钥，从而更容易提供前向保密。 每一个关于后量子密码系统的严肃提案都会列出一小组安全参数集合，而不是邀请开发者去想象自己的参数。
这些都是有意、谨慎做出的决定。每一个都是基于过去 40 年左右间出现的现实世界的故障。在密码学中，我们经常将这些故障场景称为“footguns”，这里很容易搬起石头砸自己的脚；较新的设计不遗余力地使其变得困难。
用例灵活性
新算法带来了新的权衡，在后量子标准中可以找到很多东西。基于哈希的签名可以达到 50 KB，但公钥很小。 McEliece 等基于编码的系统具有较小的密文，并且解密速度很快，但公钥可能有几百字节。
这种不同的权衡为开发者提供了很大的灵活性。对于速度和带宽很重要但 ROM 空间便宜的嵌入式设备来说，McEliece 可能是密钥建立的绝佳选择。对于处理器时间很便宜但在每个连接上节省几个字节的网络活动合起来可以有真正节省的服务器农场来说，NTRUSign 可能是签名的一个不错的选择。有些算法甚至提供了多个参数集来满足不同的需求：SPHINCS+ 就包括相同安全级别的“快速”签名和“小”签名的参数集。
后量子的缺点：不确定性
当然，一个大的担忧是每个人都在试图标准化相对年轻的密码系统。如果行业（或 NIST）选择了不安全的方案要怎么办？如果他们选择的东西明天就被攻破了怎么办？
这个想法甚至让人感觉非常合理。 RAINBOW 在被攻破之前已进入 NIST PQC 标准化工作的第三轮。 SIKE 在被攻破之前进入了（计划外的）第四轮。
一些人担心新标准可能会遭受与 RAINBOW 和 SIKE 同样的命运，但要等到其在行业中得到广泛采用之后。
但这里有一个可怕的事实：我们已经在冒着这种风险了。从数学角度来看，没有证据表明 RSA 模不能被很容易地分解。没有一个证明表明破解当今使用的 RSA 要等价于因子分解（事实上，事实恰恰相反）。完全有可能明天就有人发布一种算法，彻底摧毁 Diffie-Hellman 密钥交换。有人可能在下个月就发表一篇聪明的论文，展示如何恢复 ECDSA 私钥。
https://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf
更可怕的事实？如果你仔细观察，你会发现因子分解和有限域离散对数已经发生了重大突破。如上所述，二十多年来，GNFS 的进步一直在推动着 RSA 和 Diffie-Hellman 的密钥大小。在 1994 年被认为很好的密钥在 2024 年则被认为是可笑的。旧密码朋克时代的 RSA 和 Diffie-Hellman 已经被破解了。你只是没有注意到它们被破解，因为这花了 30 年的时间才发生，而且密钥一直在变大。
我并不想说得轻描淡写。过去几年里，严肃的研究者已经投入了大量精力来研究新的后量子系统。当然他们也可能错过一些东西。但如果你真的担心有人会找到破解 SPHINCS、McEliece、CRYSTALS-KYBER 或 FALCON 的方法，你可以继续使用当前的算法一段时间。或者，你也可以切换到混合密码系统，该系统将后量子和前量子的方法结合在一起，只要两者都没有被攻破，就会继续保持安全。
https://xiphera.com/hybrid-models-connect-the-post-quantum-with-the-classical-security/
总结
对量子计算机的恐惧可能是也可能不是被夸大的。我们只是还不知道。但后量子密码学研究和标准化工作的影响则是，我们已经从一个篮子里拿出了大量鸡蛋，而且我们正在构建一套更加多样化和现代的篮子。
后量子标准最终将用不会因最细微的差别而崩溃的算法取代那些旧的、更挑剔的算法。一些常见的实现故障来源将被消除。开发者将能够选择适合广泛用例的算法。如果数学突破导致其中一种算法不再安全，各种新的数学基础都可以提供“后备计划”。后量子算法并不是万能药，但它们确实可以解决我们在工作中遇到的许多令人头痛的问题。
忘记量子计算机吧，去看看后量子密码研究和标准化的本质：这是一种多元化和现代化的努力。
Kurt Pan 翻译后记：既然“后量子密码学”名称存在一定对专注点的误导，不如我们就将其称为“后现代密码学 Post-Modern Cryptography”吧！