新的 Bleichenbacher 记录:对 qDSA 签名的实际故障攻击

作者 Akira Takahashi,Mehdi Tibouchi,Masayuki Abe
时间 2018-04-29

本文优化了 Bleichenbacher 针对 ECDSA 和其他 Schnorr-like 签名方案的统计攻击方法,并使用偏向或部分暴露的随机数。 之前对 Bleichenbacher 攻击的方法在所谓的「范围缩减」阶段期间遭受了非常大的内存消耗。 基于 Schroeppel-Shamir 背包算法,使用经过仔细分析和高度可并行化的方法来减少此范围,从而克服了以前工作的内存障碍,同时在时间复杂度方面保持了实用的效率水平。

作为单独的贡献,本文在 Curve25519Montgomery 曲线上实例化时,针对 Renes 和 Smith 的 qDSA 签名方案提出了新的故障攻击,并且使用实际的故障实验验证了其中的一些关于 qDSA的AVR 微控制器实现 ChipWhisperer-Lite 评估板。 这些故障攻击使攻击者能够生成 2 位或 3 位已知随机数的签名。

结合以上两个贡献,本文能够通过将 Bleichenbacher 版本的攻击应用于这些错误的签名,来实现 qDSA 上的全密钥恢复。 使用依赖共享和分布式内存的混合并行模型,实现了高度可扩展的范围缩减算法的高效实现, 使得能够在合理的时间框架内完成 Bleichenbacher 在 Curve25519 的 252 位素数阶群组中的攻击,并使用相对适中的计算资源进行 3 位随机数暴露和 2 位随机数暴露的更困难的情况。 这两项计算,尤其是后者,在 Bleichenbacher 的攻击实施中创造了新的记录。

App

链闻 App

扫码下载

公众号 小程序