RSA签名故障分析 - Trail of Bits博客

Aditi Gupta
2018年8月14日
密码学, 实习项目, Manticore

今年春夏，作为Trail of Bits的实习生，我研究了RSA签名中的故障攻击建模。我研究了使用中国剩余定理(CRT)优化RSA签名的过程，并通过诱导计算故障来揭示私钥。我在底层而非数学层面分析了故障攻击。在分析了一个玩具程序和mbed TLS的RSA实现后，我识别出了内存中翻转后会泄露私钥的位。

使用RSA-CRT的签名过程

通常，RSA签名操作使用以下算法：s=m^d (mod n)。其中，s代表签名，m代表消息，d代表私钥指数，n代表公钥。这个算法是有效的，但当涉及的数字增加到安全所需的大小时，计算开始变得极其耗时。因此，许多密码学库使用中国剩余定理(CRT)来加速解密和签名。CRT将单个大计算拆分为两个较小的计算，然后将它们的结果拼接在一起。

给定私钥指数d，我们计算两个值dp和dq：dp=d (mod (p-1)) 和 dq=d (mod (q-1))。

然后我们计算两个部分签名，每个使用这两个数字中的一个；第一个部分签名s1等于m^dp (mod p)，而第二个s2等于m^dq (mod q)。计算p (mod q)和q (mod p)的逆元，最后将两个部分签名组合成最终签名s，其中s=(s1qqInv)+(s2ppInv) (mod n)。

故障攻击

当两个部分签名中的一个（假设是使用q计算的s2）不正确时，问题就出现了。这种情况确实会发生。

组合两个部分签名会得到一个错误的最终签名。如果签名正确，我们可以通过比较原始消息和s^e (mod n)来验证它，其中e是公钥指数。然而，对于错误的签名，s^e (mod p)仍然等于m，但s^e (mod q)不会。

从这里，我们可以说p是s^e-m的一个因子，但q不是。因为p也是n本身的一个因子，攻击者可以取n和s^e-m的最大公约数来提取p。n除以p就是q，攻击者现在拥有了两个私钥。

故障玩具程序

我首先用C语言编写了一个简单的玩具程序，使用中国剩余定理进行RSA签名。这个程序没有填充也没有检查，使用教科书式的RSA来签名相当小的数字。我使用调试器手动修改其中一个部分签名，并产生错误的最终签名。我写了一个Python程序来使用这个错误的签名计算私钥，并成功解密了另一个加密消息。我尝试在签名过程的不同阶段改变数据，看看是否仍然可以提取私钥。当我熟练手动执行这些故障攻击后，我开始自动化这个过程。

使用Manticore翻转位

我使用Binary Ninja查看程序的反汇编，并识别出我感兴趣的数据的内存位置。当我尝试求解私钥时，我知道该在哪里查找。然后，我安装并学习了如何使用Manticore，这是Trail of Bits开发的二进制分析工具，我将用它来进行故障攻击。

我写了一个Manticore脚本，它会遍历内存的每个连续字节，通过翻转该字节中的一个位来改变指令，并执行RSA签名程序。对于每次没有导致崩溃或超时的执行，我使用输出来尝试提取私钥。我通过尝试成功解密另一个消息来检查它们是否正确。利用所有这些数据，我生成了一个CSV文件，记录了每次位翻转的中间和最终结果，包括部分签名、私钥以及私钥是否准确。

图1：在玩具程序中查找可故障地址的代码摘录

结果

我总共测试了938次位翻转，发现其中45次（4.8%）成功产生了正确的私钥。近55%导致崩溃或超时，意味着程序未能创建签名。大约31%没有改变部分签名。

图2：分析代码的输出

图3：玩具程序的位翻转结果

这种自动化在开发类似漏洞的利用时提供了巨大的加速，因为一旦你简单地向Manticore描述了漏洞，你就会得到一个全面的利用方法列表。如果你能够引入一些不精确的故障（例如使用Rowhammer），这尤其有用，因为你可以找到位的集群，当翻转时，会泄露私钥。

故障mbed TLS

一旦我有了玩具程序的位翻转结果文件，我就寻找一个真实的密码学库来攻击。我选择了mbed TLS，这是一个主要用于嵌入式系统的实现。因为它比我写的程序复杂得多，我花了一些时间查看mbed TLS的源代码，试图理解RSA签名过程，然后编译它并使用Binary Ninja查看反汇编的二进制文件。

mbed TLS和我的玩具程序之间的一个关键区别是，使用mbed TLS的签名是填充的。我试图建模的故障攻击仅适用于确定性填充，其中给定的消息总是产生相同的填充值，而不适用于概率方案。尽管mbed TLS可以实现各种不同的填充方案，但我研究了使用PKCS#1 v1.5的RSA签名，这是一个确定性方案，替代了更复杂、随机的PSS填充方案。再次，我使用调试器定位目标数据。当我知道我将从哪些内存位置读取时，我开始故障其中一个部分签名并产生错误的签名。

然而，我很快意识到，有一些运行时检查旨在防止我试图进行的那种故障攻击。特别是，两个检查如果失败，会停止执行并输出错误消息，而不创建签名。我使用调试器跳过这些检查，产生我寻找的错误签名。

有了错误的签名和所有公钥数据，我能够复制我在玩具程序中使用的过程，成功提取私钥。

自动化攻击

就像我对玩具程序所做的那样，我开始尝试自动化故障攻击，并识别会泄露私钥的位翻转。为了加速过程，我写了一个GDB脚本，而不是使用Manticore。我找到了位翻转，可以让我绕过通常会阻止创建错误签名的两个检查。我使用GDB改变了这两个内存指令。在一个与玩具程序相同的过程中，我还翻转了给定内存地址中的一个位。然后我使用Python循环遍历内存的每个字节，调用这个脚本，并尝试提取私钥，再次通过尝试解密已知消息来检查它们是否正确。我收集了求解的私钥，并将所有位翻转的结果写入CSV文件。

图4：在mbed TLS中查找可故障位置的代码摘录

图5：从Python代码调用的GDB脚本摘录，用于在mbed TLS中诱导故障

结果

我测试了566次位翻转，所有这些都在执行签名操作的mbed TLS代码部分内。结合确保检查通过的两个位翻转，我发现其中28次——近5%——泄露了私钥。约55%未能产生签名。

图6：mbed TLS的位翻转结果

这种分析在真实程序上有效的事实令人兴奋，但不幸的是，夏天的时间不够，我没能在“真实世界”中测试它。尽管如此，能够输入真实的TLS代码并获得对其故障攻击的全面描述是令人兴奋的，并为未来的研究提供了迷人的可能性。

结论

我喜欢在Trail of Bits工作。我更好地理解了密码学，并熟悉了安全工程师使用的一些工具。这是一次美妙的经历，我兴奋地期待明年在卡内基梅隆大学的课程和项目中应用我学到的一切。

如果你喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容
使用RSA-CRT的签名过程
故障攻击
故障玩具程序
使用Manticore翻转位
结果
故障mbed TLS
自动化攻击
结果
结论
近期文章
构建安全消息传递很难：对Bitchat安全辩论的 nuanced 看法
使用Deptective调查你的依赖项
系好安全带，Buttercup，AIxCC的评分回合正在进行中！
成熟你的智能合约超越私钥风险
Go解析器中意想不到的安全陷阱
© 2025 Trail of Bits。
使用Hugo和Mainroad主题生成。