简注 - Differential Fault Analysis on AES

简注 - Differential Fault Analysis on AES

Differential Fault Analysis, a.k.a DFA, 是一种侧信道分析手段。通过对二进制进行注入故障,将结果与原始运行时做差,在特定的平衡下可获得一轮的轮密钥。在最近的研究中,可被用来做白盒算法的密码分析。

简述

本文为如下工作的总结:

  1. https://blog.quarkslab.com/differential-fault-analysis-on-white-box-aes-implementations.html
  2. Differential Computation Analysis: Hiding Your White-Box Designs is Not Enough. Joppe W. Bos, Charles Hubain, Wil Michiels and Philippe Teuwen, CHES 2016
  3. Differential Fault Analysis on A.E.S. Pierre Dusart, Gilles Letourneux and Olivier Vivolo, ACNS 2003, pages 293-306

DFA攻击试图通过注入错误-与对照组求差求得轮密钥中的字节。针对一个状态注入时,每注入一个故障,可以扰乱4个轮密钥字节。重复此过程,就可以得到所有的状态轮密钥。DFA并不是最近才出现的一个新技术,而配合Deadpool,利用Tracer跟踪加密器整个运行过程,从中得到running trace, 经过计算可以针对性地得到攻击的某一环。获得一轮的密钥,是DFA攻击的目的。

执行过程

差分故障的攻击执行过程大致如下:

  1. 通过一定的工具,判断AES每一轮状态的位置
  2. 针对特定轮状态,以及特定故障点:
    1. 状态正常运行一遍,得到状态$O$
    2. 注入一个故障,运行,得到$O’$
    3. 利用两次执行的差,针对每个差对进行计算,得到candidate fault的集
    4. 多次插入故障,得到不同解集,求交集。最后得到固定的结果

详述

在AES(AES-128)的DFA中,最主要的是得到最后一轮$K_{10}$的值。因为一轮可以倒推出所有轮,这样就相当于得到了密钥。其主要内容就是在最后两轮MixColumn之间插入一个错误,观察错误的扩散情况,然后求值。从FIPS192知道,最后三轮的过程大约为:

  • SubBytes
  • ShiftRows
  • MixColumns
  • AddRoundKey $K_8$

  • SubBytes

  • ShiftRows
  • MixColumns
  • AddRoundKey $K_9$

  • SubBytes

  • ShiftRows
  • AddRoundKey $K_{10}$

由于故障插入位于两次MixColumn之间,所以只有一轮MixColumn会被执行。最终这个错误会被扩散到4个字节上。为方便讨论,我们在第9轮的MixColumn前插入故障,观察其扩散情况。以插入故障的运行过程为实验组,与未插入故障的运行为对照组。
插入故障$X$。插入前后的对比:
$$
\begin{pmatrix} A & E & I & M \\ B & F & J & N \\ C & G & K & O \\ D & H & L & P \end{pmatrix} \text{和} \begin{pmatrix} X & E & I & M \\ B & F & J & N \\ C & G & K & O \\ D & H & L & P \end{pmatrix}
$$
在此之后,实验组(插入故障组)与对照组将会同样进行以下操作:

  • MixColumns
  • AddRoundKey $K_9$

  • SubBytes

  • ShiftRows
  • AddRoundKey $K_{10}$

Mixcolumn后:
$$
\begin{pmatrix} 2A+3B+C+D & \cdots & \cdots & \cdots \\ A+2B+3C+D & \cdots & \cdots & \cdots \\ A+B+2C+3D & \cdots & \cdots & \cdots \\ 3A+B+C+2D & \cdots & \cdots & \cdots \end{pmatrix} \text{and} \begin{pmatrix} 2X+3B+C+D & \cdots & \cdots & \cdots \\ X+2B+3C+D & \cdots & \cdots & \cdots \\ X+B+2C+3D & \cdots & \cdots & \cdots \\ 3X+B+C+2D & \cdots & \cdots & \cdots \end{pmatrix}
$$
加入第9轮密钥:
$$
\begin{pmatrix} 2A+3B+C+D+K_{9,0} & \cdots & \cdots & \cdots \\ A+2B+3C+D+K_{9,1} & \cdots & \cdots & \cdots \\ A+B+2C+3D+K_{9,2} & \cdots & \cdots & \cdots \\ 3A+B+C+2D+K_{9,3} & \cdots & \cdots & \cdots \end{pmatrix} \text{and} \begin{pmatrix} 2X+3B+C+D+K_{9,0} & \cdots & \cdots & \cdots \\ X+2B+3C+D+K_{9,1} & \cdots & \cdots & \cdots \\ X+B+2C+3D+K_{9,2} & \cdots & \cdots & \cdots \\ 3X+B+C+2D+K_{9,3} & \cdots & \cdots & \cdots \end{pmatrix}
$$

SubBytes:
$$
\begin{pmatrix} S(2A+3B+C+D+K_{9,0}) & \cdots & \cdots & \cdots \\ S(A+2B+3C+D+K_{9,1}) & \cdots & \cdots & \cdots \\ S(A+B+2C+3D+K_{9,2}) & \cdots & \cdots & \cdots \\ S(3A+B+C+2D+K_{9,3}) & \cdots & \cdots & \cdots \end{pmatrix} \text{and} \begin{pmatrix} S(2X+3B+C+D+K_{9,0}) & \cdots & \cdots & \cdots \\ S(X+2B+3C+D+K_{9,1}) & \cdots & \cdots & \cdots \\ S(X+B+2C+3D+K_{9,2}) & \cdots & \cdots & \cdots \\ S(3X+B+C+2D+K_{9,3}) & \cdots & \cdots & \cdots \end{pmatrix}
$$

ShiftRows:
$$
\begin{pmatrix} S(2A+3B+C+D+K_{9,0}) \qquad \cdots \qquad \cdots \qquad \cdots \\ \cdots \qquad \cdots \qquad \cdots \qquad S(A+2B+3C+D+K_{9,1})\\ \cdots \qquad \cdots \qquad S(A+B+2C+3D+K_{9,2}) \qquad \cdots \\ \cdots \qquad S(3A+B+C+2D+K_{9,3}) \qquad \cdots \qquad \cdots \end{pmatrix}\\ \text{and} \\\begin{pmatrix} S(2X+3B+C+D+K_{9,0}) \qquad \cdots \qquad \cdots \qquad \cdots \\ \cdots \qquad \cdots \qquad \cdots \qquad S(X+2B+3C+D+K_{9,1})\\ \cdots \qquad \cdots \qquad S(X+B+2C+3D+K_{9,2}) \qquad \cdots \\ \cdots \qquad S(3X+B+C+2D+K_{9,3}) \qquad \cdots \qquad \cdots \end{pmatrix}
$$

AddRoundKey $K_{10}$:
$$
\begin{pmatrix} S(2A+3B+C+D+K_{9,0})+K_{10,0} \qquad \cdots \qquad \cdots \qquad \cdots \\ \cdots \qquad \cdots \qquad \cdots \qquad S(A+2B+3C+D+K_{9,1})+K_{10,13}\\ \cdots \qquad \cdots \qquad S(A+B+2C+3D+K_{9,2})+K_{10,10} \qquad \cdots \\ \cdots \qquad S(3A+B+C+2D+K_{9,3})+K_{10,7} \qquad \cdots \qquad \cdots \end{pmatrix}\\ \text{and}\\ \begin{pmatrix} S(2X+3B+C+D+K_{9,0})+K_{10,0} \qquad \cdots \qquad \cdots \qquad \cdots \\ \cdots \qquad \cdots \qquad \cdots \qquad S(X+2B+3C+D+K_{9,1})+K_{10,13}\\ \cdots \qquad \cdots \qquad S(X+B+2C+3D+K_{9,2})+K_{10,10} \qquad \cdots \\ \cdots \qquad S(3X+B+C+2D+K_{9,3})+K_{10,7} \qquad \cdots \qquad \cdots \end{pmatrix}
$$

So,未修改过的结果为$O_0$, 修改过的结果为$O_0’$。(第0个字节,为0)
$$
O_0 = S(2A+3B+C+D+K_{9,0})+K_{10,0} \\
O_0’ = S(2X+3B+C+D+K_{9,0})+K_{10,0}
$$

作差:($GF(2^8)$,加即为减)

$$
O_0 + O’_0 = S(2A+3B+C+D+K_{9,0})+K_{10,0} + S(2X+3B+C+D+K_{9,0})+K_{10,0} \\
O_0 + O’_0 = S(2A+3B+C+D+K_{9,0}) + S(2X+3B+C+D+K_{9,0})
$$

在后排的Sbox操作构造两个$2A$:
$$
O_0 + O’_0 = S(2A+3B+C+D+K_{9,0}) + S(2X+\mathbf{2A+2A}+3B+C+D+K_{9,0})
$$

就可以得到:
$$
Y_0=2A+3B+C+D+K_{9,0}\\
Z=A+X
$$
原式转换为:
$$
O_0 + O’_0 = S(Y_0) + S(2Z+Y_0)
$$
其他被影响的字节也类似:
$$
O_7 + O’_7 = S(Y_1) + S(3Z+Y_1) \\
Y_1 = 3A+B+C+2D+K_{9,3} \\
O_{10} + O’_{10} = S(Y_2) + S(Z+Y_2) \\
Y_2 = A+B+2C+3D+K_{9,2} \\
O_{13} + O’_{13} = S(Y_3) + S(Z+Y_3) \\
Y_3 = A+2B+3C+D+K_{9,1} \\
$$
这4个等式联立。针对Z,只有给定的故障集合$x\in X$才能联立。针对给定的故障X,存在一个求K解集。多次插入不同故障,最后求得交集,就是所需要的单一值。

问题

注入点问题

以chow’s implementation为例。如果所有的表被集成起来,那就无法区分出哪里是MixColumn了。无法从MixColumn注入。但是,根据Dusart et al的说明,只要注入点在两轮MixColumn之间,就可以完成。
对于这个问题,作者菲利普·吐温用了对key file进行注入的方法来避开。也就是说,作者并没有直接把注入作用于二进制。它针对的地址空间是文件的地址空间。通过改写其中的一些字节,实现静态注入

倘若是从第8轮完毕的state开始进行注入,

初始状态:
$$
\left(\begin{matrix}A & E & I & M\\B & F & J & N\\C & G & K & O\\D & H & L & P\end{matrix}\right)
$$

SubBytes:
$$
\left(\begin{matrix}S{\left(A \right)} & S{\left(E \right)} & S{\left(I \right)} & S{\left(M \right)}\\S{\left(B \right)} & S{\left(F \right)} & S{\left(J \right)} & S{\left(N \right)}\\S{\left(C \right)} & S{\left(G \right)} & S{\left(K \right)} & S{\left(O \right)}\\S{\left(D \right)} & S{\left(H \right)} & S{\left(L \right)} & S{\left(P \right)}\end{matrix}\right)
$$

ShiftRows:
$$
\left(\begin{matrix}S{\left(A \right)} & S{\left(E \right)} & S{\left(I \right)} & S{\left(M \right)}\\S{\left(F \right)} & S{\left(J \right)} & S{\left(N \right)} & S{\left(B \right)}\\S{\left(K \right)} & S{\left(O \right)} & S{\left(C \right)} & S{\left(G \right)}\\S{\left(P \right)} & S{\left(D \right)} & S{\left(H \right)} & S{\left(L \right)}\end{matrix}\right)
$$

Mixcolumns:
$$
\left(\begin{matrix}K_{9} + 2 S{\left(A \right)} + 3 S{\left(F \right)} + S{\left(K \right)} + S{\left(P \right)} & … & … & … \\ K_{9} + S{\left(A \right)} + 2 S{\left(F \right)} + 3 S{\left(K \right)} + S{\left(P \right)} & … & … & …\\ … & … & … & … \\ … & … & … & …\end{matrix}\right)
$$
这就是State 9.
简单带过一下,final state的state[0]为:
$$
K_{10} + S{\left(K_{9} + 2 S{\left(A \right)} + 3 S{\left(F \right)} + S{\left(K \right)} + S{\left(P \right)} \right)}\\
K_{10} + S{\left(K_{9} + 2 S{\left(X \right)} + 3 S{\left(F \right)} + S{\left(K \right)} + S{\left(P \right)} \right)}
$$
两式相减:
$$
S{\left(K_{9} + 2 S{\left(A \right)} + 3 S{\left(F \right)} + S{\left(K \right)} + S{\left(P \right)} \right)} + S{\left(K_{9} + 2 S{\left(X \right)} + 3 S{\left(F \right)} + S{\left(K \right)} + S{\left(P \right)} \right)}
$$
设:
$$
Y_0 = K_9 + 2S(A)+ 3 S(F) + S(K) + S(P) \\
Z = S(A) + S(X)
$$

同样地,对其他状态推导,只有符合特定条件的$S(X)$才能使得扩散的4个等式联立。

对WBAC-AES的影响

内编码失效

以chow’s implementation为例,包括encoding和Mixing Bijections。
在encoding方面:
$$
T’ = g \circ T \circ f^{-1}
$$
对此类白盒实现的注入,相当于对lookup-table的注入。修改lookup-table的一个字节,其作用也可以在最后的结果反映出来。这并不影响以上描述的注入方式。

TODO

  1. 双路冗余的DFA
  2. 等效轮的DFA
# crypto

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×