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

背景

在密码学实践中，随机数生成的质量直接决定了密钥的安全性。然而，当 RSA 私钥的比特位并非随机生成，而是严重偏向于 0 时，会发生什么？这种偏差可能导致公钥中的比特位出现可检测的模式，从而让攻击者识别出这些在野外（即互联网上）错误生成的密钥。

由 Hanno Böck 领导的 badkeys 项目是一个开源服务，旨在检查公钥是否存在已知漏洞。该项目从公共来源（包括 Certificate Transparency 日志、全网 TLS 和 SSH 扫描、PGP 密钥等）收集了大量真实世界的密钥数据。研究人员与 Hanno Böck 合作，在该数据集中搜索异常稀疏的 RSA 模数，发现了几百个独特的“短袖”（short-sleeve）密钥。这些密钥不仅具有特定的比特位偏差模式，而且可以被快速分解。

更令人惊讶的是，这些 0 比特的模式往往具有高度结构化的特征，这使得研究人员能够开发一种强大的基于多项式的密码分析技术来利用这一模式。

核心内容

“短袖”密钥的发现与分类

研究人员发现了两种主要的“短袖”密钥模式。这种称呼源于 0 比特并没有完全覆盖大整数的“肢体”（limbs，即构成大整数的较小机器字长值块），使得部分肢体暴露在外。

1. 模式 1：出现在 Certificate Transparency (CT) 日志中，涉及 Yahoo、Verizon 等大型组织颁发的证书，以及运行 NetApp 软件的一些设备。幸运的是，这些证书大多已过期，但研究人员已将发现告知相关公司。目前该模式的成因尚未完全解释。
2. 模式 2：出现在运行 CompleteFTP 软件（由 EnterpriseDT 开发）的 SSH 主机上。研究人员通过逆向工程找到了导致此模式的 Bug。

基于多项式的分解技术

RSA 算法通常需要使用数百或数千位的大整数。在计算机实现中，这些大整数通常表示为较小机器字长值的数组，称为“肢体”（limbs）。

• 结构特征：如果将模式 1 解释为 128 位肢体序列，或将模式 2 解释为 32 位肢体序列，重复的零块对应于每个肢体中的一个零块。只有肢体的一小部分被随机比特填充，其余部分未覆盖，因此被称为“短袖密钥”。
• 数学转换：利用这种数学结构，研究人员将困难的整数分解问题转化为简单的多项式分解问题。
  • 设模数为 $n$，未知因子为 $p$ 和 $q$。
  • 将 $n$ 表示为具有小系数的多项式 $f_n(x)$。
  • 将 $f_n(x)$ 分解为 $f_p(x)$ 和 $f_q(x)$。
  • 将这些因子转换回整数 $p$ 和 $q$。
• 具体方法：
  • 利用整数在基 $B$ 下的表示法来设置多项式的系数。例如，在基 $2^w$ 表示法中（$w$ 为肢体位数），整数 $a = \sum_i a_i B^i$ 对应于多项式 $f_a(x) = \sum_i a_i x^i$。
  • 对于“短袖”密钥，由于每个肢体中有多余的零比特，生成的多项式具有异常小的系数。
  • 如果 $f_p(x)$ 和 $f_q(x)$ 也具有异常小的系数，则 $f_n(x) = f_p(x) * f_q(x)$ 成立。
  • 由于多项式分解相对容易，研究人员可以分解 $f_n(x)$ 得到 $f_p(x)$ 和 $f_q(x)$，然后在 $2^w$ 处求值得到 $p$ 和 $q$。

注：虽然 General Number Field Sieve (GNFS) 算法也利用多项式，但本文所述方法针对的是这种特定类型的故障，具有更高的效率。

CompleteFTP 漏洞逆向工程

针对模式 2，研究人员逆向工程了 CompleteFTP 的试用版，以确定导致脆弱密钥生成的原因。

• 动态测试失败原因：动态生成的 RSA 密钥没有表现出“短袖”模式。这是因为最新的版本中，genRandomBits 函数虽然被编译但不可达。旧版本使用自定义编写的密钥生成代码，调用了这个有漏洞的函数，后来重构为使用标准的 .NET 加密 API。
• Bug 定位：
  • 使用 ILSpy 工具反编译 .NET 代码。
  • 发现 bignumLimbs 函数在填充大整数时存在类型不匹配。
  • 具体错误：每个肢体需要 32 位的随机材料，但 Array.Copy 隐式地将 RNG（随机数生成器）输出的每个 8 位元素复制到大整数肢体的各自元素中。
  • 后果：这导致每个肢体复制的值过小，从而产生了重复的结构和大量的 0 比特。
• 影响范围：
  • RSA 密钥：受影响的版本为 10.0.0 – 12.0.0（2016 年 12 月 – 2019 年 3 月）。
  • DSA 密钥：受影响的版本为 v10.0.0 – 23.0.4（2016 年 12 月 – 2023 年 12 月）。
  • DSA 漏洞：160 位的 DSA 私钥 $x$ 也是由这个有漏洞的函数生成的。

实际发现与修复

• 研究人员从互联网扫描中恢复了 603 个独特的 RSA 私钥 和 74 个 DSA 私钥。
• CompleteFTP 已发布工具，供用户在 2016 年 12 月至 2023 年 12 月期间生成主机密钥的用户检查其密钥是否需要重新生成。

关键要点

• 密钥生成缺陷：RSA 私钥的比特位若严重偏向 0，会形成可检测的结构化模式，导致密钥极易被分解。
• 多项式分解技术：通过将大整数转换为具有小系数的多项式，可以将困难的整数分解问题转化为简单的多项式分解问题，从而快速破解此类脆弱密钥。
• CompleteFTP 漏洞根源：在旧版 CompleteFTP 软件中，大整数肢体大小与随机数生成器（RNG）输出大小之间的类型不匹配，导致复制了过小的随机值，从而产生“短袖”密钥。
• 受影响范围：
  • RSA 密钥：CompleteFTP 版本 10.0.0 – 12.0.0。
  • DSA 密钥：CompleteFTP 版本 v10.0.0 – 23.0.4。
  • 其他模式：模式 1 涉及 Yahoo、Verizon 等组织的证书及 NetApp 设备，但成因尚不明确。
• 独立实现失败：不同独立实现的密码学库出现了类似的失败模式，表明需要针对此类特定故障定制密码分析算法。

意义与影响

1. 密码实现的安全性警示： 尽管受影响的主机在互联网上占少数，但这一事件揭示了独立密码学实现在随机数处理和类型转换上可能犯下的相似错误。它提醒开发者，在使用大整数库时，必须严格检查内存拷贝、类型转换和随机数填充逻辑，避免隐式转换导致的数据截断或填充错误。

2. 密码分析方法的创新： 研究人员展示的“整数-多项式”转换技术不仅用于破解特定的“短袖”密钥，还为一般 RSA 模数的分解提供了新的视角。虽然 GNFS 是已知渐近性能最好的算法，但针对特定结构缺陷的多项式分解方法展示了在特定条件下的高效性。

3. 对现有基础设施的影响：

   • **Complete