DES的DPA攻击过程

一般智能卡只使用DES算法对数据进行加密，不采取其他防御措施，所以安全性不高。本博文主要研究智能卡使用DES算法对数据进行加密的具体细节，并针对加密过程中的关键步骤给出DPA攻击的设计思路。

DES数据加密过程

智能卡对密码算法的要求是功耗低、运算速度快，结合几个加密算法的优缺点考虑，目前智能卡使用的主流算法仍然是DES算法，所以本文研究的是针对使用DES算法智能卡的DPA攻击。

在DES算法16轮操作的每一轮中，都会进行8次S盒查表操作。S盒的输入为6bit的密钥与R寄存器6bit数据进行异或的值，输出为4bit。这8个S盒共32bit的输出被重组，然后与L寄存器的32bit数据进行异或。接着，将L和R的值进行交换。每一轮处理数据的方式都相同，下图是DES算法一轮加密的详细过程。

在上图中，输入明文M（64bit）经过IP置换后分成左半部分$L_0(32bit)$和右半部分$R_0(32bit)$，$R_0$经扩充之后变成 48 bit，与子密钥$k_1$经异或运算后进入S盒进行压缩得到32bit，该32bit与 $L_0$进行异或得到 $R_1$，同时原来的 $R_1$形成新的$L_2$， 即：
$$L_1=R_0$$
$$R_1=L_0\oplus f(R_0,k_1)$$
其中，f函数包括了明文扩充E,数据异或、数据压缩S，和置换P这几个步骤，是加密过程中的非线性操作步骤。

智能卡DES的DPA攻击过程

DPA攻击主要包括两大步骤：波形采集和数据分析。详细步骤如下：
（1）给出N组不同的明文，对其进行加密，测量出在DES运算过程中第一轮的功耗曲线{$P_i|i\le i\le N$}。
（2）选择DES算法第一轮第一个S盒运算输出值的某一个比特作为选择函数 D， 以 b 表示该比特值，称为中间值，可以看出b仅仅取决于密钥K和明文M，所以可表示为 b=D(K,M)。攻击时可以对相关的值进行猜测，得到相应的中间值。根据推导得到中间值b将N组功耗曲线分为两类；
S 1 = { P i ∣ D i = 1 , 1 ≤ i ≤ N } S_1 = \{P_i|D_i=1, 1\leq i \leq N\} S1?={Pi?∣Di?=1,1≤i≤N}
S 0 = { P i ∣ D i = 0 , 1 ≤ i ≤ N } S_0 = \{P_i|D_i=0, 1\leq i \leq N\} S0?={Pi?∣Di?=0,1≤i≤N}
（3）分别计算集合 $S_1$和 $S_0$的功耗平均值：
$$A_1=\frac{1}{|S_1|}\sum _i{S}_1(i)$$
$$A_0=\frac{1}{|S_0|}\sum _i{S}_0(i)$$
其中$|S_0|$和 $|S_1|$分别表示对应集合的功耗曲线的数目，则：
$$|S_0|+|S_1|=N$$
（4）求二者的差值：
$$T=A_1?A_0$$
若猜测得到的密钥是正确的，那么对功耗曲线的分类也是正确的，也就是说所有 $b=1$的曲线都分到了 $S_1$ 中而剩下的 $b=0$的曲线都分到了$S_0$中，那么差值曲线$T$中会出现明显的峰值；若猜测得到的密钥是不正确的，那么$T$的峰值会非常小甚至没有。

利用中间值对集合进行分类相当于使用随机函数对集合进行分类，根据数理统计理论知识可知，利用随机函数把某个集合一分为二后，当这两个子集合中的元素个数趋于无穷大时，两个子集合的平均值之差将趋于0，若采集得到的功耗曲线样本足够多，数据功耗转换模型选择恰当，外部噪声足够小，那么使用差分统计分析方法可以得到含有峰值的差分功耗曲线，峰值所在位置即为正确密钥位置。按照上述方法推导计算，就可得到第一个S盒的子密钥。重复操作可得到剩余7个S盒的子密钥，也就得到了实际使用的48bit轮密钥，剩下的8bit用穷举法猜测得到，最终恢复56bit密钥。这样密钥猜测的工作量为 $2^6\times 8+2^8=768$，远小于直接使用暴力破解密钥的工作量$2^{256}=7.2\times 10^{16}$。详细算法如下图所示：

DPA攻击最重要的就是选择与密钥相关的功耗分类函数D，针对不同的算法和不同的实现，选取的D函数也有所不同。但是DPA也存在局限性，即，D函数只选取某一个S盒中的某一位作为中间值，而没有考虑到其他S盒的输出对其的影响。在实际测试工作中，可采用CPA进行分析，即选择S盒输出结果的多位作为中间值，并计算和猜测子密钥对应的多位输出值的汉明重量，然后通过统计学的办法得到和实际功耗曲线的汉明重量的相关性，进一步得到结果。这种方法的优点是攻击效果明显，噪声干扰小。

DPA攻击的完整步骤如下：
输入：M;//明文集合，每个明文为 M i , i ∈ { 1 , ? ? , s i z e ( M ) } M_i, i\in \{1,\cdots ,size(M)\} Mi?,i∈{1,?,size(M)}
?? ?wave;//功耗曲线集合，每条曲线为 w a v e i , i ∈ { 1 , ? ? , s i z e ( M ) } wave_i, i\in \{1,\cdots ,size(M)\} wavei?,i∈{1,?,size(M)},与明文 $M_i$对应。
???D；//基于S盒输出的选择函数，选定中间值并对功耗曲线进行分类的标准， D ∈ { 0 , 1 } D \in \{0,1\} D∈{0,1}
输出： Code； // 密文集合，每个密文为 $Cod{e}_i$;
???$Se{t}_i$;// 每一个子密钥对应的功耗曲线分类集， i ∈ { 0 , 1 } i \in \{0,1\} i∈{0,1}
???$\Delta \overline{P}$；功耗曲线集合对应的平均功耗差值
???$k_1{S}_i$;//第一轮加密对应的每个S盒的子密钥块， i ∈ { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } i \in \{1,2,3,4,5,6,7,8\} i∈{1,2,3,4,5,6,7,8}

1. for j = 1 to 8 do //对8个S盒循环计算相应的子密钥块
2. ?? for i=0 to 63 // 对应于第j个S盒的6bit子密钥块的64种情况循环计算
3. ????for m = 1 to size(M) do // 对每个明文的功耗曲线进行分类
4. ??????if D == 0
5. ???????? S e t 0 = { S e t 0 , W a v e i } Set_0 = \{Set_0,Wave_i\} Set0?={Set0?,Wavei?}
6. ??????else
7. ???????? S e t 1 = { S e t 1 , W a v e i } Set_1 = \{Set_1,Wave_i\} Set1?={Set1?,Wavei?}
8. ??????end
9. ????end
10. ????$\Delta \overline{P}=\overline{P_0}?\overline{P_1}$
11. ??end
12. end

对DES算法的第一轮加密操作的第一个S盒执行上述算法，如果第i个猜测的子密钥块对应的平均功耗差$\Delta \overline{P}$有明显的峰值，则i即是该S盒的正确子密钥块；如果没有峰值则继续进行下一个子密钥块（i=i+1）,一直重复，直到找到正确子密钥块。8个S盒都执行相同的步骤，则可以恢复所有子密钥块。找到8个子密钥块($6\times 8=48$bit)后，按照轮密钥生成算法逆向推导，再对剩下的8bit进行穷举，即可恢复正确的56bit密钥。