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

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

图片[1]-研究人员使用具有 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 还实现了一个检查器,该检查器将检测具有太靠近的素数的密钥。

THE END
喜欢就支持一下吧
点赞2251 分享
10款精品软件推荐!完全免费开源,超级实用,看到就是赚到!! | 零度解说-零度博客
Copilot 一款基于 GPT-4 的人工智能编程助手!  完全免费-零度博客

Copilot 一款基于 GPT-4 的人工智能编程助手! 完全免费

微软的 Copilot 是一款基于 GPT-4 的人工智能编程助手,它可以帮助开发者更高效地完成各种编程任务。自从 OpenAI 在2023年推出 GPT-4 以来,Copilot 也得以大幅提升其功能和性能。 官方链接:【点...
admin的头像-零度博客admin
2.7W+1538
联想笔记本 BIOS 漏洞的修复方法-零度博客

联想笔记本 BIOS 漏洞的修复方法

  联想官方驱动下载:https://newsupport.lenovo.com.cn/driveDownloads_index.html   联想笔记本 BIOS 漏洞 联想安全公告: LEN-73440 潜在影响:权限升级 影响范围:联想特定 CVE ...
admin的头像-零度博客admin
1.7W+2250
Google 为可在各种设备上运行的 Android 应用打开了大门!-零度博客

Google 为可在各种设备上运行的 Android 应用打开了大门!

谷歌试图让开发人员更容易创建以某种方式跨一系列设备连接的 Android 应用程序。在一篇博文中,谷歌解释说它正在推出一个新的跨设备软件开发工具包 (SDK),其中包含开发人员使他们的应用程序在 ...
admin的头像-零度博客admin
1.7W+2250
终于来了!微软推出 DALL-E 3 图片生成功能,免费用!输入中文就能生成精美的AI图片 | 零度解说-零度博客

终于来了!微软推出 DALL-E 3 图片生成功能,免费用!输入中文就能生成精美的AI图片 | 零度解说

https://youtu.be/EX7SrTaCqQo ============== 必备环境+Stable diffusion及提示词下载 :https://www.freedidi.com/8474.html
admin的头像-零度博客admin
1.7W+1682
Llama 3 大模型最简单的下载方法!实现本地可视化部署-零度博客

Llama 3 大模型最简单的下载方法!实现本地可视化部署

Llama 3 模型的发布彰显了Meta在开源AI领域的决心和影响力。我们有理由期待,Llama 3将为自然语言处理、机器学习等AI前沿技术的发展注入新动力。 在线使用:【链接直达】 不仅可以智能对话,也可...
admin的头像-零度博客admin
2.2W+2177
密码末日即将来临!NIST 推出新的加密标准以做好准备-零度博客

密码末日即将来临!NIST 推出新的加密标准以做好准备

决策将对许多公司产生约束力,并改变他们保护数据的方式。   在不远的将来——也许只有十年,没有人确切知道多久——随着量子计算的出现,保护你的银行交易、聊天信息和医疗记录免遭窥探的...
admin的头像-零度博客admin
1.6W+2251
Microsoft to do 最好用的【代办事项】管理工具!  微软出品,完全免费-零度博客

Microsoft to do 最好用的【代办事项】管理工具! 微软出品,完全免费

如果要零度推荐一款,最好用,效率最高的代办事项管理工具,那么微软出品的 Microsoft to do 无疑是最佳选择!不仅完全免费,而且兼容性极好,又轻量级,支持跨平台使用,无论是在Windows、Mac...
admin的头像-零度博客admin
1.2W+4543
免费注册Amazon云服务器!并搭建网站、博客等-零度博客

免费注册Amazon云服务器!并搭建网站、博客等

  1.Amazon免费注册链接:【点击前往】 2.安装docker : curl -fsSL https://get.docker.com | sh 3.安装docker-compose: sudo apt-get install composer   4.创建wordpress文件夹并...
admin的头像-零度博客admin
1.4W+1528