安全错误攻击

   近年来基于错误的密码分析（fault-based cryptanalysis）已成为检测智能卡（Smartcard）安全的重要因素。这种基于错误的密码分析，假设攻击者可以向智能卡中导入一定数量的、某种类型的错误，那么智能卡会输出错误的信息，攻击者有可能利用这些错误信息揭露出嵌入在智能卡中的秘密参数（如密钥）。为此，一些研究者提出了通过检验计算结果的正确性来防止这种攻击，即如果检验结果不正确，那么拒绝输出，从而使攻击者无法得到想要的错误信息。
   然而，仅通过检验计算结果来防止这种攻击的方法不可行。以RSA中模指数运算为例，提出了一种所谓基于安全错误的对RSA的攻击。该攻击可以攻破RSA的一些实现算法，即使那些算法中加入了检验计算结果的步骤。

密码实现

   RSA 算法中经常用到的是模幂运算 $M^d\mathrm{mod}N$。其中将私钥表达成二进制的形式，即， d = ∑ i = 0 n − 1 d i 2 i , d i ∈ { 0 , 1 } d = \sum_{i=0}^{n-1}d_i 2^i, d_i\in\{0,1\} d=∑i=0n−1​di​2i,di​∈{0,1}。从而在密码芯片中对应R-L比特算法实现。
  在算法1中，当 $d_i=1$ 时，算法执行一次模乘运算($A\cdot B^2\mathrm{mod}N$)和一次摸平方运算（$B^2\mathrm{mod}N$）。当 $d_i=0$时，算法只需执行一次摸平方运算。
   其中，RSA 用到模乘运算 $R=A\cdot B\mathrm{mod}N$。将A表达成$2^t$进制的形式， A = ∑ j = 0 m − 1 A j ( 2 t ) j A j ∈ { 0 , 1 , ⋯ , 2 t − 1 } , m = ⌈ n / t ⌉ A = \sum_{j=0}^{m-1}A_j(2^t)^j A_j\in\{0,1,\cdots,2^t-1\},m=\lceil n/t \rceil A=∑j=0m−1​Aj​(2t)jAj​∈{0,1,⋯,2t−1},m=⌈n/t⌉。则 模乘运算的结果 $R$ 可用以下表达式来实现。
$$R=((\cdots ((A_{m-1}B)2^t+A_{m-2}B)2^t+\cdots +A_{1}B)2^t+A_{0}B)\mathrm{mod}N$$

算法1 R-L 比特模幂
输入： $M$, $d=(d_{n-1},\cdots ,d_0{)}_2$, $N$
输出：$A=M^d\mathrm{mod}N$
1.1 $A⟵1$; $B⟵M$
1.2 for $i$ from $0$ to $n-1$
1.3   if ($d_i=1$) then $A⟵A\cdot B\mathrm{mod}N$
1.4  $B⟵B^2\mathrm{mod}N$
1.5 endfor

算法2 底数为 $2^t$的模乘运算
输入：$A,B,N$
输出： $R=A\cdot B\mathrm{mod}N$
2.1 $R⟵0$
2.2 for $j$ from $m-1$ downto $0$
2.3    $R⟵(R{2}^t+A_{j}B)\mathrm{mod}N$
2.4 endfor

   将算法1和算法2合并起来，那么R-L比特模幂运算可写成如下实现过程。

算法3
输入： $M$, $d=(d_{n-1},\cdots ,d_0{)}_2$, $N$
输出：$A=M^d\mathrm{mod}N$
3.1 $A⟵1$; $B⟵M$
3.2 for $i$ from $0$ to $n-1$
3.3   if ($d_i=1$) then
3.4     $R⟵0$
3.5     for $j$ from $m-1$ downto $0$
3.6        $R⟵(R{2}^t+A_{j}B)\mathrm{mod}N$
3.7     endfor
3.8     $A⟵R$
3.9   endif
3.10  $R⟵0$
3.11   for $j$ from $m-1$ downto $0$
3.12      $R⟵(R{2}^t+A_{j}B)\mathrm{mod}N$
3.13   endfor
3.14  $B⟵R$
3.15 endfor

基于安全错误的攻击

   考虑针对算法3进行攻击，攻击者攻击目的是要找到运算中隐藏着的密钥 $d$。
   所谓安全错误，是指在算法中导入1比特或几比特错误，但这一错误可能并不会影响最终的模幂运算结果。
   例如，在 $d_i=1$时的第$i$ 次循环中，向寄存器 $A_k$ 中导入错误，且满足 $k>j$，那么，由于正确的$A_k$ 在先前的子循环中已经使用了，所以算法三第3步的子循环不会计算出错，即，$R$计算正确。而紧接着$A⟵R$使得先前导入的错误被清除。于是算法三在以下的计算都不会受到影响。从而使得最终的计算结果是正确的。把这样导入的错误称之为安全错误。换言之，安全错误发生了却并没有带来错误的计算结果。
   但是，导入的安全错误并不总是安全的。在一些情况下安全错误也会使得计算结果不正确。例如，在 $d_i=0$的第$i$次循环中，向$A_k$ 中导入错误，且满足 $k>j$，这时导入的错误就会使得最后的计算结果出错。因为，当 $d_i=0$时，整个循环将跳过第3步，从而使得导入的错误不能得到纠正，并带入到下面的循环中。
   通过上面分析得到以下结论。当 $d_i=1$时，导入的安全错误不会影响计算结果的正确性；当 $d_i=0$时，导入的安全错误会使得计算结果不正确。
   基于以上的分析，攻击者分别对 $d$的每一位$d_i$进行攻击。为了攻击第 $i$ 比特，在算法第$i$次循环中导入安全错误。如果算法三输出正确结果，那么由以上分析，得$d_i=1$；如果算法三输出错误结果，或者算法三通过附加的检测出计算结果错误，从而拒绝输出，那么攻击者可知 $d_i=0$。
   这就是说，即是智能卡检测出错误，并拒绝输出，攻击者仍可利用这一点得到 $d_i$ 的值。所以说，对算法三实现模幂运算，通过检验计算结果的方式不能防止基于安全错误的攻击。但，通过加指数掩码，每一次进行模幂运算时，在指数$d$上增加随机数，可防止该攻击。