基于代数表达式功耗模型的差分功耗分析攻击

摘 要：

差分功耗分析（DPA）攻击被证明是一种非常有效的针对加密设备的攻击方法，但目前存在的几个版本的DPA攻击方法对差分信息的需求量过高，且抗干扰能力有限、稳定性不强。在研究DPA攻击的基础上对DPA攻击方法进行了重构，简化DPA攻击复杂度，并提出基于代数表达式功耗模型的DPA攻击方法，该方法能够提高攻击的准确性，降低DPA攻击对差分信息的需求量。在SASEBO-GII实验平台上的实验结果表明，在不增加时间复杂度的前提下，提出的方法能够将针对硬件执行高级加密标准算法（AES）的DPA攻击对差分信息的需求量从数千条降到数百条，甚至更低。

关键词：差分功耗分析；高级加密标准；代数表达式；功耗模型

中图分类号： TP309

文献标志码：A

Differential power analysis attack based on algebraic expression for power model

Abstract：

Differential Power Analysis （DPA） attack is the most efficient attack to encryption device. Some existing DPA methods have high demands for differential information and their stabilities are not strong. In this paper based on the analysis of DPA， the authors reconstructed the model of DPA， which reduced the complexity of attack. A new DPA attack combining new power model based on algebraic expression was proposed， and the experimental results show that the proposed DPA attack has the advantages of increasing the correctness of attacking without increasing the time complexity and reducing the number of the needed differential information from thousands to hundreds compared with the existing method.

Key words：

Differential Power Analysis （DPA）； Advanced Encryption Standard （AES）； algebraic expression； power model

0 引言

2001年由美国国家标准与技术研究所正式公布的高级加密标准（Advanced Encryption Standard，AES）[1]在工业界已被广泛应用，针对AES所展开的攻击技术受到越来越多学者们的关注。旁路攻击 （Side-Channel Attack，SCA）[2]中的差分功耗分析（Differential Power Analysis， DPA）攻击是一种非常有效的攻击方式，其利用密码设备产生的功耗对数据的依赖性，记录密码设备加密/解密不同数据分组时产生的大量功耗迹，通过分析固定时刻的功耗来获取密码算法的密钥。

Kocher等在文献[3]中第一次提到了差分功耗分析（DPA）攻击方法，并提出 “均差值”方法来比较分析固定时刻实测功耗，在此基础上找到功耗与密钥的内在联系，从而推导出密码算法的密钥；该方法的成功率比较低，稳定性非常差。Agrawal等在文献[4]中提出了一种基于“广义极大似然检验”的统计概念来计算固定时刻实际功耗与功耗模型所得的逻辑功耗的关联性，进而推导出密码算法的密钥；该方法较文献[3]方法攻击成功率有了较大的提高，但其计算过程较为复杂，且其对差分信息的需求量在104～105条。Mangard等在文献[5]中提出了“相关性系数法”，该方法攻击效果明显，但易受环境的影响抗干扰能力较差，对差分信息的需求量在103～104条。代数攻击[6]稳定性强，对信息量的需求低，在一定程度上弥补了DPA攻击的不足。Courtois等在文献[7]通过对密码算法的分析，将密码算法的安全性完全规约于求解一个超定多变元高次方程组的问题上，但其分析过程复杂，计算难度大且实效性不强。

本文在Mangard等工作的基础上，结合代数攻击核心思想，构造一个基于代数表达式功耗模型的DPA攻击方法，提高攻击的抗干扰能力和稳定性，将攻击对差分信息量的需求降低至102～103条。

本文的工作包括：1）利用“相关性系数”来计算固定时刻实际功耗与功耗模型所得的逻辑功耗的关系，进而实施DPA攻击；2）重构DPA攻击模型，在SASEBO-GII平台上，验证重构后DPA攻击的有效性；3）提出基于代数表达式的差分功耗攻击方法，并在SASEBO-GII平台上进行验证。

1 AES以及DPA

1.1 AES

AES是一种能够进行加密和解密信息的对称分组密码算法，其使用的密钥长度分别有128 位、192位 和256位，根据密钥长度的不同，相应的加密算法分别称为AES-128、AES-192和AES-256。本文主要针对AES-128进行研究，AES-128的算法描述如下：

AES先将输入明文复制到状态矩阵（State）中，经过原始密钥扩展后，AES执行10轮函数来变换状态矩阵。轮函数（Round）主要由四个变换组成，分别是：AddRoundKey、SubBytes、ShiftRows以及MixColumns变换。最后一轮轮函数没有MixColumns运算。

AddRoundKey将轮密钥与状态矩阵进行异或运算得到新状态矩阵；SubBytes利用AES的S盒分别对新状态矩阵的每一个字节进行字节替换，它是轮变换中唯一的非线性变换操作；ShiftRows以字节为单位，将状态的每一行按照不同的位移量进行循环移位；MixColumns对状态矩阵中每一列的各个字节进行列混合操作。

1.2 DPA攻击

DPA攻击的步骤如下：

1.3 DPA攻击模型的重构

AES的轮运算比较多，因此要实现完整的AES密码算法的DPA攻击是比较复杂与困难的。通过对AES加密算法过程的分析可知，从最后一轮子密钥可推导出AES密码算法的全部密钥，因此破译AES的最后一轮的子密钥即可推导出其他轮使用的子密钥。基于以上知识，本文将AES密码算法重构如下：

ReCreate_AES的输入是密文与密钥，其中只包含三个简单的操作，即Inv_SubBytes、Inv_ShiftRow和AddRoundKey。经过改造后的密码算法，结构简单，很大程度上降低了DPA攻击的复杂度。使用ReConstruct_AES密码算法后的DPA攻击得到的结果是AES加密算法最后一轮的子密钥，进而通过密钥扩展理论可以很容易地将AES的全部加密密钥推导出来。

实验证明，重构后的DPA攻击模型降低了时间复杂度和空间复杂度，也降低了DPA攻击的难度，同时，重构后DPA攻击的有效性明显增强；但是，该重构的方法并没有改善DPA攻击的抗干扰能力和DPA攻击的准确度。

2 基于代数表达式功耗模型的DPA攻击

DPA功耗模型是为求出DPA攻击中的假设能耗而建立的模型。现阶段功耗统计模型只有有限且固定的选择：汉明重量模型[8]、汉明距离模型[9]、ZV模型[10]、LSB模型[11]。DPA攻击所需差分信息的量比较大且攻击效果不稳定的一个重要原因在于，收集密码算法的实测功耗过程中很容易受到外界的干扰，从而使得采集到的功耗值与正确值出现较大程度的偏差，导致在计算假设能量消耗值时所采取的功耗模型与实际的偏差变大，影响了最终的攻击效果。为了降低干扰对最终攻击结果的影响，提高攻击的抗干扰能力，本文将代数攻击思想与原DPA攻击方法相结合提出新型的DPA攻击方案。

代数攻击是一种对密码算法进行代数结构分析的攻击方法，通过研究发现SubBytes操作具有良好的代数性质，因此将AES密码算法的SubBytes操作作为改进点，用一个代数运算表达式来完全替代简单的S盒/逆S盒的字节替换操作，通过运算推导，得到S盒替换运算的代数表达式如（1）所示；

S盒的代数表达式只有简单的九项，而逆S盒的替换运算代数表达式有255项，逆S盒的替换运算代数表达式如（2）所示，它的各项系数如表1所示。

在使用代数表达式的基础上建立新的基于代数表达式的功耗模型，如图1所示。其中数据处理模型主要由以下三个部分组成：

1）功耗值的计算。DPA攻击的假设中间值一般是通过密码算法后得到的输出值，功耗统计模型使用汉明重量模型得到假设功耗值h，该方法还需对替换SubByte操作的代数表达式的每个单元运算进行功耗统计，仍使用汉明重量模型来统计功耗，从而得到功耗值S。

2）功耗值的处理。由于代数表达式的运算单元比较多，得到的功耗值S是比较大的，不适合直接使用，对S作一定的处理，选取S的均值s用来反映原S的性质。

3）功耗值的调和。实验发现直接使用h+s值，取得的实验效果不够理想，需对h和s作一定的处理，由此构建获取假设功耗值h′的一般化形式：

与DPA攻击相比，新的方法在统计假设能量消耗时增加了255次乘法运算，因此，针对128位的AES加密算法的破译就要增加255×16=4080次乘法运算。

3 实验结果与比较

C语言用来计算相关系数等参数，实验结果波形图使用VC++提供的MFC框架来完成。主要的实验设备有：SDS1022DL示波器一台，SASEBO-GII实验平台；配置为CPU：Pentium Dual-Core CPU- E6700 @3.20GHz； 操作系统： Microsoft Windows XP。

3.1 DPA攻击实验结果

本文中的DPA攻击实验采用与文献[5]中同样的方法，为降低攻击实验的难度，本文选取重构后的DPA模型进行DPA攻击实验，实验结果较文献[5]中方法而言除正确性有些许提高之外，所得结论与结果完全相同。同时，为了测试成功破译子密钥所需的最少能耗迹条数，本文选取3000条、2000条、1000条、998条、800条、500条等多组数据进行测试，其中每条能量迹选取了1000个数据点。

表2中初始密钥与各轮轮密钥是通过对原始密钥执行密钥扩展操作后得到的各轮子密钥值。由于针对128位版本AES算法，最后得到16个时间相关系数波形图，限于篇幅从实验所获得的16幅结果示意图中选取第0字节和第7字节展示实验结果。

表2中DPA攻击实验所针对的AES第10轮真实密钥分别是：d0，14， f9，a8，c9，ee，25，89，e1，3f，0c，c8，b6，63，0c，a6，与表3所示攻击结果进行匹对可得，表3中除第5与第15字节出现错误，其他完全吻合，从而表明采用2000条能量迹的DPA攻击能够比较准确地获取AES密码算法的子密钥。对采集的多组数据进行了同样的验证性试验，结果证明能耗迹数量越多，破译的准确度越高。998条能量迹可以得到少量的正确密钥字节，结果如表4所示，其中带下划线部分表示猜测正确的密钥字节。对低于998条能耗迹的数据集进行同样的验证性实验均无法破译任何子密钥字节，表明成功的DPA攻击对能耗迹的条数是有一定要求的。

3.2 新的功耗模型DPA攻击试验结果

利用新的功耗模型在重新采集实测功耗数据的基础上进行多次完整的DPA攻击，表5与表6为使用改进功耗模型后的DPA攻击所得到的实验结果集。

3.3 实验结果比较与结论

两组实验结果对比发现：使用2000条功耗迹时，改进前可以正确破译AES-128子密钥中的14个字节子密钥，结果如表3所示；改进功耗模型后DPA攻击能够获取全部正确的子密钥，结果如表5所示。使用998条功耗迹时，改进前只能正确获得第0、2、14三个子密钥比特，结果如表4所示；使用改进后的方法，可知除第5、13两个字节的密钥猜测错误外其他子密钥字节均正确，其结果如表6所示；通过对比可知表6与表3中所示结果的准确性十分接近。由此可以得出结论：使用改进功耗模型的DPA攻击效果较改进前而言，准确性明显提高，并且在取得同等攻击效果的情况下对差分功耗信息的需求量显著降低。

4 结语

DPA攻击以攻击原理简单、攻击效果明显而被广泛使用。本文首先利用“相关性系数”计算固定时刻实际功耗与功耗模型所得逻辑功耗的关联性得到真实密钥，然后对重构DPA攻击模型进行实验验证，可知重构DPA攻击降低了DPA攻击复杂度；最后，提出基于代数表达式功耗模型的DPA攻击方法，实验结果表明，新DPA攻击方法在增加有限运算量的前提下提高了攻击的准确度，降低了DPA攻击对差分信息的需求量。与已有攻击方法一样，本文中的DPA攻击方法仍无法实现对使用掩码技术[12]的密码算法进行有效的攻击，需要进一步的研究。

参考文献：

[1] National Institute of Standards and Technology. Advanced Encryption Standard （AES）[S/OL].[2013-06-20]. http：//csrc.nist.gov/publications/fips/fips197/fips-197.pdf.

[2] MANGARD S， OSWALD E， POPP T. Power analysis attacks， revealing the secrets of smart cards[M]. New York： Springer-Verlag， 2007：1-272.

[3] KOCHER P C， JAFFE J， BENJIMIN J. Differential power analysis[C]// Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology. London： Springer-Verlag， 1999：388-397.

[4] AGRAWAL D， ARCHAMBEAULT B， JOSYULA R，et al. The EM side-channel（s）[C]// Proceedings of the 4th International Workshop Redwood Shores. Heidelberg： Springer， 2003：29-45.

[5] MANGARD S， OSWALD E， POPP T. Power analysis attacks， revealing the secrets of smart cards[M]. New York： Springer-Verlag， 2009： 97-130.

[6] ZHANG L. Algebraic attacks issues research[D]. Xian： Xidian University， 2005.（张莉.代数攻击的若干问题研究[D]. 西安：西安电子科技大学，2005.）

[7] COURTOIS N T. Higher order correlation attacks， XL algorithm and cryptanalysis of Toyocrypt[C]// Proceedings of the 5th International Conference on Information Security and Cryptology. Berlin： Springer-Verlag， 2003： 182-199.

[8] AKKAR M， GIRAUD C. An implementation of DES and AES secure against some attacks[C]// Proceedings of the 3rd International Workshop on Cryptographic Hardware and Embedded Systems. London： Springer-Verlag， 2001： 309-318.

[9] MESSERGES T S， DABBISH E A， SLOAN R H. Examining smart-card security under the threat of power analysis attacks[J]. IEEE Transactions on Computers， 2002， 51（5）： 51-55.

[10] MORADI A， OLIVER M， EISENBARTH T. ZV model for power consumption statistics[C]// CHES 2010： Proceedings of the 2010 Workshop on Cryptographic Hardware and Embedded Systems. Berlin： Springer， 2010： 125-139.

[11] JEVTIC R，VITAE A， CARRERAS C. A complete dynamic power estimation model for data paths in FPGA DSP designs[J]. The VLSI Journal， 2012， 45（2）： 172-185.

[12] SHAN W W， CHEN X， LI B. Evaluation of correlation power analysis resistance and its application on asymmetric mask protected data encryption standard hardware[J]. IEEE Transactions on Instrumentation and Measurement， 2013，62（10）： 2716-2724.