研究人员使用具有 379 年历史的算法破解在野外发现的加密密钥-零度博客

破解少数弱密钥只需要一秒钟。还有更多吗？

一位研究人员周一报告说，现在由科技公司 Rambus 拥有的旧软件生成的加密密钥足够弱，可以使用商品硬件立即破解。这一发现是一项调查的一部分，该调查还发现了一些野外的弱键。
Rambus 的一位代表表示，该软件来自 SafeZone Crypto Libraries 的基本版本，该版本由一家名为 Inside Secure 的公司开发，并被 Rambus 收购，作为其2019 年收购Verimatrix 的一部分。该版本在收购之前已被弃用，与该公司现在以 Rambus FIPS 安全工具包品牌销售的 FIPS 认证版本不同。
注意你的 Ps 和 Qs
研究员Hanno Böck表示，易受攻击的 SafeZone 库没有充分随机化用于生成 RSA 密钥的两个素数。（这些密钥可用于保护 Web 流量、shell 和其他在线连接。）相反，在 SafeZone 工具选择一个素数后，它会选择一个非常接近的素数作为形成密钥所需的第二个素数。
“问题是两个素数都太相似了，”博克在接受采访时说。“所以这两个素数之间的差异真的很小。” SafeZone 漏洞被跟踪为 CVE-2022-26320。
密码学家早就知道，用太接近的素数生成的 RSA 密钥可以用费马分解方法轻松破解。法国数学家皮埃尔·德·费马于 1643 年首次描述了这种方法。
费马算法的基础是任何奇数都可以表示为两个平方之间的差。当因子接近数字的根时，它们可以轻松快速地计算出来。当因素是真正随机的并因此相距甚远时，该方法是不可行的。
RSA 密钥的安全性取决于分解密钥的大合数（通常表示为 N）以导出其两个因数（通常表示为 P 和 Q）的难度。当 P 和 Q 公开时，它们组成的密钥被破坏，这意味着任何人都可以解密受密钥保护的数据或使用密钥来验证消息。到目前为止，Böck 只发现了少数容易受到因式分解攻击的密钥。一些密钥来自最初品牌为富士施乐但现在属于佳能的打印机。打印机用户可以使用密钥生成证书签名请求。密钥的创建日期是 2020 年或更晚。弱佳能密钥被跟踪为 CVE-2022-26351。
Böck 还在 SKS PGP 密钥服务器上发现了四个易受攻击的 PGP 密钥，通常用于加密电子邮件。与密钥绑定的用户 ID 暗示它们是为测试而创建的，因此他不相信它们正在使用中。
Böck 说他相信他发现的所有密钥都是使用未连接到 SafeZone 库的软件或方法生成的。如果为真，其他生成密钥的软件可能很容易使用 Fermat 算法破解。Böck 说，密钥是手动生成的，“可能是由知道这种攻击创建测试数据的人手动生成的，”这似乎是合理的。
研究人员通过搜索他可以访问的数十亿个公钥找到了这些密钥。他还查看了其他研究人员与他共享的密钥以及可通过证书透明计划获得的密钥。
ARS 视频
《银翼杀手》游戏总监 Louis Castle：延长采访
太近了不舒适
在解释该漏洞时，Böck写道：
费马分解算法的思想是两个大素数的乘积总是可以写成 N=(ab)(a+b)，a 是两个素数的中间，b 是中间到每个素数的距离素数。
如果素数接近，则 a 接近 N 的平方根。这允许从 N 的平方根开始猜测 a 的值，然后每轮将猜测值加一。
对于每个猜测，我们可以计算 b^2 = a^2 – N。如果结果是一个正方形，我们就知道我们猜对了 a。由此，我们可以计算出 p=a+b 和 q=ab。
费马最初在 1643 年的一封信中描述了这个算法。原始信件的文本可以在Oeuvres de Fermat的第 256 页中找到，可在 Internet 档案中找到。
他继续：
这怎么可能发生？
如果两个素数 p 和 q 接近，则 RSA 库很容易受到攻击。如果素数是独立随机生成的，那么 p 和 q 接近的可能性可以忽略不计。
然而，一个 RSA 库可能会实现一个有缺陷的密钥生成算法，如下所示：
生成随机数 X。
搜索 X 之后的下一个素数并将其用作 p。
搜索 p 之后的下一个素数并将其用作 q。
对于常见的 RSA 密钥大小，这会创建 p 和 q，其差异通常为数千或更低。这可以很容易地用费马的因式分解方法来解决。
素数需要多“接近”才能变得脆弱？
在我们的测试中使用常见的 RSA 密钥大小（2048 位），具有 100 轮的 Fermat 算法可靠地分解 p 和 q 相差高达 2^517 的数字。换句话说，可以说仅在低 64 字节（或大约一半大小）内不同的素数将很容易受到攻击。
直到 2^514，它几乎总能在算法的第一轮中找到分解。因此可以说 100 发是多余的；然而，该算法是如此之快，以至于它实际上并不重要。
如果素数是随机独立生成的，是否会意外生成易受攻击的密钥？
这几乎是不可能的。对于要“接近”的素数，它们至少在其高 500 位上必须相同。因此，发生这种情况的机会小于 1:2^500。
这些密钥的发现并不表明它们已经造成了很大的安全风险，特别是因为它们都没有用于特别敏感的应用程序。尽管如此，该发现仍有可能表明存在更大的问题，并且更易受攻击的密钥或密钥生成软件仍然存在。
拥有易受攻击的打印机的人应与制造商联系，以了解是否有固件更新可以替换弱键。Let’s Encrypt 还实现了一个检查器，该检查器将检测具有太靠近的素数的密钥。