使用多项式分解“短袖”RSA密钥

# "用多项式分解「短袖」RSA 密钥" 来源：https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/ 如果 RSA 私钥的比特严重偏向于 0 而不是随机生成，会发生什么？公钥的比特可能会偏斜到足以让我们在现实中检测到这些错误生成的密钥。我们与 badkeys 项目（https://badkeys.info/）的 Hanno Böck 合作，发现了数百个独特的密钥，这些密钥不仅具有这种属性，而且可以快速分解。我们还找到了导致其中许多密钥的漏洞，并分析了历史数据以追踪该问题随时间的变化。令人惊讶的是，0 比特的模式通常具有高度结构性，这使我们能够开发出一种强大的基于多项式的密码分析技术来利用这种模式。 图 1：现实世界中看到的两种具有重复 0 比特块的 RSA 模数模式。 这些「短袖」密钥——得名于 0 比特并未完全覆盖大整数的「肢干」——主要分为两种模式。模式 1 仍未解释清楚，但我们将模式 2 追溯到了旧版 CompleteFTP 文件传输软件的大整数代码中的类型不匹配错误。CompleteFTP 的这个错误还生成了易受攻击的短袖 DSA 密钥，我们从互联网扫描中恢复了 603 个独特的 RSA 私钥和 74 个 DSA 密钥。如果你在 2016 年 12 月至 2023 年 12 月期间使用 CompleteFTP 生成主机密钥，CompleteFTP 已经发布了一个工具（https://enterprisedt.com/downloads/KeyChecker.zip）来检查你的密钥是否需要重新生成。 ## 我们如何发现弱密钥 badkeys 项目是一个开源服务，用于检查公钥是否存在已知漏洞。在开发这个工具的过程中，Hanno 从公开来源收集了大量现实世界的密钥，包括证书透明度日志、全网 TLS 和 SSH 扫描、PGP 密钥等。通过搜索这个数据集以寻找异常稀疏的 RSA 模数，我们发现了大量具有图 1 所示模式的现实密钥。 两种模式都包含几个等间距的全零块，中间穿插着看似随机的数据。模式 1 出现在颁发给 Yahoo（https://crt.sh/?id=375717364）和 Verizon（https://crt.sh/?id=14320619439）等几个大型组织的证书的 CT 日志中，以及一些运行 NetApp 软件的设备上。幸运的是，这些证书已经过期，但我们仍然将我们的发现分享给了这些公司。我们想进一步了解是哪种产品生成了这些密钥，但没有收到回复。模式 2 出现在运行 EnterpriseDT 开发的 CompleteFTP 软件的 SSH 主机上。潜在的漏洞影响使用版本 10.0.0–12.0.0（2016 年 12 月–2019 年 3 月）生成的 RSA 密钥，以及使用版本 10.0.0–23.0.4（2016 年 12 月–2023 年 12 月）生成的 DSA 密钥。 这些漏洞只影响互联网上少数主机，但更有趣的结论是，独立的密码学实现以类似的方式失败了。更多的实现可能包含相同的错误，因此值得为这种特定类型的失败量身定制密码分析算法。 密码学算法经常需要数百或数千位长的整数，它们使用较小的机器尺寸值的数组来表示这些「大整数」，这些值称为*肢干*。如果我们将模式 1 解释为 128 位肢干的序列，或者将模式 2 解释为 32 位肢干的序列，那么重复的全零块对应于每个肢干中的一个零块。只有一小段连续的肢干填充了随机位，其余部分裸露在外，因此得名「短袖密钥」。 通过利用这些模数肢干中的数学结构，我们将分解整数的困难问题替换为分解多项式的简单问题。也就是说，我们取模数 n（未知因子 p 和 q），将其表示为一个系数很小的多项式 f_n(x)，将 f_n(x) 分解为 f_p(x) 和 f_q(x)，然后将这些因子转换回 p 和 q。在整数和多项式之间进行转换的技术很常见，包括进行快速多项式乘法（https://en.wikipedia.org/wiki/Kronecker_substitution），但遗憾的是，很少有资源描述（https://groups.google.com/a/mozilla.org/g/dev-security-policy/c/o2_vKIslDBc/m/iz7yNMy_AAAJ）如何将其用于快速整数分解。 具体来说，我们使用整数的基 B 表示中的数字来设置多项式的系数。在通常的基 10 表示中，这涉及将 10 的幂替换为 x 的幂，而将多项式转换回整数则涉及将 x 的幂替换为 10 的幂。数学上，整数 a = Σ_i a_i B^i 的基 B 表示对应于多项式 f_a(x) = Σ_i a_i x^i，而多项式求值 a = f_a(B) 则转换回整数。对于短袖密钥，基对应于肢干的大小，每个肢干中额外的零位将导致系数非常小的多项式。 图 2：具有 0 位块的整数可以表示为系数很小的多项式。 这种用多项式表示整数的方法很有用，因为求值乘积 f_a(B) * f_c(B) 等于乘积求值 (f_a * f_c)(B)。求值所做的只是将 x 替换为 B，因此在乘法之前或之后进行求值没有区别。加法也是如此。^(1)（https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/#fn:1） 对于一个具有 w 位肢干的短袖 RSA 模数 n，我们可以使用基 2^w 表示来找到一个系数非常小的多项式 f_n(x)。如果 f_p(x) 和 f_q(x) 的系数也非常小，那么 f_n(x) = f_p(x) * f_q(x)。注意，对于正确生成的素数因子，f_p(x) 和 f_q(x) 通常会有 w 位系数；这就是为什么这种攻击通常不成立的原因。 分解多项式（https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers）很容易，因此我们可以分解 f_n(x) 得到 f_p(x) 和 f_q(x)，然后在 2^w 处对这些因子求值得到 p 和 q。这是该攻击的基本版本，但我故意省略了一个分解这些现实模数所需的关键见解。完整的解释在本文末尾。 图 3：特殊形式的多项式可以被分解以揭示 RSA 私钥。 整数和多项式之间的对应关系使得分解这些特殊形式的模数变得容易，但有趣的是，它也有助于分解一般的 RSA 模数。通用数域筛法（GNFS）算法具有已知的最佳渐近性能，其第一步（https://members.loria.fr/PZimmermann/talks/rsa250-prace.pdf）是选择一个多项式 f_n(x) 和求值点 m，使得 f_n(m) = n。^(2)（https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/#fn:2） ## 逆向工程 CompleteFTP 漏洞 在将此技术应用于 Hanno 找到的密钥后，我们发现私因子确实是短袖的：素数因子具有大的、等间距的未设置比特块。具有第二种模式的主机的 SSH 横幅表明它们使用了 CompleteFTP 软件，因此我们逆向工程了一个试用版以确定是什么导致了易受攻击的密钥。 动态生成的 RSA 密钥没有短袖模式。^(3)（https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/#fn:3）因此我们使用了 ILSpy（https://github.com/icsharpcode/ilspy）工具来反编译演示二进制文件中的 .NET 代码。经过一些逆向工程后，我们发现了生成短袖密钥的错误。以下函数用所需位长度的随机生成值填充由 `bignumLimbs` 表示的大整数。看看你是否能发现问题。 `` public void genRandomBits(int bits) { // 计算肢干数量 int numLimbs = bits / 32; // 为 RNG 输出分配空间 byte[] array = new byte[numLimbs]; // 调用系统 RNG rngProvider.GetNonZeroBytes(array); // 复制到大数的肢干 Array.Copy(array, 0, bignumLimbs, 0, numLimbs); // 设置最高位以确保正确的位长度 bignumLimbs[numLimbs - 1] |= 0x80000000; // 存储长度 dataLength = numLimbs; } `` 图 4：CompleteFTP 中易受攻击的 genRandomBits 的反编译代码。为清晰起见，删除了几个分支，并添加了注释。 肢干的大小与 RNG 输出的大小不匹配！每个肢干需要 32 位的随机材料，但 `Array.Copy` 隐式地将 RNG 输出的每个 8 位元素转换为其自己的大整数肢干元素（https://learn.microsoft.com/en-us/dotnet/api/system.array.copy?view=netframework-4.8.1）。短袖密钥中的重复结构是因为该问题影响了每个肢干，而 0 位则是因为复制到每个肢干的值太小。这与被密码分析过的密钥模式完全匹配。 我们还弄清楚了为什么我们的动态测试没有生成损坏的密钥：`genRandomBits` 函数已编译在内，但在最新版本中不可达。旧版本使用自定义编写的密钥生成代码，该代码调用了这个易受攻击的函数，后来被重构以使用标准的 .NET 加密 API。 我们逆向工程了旧版本的 CompleteFTP 软件以查找对 `genRandomBits` 的其他调用，并发现 DSA 密钥生成也受到了影响。160 位的 DSA 私钥 x 以前是由这个函数生成的，公钥和参数包括生成器 g 和目标 y = g^x。私钥很容易恢复（https://en.wikipedia.org/wiki/Baby-step_giant-step），一旦我们知道要寻找什么，我们在现实中也发现了易受攻击的 DSA 密钥。^(4)（https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/#fn:4） 从 v12.1.0 开始，CompleteFTP 使用 .NET 的 `RSACryptoServiceProvider` 生成 RSA 密钥，从 v23.1.0 开始，它使用 `DSA.Create` API 生成 DSA 密钥。 ## 漏洞如何传播以及如何被遏制 使用标准库重构密钥生成代码的决定大大减轻了影响范围。这实际上反映在数据中。Nadia Heninger 教授有一个大型的历史和当代 SSH 扫描集合，我们曾用它来发现损坏的 SSH RSA 签名（https://eprint.iacr.org/2023/1711），因此我检查了它是否包含 CompleteFTP 主机。在每次 IPv4 全网扫描中，通常有数百个 CompleteFTP 主机，在将历史扫描与发布历史对齐后，趋势很明显。 图 5：随着时间的推移，运行易受攻击软件的 CompleteFTP 主机越来越少，但仍有相当一部分主机使用易受攻击的密钥。 从 2016 年 12 月引入 RSA 漏洞开始，具有易受攻击密钥的主机数量持续增加，一旦重写的 RSA 代码于 2019 年 3 月发布，这一趋势立即停止。然而，尽管此后运行受影响版本的主机数量稳步下降，但受影响密钥的比例已经趋于平稳，这与定期更新软件但只生成一次密钥的客户行为一致。 EnterpriseDT 团队在披露过程中非常积极响应。为了帮助这些用户，EnterpriseDT 于 2026 年 5 月 8 日发布了 CompleteFTP（https://enterprisedt.com/products/completeftp/）的 v26.1.0 版本；此更新自动检查系统是否使用了易受攻击的 RSA 或 DSA 密钥，并在需要重新生成密钥时提醒用户。他们还发布了独立的工具（https://enterprisedt.com/downloads/KeyChecker.zip）来实现相同的功能。此外，badkeys 网站（https://badkeys.info/）和独立工具（https://github.com/badkeys/badkeys）现在支持检测易受攻击的短袖 RSA 密钥。 总共，我们恢复了由易受攻击的 CompleteFTP 版本生成的 603 个独立 RSA 公钥和 74 个 DSA 密钥的私钥，以及 26 个具有未识别短袖模式的 RSA 密钥。我们的数据源严重偏向于 RSA SSH 密钥，因此这些数字并不反映实际流行程度。 ## 寻找更多短袖密钥 不幸的是，我们没有关于短袖模式 1 的更多信息，也不知道该漏洞是否扩展到其他密钥类型。利用*不规则*间隔的已知比特块（包括 ECDSA^(5)（https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/#fn:5）和 RSA^(6)（https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/#fn:6））的密码分析算法很常见，但短袖泄漏的规则间隔增加了新的结构，并且可能存在能够利用此属性的强大变体算法。如果这种类型的泄漏出现在两个独立的 RSA 实现中，那么很可能还有更多短袖密钥的例子。 在这种情况下，漏洞的影响是有限的，但它展示了实际研究的力量。利用已知漏洞来启发更强大的算法，然后使用这些算法发现新漏洞的过程，在密码分析中形成了一个强大的反馈循环。它帮助我们理解真实密码系统在实践中是如何失败的，并且只有通过观察系统如何被攻破，我们才能学会如何让它们更安全。 ## 致谢 感谢 Nadia Heninger 将我介绍给 Hanno，并允许我为这个项目使用 SSH 扫描数据。这些扫描包括来自 Censys 和密歇根大学的历史数据（由 Zakir Durumeric 提供），以及来自 Kevin He 和 George Sullivan 的当代数据和分析脚本。 ## 附录 最后这一部分是为那些想要实现该攻击或编写攻击证明的人准备的。我在主体文章中省略了关键细节，但以下引导性问题将帮助你填补这一空白。首先，这里是供你分解的完整模数。它们是合成生成的，但遵循与现实中密钥相同的模式。n_2 的因子是通过在一个循环中调用 `genRandomBits(1024)` 直到结果为素数而生成的。 `` n_1=0xc889f7ef523b08e400000000000000014d2ee8284c7a03c000000000000000012c16eeaeab96ddc8000000000000000201036d671407a06600000000000000022f743377005a840d0000000000000001e8e3c0efdd8054ba000000000000000306ee98c677dfdf190000000000000002de525d2b1011ceae0000000000000424455c59eec3a0654500000000000003f8d762d68bcbe8cc3a00000000000000d31291f9aaa7e9a7d60000000000000337a82a59342aadff570000000000000295c495b3690a69b66c00000000000000d9c5e55654e9b14cba000000000000040f0f0f7d3bfdce03d6000000000000026b89ac77db000000000000000000036a77 n_2=0x40000049000014ac8000900e00010ec58000b17b8001e0720001be890002169f80029cd5000349190003cd4480037c8c000397660003b28300041021000418cb00058a210004c2708004924980053b8780051cbd8005ebe80006bb27800765e6800651478007f62300073949800860950008614d800863988008d103800884c100099a260009a6d90009578f0007e843000 ``