RSA定时攻击及盲防

Question

我对RSA的定时攻击有点困惑。我知道攻击利用了模幂(平方和乘)有依赖于键的分支这一事实。也就是说，如果位$k$ of $x$为$1$，则指数化的持续时间要比位为$0$的时间长。

但是，执行如何也依赖于消息(输入)？

Kocher提出的解决方案是通过在消息中添加一个随机值来“致盲”。因此，执行时间不能再与输入相关联了，但是这有什么帮助呢？如果指数位是$1$，那么执行不是更慢了吗？

提前感谢！

Answer 1

但是，执行如何也依赖于消息(输入)？

实际上，(至少)有两种潜在的定时攻击。

一个是你建议的，时间(至少对于这个简单的指数算法来说)与秘密指数的汉明重量有关。然而，正如你所观察到的，秘密指数并不依赖于密文。

但是，攻击者可能试图利用第二种可能的时间变化。假设您计算了一个中间值$C^{k} \bmod N$，而该值恰好非常小。然后，取决于您使用的bignum库，下一个操作(特别是如果它是正方形的话，可能是乘法的话)可能会意外地快速进行，而时间变化会告诉您$k$是否是一个中间指数(这会给出一些秘密指数的比特)。

现在，在实践中，它不太好用；在$C$ \bmod N$很小的情况下，很难计算$C^k值(如果实现使用$C^k，则需要$C^k \bmod p、q$较小的值。

因此，您最终要做的是传递随机的$C$值，寻找处理得出乎意料的快的值，并从中推断出事情。

Kocher提出的解决方案是通过在消息中添加一个随机值来“致盲”。

我很确定你误会了。首先，向消息添加一个随机值会产生一个不相关的结果。

如果保罗提出了任何建议(他提出了许多建议；我不记得具体是从他那里听到的)，他可能提出了以下两项建议之一：

• 将随机值乘以消息。也就是说，选择一个随机值$r$，计算$r^e \bmod n$和$r^{-1} \bmod n$；然后多个$c‘= (r^e \bmod n) \cdot c$；在$c'$上执行RSA操作，得到$t’=RSA_{私有}(c‘)$，然后计算出最终的$t = t’\cdot (r^{-1} bmod)$。RSA操作是在等量值上完成的，因此不存在任何基于消息的侧通道泄漏。
• 向指数添加一个随机值。也就是说，(我假设您在这里做CRT )选择一个随机值$r$，并计算$t_p =(CRT p)^{d_p + r(p-1)} \bmod $(与$q$类似)。除了几个低阶位外，您使用的指数是随机的(这可以通过始终选择$p \equiv q \equiv 3 \pmod 4$来实现)。

另一方面，Paul绝不会将上述任何一项作为严重泄漏的模块指数例程的唯一保护。使用幂分析(由Paul发明)，您可以从单个跟踪中获得指数；这将挫败这些对策中的任何一个。