陈佳哲 , 李贺鑫 , 王蓓蓓
中国信息安全测评中心, 北京 100085

收稿日期：2016-12-14
基金项目：国家自然科学基金资助项目（61402536，61402252，61202493）
作者简介：陈佳哲(1985-), 男, 副研究员。E-mail:chenjz@secemail.cn


摘要：侧信道攻击，特别是差分功耗分析（differential power analysis，DPA）是对芯片中运行的分组密码算法进行安全性分析的主要手段之一。该文主要研究针对硬件实现的SM4算法的DPA攻击。合理地对明文进行选择，可以使SM4线性变换层有变化的输入比特尽可能少地影响输出比特，从而对硬件实现的SM4算法进行有效的侧信道攻击。通过分析线性变换层的比特关系，该文发现了选择明文模型下8个比特依赖关系。在此基础上，将这些比特依赖关系结合已有的比特关系，建立分析模型、更充分地利用轮输出的比特信息，对现有的SM4选择明文DPA攻击进行了改进。实验结果表明：该方法能有效提高SM4算法选择明文DPA攻击的成功率。
关键词：分组密码算法侧信道分析SM4算法选择明文差分功耗分析(DPA)
Improved chosen-plaintext DPA on block cipher SM4
CHEN Jiazhe, LI Hexin, WANG Beibei
China Information Technology Security Evaluation Center, Beijing 100085, China


Abstract: Since differential power analysis (DPA) is one of most important side-channel attacks on block ciphers implemented in chips, this paper revisits the DPA attack on hardware-implemented SM4. Reasonably choosing the plaintexts minimizes the affection of the variable input bits on the output bits, of the linear transformation of SM4, which leads to effective side-channel attacks on SM4. This paper deduces 8 bit-relationship in the chosen-plaintext setting by going into the linear transformation of SM4. Incorporating the bit-relationship with the known ones, this paper improves the previous chosen-plaintext DPA attacks on SM4, by proposing an analyzing module that makes better use of the side-channel information of the round-output bits. Experimental results show that the proposed manner improves the success rate of the chosen-plaintext DPA attacks on SM4.
Key words: Block ciphersside-channel analysisSM4 cipherchosen-plaintextdifferential power analysis(DPA)
差分功耗分析(differential power analysis, DPA)^[1]是对芯片中分组密码实现安全性的最主要威胁之一。因此，在评估芯片安全性的时候，其运行的分组密码算法的DPA安全性是衡量的要素之一。DPA由Kocher等^[1]首先提出，该攻击基于中间变量一个比特的均值距离(distance-of-means, DoM)模型；此后一些基于其他模型的攻击方法被相继提出，如相关性功耗分析(correlation power analysis, CPA)^[2]和基于中间变量的Hamming重量或Hamming距离模型。但由于它们本质上是等价的，因此文[3]将这些攻击统称为DPA攻击；本文中所指的DPA攻击与文[3]中一致。
分组密码算法SM4(原SMS4算法)^[4]是目前商用密码管理办公室公开发布的唯一分组密码算法。随着国密算法在国内的推广使用，SM4算法的DPA安全性受到了越来越多的关注。一般来说，对软件实现的SM4算法进行DPA分析，关注点可以是轮密钥异或之后、S盒输出、线性变换输出和轮输出等。但对于硬件实现的SM4算法，1轮的运算在一个时钟周期内完成，因此轮密钥异或、S盒输出、线性变换输出等位置(这些位置可能可以采用Glitch模型^[5]进行分析，但对于不知道芯片设计细节的攻击者来说并不现实)并没有寄存器的参与，一般只有轮输出值能被DPA攻击所利用。但由于SM4线性变换的存在，轮输出的1-b与所有32-b轮密钥都相关, 因此对轮输出做DPA攻击，需要猜测所有32-b的轮密钥，造成进行DPA攻击的复杂度过高。基于这个原因，文[6-9]提出使用选择明文的方法，使得轮输出的一个字节变化只由轮密钥的一部分决定，以降低DPA攻击的复杂度。
本文进一步对SM4算法的选择明文DPA攻击进行研究，通过尽可能多地利用轮输出的比特信息量，改进了现有的选择明文DPA攻击。
1 分组密码算法SM4及其选择明文DPA攻击1.1 SM4算法简介分组密码算法SM4为非对称扩展Feistel结构，其分组长度和密钥长度都为128位，轮数为32轮。定义SM4的主密钥为MK=(MK₀, MK₁, MK₂, MK₃), 主密钥经过密钥生成算法生成轮密钥(rk₀, rk₁, …, rk₃₁), 其中MK₀, MK₁, …, MK₃和rk_i(0≤i≤31)为32-b的字。
令明文为(P₀, P₁, P₂, P₃)=(X₀, X₁, X₂, X₃)∈(Z₂³²)⁴, 则SM4的加密过程如下：

$\begin{align} &~\ \ \ {{X}_{i+4}}=F({{X}_{i}}, {{X}_{i+1}}, {{X}_{i+2}}, {{X}_{i+3}})= \\ &\ {{X}_{i}}\oplus T({{X}_{i+1}}\oplus {{X}_{i+2}}\oplus {{X}_{i+3}}\oplus {{{\text{rk}}}_{i}})= \\ &{{X}_{i}}\oplus L(S({{X}_{i+1}}\oplus {{X}_{i+2}}\oplus {{X}_{i+3}}\oplus {{{\text{rk}}}_{i}})). \\ \end{align}$

其中：i=0, 1, …, 31，⊕表示异或。
密文(C₀, C₁, C₂, C₃)=(X₃₅, X₃₄, X₃₃, X₃₂)。
SM4算法的轮函数如图 1所示。从图中可知，T函数由S层和L层组成。S层为非线性变换层，由4个同样的8×8 S盒并排构成。对S盒的详细描述可见文[4]。L层为线性变换层，将一个32位的字B变成另一个32位的字D。

$\begin{align} &\ \ \ \ \ D=L\left( B \right)=B\oplus \left( B\lll 2 \right)\oplus \\ &\left( B\lll 10 \right)\oplus \left( B\lll 18 \right)\oplus \left( B\lll 24 \right). \\ \end{align}$

图 1 SM4算法的轮函数

图选项

对密钥生成算法进行描述。定义K_i∈Z₂³²(i=0, 1, …, 35)，对(K₀, K₁, K₂, K₃)进行初始化：

$\begin{align} &({{K}_{0}}, {{K}_{1}}, {{K}_{2}}, {{K}_{3}})=(\rm{M}{{\rm{K}}_{0}}\oplus \rm{F}{{\rm{K}}_{0}}, ~ \\ &\rm{M}{{\rm{K}}_{1}}\oplus \rm{F}{{\rm{K}}_{1}}, ~\rm{M}{{\rm{K}}_{2}}\oplus \rm{F}{{\rm{K}}_{2}}, ~\rm{M}{{\rm{K}}_{3}}\oplus \rm{F}{{\rm{K}}_{3}}). \\ \end{align}$

轮密钥计算如下：

${\rm{r}{{\rm{k}}_{\mathit{i}}}}={{\mathit{K}}_{i+4}}={{K}_{i}}\oplus T' ({{K}_{i+1}}\oplus {{K}_{i+2}}\oplus {{K}_{i+3}}\oplus \rm{C}{{\rm{K}}_{\mathit{i}}}).$

其中：T′和T类似，但线性变换L用线性变换L′代替。

$L' \left( B \right)=B\oplus \left( B\lll 13 \right)\oplus \left( B\lll 23 \right).$

FK_i(i=0, 1, 2, 3)和CK_j(j=0, 1, …, 31)为常数，具体值见文[4]。由SM4的密钥生成算法可知，由连续4轮子密钥可推导出主密钥。
1.2 现有的对SM4算法的选择明文DPA攻击DoM^[1]、CPA^[2]和互信息分析(mutual information analysis, MIA)^[10]的共同特点为采取分而治之(divide-and-conquer)的方法，首先用上述方法对密钥的一部分(通常是1个S盒对应的子密钥)进行分别恢复(divide)，再通过各部分的子密钥得出主密钥并验证其正确性(conquer)。这些方法的关注点都在于研究如何建立区分器对1个S盒的子密钥进行恢复，这也是本文的关注点。
Wang等^[6]指出，对于硬件实现的SM4算法在进行DPA攻击时可以使用选择明文的方法来避免猜测轮密钥的所有比特，以降低猜测密钥的复杂度。对于SM4的第1轮，文[6]中遍历X₃的一个字节、固定其他字节，并指出此时第1轮输出的1个字节只和第1轮轮密钥的1个字节以及1个未知的固定字节相关，也提出了猜测这2个字节并用Hamming距离模型进行CPA的攻击；为了进一步降低复杂度，还提出了只猜测1个密钥字节并用轮输出的单个比特进行CPA的攻击。文[7]对文[6]中的单比特方法进行了改进，对轮输出的1个字节的所有比特逐个做CPA，并将所有比特相关系数的绝对值相加作为最终相关性来进行密钥恢复。文[9]中利用第1轮密钥与未知固定字节之间的关系，使得文[6]中恢复完1个S盒所对应密钥后，再恢复同一轮的其他密钥字节时无需再次选择明文，降低了所需的选择明文数。此外，与上述攻击的选择明文思路不同，文[8]中随机选择X₀，固定X₁~X₃，对X₄的Hamming重量进行CPA以恢复第1轮S盒输出的值，并反推出第1轮的轮密钥。但文[8]中的攻击中只能采取选择明文策略，如果在某些攻击条件下无法随机选择X₀，固定X₁~X₃(如果某些应用中X₀为常数)则不能进行这样的攻击。而其他文献中的攻击选择余地则较大，即只要随机选择X₁~X₃中的1个字节即可。
2 本文的SM4算法选择明文DPA攻击对SM4算法的线性变换L层进行比特分解，给出在选择明文模型下的比特变换关系，并由此给出改进的DPA攻击。
2.1 第1轮输出的比特关系首先对32-b字X，定义Xⁱ为其第i个字节(i=0, 1, 2, 3)；定义B⁽ⁱ⁾和D⁽ⁱ⁾(i=0, 1, …, 31)分别为第1轮S层输出B和L层输出D的第i-b(第0-b为最高位)，则可将其比特关系表示为

$ \begin{align} &{{D}^{(i)}}={{B}^{(i)}}\oplus {{B}^{(\left( i+2 \right)\rm{mod}32)}}\oplus {{B}^{(\left( i+10 \right)\rm{mod}32)}}\oplus \\ &\ \ \ \ \ \ \ \ \ \ \ {{B}^{(\left( i+18 \right)\rm{mod}32)}}\oplus {{B}^{(\left( i+24 \right)\rm{mod}32)}}. \\ \end{align} $

(1)

在对SM4的选择明文DPA分析中，需要选择明文以使DPA分析过程中中间变量依赖的密钥比特数尽量少。为使第1轮输出中间变量D满足这个目的，本文随机选取P₁⊕P₂的1个字节，其他字节固定。不失一般性，这里随机选取(P₁⊕P₂)⁰, 将其他字节固定为0(所分析的子密钥为rk₀⁰)。这样B^(j)(j=8, 9, …, 31)为未知但是固定的数。假设x、y₀、y₁为单比特数，用〈x, y〉表示比特x的变化仅依赖于比特y的变化；〈x, (y₀, y₁)〉表示比特x的变化仅依赖于比特y₀⊕y₁的变化。
因此，由式(1)有以下关系：

$\begin{align} &\langle {{D}^{(0)}}, ({{B}^{(0)}}, {{B}^{(2)}})\rangle, \langle {{D}^{(1)}}, ({{B}^{(1)}}, {{B}^{(3)}})\rangle, \\ &\langle {{D}^{(2)}}, ({{B}^{(2)}}, {{B}^{(4)}})\rangle, \langle {{D}^{(3)}}, ({{B}^{(3)}}, {{B}^{(5)}})\rangle, \\ &\langle {{D}^{(4)}}, ({{B}^{(4)}}, {{B}^{(6)}})\rangle, \langle {{D}^{(5)}}, ({{B}^{(5)}}, {{B}^{(7)}})\rangle, \\ &\langle {{D}^{(6)}}, {{B}^{(6)}}\rangle, \langle {{D}^{(7)}}, {{B}^{(7)}}\rangle, \langle {{D}^{(8)}}, {{B}^{(0)}}\rangle, \\ &\langle {{D}^{(9)}}, {{B}^{(1)}}\rangle, \langle {{D}^{(10)}}, {{B}^{(2)}}\rangle, \langle {{D}^{(11)}}, {{B}^{(3)}}\rangle, \\ &\langle {{D}^{(12)}}, {{B}^{(4)}}\rangle, \langle {{D}^{(13)}}, {{B}^{(5)}}\rangle, \langle {{D}^{(31)}}, {{B}^{(1)}}\rangle, \\ &\langle {{D}^{(14)}}, ({{B}^{(0)}}, {{B}^{(6)}}\rangle, \langle {{D}^{(15)}}, ({{B}^{(1)}}, {{B}^{(7)}}\rangle, \\ &\langle {{D}^{(16)}}, {{B}^{(2)}}\rangle, \langle {{D}^{(17)}}, {{B}^{(3)}}\rangle, \langle {{D}^{(18)}}, {{B}^{(4)}}\rangle, \\ &\langle {{D}^{(19)}}, {{B}^{(5)}}\rangle, \langle {{D}^{(20)}}, {{B}^{(6)}}\rangle, \langle {{D}^{(21)}}, {{B}^{(7)}}\rangle, \\ &\langle {{D}^{(22)}}, {{B}^{(0)}}\rangle, \langle {{D}^{(23)}}, {{B}^{(1)}}\rangle, \langle {{D}^{(24)}}, {{B}^{(2)}}\rangle, \\ &\langle {{D}^{(25)}}, {{B}^{(3)}}\rangle, \langle {{D}^{(26)}}, {{B}^{(4)}}\rangle, \langle {{D}^{(27)}}, {{B}^{(5)}}\rangle, \\ &\langle {{D}^{(28)}}, {{B}^{(6)}}\rangle, \langle {{D}^{(29)}}, {{B}^{(7)}}\rangle, \langle {{D}^{(30)}}, {{B}^{(0)}}\rangle .~ \\ \end{align}$

可以看出，D⁽⁰⁾，D⁽¹⁾，…，D⁽⁵⁾, D⁽¹⁴⁾, D⁽¹⁵⁾的变化和B⁽⁰⁾，B⁽¹⁾，…，B⁽⁷⁾的2比特相关，其余比特的变化只和B⁽⁰⁾，B⁽¹⁾，…，B⁽⁷⁾的1比特相关。并且，B⁽⁰⁾，B⁽¹⁾，…，B⁽⁷⁾的1比特变化将确定同时引起D的3比特变化。这样的关系可以被选择明文DPA攻击所利用，以减少密钥的猜测量。
2.2 单个S盒的攻击模型采用文[1]中的DoM模型作为区分器来进行DPA攻击。文[11]中指出，对于满足EIS (equal images under different subkeys)性质的S盒(如SM4的S盒)的一阶DPA，在泄露模型一样的情况下，DoM和CPA本质上是一样的，即用2种方法成功获取密钥所需的曲线数是一样的。所以在对单一比特进行分析的情况下，本文的结果和文[7]中使用CPA的结果应该是一样的。但由于本文利用了轮输出的所有比特的信息泄露(比文[7]中多利用了8比特信息)，因此预计对文[7]中的结果将有所改进。
此外，本文将不直接采用均值来区分，而是如文[12]中使用了t值。这样使本文的方法更为稳健，而且更易于量化信息泄露。
定义选择函数?(W)=b, W∈Z₂³², b∈Z₂。对SM4算法的第一轮，将?(B)取为B的每一比特，以及B⁽⁰⁾⊕B⁽²⁾、B⁽¹⁾⊕B⁽³⁾、B⁽²⁾⊕B⁽⁴⁾、B⁽³⁾⊕B⁽⁵⁾、B⁽⁴⁾⊕B⁽⁶⁾、B⁽⁵⁾⊕B⁽⁷⁾、B⁽⁰⁾⊕B⁽⁶⁾、B⁽¹⁾⊕B⁽⁷⁾，共有16个选择函数。
利用节2.1中所述方法选择明文，进行SM4加密并采集侧信道曲线。对采集到的曲线，进行合适的信号处理并进行点的选取后猜测rk₀⁰，计算B并根据?(B)为0或1将曲线分成2个集合，并计算这2个集合的t值：

$t=\frac{{{\mu }_{1}}-{{\mu }_{2}}}{\sqrt{s_{1}^{2}/{{N}_{2}}+s_{2}^{2}/{{N}_{2}}}}.$

其中μ_i、s_i和N_i(i=1, 2)分别为第i个集合中曲线的均值、标准差和曲线数。
对于猜测的每一个子密钥，将由16个选择函数?(B)得到16个t值。将这16个t值定义为t_i(i=0, 1, …, 15)，本文给出3个攻击模型。
模型1??对rk₀⁰的每个猜测值k, 计算$\sum\limits_{i=0}^{7}{\left| {{t}_{i}} \right|}$, 取${\rm{rk}}_{0}^{0}=\arg \ {{{\max }_{\mathit{k}}}}\left\{ \sum\limits_{i=0}^{15}{\left| {{t}_{i}} \right|} \right\}$。
由文[11]中结果可知，模型1与文[7]中的方法是等价的。
模型2??对rk₀⁰的每个猜测值k, 计算$\sum\limits_{i=0}^{15}{\left| {{t}_{i}} \right|}$, 取${\rm{rk}}_{0}^{0}=\arg \ {{{\max }_{\mathit{k}}}}\left\{ \sum\limits_{i=0}^{15}{\left| {{t}_{i}} \right|} \right\}$.
模型2是模型1的扩展，利用的比特信息量比模型1多了8-b，由此将提高分析效率，是本文提出的主要模型。
模型3??对rk₀⁰的每个猜测值k, 将其权值清零。对i=0, 1, …, 15, 将arg max_k{|t_i|}(其中t_i≥4.5)所对应的权值加1，取rk₀⁰为权值最大的k。
本文的实验结果中，虽然在曲线数少的情况下模型3的成功率并不如模型1，但可能在某些情况下有优势。
本文主要提出模型2和3，即充分利用信息量以提高恢复单个S盒子密钥的效率。
2.3 主密钥恢复利用节2.2中的模型，可以对第1轮的1个S盒进行密钥恢复。为了完整起见，这里简要描述恢复其他子密钥、最终得出主密钥的过程。
对于第1轮其他S盒所对应的子密钥，采用文[9]中的方法来进行密钥恢复，以此来降低所需的数据量；然后重新选择明文，使得第2、3、4轮的输入满足所需条件，即只有1个字节变化，其他字节固定；最后对第2、3、4轮的轮密钥进行与第1轮类似的DPA攻击，并根据节1.1中所述的密钥生成算法计算出主密钥。
3 实验结果本文中用于实验的SM4算法为硬件实现的ASIC芯片中的SM4协处理器，芯片采用USBKey的形式进行封装，通信协议为CCID。芯片中SM4算法运行的时钟频率为50 MHz。USBKey的通信、控制和功耗的采集设备为自行开发的专用于USB设备的功耗采集设备Insight USB Monitor (见图 2)。

图 2 Insight USB Monitor设备

图选项

所用示波器为LeCroy WaveRunner 104Xi-A, 实验中采集功耗信号时所使用的采样率为1 GHz。在采集功耗曲线时，实验中对SM4所运行的位置做了较为精确的触发以减少对齐曲线所需的工作量。
利用上述环境采集的其中一条SM4的功耗曲线如图 3所示。

图 3 采集的SM4功耗曲线

图选项

可见从图 3并无法直接分辨每轮运行的位置，所以对其利用DPA进行分析。
分别利用模型1、2和3对单个S盒的成功率进行实验。成功率指的是正确的子密钥在所选攻击模型下被正确恢复的概率。对于每个实验，本文都采用不同数据重复100次以统计成功率。实验结果如图 4所示。

图 4 模型对单个S盒的成功率实验结果

图选项

从图 4中可以看出：在本文的实验中，模型2的表现要优于模型1，这与之前的预测相同，即本文提出的模型2在效率上优于文[7]中的方法。而在曲线数较少时，本文的模型3不如模型1和2，这是由于模型3是对单比特结果的加权，并未将信息量组合使用，且只对t＞4.5的密钥猜测加权。虽然如此，模型3的好处在于若有些比特未泄露真实密钥的信息，甚至使错误密钥出现了较大的尖峰，则这样的比特对使用模型1和2将可能造成严重影响，最终得出错误的结果；而此时在曲线数足够多的情况下使用模型3有利于排除这些比特的影响，从而提高攻击的正确性。
4 结论选择明文DPA攻击是对硬件实现的SM4算法进行侧信道分析的有效手段。本文采用该方法，通过研究SM4算法线性变换层输入和输出的比特依赖关系，给出了8个可被选择明文DPA利用的比特关系，并由此改进了SM4算法的选择明文DPA攻击。与现有的方法相比，模型2用更少的曲线便可以达到相同的成功率。实验结果表明了该方法的有效性。说明利用更多的侧信道信息泄露有助于改进DPA攻击的结果。后续将继续研究充分利用信息量的其他模型，以进一步提高成功率。

参考文献

[1]	Kocher P, Jaffe J, Jun B. Differential power analysis[C]//Proc CRYPTO' 99. Berlin Heidelberg:Springer-Verlag, 1999:388-397.
[2]	Brier E, Clavier C, Olivier F. Correlation power analysis with a leakage model[C]//Proc CHES 2004. Berlin Heidelberg:Springer-Verlag, 2004:16-29.
[3]	Mangard S, Oswald E, Popp T. Power Analysis Attacks:Revealing the Secrets of Smart Cards[M]. New York: Springer, 2007.
[4]	国家商用密码管理办公室. 无线局域网产品使用的SMS4密码算法[Z/OL]. [2016-05-03]. http://www.oscca.gov.cn/UpFile/200621016423197990.pdf. Office of State Commercial Cryptography Administration. Specification of SMS4, block cipher for WLAN products-SMS4[Z/OL].[2016-05-03]. http://www.oscca.gov.cn/UpFile/200621016423197990.pdf. (in Chinese)
[5]	Mangard S, Pramstaller N, Oswald E. Successfully attacking masked AES hardware implementations[C]//Proc CHES 2005. Berlin Heidelberg:Springer-Verlag, 2005:157-171.
[6]	Wang S T, Gu D W, Liu J R, et al. A power analysis on SMS4 using the chosen plaintext method[C]//Proc CIS 2013. New York:IEEE, 2013:748-752.
[7]	Shan W J, Wang L H, Li Q, et al. A chosen-plaintext method of CPA on SM4 block cipher[C]//Proc CIS 2014. New York:IEEE, 2014:363-366.
[8]	王敏, 杜之波, 吴震, 等. 针对SMS4轮输出的选择明文能量分析攻击[J]. 通信学报, 2015, 36(1): 142–148.WANG Min, DU Zhibo, WU Zhen, et al. Chosen-plaintext power analysis attack against SMS4 with the round-output as the intermediate data[J]. Journal on Communications, 2015, 36(1): 142–148. (in Chinese)
[9]	杜之波, 吴震, 王敏, 等. 针对SM4轮输出的改进型选择明文功耗分析攻击[J]. 通信学报, 2015, 36(10): 85–91.DU Zhibo, WU Zhen, WANG Min, et al. Improved chosen-plaintext power analysis attack against SM4 at the round-output[J]. Journal on Communications, 2015, 36(10): 85–91. DOI:10.11959/j.issn.1000-436x.2015270(in Chinese)
[10]	Gierlichs B, Batina L, Tuyls P, et al. Mutual information analysis:A generic side-channel distinguisher[C]//Proc CHES 2008. Berlin Heidelberg:Springer-Verlag, 2008:426-442.
[11]	Mangard S, Oswald E, Standaert F X. One for all-all for one:Unifying standard differential power analysis attacks[J]. IET Information Security, 2011, 5(2): 100–110. DOI:10.1049/iet-ifs.2010.0096
[12]	Goodwill G, Jun B, Jaffe J, et al. A testing methodology for side channel resistance validation[Z/OL].[2016-05-03]. http://csrc.nist.gov/news_events/non-invasive-attack-testing-workshop/papers/08_Goodwill.pdf