G.O.S.S.I.P 阅读推荐 2023-11-20 RSA公钥之殇

在G.O.S.S.I.P编辑部看来，密码学研究领域最富有创造力的研究人员之一当属Nadia Heninger教授，这位女性密码学人在过去的10年期间发现了大量现实世界中的密码学安全问题，而且绝非那种只在教科书上才会出现的理论缺陷，而是同我们所在的宇宙实体息息相关的问题。今天要介绍的就是她所领导的研究组的最新作品——Passive SSH Key Compromise via Lattices

要介绍这篇论文，我们需要坐上时光机回到上个世纪，先看看1996年发生了什么。首先大家是否还记得我们曾经在2022年2月8日介绍过一本神奇的密码学书籍，致敬了知名的荷兰数学家、密码学家Arjen Klaas Lenstra，而正是这位Lenstra在1996年写下了Memo on RSA signature generation in the presence of faults这样一份技术备忘录，指出在某些特殊的情况下（例如被宇宙射线轰击、功率波动和温度升高/降低），电子计算机在运行中可能发生非常微小而隐蔽的错误（比如有一个bit发生了翻转），而假设这种错误又恰好影响到了RSA的签名过程，攻击者只需要得到这样一个在错误条件下生成的签名，就可以恢复私钥（这里的前提是要使用中国剩余定理也就是CRT的快速实现，并且使用了确定性的填充方式如PKCS#1 v1.5，如果你不太懂括号里面说的是什么，赶紧去复习密码学）！

当然，大家曾经以为这种“伽马射线撞电路”的事情，可能比彗星撞地球还要让人觉得不可能发生，但是我们的世界早已经不是只有3台计算机的时代了，密码学在几乎每台计算机上都在使用，应用实在是太广泛，这种故障攻击（fault attack）已经真正成为了一种安全威胁：2015年，Redhat的工程师在公司的blog上介绍了一个真实的案例——由于现实中一些网络设备本身的计算硬件不太稳定，再加上使用的密码学库和配置容易受到故障攻击的影响，导致它们使用的私钥惨遭分解：

https://www.redhat.com/en/blog/factoring-rsa-keys-tls-perfect-forward-secrecy
https://people.redhat.com/~fweimer/rsa-crt-leaks.pdf

随后，我们又进入了“Rowhammer”时代，随着安全研究人员了解并开始利用越来越高性能的DRAM的不稳定性——大量的读写可能会导致邻近区域的bit翻转，这种硬件故障一下子和1996年的概念性攻击结合在一起，大大增加了现实中的威胁！这时候就需要Nadia Heninger研究团队登场了，他们在2022年的USENIX Security论文Open to a fault: On the passive compromise of TLS keys via transient errors中报告了针对整个公开互联网上使用TLS协议时可能遇到的故障攻击，以及恢复TLS相关密钥的可能性：

https://www.usenix.org/conference/usenixsecurity22/presentation/sullivan

尽管这篇论文已经发表，但是大家仍然觉得，像IPsec和SSH这种协议的密钥协商，和TLS协议相比多了一些计算要素（包括一个Diffie-Hellman shared secret），即使产生了一个错误的RSA签名，如果攻击者只是监听而非主动参与，就不太可能攻击成功。然而今天介绍的这篇论文（当然还是Nadia Heninger研究团队）打破了这个安全的幻觉——通过利用CHES 2009上的一项针对故障RSA签名的攻击技术（Fault Attacks on RSA Signatures with Partially Unknown Messages @ CHES 2009），即使是被动监听的攻击者也可以单凭一个故障RSA签名来恢复私钥。基于这项技术，Nadia Heninger研究团队再接再厉，对52亿条SSH连接记录进行了分析，发现其中存在超过59万个故障RSA签名，其中超过4900个故障签名可以用来恢复私钥，而作者最终确实把这些故障签名所涉及的所有189个RSA公钥都成功分解并获取了私钥！

今天的阅读推荐并不打算带大家去重温RSA（及其快速实现）签名、填充和SSH协议的握手细节，这些都交给读者自己去学习（最好自己动手写一遍代码，增强理解）。同时也不会介绍CHES 2009那篇论文的攻击方法，留给有兴趣的CTF出题人和赛棍们去动手~ 我们直接进入到实验部分。

作者从2022年10月26日到2023年8月22日主动用ZMap对全网的22端口（嗯我们的VPS也难逃一劫）进行了扫描，然后用ZGrab2的ssh module模块发起SSH握手请求（只进行了–host-key-algorithms=ssh-rsa请求），一次全网扫描大概会收集到2200万个（22端口开放的）主机，完成大约1600万次SSH握手请求，其中能够收集到3-5百万个RSA host key的签名。同时，作者还和University of Michigan以及Censys公司合作，分析了2015年4月到2020年6月间记录的一些历史数据。下图显示了所有这些记录中，使用的密码算法的分布情况，可以看到RSA依然是大家会广泛使用的。

通过进一步分析，作者发现这些SSH连接所使用的RSA密钥长度从2018年开始就逐渐开始朝着2048-bit过渡：

而随着时间的推移，有问题的故障签名逐渐变少了，

除了针对SSH的主动探测，作者也对IPSec（包括IKEv1和IKEv2）的服务器进行了扫描，扫描的结果见下面的表格：

目前IKEv1版本的IPSec服务器比较少，作者在扫描过程中并没有发现太多的故障签名（只有83个），也没有能够找到可以帮助分解公钥的签名。而对于IKEv2版本的IPSec服务器，作者总共收集到了65002个故障RSA签名，其中并没有发现因为PKCS#1 v1.5填充错误导致公钥可分解的情况，而对于RSA的公钥错误（也就是p和q可能错了1个bit）导致的故障签名，作者发现在2023年1月6日收集到的579个故障签名中，有576个可以用于恢复私钥，这其中有一半都是来自于Watchguard VPN产品（说明这个产品质量堪忧啊）。

总之，本文更像是一篇IMC论文，但是它揭示出的现实中的密码学安全风险让我们反思，理论要扎根于现实的土壤才能结出健硕的果实啊！

---

论文：https://eprint.iacr.org/2023/1711.pdf

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2023-11-20 RSA公钥之殇