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.