量子对后量子密码并不重要 - Trail of Bits博客
Opal Wright | 2024年7月1日 | 密码学
最近你可能经常听到后量子密码学的讨论，很容易让人疑惑：在没人真正见过量子计算机的情况下，为什么这如此重要？但即使量子计算机永远无法建成，新的后量子标准也比传统密码更安全、更具弹性且更灵活。
众说纷纭的量子计算机
量子计算机确实是个大话题；随便问问，你会得到各种观点。也许量子计算机即将摧毁我们所知的公钥密码学；也许具有密码学意义的量子计算机只是不可能实现的空想；也许公钥密码学的终结不是现在，而是二十年后；又或者我们还有50到60年时间，因为实用的量子计算机"还有二十年就能实现"的说法已经持续了三十年，而且短期内不会改变。
这些关于量子计算机的观点和预测也导致了对后量子密码学的不同看法。也许我们需要尽快转向后量子密码；也许后量子密码也是空想，因为有人会找到用量子计算机破解新算法的方法；也许某个世界大国已经拥有量子计算机但将其列为机密。
事实是，在我们亲眼见到之前，很难知道具有密码学意义的量子计算机会何时出现。我们可以猜测，可以基于现有有限数据推断，可以期待某种结果，但我们无法确定。
不过这没关系，因为抗量子性并不是后量子密码的主要好处。
当前的研究和标准工作将基于多样化的密码学问题产生更安全、更具弹性的加密算法。这些算法受益于过去40年的实践经验，并提供用例灵活性。无论是末日论者还是量子怀疑论者都应该为此欢呼。
孤注一掷的风险
担心量子计算机的人通常关注一个重点，他们完全正确：目前广泛使用的几乎所有公钥密码学都可能因为量子计算的几个不确定但可能的进步而被破解。
通俗地说，最常用的公钥算法基于三个问题：因数分解（RSA）、有限域离散对数（Diffie-Hellman）和椭圆曲线离散对数（ECDH和ECDSA）。这些都是更一般的计算问题——隐藏子群问题的特殊实例。而量子计算机擅长解决隐藏子群问题。它们非常擅长，以至于如果有人建造一个许多研究人员认为合理大小的量子计算机，他们就能做各种坏事：读取加密消息、在线冒充可信组织，甚至用它来构建破解某些非量子加密的工具。
但即使量子计算永远无法强大到破解当前公钥，量子末日论者的恐惧基于一个完全有效的观察：互联网几乎将所有密码学希望都寄托在隐藏子群问题这一个篮子里。如果有人能高效解决隐藏子群问题，无论是用量子计算机还是经典计算机，他们就能破解互联网上使用的大多数公钥密码学。
经常被忽视的是，在过去40年里，隐藏子群这个篮子一再被证明比我们预期的更不安全。
因数分解和离散对数的进展
在1987年的演讲"从弩到密码学：技术挫败国家"中，Chuck Hammill讨论了200位（约664位）的RSA密钥，称地球上最强大的超级计算机在100年内也无法分解这样的数字。Unix版PGP 1.0支持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公式表明，密钥需要达到15360位才能匹配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
- NIST决赛选手中的非均匀分布随机采样技术已完全指定并作为标准化工作的一部分进行分析，降低依赖有偏采样的攻击风险
- 许多后量子算法在输入上完全确定性，减少随机数重用问题和值重用时的信息泄露风险
- 许多算法设计允许快速轻松生成新密钥，使得提供前向保密更容易
- 每个严肃的后量子密码系统提案都列出少量安全参数化集合，而不是邀请开发者自己构想参数
这些都是有意、精心做出的决定。每个都基于过去40年左右出现的真实世界失败。在密码学中，我们经常称这些失败场景为"footguns”，因为它们容易让人自伤；新设计特意使其难以发生。
用例灵活性
新算法带来新权衡，后量子标准中有很多这样的权衡。基于哈希的签名可能达到50千字节，但公钥很小。像McEliece这样的基于代码的系统具有小的密文，解密速度快，但公钥可能达到数百千字节。
这种不同的权衡给开发者很大灵活性。对于速度和带宽重要但ROM空间便宜的嵌入式设备，McEliece可能是密钥建立的绝佳选择。对于处理器时间便宜但每个连接节省几个字节网络活动可以累积成真正节省的服务器农场，NTRUSign可能是签名的好选择。一些算法甚至提供多个参数集以满足不同需求：SPHINCS+包括相同安全级别下"快速"签名和"小"签名的参数集。
后量子密码的缺点：不确定性
当然，一个大担忧是每个人都在尝试标准化相对年轻的密码系统。如果行业（或NIST）选择了不安全的东西怎么办？如果他们选择明天就会破解的东西怎么办？
这个想法甚至可能感觉令人恐惧地合理。RAINBOW进入了NIST PQC标准化努力的第三轮才被破解。SIKE进入了（未计划的）第四轮才被破解。
有些人担心新标准可能遭受与RAINBOW和SIKE相同的命运，但直到在行业广泛采用之后。
但这里有一个可怕的事实：我们已经承担这种风险。从数学角度看，没有证据表明RSA模数不能容易地分解。没有证据表明破解当今使用的RSA等同于因数分解（事实上相反）。完全有可能有人明天发布一个完全摧毁Diffie-Hellman密钥交换的算法。有人下个月可能发表一篇聪明论文，展示如何恢复私有ECDSA密钥。
更可怕的事实？如果你眯眼看看，会发现因式分解和有限域离散对数已经发生了重大突破。如上所述，GNFS的进步二十多年来一直在推高RSA和Diffie-Hellman密钥大小。1994年认为没问题的密钥在2024年被认为可笑。来自老密码朋克时代的RSA和Diffie-Hellman已经被破解。你只是没注意到它们被破解了，因为这花了30年发生，密钥大小一直在增加。
我并不是轻率地说。严肃的研究人员过去几年投入大量精力研究新的后量子系统。当然，他们可能遗漏了什么。但如果你真的担心有人会找到破解SPHINCS、McEliece、CRYSTALS-KYBER或FALCON的方法，你可以暂时继续使用当前算法。或者你可以转向混合密码系统，它将后量子和前量子方法结合在一起，只要两者都未被破解，就应该保持安全。
总结
对量子计算机的恐惧可能被夸大，也可能没有。我们只是还不知道。但后量子密码研究和标准化工作的效果是，我们从一個篮子中取出了大量鸡蛋，正在构建更加多样化和现代化的篮子集合。
后量子标准最终将用不会因最微小细节而崩溃的算法取代更挑剔的旧算法。几个常见的实现错误来源将被消除。开发者将能够选择适合广泛用例的算法。如果数学突破使某个算法不安全，新数学基础的多样性提供了"备用计划"。后量子算法不是万能药，但它们确实解决了我们在Trail of Bits看到的许多头痛问题。
忘记量子计算机，看看后量子密码研究和标准化的本质：多样化和现代化努力。