驳斥关于 ML-KEM 的误解

1. 引言最近人们对 NIST 的后量子密码加密标准 ML-KEM、IETF 的相关标准产生了一些担忧还有许多阴谋论声称恶意行为者操纵了标准化流程。作为一个几乎参与了这一标准化流程各个层面的人Sophie Schmieg 想快速驳斥自己听到的种种无稽之谈。下面就以常见问题的形式开始吧。2. ML-KEM 是 NSA 发明的吗不是。它最初由多位欧洲密码学家组成的团队定义可以在他们的网站上查看成员名单。3. 好吧但那是 Kyber不是 ML-KEMNSA 修改了 Kyber 吗没有。Kyber 与 ML-KEM 之间的差异非常小主要是 NIST 所作的编辑性修改。唯一称得上有些实质意义的变化是对某些密钥派生机制进行了轻微调整。这项修改由 Kyber 的原作者之一 Peter Schwabe 提出而且分析起来相当直接。修改的原因是Kyber 最初通过加入一个 KDF 步骤可以生成任意长度的共享秘密。然而应用通常还需要对共享秘密应用自己的 KDF以便将共享秘密与会话记录等信息绑定因此最终会调用两次 KDF。由于 Kyber 使用 KDF 仅仅是为了扩展输出移除它可以略微提升算法性能而不会产生任何安全影响。简而言之某项功能后来被证明在真实场景中其实算不上功能于是 NIST 在审慎考虑、该方案作者本人明确建议这样做并且整个密码学界都密切关注的情况下将其删除。这里没有发生任何不当行为。补充编辑2026-07-09NIST 所做的一项小改动最近又被一位声名扫地的前密码学家翻了出来也就是所谓的“耻辱哈希”hash of shame。在 Kyber 草案中封装方从随机数生成器取得随机值后会先对这个随机值进行哈希再继续执行封装算法。应 Markku 和Sophie Schmieg 的要求NIST 删除了这次额外哈希。最初加入它是为了防御 DUAL_EC_DRBG要利用 DUAL_EC_DRBG 的后门必须取得 DRBG 未经处理的输出。然而防范这个问题简单得多的方法就是不要使用 DUAL_EC_DRBG。随机数生成器包括 TRNG 和 DRBG对任何密码算法的安全运行都至关重要。TRNG 和 DRBG 都存在多种失效模式而 DUAL_EC_DRBG 式后门只是其中之一。DUAL_EC_DRBG 从来都不是特别流行的 DRBG因此 NIST 将其弃用并没有遇到多少阻力。在Sophie Schmieg 的职业生涯中其从未见过它的实现更不用说实际部署。Sophie Schmieg 倒见过很多糟糕的随机数生成器但它们没有一个能靠不加区分地额外做一次哈希来修复。因此这个哈希虽然可以作为抗议国家行为者蓄意削弱标准的一种姿态却不应出现在最终标准中因为它只会拖慢算法得不到任何收益。弱随机数生成器当然是一个值得担忧的问题但解决办法应当是修复随机数生成器而不是在上一层临时发明一种新的 DRBG。4. 好吧但里面会不会仍然存在某种后门ML-KEM 中没有后门而且Sophie Schmieg 可以证明这一点。某种机制要成为后门特别是“只有我们能用的后门”Nobody But UsNOBUS就必须确保其他人无法利用它。否则它就不是后门而只是一个已经被攻破的算法你掌握的任何内部密码分析成果最终也会被学术界追上。因此一个有用的后门要求植入者拥有某种无法通过暴力破解获得的秘密这个秘密相当于一把私钥可以解开该算法产生的任何密文。这正是 DUAL_EC_DRBG 中的后门类型。考虑到美国自己也打算使用 ML-KEM——不同于当年的出口密码闹剧——这也是他们唯一有理由植入标准的后门类型。然而如果存在一把无法暴力破解的私钥就还必须存在相应的公钥这个公钥必须足够大才能抵抗暴力破解而且必须作为参数嵌入算法。要达到不可暴力破解的程度该公钥至少需要具有 128 位熵。由此得到了一种很好的测试方法用来判断某个方案是否有能力容纳密码学意义上的 NOBUS 后门把参数空间的熵全部加起来。如果结果明确少于 128 位那么该方案最多只能是已被攻破而不可能被植入这种后门。下面就对 ML-KEM 做这个计算这就是它的参数集合。下面把各项熵加起来并完全忽略这些选择实际上远比任意随机整数受到更多约束这一事实不过在合计时仍会采用较大的数值。数域的阶8 位实际上它必须是 2 的幂所以其实只有 3 位素数12 位实际上它必须是素数所以是 10.2 位再进一步说它还必须是形如k ⋅ n 1 k\cdot n1k⋅n1的素数至少要达到秩与阶乘积的两倍而 3329 恰好就是满足这些条件的最小素数模的秩3 位模的秩本身就是主要安全参数实际只是在 2 到 4 之间计数秘密项与误差项的界2 2 位实际上这些值由素数大小、模的秩和数域阶共同决定压缩强度4 3 位总计为 34 位而且这个估算已经宽松得过分。甚至还给所有小数字额外送了一位任何公钥只有 34 位的非对称密码系统都能被一台笔记本电脑在几分钟内暴力破解这样的 ML-KEM 不会是“带后门”而会是彻底被攻破。ML-KEM 中不存在后门因为 ML-KEM 根本没有藏下后门的空间。为了再确认一次如果对著名的后门算法 DUAL_EC_DRBG 应用同样的“统计参数位数”测试就会看到标准中毫无理由地定义了多个椭圆曲线点参数熵立即突破了 128 位预算。事实上只要采用所谓的“袖中无物”Nothing up my sleeves范式就能轻易修复 DUAL_EC_DRBG不要让那些椭圆曲线点毫无解释地摆在那里而应从π \piπ、e ee的数字或者某个公开种子的哈希输出中派生它们。即便如此它依然无法通过本测试但这是因为在此故意把测试设计得过于激进。正如括号中的说明所示这些参数其实没有多少真正的选择空间它们只不过是能够得到安全方案的最小参数集合增大它们只会让方案变慢和或增加开销。所以不ML-KEM 中没有后门。5. 但 NIST 在选择 ML-KEM 时不是连基础数学都算错了吗没有。事实上Sophie Schmieg 2023年11月专门写过一篇博客Kyber512’s security level 讨论这个话题不过用一个“没有”概括全文也是准确的。6. 我以为 ML-KEM 已经被攻破了好像与故障攻击有关ML-KEM 的确存在故障攻击。如果你了解什么是故障攻击也称毛刺攻击这并不特别令人意外。进行故障攻击时需要在算法计算过程中注入一个错误——也就是故障。可以通过干扰物理硬件来实现如 ROWHAMMER 这类会在计算进行时直接改变内存内容的攻击。分析此类失效非常重要但现实中存在的任何实用密码算法都会受到故障攻击的影响。这实际上就是计算机连自己唯一的工作都没做好没有正确计算。CPU 和内存攻击可能是人们掌握的最强大攻击类别之一而且事实证明它们极难缓解。算法面对这种攻击时失效并不令人惊讶毕竟如果你能任意翻转一个比特完全可以直接把verified_success设为true然后收工。严格来说这是最强形式的故障攻击即攻击者可以选择故障发生的位置。但即使是随机故障通常也足以摧毁几乎所有密码算法。我们知道这些攻击的存在只能证明该算法被认为足够重要值得人们从数学上精确研究当你真的抽走它脚下的地板时它究竟会怎样失效。7. 那解密失败攻击呢听起来很吓人ML-KEM 有一个奇怪的特性从理论上说确实有可能以完全诚实的方式生成一份密文却被私钥持有者拒绝。如果成功做到这一点就能获得关于私钥的信息。但关键在于生成这种“有毒密文”的唯一方法是诚实运行封装算法然后期待自己走运。确实存在一种可以让密文分布略微偏斜的方法但即便如此仍然必须实际计算这些密文而且得到的优势微乎其微因为 ML-KEM 几乎替封装方决定了所有选择。利用相对直接的数学方法——柯西–施瓦茨不等式——可以计算出这种解封装失败的概率。ML-KEM 的参数经过专门选择使实际概率小到几乎可以忽略低于1 : 2 100 1:2^{100}1:2100。到了这个数量级攻击者实际上已经不能假定自己观察到的是解封装失败因为还有许多其他极不可能的事件反而更有可能发生如宇宙射线同时造成足够多次比特翻转并逃过错误检测。的确观察到第一次解封装失败后攻击者就有了更多手段让局面朝有利方向发展但要做到这一点首先必须让第一次失败发生而这基本没有希望。除此之外一把普通的 ML-KEM 密钥通常只使用一次——这正是密钥交换所用密钥的命运——进一步使此类自适应攻击失去意义。不过即使对同一把密钥执行多次解封装ML-KEM 密钥依然安全。8. 但不是还有一个叫 KyberSlash 的问题吗是的。事实证明实现密码代码仍然很难。可以稍微自夸一下Sophie Schmieg的实现后来逐渐演变为 BoringSSL 的 ML-KEM 实现而它从未出现过这个问题。所以这里的答案大概是“变强一点”git gud之类的吧。不过说正经的特别是在早期阶段新实现总会有一些毛刺随着人们逐渐掌握避免这些问题的正确技术情况才会改善。重要的是这是实现中的缺陷而不是算法数学结构中的缺陷。事实上好消息是从实现角度看ML-KEM 其实比椭圆曲线简单得多所以这种小型侧信道问题在这里可能会更少只是人们实现 ML-KEM 的次数还不像实现椭圆曲线那么多。9. 好吧ML-KEM 先说到这里混合方案和 IETF 又是怎么回事好吧这件事确实挺有趣——前提是你喜欢严重失灵的细枝末节争论、故意曲解和各种戏剧性冲突。首先什么是混合方案假设你有两个功能相同的密码方案而且两个都不信任但你信任二者的组合。混合方案本质上正是为了实现这一点把两个相同类型的方案组合成一个使组合方案至少与其中任意一个同样安全。通常的说法是这非常适合 PQC因为它能把经过充分研究的经典方案安全性与 PQC 方案的抗量子能力结合起来。此外与格密码相比椭圆曲线密码的额外开销微乎其微那为什么不顺手加上呢总体上Sophie Schmieg赞同这种立场。不过Sophie Schmieg对格密码的信任程度与对椭圆曲线的信任程度基本相同而且远高于对 RSA 的信任程度因此Sophie Schmieg并不认为混合方案在任何时候、任何地方都绝对、永远、超级无敌地不可或缺。但它们基本不增加成本所以为什么不用最终结论是没错混合方案是最佳选择而 IETF 的确也让人们能够这样做。已经有多份相关 RFC。要理解当前争议需要聚焦于两个与 TLS 有关的方案X25519MLKEM768又称 0x11EC和 MLKEM1024。前者是混合方案后者不是。与上述推理完全一致0x11EC 是 Chrome、Firefox 以及几乎所有当前支持 PQC 的 TLS 客户端所采用的默认密钥交换算法。那么 MLKEM1024 有什么意义事实证明有一个客户真的、真的非常讨厌混合方案只想在自己的所有系统中使用 ML-KEM1024而这个客户恰好就是 NSA。说实话这看不出这有什么问题。如果 NSA 想让自己的系统效率更低那是他们的选择。为什么会更低效由于 TLS 的工作方式存在一些特性客户端需要预测服务器可能接受什么。客户端可以多预测几种但 PQC 密钥相当壮硕同时发送多把 PQC 密钥会让握手变慢。预测错误同样会拖慢握手因为服务器会回应“再试一次这回请使用正确的公钥。”因此如果除了 NSA 以外的所有人都使用 X25519MLKEM768主要结果只是 NSA 的握手速度更慢。如前所述Sophie Schmieg不认为可以合理地说他们的握手安全性明显更低不过如果你真的认为 ML-KEM 已被攻破那么没错NSA 成功破坏了 IETF好让自己的系统变得更不安全同时不影响任何其他人。那就恭喜他们吧大概。10. 但 IETF 不是在积极劝阻人们使用混合方案吗没有。要理解这一点需要看看 TLS 密钥交换算法附带的两个标志Recommended推荐和 Mandatory To Implement强制实现MTI。Recommended 标志有三个取值Yes、No 和 Discouraged。Discouraged 用于已知被攻破的算法如 RC4。显然无论是否采用混合形式ML-KEM 都没有被确认攻破因此 Discouraged 并不适用。0x11EC 确实没有被标记为 Recommended主要是因为它最初只是一个实验性组合后来不知怎么就变成了所有人都在用的东西。尽管人们为了争论是否应该推荐它耗费了大量“数字墨水”但在 RFC 发布之前没有人更新这个标志。严格来说该 RFC 尚未发布不过其余流程基本只是手续而且这个标志不太可能改变。所以是的从技术上讲IETF 并未推荐一种混合算法。但你的浏览器和其他所有人都在使用它这一点也摆在那里。另外如果你担心的话NSA 选用的 MLKEM1024 同样没有被标记为推荐。补充编辑2026-06-30此后IETF 最终更新了 IANA 注册表将 0x11EC 的标志改为推荐。纯 MLKEM1024 仍然未被推荐。最后Mandatory To Implement 是 TLS 发明者精心设计的一个恶作剧目的是让邮件列表里出现更多争论。正如 David Benjamin 曾经说过的真正强制实现的唯一算法是“空算法”null algorithm因为 TLS 连接在协商出算法之前其初始状态就叫这个名字。除此之外至少Sophie Schmieg的建议是每当有人要求你支持一个你不想支持的 MTI 算法时就回复下面这张动图这个标志实际上毫无意义。哦对了上述两个算法都不是 MTI。11. 补充编辑加赛环节这篇博客发布后又收到了一些问题因此把它们补充在这里。11.1 IETF浏览器服务器的支持不会让我们遭受降级攻击吗不会。TLS 密钥协商可以抵御降级攻击。如果你的浏览器已经大约十年没有更新它或许容易受到降级至 SSL3 的攻击不过在这种情况下也不会再担心 PQC 了。更具体地说客户端支持的密码套件列表和服务器选择的密码套件都会加入密钥派生过程因此任何对这些选项的篡改都无法成功协商出 TLS 1.3 密钥。TLS 1.3 的降级保护甚至更有意思一台本可支持 TLS 1.3、却正在协商 TLS 1.2 的服务器需要设置一个特定的服务器随机值以向客户端表明它其实更希望使用 TLS 1.3。这些机制共同保护 TLS 1.3 的密钥协商因此额外加入客户端和服务器都不优先选择的密钥协商方案并不会导致它们最终被选中。11.2 但 NSA 为什么不喜欢混合方案最初没有写这一点因为只能告诉你 NSA 声称自己为何不喜欢混合方案并评估这些理由是否合理但无法告诉你这些是否是其真实原因。就其公开理由而言基本有三点反复出现担心组合爆炸导致互操作性问题。由于已经使用双重加密因此没有采用混合方案的必要。希望向世界其他地方——显然也包括美国政府内部的某些部门——表明 NSA 信任格密码。对于第一点他们的判断算是对了一半确实见到了巨大的组合爆炸因为人们拼命要求支持自己最喜欢的经典方案和最喜欢的 PQC 方案导致 LAMPS、CFRG 和 PGP 工作组定义了数量多到有些荒谬的混合方案。然而TLS 密钥协商并没有掉进这个陷阱。那里只有一种混合算法而且所有人似乎都喜欢并在使用它。需要注意的是NSA 主张不使用混合方案的 CNSA 2.0 指南早在 Kyber 最初的实验——后来逐渐演变成 0x11EC——之前就已经出现。对于第二点需要知道的是显然在处理高度敏感的信息时情报活动中已经普遍采用两次加密而且两层技术栈由完全不同的供应商实现。这很合理因为它既能防御内部威胁也能防范实现错误尽管代价是显著的性能损失不知道他们是不是根本没有对性能敏感的绝密任务。既然已经具备这种能力就可以让其中一层使用经典密码另一层使用 PQC从而构造混合密码而无须使用混合密钥交换。最后一点更多存在于字里行间也曾在一些较为非正式的对话中出现NSA 必须表明他们以及为其工作的那一大群数学家确实信任 PQC 算法。对其他任何组织来说采用混合方案可能只是看起来谨慎但如果 NSA 也这样做完全有理由怀疑他们是否真的足够信任 PQC认为它可以投入部署。通过强制使用纯格密码——但只用于自己的系统——他们用行动证明了自己的立场。最终这意味着如果格密码或 ML-KEM 真的被攻破面临风险的只会是他们自己的系统。初步看来这些都是合理的论据但它们当然不代表这一定就是该组织的真实动机。还要记住和任何大型组织一样NSA 内部未必存在一种统一意见可能只是不同个体各有不同动机。11.3 如果真的想给 MLWE 植入后门可以做到吗它会是什么样子MLWE 是 ML-KEM 背后的基础机制是对问题更一般化的数学描述而不是具体规定哪些字节放在哪里。如果想给它植入后门实际上确实可以。将以 RLWE——MLWE 的环版本——来说明二者原理相同但环的形式更容易写清楚。RLWE 的公钥a , t a,ta,t按t a s e tasetase计算其中a aa是任意数域整数而s , e s,es,e是短数域整数。要攻击它首先构造一个格其中包含所有满足0 a p q 0apq0apq的数域整数对( p , q ) (p,q)(p,q)然后在这个格中寻找最接近某个特解t a s ′ e ′ tasetas′e′的格向量。按照最近格点的定义这个最近格向量与特解( s ′ , e ′ ) (s,e)(s′,e′)之间的差很短而且它等于原始秘密或至少具有与原始秘密等价的能力。RLWE 的安全性来自这样一个事实当a aa随机选取时计算这个最近向量非常困难。因此如果想给 RLWE 植入后门只需不随机选择a aa而是先选择短的p , q p,qp,q使得在模该素数的意义下a − q / p a-q/pa−q/p。对任何外部观察者来说这类a aa与真正随机生成的a aa无法区分而攻击者却能攻破由它生成的任何公钥事实上另一种稍有不同的格密码方案 NTRU 正是以这种方式工作的。因此如果想给 MLWE 类算法植入后门只需要规定一个固定矩阵A AA它是 RLWE 中整数a aa的高维对应物并要求所有密钥生成都使用它。如果这个矩阵随机生成那么方案是安全的如果它包含后门那么除非整个格密码都已被攻破否则人们无法区分随机矩阵与带后门的矩阵——除非使用“袖中无物”变换如通过对公开种子做哈希来生成矩阵。但是这种做法无法通过前面提出的测试。矩阵A AA包含 4 到 16 个模 3329ML-KEM 所用素数的数域整数元素每个数域整数又包含 256 个元素数域阶因此这样的参数会给总数增加惊人的 12288 到 49152 位。这说明该测试能够成功发现此类问题。如果好奇ML-KEM 选择矩阵的方法非常简单每个公钥都有自己独立的随机矩阵。只有执行密钥生成的人可能给该矩阵植入后门但无论如何他们本来就拥有私钥。事实上他们甚至连这样做都不行因为 ML-KEM 通过只把一个派生种子放入公钥来压缩矩阵。11.4 密码学意义上的 NOBUS 后门真的是唯一选择吗已经证明这里不可能存在密码学意义上的 NOBUS 后门但它真的是唯一选择吗简而言之是的。让人困惑的是实现中可以存在复杂得多的后门因为任何测试都无法保证程序对所有查询都作出正确响应只能保证它对测试过的查询作出正确响应。然而算法并非如此。任何想植入算法的后门都必须写进算法本身的数学描述因为任何人都可以选择从零开始实现给定算法并期待它能够与其他实现互操作。这样一来只剩两种选择一种后门理论上任何人都能发现和利用也就是算法本身已被攻破另一种后门即使被发现也只有植入者可以利用也就是 NOBUS 后门。前一种会让算法同样不适合植入者自己使用因为这些算法会受到严格审查任何有兴趣的参与者都很可能迟早发现这种后门。第二种则必须包含某种具有足够熵的秘密否则攻击者只需遍历植入者可能掌握的所有值就能找出正确值换句话说这个后门会再次沦为第一种。补充编辑2026-07-01Sophie Schmieg 见过这种论证的一个变体会不会存在一种只影响一定比例密钥的破解方法也就是所谓的弱密钥问题掌握这种破解方法的国家行为者可以在密钥生成算法中添加额外代码使自己的实现避开该问题同时仍然能够破解数量不可忽略的通信流量。然而这同样不是 NOBUS 后门任何人只要阅读规范就有可能发现这个问题。这意味着它迟早会被其他对手或公众发现。一个只关心自身通信、并能高度控制所有生成和接收这些通信的端点的对手或许确实没有太强的动机公开这种弱点。然而由于安全算法此时已经不再遵循规范——即使外部看不出这种偏离——这个对手也无法再把实现外包给第三方因为第三方会按照原始且有缺陷的规范来实现。事实上由于密码结果通常与随机值不可区分不过对 ML-KEM 而言不是与均匀随机值不可区分他们完全可以在内部运行另一套不同的算法根本无须考虑该标准的防御性用途。更糟的是如果这个对手不能控制所有端点或者关心自身通信之外的流量也就是说对该标准存在任何防御利益那么它又会让其他人能够攻破这种加密。在除该对手之外的所有人都使用混合方案的情况下只要经典密码仍然安全基本不会发生什么。总体而言“如果存在一些只有 NSA 知道的弱密钥怎么办”这个问题与“如果 NSA 在精心上演一出偷梁换柱的戏码表面上宣传并外包大量 ML-KEM 工作实际上却秘密使用完全不同的东西怎么办”基本等价。参考资料[1] Sophie Schmieg 2025年11月27日博客 ML-KEM Mythbusting