RSA签名故障分析 - The 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签名故障分析：利用位翻转泄露私钥

本文详细分析了RSA签名中使用中国剩余定理(CRT)优化时的故障攻击漏洞。通过玩具程序和mbed TLS实现，研究发现特定内存位翻转可导致私钥泄露，并展示了使用Manticore和GDB自动化攻击的过程。