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

Aditi Gupta

2018 年 8 月 14 日

密码学, 实习项目, Manticore

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

CRT-RSA 签名流程

标准 RSA 签名算法为：s=mᵈ (mod n)，其中 s 代表签名，m 为消息，d 是私钥指数，n 为公钥。虽然有效，但当数字达到安全所需规模时计算耗时极长。因此许多密码库使用 CRT 加速解密和签名——将大型计算拆分为两个较小计算后再合并结果。

给定私钥指数 d，我们计算两个值：

dₚ = d mod (p-1)

d_q = d mod (q-1)

接着计算两个部分签名：

s₁ = mᵈᵖ mod p

s₂ = mᵈᵟ mod q

计算 p mod q 和 q mod p 的逆元后，最终签名通过公式组合：

s = (s₁·q·qInv + s₂·p·pInv) mod n

故障攻击原理

当两个部分签名之一（假设是使用 q 计算的 s₂）出错时问题显现。组合部分签名将产生错误最终签名。若签名正确，可通过比较原消息与 sᵉ mod n（e 为公钥指数）验证；但故障签名会使 sᵉ mod p 仍等于 m，而 sᵉ mod q 不等。

由此可知 p 是 sᵉ-m 的因子而 q 不是。由于 p 也是 n 的因子，攻击者可取 n 和 sᵉ-m 的最大公约数提取 p。n 除以 p 即得 q，此时攻击者已获得全部私钥。

玩具程序故障注入

我首先用 C 语言编写了使用 CRT 进行 RSA 签名的简易程序。该程序无填充无校验，采用教科书式 RSA 处理较小数字。通过调试器手动修改部分签名产生故障签名，并用 Python 程序基于故障签名计算私钥成功解密另一加密消息。尝试在签名过程不同阶段篡改数据后，开始自动化此过程。

使用 Manticore 进行位翻转

通过 Binary Ninja 查看程序反汇编代码，定位目标数据内存地址。随后使用 Trail of Bits 开发的二进制分析工具 Manticore 执行故障攻击：编写脚本遍历连续内存字节，翻转特定位后执行 RSA 签名程序。对未崩溃或超时的执行，尝试用输出提取私钥并通过解密验证准确性。最终生成包含每次位翻转的中间结果、私钥及准确性的 CSV 文件。

实验结果

测试 938 次位翻转中，45 次（4.8%）成功产生正确私钥。近 55%导致崩溃或超时，31%未改变部分签名。

此类自动化极大加速了漏洞利用开发——仅需向 Manticore 描述漏洞即可获得完整利用方案列表。这对不精确故障（如 Rowhammer）尤其有用，可找到翻转即泄露私钥的位簇。

攻击 mbed TLS

获得玩具程序位翻转结果后，我开始寻找真实密码库攻击目标。最终选定主要用于嵌入式系统的 mbed TLS。因其复杂度远高于自制程序，我先阅读源码理解 RSA 签名流程，再编译并用 Binary Ninja 分析反汇编二进制文件。

与玩具程序的关键差异在于 mbed TLS 使用填充签名。我研究的故障攻击仅适用于确定性填充（给定消息总是生成相同填充值），而非概率方案。虽然 mbed TLS 支持多种填充方案，我选择使用 PKCS#1 v1.5（复杂随机化 PSS 填充方案的确定性替代品）。同样使用调试器定位目标数据后开始故障部分签名。

但很快发现存在运行时检查阻止此类攻击：两项检查若失败将停止执行并报错而不生成签名。通过调试器跳过检查后成功产生目标故障签名。借助故障签名和公钥数据，成功复现玩具程序的私钥提取流程。

自动化攻击

如同对玩具程序的操作，我开始自动化故障攻击并识别可泄露私钥的位翻转。为加速过程，改用 GDB 脚本替代 Manticore：找到可绕过两项防护检查的位翻转，用 GDB 修改对应内存指令，再在特定内存地址翻转一位。通过 Python 循环遍历内存字节，调用脚本并尝试提取私钥（通过解密已知消息验证准确性），最终将结果写入 CSV 文件。

实验结果

在 mbed TLS 签名代码段的 566 次位翻转测试中，结合确保检查通过的两个位翻转，发现 28 次（近 5%）泄露私钥，约 55%未能产生签名。

此类分析对真实程序有效令人兴奋，但遗憾的是未能在夏季结束前进行"真实世界"测试。不过，输入真实 TLS 代码并获得完整故障攻击描述的能力，为未来研究开辟了广阔可能性。

结论

在 Trail of Bits 的工作经历令我获益匪浅：深化了对密码学的理解，熟悉了安全工程师的常用工具。这段宝贵经验将助力我在卡内基梅隆大学明年的课程和项目。如果你喜欢本文，请分享至：

[Twitter] [LinkedIn] [GitHub] [Mastodon] [Hacker News]

页面目录

• CRT-RSA 签名流程

• 故障攻击原理

• 玩具程序故障注入

• 使用 Manticore 进行位翻转

• 实验结果

• 攻击 mbed TLS

• 自动化攻击

• 实验结果

• 结论

• 近期文章

我们构建了 MCP 始终需要的安全层

挖掘废弃硬件中的零日漏洞

EthCC[8]内幕：成为智能合约审计师

用 Vendetect 实现大规模代码复制检测

构建安全消息系统之难：关于 Bitchat 安全辩论的深度解析

© 2025 Trail of Bits.

使用 Hugo 和 Mainroad 主题生成。更多精彩内容 请关注我的个人公众号 公众号（办公 AI 智能小助手）公众号二维码

办公AI智能小助手