Camellia算法简单和差分功耗分析组合攻击

杨 斌, 陈 运, 陈 俊, 罗晓飞

（成都信息工程学院应用密码学研究所,四川成都 610225）

0 引言

传统的密码破解方法,通常是从数学角度分析密码算法设计的缺陷从而破解密钥,或采用穷举方法进行暴力破解。但是随着密码算法的复杂度越来越高,使用数学方法分析破解密码算法通常效果欠佳或者代价巨大。随着集成电路技术的发展和嵌入式系统的大规模应用,加密芯片的实现电路在运行过程中会泄露一些边信息,如运算时间、电磁辐射、功耗信息等。利用这些泄露的信息对硬件密码电子设备进行攻击,即边信道攻击[1]。边信道攻击可分为计时攻击[2]和能量攻击等。利用硬件加密电路在进行加密操作时所泄露的旁路信息对加密系统进行分析、破译,即功耗攻击[3]。其中功耗攻击因其效率较高,成为边信道攻击的主要手段。功耗攻击包括简单功耗攻击（Simple Power Analysis,SPA）[4]、差分功耗攻击（Differential Power Analysis,DPA）[5-6]等。当前对分组密码算法的功耗分析研究大多针对DES[7-8]、AES[9-10]算法,对Camellia密码算法[11-13]的研究大多是从数学角度对算法本身的安全性进行分析,而对Camellia密码算法的功耗分析研究较少。

1 Camellia算法简介

Camellia算法由三菱公司和日本电信电话公司于2000年共同设计。Camellia算法以其高安全性和在各种软件、硬件平台上的高效率等显著特点,在2003年被欧洲NESSIE计划评选为获胜算法,同年又被日本CRYPTREC计划评选为推荐算法,2004年成为Internet工程任务组（Internet Engineering Task Force,IETF）标准算法,2005年成为ISO/IEC标准算法,2006年成为PKCS#11的认可密码,2009年Camellia算法的计数器使用模式和循环移位模式（Cipher-block chaining-Message Authentication Code,CBC-MAC）成为 IETF标准[14]。可以说,Camellia算法是继高级加密标准（Advanced Encryption Standard,AES）算法后最具竞争优势的分组密码算法之一,它已经在信息安全的很多领域得到广泛的应用。

Camellia算法的分组长度为128比特,密码长度分为128,192和256比特。当密码长度为128比特时,迭代轮数为18轮,当密码长度为192比特或256比特时,迭代轮数为24轮。Camellia算法整体上采用Feistel结构,但加入了白化处理,每隔6轮加入了密钥相关的FL和FL-1变换。加密流程如图1所示。

Camellia-128的加密流程如下:

（1）128比特明文M与白化密钥kw1和kw2或运算的结果进行异或运算后分为左半部分64比特L0和右半部分64比特 R0,即 M ⊕（kw1‖kw2）=L0‖R0。

（2）对 r=1,2,…,18,r≠6,r≠12进行如下变换:（3）R18‖L18与白化密钥kw3和kw4或运算的结果进行异或运算,获得密文C=（R18‖L18）⊕（kw3‖kw4）

图1 Camellia算法加密流程图

对于每一轮的F函数,包括S盒运算和P变换,其中S盒运算是一个在GF（28）上的可逆运算,它加强了算法的安全性,并且适用于小硬件设计。P变换是一个线性变换,它采用异或运算,其安全性足以抵抗差分和线性密码分析。F函数的具体过程如下,其中 x表示初始值,y表示进入F函数的初值,z表示经过F函数后的结果。

图2 F函数流程图

2 差分功耗分析（DPA）

对于分组密码算法,通常的功耗攻击方法是差分功耗攻击（DPA）,DPA攻击的目标是记录密钥设备对大量不同数据分组进行加密或解密操作时的功耗,并基于功耗轨迹恢复密钥。DPA攻击一般过程如下:

（1）选择所执行的算法的某个中间值,这个中间值由一个函数f（d,k）得到,是已知的非常量数据,k是密钥中的一小部分。通常对分组密码算法来说,这个中间值选取经过S盒的数据。

（2）采集大量的功耗曲线。并且在采集同一批数据的时候芯片内部的密钥是不变化的。只有这样,所有被采集的功耗波形中才会有相同的密钥信息。

（3）猜测（1）中k的取值k′,根据猜测的k′求得中间值,选取区分函数,根据中间值将（2）中采集的功耗曲线分组,通常使用区分函数根据中间值的某一位分为0和1两组,对这两组曲线进行差分。根据差分后曲线的跳跃或突变来判断猜测的密钥是否正确。

3 Camellia算法的差分功耗分析

当前对于分组密码算法,大多使用DPA进行攻击。针对Camellia算法,首先,使用SPA分析Camellia算法功耗曲线大致轮廓,找到攻击点,即加密运算第一轮中S盒运算在功耗曲线中的大致位置;然后使用DPA攻击 S盒运算;最后,分析攻击结果,破解密钥。

3.1 实验环境

实验使用了功耗采集平台,主要包括含有Camellia算法的STC90C516AD芯片开发板,TekDPO4032示波器,工作站。主机使用串口与开发板进行通信,示波器采集开发板加密时泄露的功耗信息,通过网线将此信息传送至PC端分析处理。

3.2 实验结果与分析

在硬件仿真环境下,首先,采集为一条Camellia算法的功耗曲线轨迹,明文:0x0123456789ABCDEFFEDCBA-9876543210,密钥:0x0123456789ABCDEFFEDCBA9876543210的功耗曲线,如图3所示。在反相和低通滤波过后,Camellia算法功耗曲线更加清晰,曲线如图4所示。可以看出,功耗曲线大概可以分为3部分,第一部分是密钥字生成的功耗轨迹,第二部分是轮密钥生成的功耗轨迹,第三部分是加密运算的功耗轨迹。

图3 Camellia算法功耗曲线原始图

图4 Camellia算法功耗曲线滤波反相图

通过分析Camellia算法流程,并与功耗曲线轨迹图对比,可以发现,第一部分中的6个凸起位置对应密钥生成时的6轮F函数运算,每隔两个凸起位置间隙较大,因为密钥生成时两轮F函数之间进行了一次异或运算。第二部分是轮密钥生成的功耗轨迹,对密钥字kA一共进行了12次左移运算,因此出现了12个凸起的部分,由于平移所产生的功耗要小于F函数运算产生的功耗,所以一次平移时凸起位置的宽度窄于F函数运算的凸起位置;第三部分是加密运算,加密时一共进行了18次的F函数运算,由于在首次F运算之前进行了一次白化,因此第一轮F函数运算的凸起位置宽于其他F函数的凸起位置,每6轮F函数运算之间存在两个宽度相对较窄的凸起,对应了加密过程中每6轮F运算之间进行的FL函数运算和FL-1运算,在18轮F函数运算之后,进行一次白化,与图中最后的一块凸起部分相对应。实验针对第一轮加密进行DPA分析,因此只需对每条曲线第三部分的第一块凸起位置进行操作,从而减少运算时间。

使用功耗曲线采集平台采集10000组随机明文,密钥相同的功耗曲线。使用DPA攻击,攻击的中间值选择为S1盒,猜测与S1盒相关的16位子密钥ks1,计算每条曲线对应的明文Ci使用猜测的子密钥按照加密流程加密,设第一轮通过S1盒第一位b,区分函数为D（C,b,Ks1）,根据区分函数将曲线分为两组,根据差分公式

经计算,实验使用STC90C516AD芯片的硬件仿真环境,样本量为10000条功耗曲线,如果子密钥猜测正确,即高功耗与低功耗之间纵坐标相差较大,差分后会出现一个尖峰,如图5所示。如果子密钥猜测错误,则不会出现明显尖峰,如图6所示。当使用5000条曲线进行DPA攻击时,由于噪声干扰较大,结果不甚理想,若再增加曲线的样本量,结果可能会更加清晰。

图5 猜测正确差分结果

图6 猜测错误差分结果

4 结束语

对分组密码算法的功耗分析研究大多使用DPA方法,针对Camellia算法,在硬件仿真环境下,使用SPA分析功耗曲线,找到S盒运算在功耗曲线中的大致位置,降低处理功耗曲所需时间,使用DPA方法对S盒进行攻击,并获取Camellia算法正确密钥,实验结果验证了差分功耗分析对Camellia算法进行攻击的可行性和有效性。

致谢:感谢成都市科研院所成果转化项目（12DXYB340JH-002）对本文的资助

[1] Thomas S Messerges.Securing the AES Finalists Against Pow Analysis Attacks[J].In Proceedings of Fast Software Encryption Workshop,Lecture Notes in Computer Science,2001,1978:298-301.

[2] J Dhem,F Koeune,P Leroux,et al.Willems,A Practical Implementation of the Timing Attack[R].UCL Crypto Group Technical Report http://users.belgacom.net/dhem/papers/CG1998 1.pdf,1998

[3] Peeters E,Standaert F X,Doncker N,et al.Improved higer-order side-channel attacks with FPGA experiments[C].Cryptographic Hardware and Embedded Systems（CHES2005）.LNCS:2005,3659:303-329.

[4] Messerge T S,Dabbish E A,Sloan RH.Power analysisattacks of modular-exponentiation in smartcards[M].Proceeding of the Workshop on Cryptographic Hardware and Embedded Systems,Worcester,USA,1999:144-157.

[5] Paul Kocher.Timing attackson implementationsof Diffie-Hellman,RSA,DSS,and other systems[C].In N.Koblitz,editor,Advances in Cryptology-CRYPTO'96,volume 1109 of Lecture Notes in Computer Science,1996:104-113.

[6] Paul Kocher,Joshua Jaffe,and Benjamin Jun.Differential Power Analysis[C].Lecture Notes In Computer Science;Vol.1666.Proceedings of the 19th Annual International Cryptology Conference onAdvancesin Cryptology:388-397,1999.

[7] Goubin L,Patarin,J DES and Differential Power Analysis Theduplication method.Cryptographic Hardware and Embed-ded Systems-CHES1999[J].Springer,1999,1717:158-172.

[8] Massimo Alioto,Senior,Santina Rocchi.Differential Power Analysis Attacks to Precharged Buses:A General Analysis for Symmetric-Key Cryptographic Algorithms[C].Ieee transactions on dependable and secure computing,2010,7（3）:226-239.

[9] G Bertoni,L Breveglieri,P Fragneto,et al.Efficient Software Implementation of AES on 32-bits Platforms.In Cryptographic Hardware and Embedded Systems CHES 2002,Lecture Notes in Computer Science[J].Springer-Verlag,2002:348-354.

[10] J Dj Golic,C Tymen.Multiplicative Masking and Power Analysis of AES.In Cryptographic Hardware and Embedded Systems CHES 2002,Lecture Notes in Computer Science[J].Springer-Verlag,2002:344,355-356.

[11] Aoki K,Ichikawa T,Kanda M,et al.Nakajima,J.,Tokita,T.:The 128-Bit Block Cipher Camellia.IEICE Trans[C].Fundamentals E85-A（1）,2002:11-24.

[12] 冯登国,林东岱,吴文玲.欧洲信息安全算法工程[M].北京:科学出版社.2003.

[13] 张翼飞.欧洲分组密码标准Camellia算法的代数性质分析[D].湖南大学硕士学位论文,2006.

[14] 李超,孙兵,李瑞林.分组密码的攻击与实例分析[M].北京:科学出版社,2010.

[15] Stefan Mangard,Elisabeth Oswald,Thomas Popp.能量分析攻击[M].北京:科学出版社,2010.