简注 - Differential Fault Analysis on AES
Differential Fault Analysis, a.k.a DFA, 是一种侧信道分析手段。通过对二进制进行注入故障，将结果与原始运行时做差，在特定的平衡下可获得一轮的轮密钥。在最近的研究中，可被用来做白盒算法的密码分析。
简述
本文为如下工作的总结：
- https://blog.quarkslab.com/differential-fault-analysis-on-white-box-aes-implementations.html
- Differential Computation Analysis: Hiding Your White-Box Designs is Not Enough. Joppe W. Bos, Charles Hubain, Wil Michiels and Philippe Teuwen, CHES 2016
- 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攻击的目的。
执行过程
差分故障的攻击执行过程大致如下：
- 通过一定的工具，判断AES每一轮状态的位置
- 针对特定轮状态，以及特定故障点：
- 状态正常运行一遍，得到状态$O$
- 注入一个故障，运行，得到$O’$
- 利用两次执行的差，针对每个差对进行计算，得到candidate fault的集
- 多次插入故障，得到不同解集，求交集。最后得到固定的结果
详述
在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
- 双路冗余的DFA
- 等效轮的DFA
