Camellia算法簡單和差分功耗分析組合攻擊

楊 斌, 陳 運, 陳 俊, 羅曉飛

（成都信息工程學院應用密碼學研究所,四川成都 610225）

0 引言

傳統(tǒng)的密碼破解方法,通常是從數(shù)學角度分析密碼算法設計的缺陷從而破解密鑰,或采用窮舉方法進行暴力破解。但是隨著密碼算法的復雜度越來越高,使用數(shù)學方法分析破解密碼算法通常效果欠佳或者代價巨大。隨著集成電路技術的發(fā)展和嵌入式系統(tǒng)的大規(guī)模應用,加密芯片的實現(xiàn)電路在運行過程中會泄露一些邊信息,如運算時間、電磁輻射、功耗信息等。利用這些泄露的信息對硬件密碼電子設備進行攻擊,即邊信道攻擊[1]。邊信道攻擊可分為計時攻擊[2]和能量攻擊等。利用硬件加密電路在進行加密操作時所泄露的旁路信息對加密系統(tǒng)進行分析、破譯,即功耗攻擊[3]。其中功耗攻擊因其效率較高,成為邊信道攻擊的主要手段。功耗攻擊包括簡單功耗攻擊（Simple Power Analysis,SPA）[4]、差分功耗攻擊（Differential Power Analysis,DPA）[5-6]等。當前對分組密碼算法的功耗分析研究大多針對DES[7-8]、AES[9-10]算法,對Camellia密碼算法[11-13]的研究大多是從數(shù)學角度對算法本身的安全性進行分析,而對Camellia密碼算法的功耗分析研究較少。

1 Camellia算法簡介

Camellia算法由三菱公司和日本電信電話公司于2000年共同設計。Camellia算法以其高安全性和在各種軟件、硬件平臺上的高效率等顯著特點,在2003年被歐洲NESSIE計劃評選為獲勝算法,同年又被日本CRYPTREC計劃評選為推薦算法,2004年成為Internet工程任務組（Internet Engineering Task Force,IETF）標準算法,2005年成為ISO/IEC標準算法,2006年成為PKCS#11的認可密碼,2009年Camellia算法的計數(shù)器使用模式和循環(huán)移位模式（Cipher-block chaining-Message Authentication Code,CBC-MAC）成為 IETF標準[14]。可以說,Camellia算法是繼高級加密標準（Advanced Encryption Standard,AES）算法后最具競爭優(yōu)勢的分組密碼算法之一,它已經(jīng)在信息安全的很多領域得到廣泛的應用。

Camellia算法的分組長度為128比特,密碼長度分為128,192和256比特。當密碼長度為128比特時,迭代輪數(shù)為18輪,當密碼長度為192比特或256比特時,迭代輪數(shù)為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函數(shù),包括S盒運算和P變換,其中S盒運算是一個在GF（28）上的可逆運算,它加強了算法的安全性,并且適用于小硬件設計。P變換是一個線性變換,它采用異或運算,其安全性足以抵抗差分和線性密碼分析。F函數(shù)的具體過程如下,其中 x表示初始值,y表示進入F函數(shù)的初值,z表示經(jīng)過F函數(shù)后的結果。

圖2 F函數(shù)流程圖

2 差分功耗分析（DPA）

對于分組密碼算法,通常的功耗攻擊方法是差分功耗攻擊（DPA）,DPA攻擊的目標是記錄密鑰設備對大量不同數(shù)據(jù)分組進行加密或解密操作時的功耗,并基于功耗軌跡恢復密鑰。DPA攻擊一般過程如下:

（1）選擇所執(zhí)行的算法的某個中間值,這個中間值由一個函數(shù)f（d,k）得到,是已知的非常量數(shù)據(jù),k是密鑰中的一小部分。通常對分組密碼算法來說,這個中間值選取經(jīng)過S盒的數(shù)據(jù)。

（2）采集大量的功耗曲線。并且在采集同一批數(shù)據(jù)的時候芯片內(nèi)部的密鑰是不變化的。只有這樣,所有被采集的功耗波形中才會有相同的密鑰信息。

（3）猜測（1）中k的取值k′,根據(jù)猜測的k′求得中間值,選取區(qū)分函數(shù),根據(jù)中間值將（2）中采集的功耗曲線分組,通常使用區(qū)分函數(shù)根據(jù)中間值的某一位分為0和1兩組,對這兩組曲線進行差分。根據(jù)差分后曲線的跳躍或突變來判斷猜測的密鑰是否正確。

3 Camellia算法的差分功耗分析

當前對于分組密碼算法,大多使用DPA進行攻擊。針對Camellia算法,首先,使用SPA分析Camellia算法功耗曲線大致輪廓,找到攻擊點,即加密運算第一輪中S盒運算在功耗曲線中的大致位置;然后使用DPA攻擊 S盒運算;最后,分析攻擊結果,破解密鑰。

3.1 實驗環(huán)境

實驗使用了功耗采集平臺,主要包括含有Camellia算法的STC90C516AD芯片開發(fā)板,TekDPO4032示波器,工作站。主機使用串口與開發(fā)板進行通信,示波器采集開發(fā)板加密時泄露的功耗信息,通過網(wǎng)線將此信息傳送至PC端分析處理。

3.2 實驗結果與分析

在硬件仿真環(huán)境下,首先,采集為一條Camellia算法的功耗曲線軌跡,明文:0x0123456789ABCDEFFEDCBA-9876543210,密鑰:0x0123456789ABCDEFFEDCBA9876543210的功耗曲線,如圖3所示。在反相和低通濾波過后,Camellia算法功耗曲線更加清晰,曲線如圖4所示。可以看出,功耗曲線大概可以分為3部分,第一部分是密鑰字生成的功耗軌跡,第二部分是輪密鑰生成的功耗軌跡,第三部分是加密運算的功耗軌跡。

圖3 Camellia算法功耗曲線原始圖

圖4 Camellia算法功耗曲線濾波反相圖

通過分析Camellia算法流程,并與功耗曲線軌跡圖對比,可以發(fā)現(xiàn),第一部分中的6個凸起位置對應密鑰生成時的6輪F函數(shù)運算,每隔兩個凸起位置間隙較大,因為密鑰生成時兩輪F函數(shù)之間進行了一次異或運算。第二部分是輪密鑰生成的功耗軌跡,對密鑰字kA一共進行了12次左移運算,因此出現(xiàn)了12個凸起的部分,由于平移所產(chǎn)生的功耗要小于F函數(shù)運算產(chǎn)生的功耗,所以一次平移時凸起位置的寬度窄于F函數(shù)運算的凸起位置;第三部分是加密運算,加密時一共進行了18次的F函數(shù)運算,由于在首次F運算之前進行了一次白化,因此第一輪F函數(shù)運算的凸起位置寬于其他F函數(shù)的凸起位置,每6輪F函數(shù)運算之間存在兩個寬度相對較窄的凸起,對應了加密過程中每6輪F運算之間進行的FL函數(shù)運算和FL-1運算,在18輪F函數(shù)運算之后,進行一次白化,與圖中最后的一塊凸起部分相對應。實驗針對第一輪加密進行DPA分析,因此只需對每條曲線第三部分的第一塊凸起位置進行操作,從而減少運算時間。

使用功耗曲線采集平臺采集10000組隨機明文,密鑰相同的功耗曲線。使用DPA攻擊,攻擊的中間值選擇為S1盒,猜測與S1盒相關的16位子密鑰ks1,計算每條曲線對應的明文Ci使用猜測的子密鑰按照加密流程加密,設第一輪通過S1盒第一位b,區(qū)分函數(shù)為D（C,b,Ks1）,根據(jù)區(qū)分函數(shù)將曲線分為兩組,根據(jù)差分公式

經(jīng)計算,實驗使用STC90C516AD芯片的硬件仿真環(huán)境,樣本量為10000條功耗曲線,如果子密鑰猜測正確,即高功耗與低功耗之間縱坐標相差較大,差分后會出現(xiàn)一個尖峰,如圖5所示。如果子密鑰猜測錯誤,則不會出現(xiàn)明顯尖峰,如圖6所示。當使用5000條曲線進行DPA攻擊時,由于噪聲干擾較大,結果不甚理想,若再增加曲線的樣本量,結果可能會更加清晰。

圖5 猜測正確差分結果

圖6 猜測錯誤差分結果

4 結束語

對分組密碼算法的功耗分析研究大多使用DPA方法,針對Camellia算法,在硬件仿真環(huán)境下,使用SPA分析功耗曲線,找到S盒運算在功耗曲線中的大致位置,降低處理功耗曲所需時間,使用DPA方法對S盒進行攻擊,并獲取Camellia算法正確密鑰,實驗結果驗證了差分功耗分析對Camellia算法進行攻擊的可行性和有效性。

致謝:感謝成都市科研院所成果轉(zhuǎn)化項目（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算法的代數(shù)性質(zhì)分析[D].湖南大學碩士學位論文,2006.

[14] 李超,孫兵,李瑞林.分組密碼的攻擊與實例分析[M].北京:科學出版社,2010.

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