等功耗編碼算法的改進實現(xiàn)及抗功耗分析攻擊研究

吳震，陳運，王敏，陳俊

（成都信息工程學(xué)院 信息安全研究所，四川 成都 610225）

1 引言

目前，各類基于功耗軌跡對密碼設(shè)備進行分析攻擊的技術(shù)發(fā)展迅速，從計時（TA, timing analysis）攻擊[1,2]到簡單功耗分析（SPA, simple power analysis）攻擊[3]和差分功耗分析（DPA, differential power analysis）攻擊[4]，現(xiàn)在又發(fā)展為地址差分功耗分析（ADPA, address-bit differential power analysis）攻擊[5,6]等，此類攻擊以其成本低、時間快等特點嚴(yán)重威脅著密碼設(shè)備運行時的安全。

在目前流行的公鑰算法或協(xié)議中，大多使用冪剩余運算作為其核心運算。針對該運算進行功耗分析攻擊，可獲取密碼體制中密鑰的部分信息，嚴(yán)重者可直接破譯出密鑰。

研究者根據(jù)功耗分析攻擊特性提出的各種防范方案主要從減小可測量的功耗差異、時間差異或破除功耗、時間差異與取值間的相關(guān)性等方面入手，如門電路級的防范[7]、抗測量技術(shù)[8]、重編碼技術(shù)[9]、隨機操作技術(shù)[10]，但這些防范措施在公鑰密碼中的實現(xiàn)，結(jié)果是效率降低、功耗增加或電路面積變大。其中最令人無法忍受的是：公鑰密碼原本就比分組密碼慢3個左右數(shù)量級，為了算法自身安全還要繼續(xù)降低效率。

等功耗編碼算法[11]運用香農(nóng)信息優(yōu)化理論，在保證甚至提高運算效率的前提下，同時獲取較好的抗功耗分析攻擊的能力，該算法的提出為公鑰密碼功耗分析攻擊的防范研究提供了新的發(fā)展方向。

本文對等功耗編碼算法的優(yōu)化改進及快速實現(xiàn)進行討論，并就真實硬件環(huán)境下該算法的功耗信息泄露進行深入分析，其研究成果對其他公鑰算法（如ECC橢圓曲線算法）也有借鑒意義。

2 冪剩余運算的BR實現(xiàn)算法

基于有限域上冪指數(shù)和離散對數(shù)的公鑰密碼體制，其核心運算有如下數(shù)學(xué)形式：

為保證密碼學(xué)上的安全性，式(1)中的各參數(shù)均采用大整數(shù)，如K、N的取值在1024bit以上，采用直接計算的方法對硬件設(shè)備要求極高，同時效率低下，在實踐中，一般采用一種迭代算法，稱為二元表示法(BR, binary representations)[12]。其他快速算法幾乎都建立在BR算法之上。

BR算法的具體實現(xiàn)形式有：從左至右(L-R)、從右至左(R-L)、左右混合或稱隨機指數(shù)(RAD,randomized exponentiation)幾種，以從左至右的BR(LR-BR)算法為例，給出算法的操作步驟如下[12]。

設(shè)：

式中，n為K的二進制長度。

輸入：P，K，N；

輸出：C；

步驟：

1) 置初始值C=1；

2) 對于 i = n -1,… ,0 ，計算 C =C2(modN)；

3) 若 ki=1，計算 C = PC ( mod N )；

4) i ≠ 0 ，返回3)；

5) 輸出結(jié)果。

BR算法在設(shè)計初，未考慮邊信道信息泄露，因此極易受邊信道攻擊，文獻[13] 分析了針對 BR算法各種可能的邊信道攻擊，并給出了真實環(huán)境下SPA攻擊成功實例。

3 等功耗編碼算法的分析與優(yōu)化

針對BR算法中不同的操作導(dǎo)致功耗差異帶來的邊信息泄露而提出的等功耗編碼實現(xiàn)算法[1]，其抗攻擊基本原理是使每一次迭代循環(huán)的操作都相同，則每一次循環(huán)消耗的時間相等，消耗的能量差異也就難以區(qū)分。該實現(xiàn)算法無疑可以有效地抵抗計時和SPA攻擊，也可使DPA攻擊的難度大幅度增加。

3.1 冪剩余運算的等功耗編碼算法原型

將式(1)中的指數(shù)K表示為

等功耗編碼算法的步驟如下。

1) 預(yù)計算Rj余數(shù)表：

2) 置初始值C= 1；

3) 對于i=s - 1 ,… ,0 ，計算：

4) 若 ki= j≠ 0 ，計算： C= RjC(mod N)，否則，計算 aC( mod N)，其中a為常數(shù)；

5)i≠0 ，返回3)；

6) 輸出結(jié)果C。

3.2 等功耗編碼算法的改進與實現(xiàn)

3.2.1 等功耗編碼原型算法的抗攻擊弱點

在等功耗編碼原型算法的第4）步中，當(dāng) ki=0時，只執(zhí)行一個模乘運算；而在其值為非零時，要執(zhí)行一個模乘運算，還執(zhí)行一個賦值操作，這個微小的差別能被攻擊者利用進行計時攻擊，從而獲取指數(shù)中的分段全零情況。

在不同的指數(shù)下， ki= 0 均使用相同常數(shù) a進行冗余計算，其對功耗的影響是一致的，這個弱點也可被攻擊者利用進行對比或模板分析攻擊，獲取指數(shù)中全零的情況。

3.2.2 等功耗編碼算法的改進

針對 ki= 0 時算法的缺陷，提出以下改進方案。

ki= 0 時：

其中，U是一個輔助冗余變量，存儲冗余計算的結(jié)果，消除 ki= 0 時無賦值運算操作的缺陷。而rand(R)為在余數(shù)表中隨機抽取的一個余數(shù)，這樣使得指數(shù)全0段對應(yīng)的操作數(shù)與指數(shù)非全0段對應(yīng)的操作數(shù)一樣，從而在操作數(shù)上無法區(qū)分兩者的差別，并且該隨機函數(shù)的種子與指數(shù)K相關(guān)，保證在相同指數(shù)下獲得相同的結(jié)果，這樣可避免攻擊者利用相同指數(shù)、明文反復(fù)運算，提取隨機信息。

該改進方案增加了一個賦值操作，同時將原算法中常數(shù) a改為隨機余數(shù)值，使得 ki= 0 時操作與ki≠ 0 完全相同，且 ki= 0 時運算結(jié)果也與 ki≠ 0 一致，完全掩蓋了 ki= 0 與 ki≠ 0 的差別，避免了針對ki= 0 的特殊攻擊。

3.2.3 等功耗編碼改進算法的快速實現(xiàn)

為提高算法的效率，采用蒙哥馬利算法對改進算法中的模乘運算進行優(yōu)化。

定義蒙哥馬利算法模除M(T, N)為定義蒙哥馬利算法模乘積MM(a, b, n)為

其中， r =2k, 2k-1≤ n ＜2k。

由式（9）可看出，蒙哥馬利算法模乘積的結(jié)果并非原模乘積的結(jié)果，因此在使用蒙哥馬利算法來實現(xiàn)等功耗編碼算法時，需對原等功耗編碼算法進行修正。

使用蒙哥馬利算法的等功耗編碼快速改進算法如下。

輸入：P，K，N；

輸出：C；

步驟：

1) 置初始值C=1 ；

2) 進行蒙哥馬利運算預(yù)處理：

P ' =MM( P, r2mod N , N )= Prmod N

C ' =MM( C, r2mod N , N )= Crmod N

3) 預(yù)計算所有的 Rj，生成余數(shù)表：

4) 對于 i = s - 1 ,… ,0 ，計算：

5) 若 xi= j≠ 0 ，計算：

否則，計算 U=MM ( rand(R), C' N)；

6) i ≠ 0 ，返回4)；

7) 進行蒙哥馬利運算后處理：

8) 輸出結(jié)果C。

其中，rand（R）為在余數(shù)表中隨機獲取一個余數(shù)。

在該快速實現(xiàn)算法中，只有第2）步中r2modN為一般模乘運算，其余模乘運算均轉(zhuǎn)換為蒙哥馬利運算。與原算法相比，雖然增加了 2個預(yù)處理、1個后處理共3個蒙哥馬利運算，但由于中間迭代次數(shù)較多，利用蒙哥馬利運算替代一般模除運算的等功耗編碼算法大大加快了整體算法的運算速度。

蒙哥馬利算法針對不同的操作數(shù)，其運算是固定的，因此每次運算的能量消耗差異極小，一般的SPA攻擊無法生效。

4 改進算法的抗攻擊能力實測分析

4.1 真實硬件環(huán)境下的功耗分析模型

文獻[13]對功耗分析模型與有效信息的提取技術(shù)進行了詳細(xì)的討論。本文使用了文獻[13]中分析模型：

該模型可進行信號處理，提取有用信息，由于篇幅所限，具體的研究結(jié)果請參考文獻[13]。

4.2 功耗測試平臺

功耗模型和功耗分析需求設(shè)計和實現(xiàn)的測試平臺框架如圖 1所示。密碼算法協(xié)處理單元使用Cyclone II 系列的EP2C8Q208C8 FPGA芯片為核心運算芯片，為做對比測試，片上先后實現(xiàn)了2組算法。

1) 數(shù)據(jù)總線寬度為 8bit的增加蒙哥馬利預(yù)處理的冪剩余R-L算法（BR算法的一種），其中底數(shù)、指數(shù)、模數(shù)均為32bit。算法采用模平方與模乘并行運算結(jié)構(gòu)，模平方與模乘均用蒙哥馬利算法實現(xiàn)。

圖1 測試平臺框架

2) 數(shù)據(jù)總線寬度為 8bit的等功耗編碼優(yōu)化算法，其中底數(shù)、指數(shù)、模數(shù)均為32bit。w取值為2。

4.3 實測信號與指數(shù)相關(guān)性分析

4.3.1 R-L并行算法的功耗信號與分析

圖2~圖4為R-L并行算法在不同指數(shù)下經(jīng)過信息處理后的冪剩余運算功耗軌跡圖，各圖像的不同之處正是對不同指數(shù)的刻畫。經(jīng)過對比觀測可發(fā)現(xiàn)，各功耗軌跡圖上均有界限分明的周期，正對應(yīng)于冪剩余運算的輪迭代。

圖2 指數(shù)為0x00000000時的功耗軌跡

圖3 指數(shù)為0x12345678時的功耗軌跡

圖4 指數(shù)為0xffffffff 時的功耗軌跡

從圖3可以看出，功耗變化較大的位置正是2個模乘器同時工作時，對應(yīng)指數(shù)取值為 1；功耗變化較小的位置對應(yīng)指數(shù)取值為0。而在圖2中，由于指數(shù)各比特位均相等，每次迭代所消耗功耗相同，因此各迭代間的波形幾乎相同，圖4的情況也是如此。由于對應(yīng)指數(shù)0與1產(chǎn)生的功耗不同，從圖2與圖4對比可看出圖4的功耗明顯比圖2大。

在圖2~圖4中，任意2個周期的時間間隔均相等，其原因是R-L并行算法消除了每次迭代的時間差異，因此無法在時間的差別上判斷指數(shù)當(dāng)前位的值，從而抵御了計時攻擊。

需要指出的是，R-L并行算法需要2個模乘器同步工作，這在一般的單運算器上無法完成，因此算法應(yīng)用有其局限性。

4.3.2 等功耗編碼改進快速算法的功耗信號與抗攻擊分析

在等功耗編碼算法中，迭代的次數(shù)不是指數(shù)的比特數(shù)，具體的次數(shù)與w的取值相關(guān)。因此，在不知道w的情況下，無法通過計時直接確定指數(shù)的比特以及迭代起始位置。即使采用窮舉搜索策略，計時攻擊的難度也已增加。

由于在每輪迭代中，對應(yīng)不同的指數(shù)，其運算操作完全相同，模平方運算和模乘運算均采用相同的蒙哥馬利運算，僅是操作數(shù)有所不同，其運算時間均相同，攻擊者無法通過每輪迭代的計時差異獲取對應(yīng)的指數(shù)信息。

從圖5的波形上看，任意2個迭代內(nèi)周期時間間隔均相等，波形一致，無法區(qū)分功耗的差別，可見改進后的快速等功耗編碼實現(xiàn)算法達(dá)到了抗計時攻擊的目的。

在改進的實現(xiàn)算法中，每一輪迭代循環(huán)（見步驟5））均要進行相同次數(shù)的蒙哥馬利運算，其功耗情況在操作相關(guān)性上無法區(qū)分。

當(dāng)指數(shù)ki為全零時，原算法只是采取了常數(shù)模乘運算，與其他指數(shù)情況下的操作存在一定差異。而在優(yōu)化實現(xiàn)算法中，采用在余數(shù)表中隨機選取一個余數(shù)進行蒙哥馬利運算，并將該結(jié)果存入某存儲單元，其操作與該余數(shù)對應(yīng)指數(shù)運算時完全一致，直接混淆了全零與其他指數(shù)值運算時的功耗差別，比原始算法更具抗“指數(shù)段全0分析”SPA的性能，圖5和圖6分別是指數(shù)為0x12345678和0xffffffff時的等功耗編碼改進快速算法功耗軌跡圖，在SPA攻擊者看來，兩者之間沒有差別，與圖2和圖4均相似。在采集大量的不同指數(shù)下該算法的功耗曲線進行分析后發(fā)現(xiàn)，各功耗曲線近似程度極大，無法從波形上進行SPA攻擊得到指數(shù)取值信息。

針對等功耗編碼算法的抗DPA特性[1]，DPA攻擊主要利用運算的數(shù)據(jù)與功耗間的相關(guān)性進行攻擊，可將系統(tǒng)噪聲、靜態(tài)偽操作形成的噪聲通過差分剔除，原型算法中的靜態(tài)偽操作實際可通過DPA鑒別出來。但對于優(yōu)化后的實現(xiàn)算法，其偽操作與真實操作完全一致，無法用一般的DPA方法加以剔除，因此攻擊者很難通過DPA直接區(qū)分“全0”和“非全0”指數(shù)段，實測結(jié)果限于篇幅，另撰文論述。

圖5 指數(shù)為0x12345678時等功耗編碼優(yōu)化算法的功耗軌跡

圖6 指數(shù)為0xffffffff時等功耗編碼優(yōu)化算法的功耗軌跡

5 結(jié)束語

本文在討論了等功耗編碼算法的抗攻擊弱點后，設(shè)計并實現(xiàn)了一個改進型快速等功耗編碼算法。提高了算法的抗功耗分析性能。利用功耗分析平臺，成功獲取各算法實現(xiàn)的功耗軌跡圖。通過對等功耗編碼優(yōu)化算法功耗軌跡圖的分析，證實該算法確實能有效抵御計時和SPA攻擊。該算法的抗DPA能力也在原理上被分析，其具體的實驗驗證另文論述。

致謝

作者誠摯感謝成都信息工程學(xué)院信息安全研究所的同仁萬武南、索望、陳艾東、杜之波，研究生周俐莎、朱冰、劉鶴、饒金濤等，感謝他（她）們在課題研究中和論文撰寫期間所做的大量協(xié)助工作和給予的無私幫助！沒有他們的工作，也不會取得本文的研究成果。

[1] KOCHER P. Timing attacks on implementations of diffie-hellman,RSA, DES, and other systems[A]. Proceedings of Advances in Cryptology-CRYPTO’96[C]. 1996. 104-113

[2] DHEM J F, KOEUME F, LEROUX P A, et al. A practical implementation of the timing attack[A]. Proceedings of CARDIS 1998[C].1998.14-16.

[3] MESSERGES T S, DABBISH E A, SLOAN R H. Investigations of power analysis attacks on smartcards[A]. Proc USENIX Workshop Smartcard Technology[C]. Chicago, Illinois ,USA , 1999. 151-161.

[4] KOCHER P, JAFFE J, JUN B. Differential power analysis[A]. Proceedings of Advances in Cryptology-CRYPTO’99[C]. 1999. 388-397.

[5] ITOH K, IZU T, TAKENAKA M. Address-bit differential power analysis of cryptographic schemes OK-ECDH and OK-ECDSA[A]. CHES 2002[C]. 2003. 129-143.

[6] ITOH K, IZU T, TAKENAKA M. A practical countermeasure against address-bit differential power analysis C D[A]. CHES 2003[C].2003.382-396.

[7] CORSONELLO P. An integrated countermeasure against differential power analysis for secure smart-cards[A]. ISCAS[C]. 2006. 5611-5614.

[8] RATANPAL G B, WILLIAMS R D, BLALOCK T N. An on-chip signal suppression countermeasure to power analysis attacks[J]. IEEE Transactions on Dependable and Secure Computing, 2004, 1(3): 179-189.

[9] MESSERGES T S. Securing the AES finalists against power analysis attacks [A]. Proceedings of Fast Software Encryption Workshop 2000[C]. 2000.150-164.

[10] GEBOTYS C H. A table masking countermeasure for low-energy secure embedded systems[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2006, 14(7): 740-753.

[11] 陳運,吳震, 陳俊等. 防范邊信道攻擊的等功耗編碼實現(xiàn)算法[J].電子科技大學(xué)學(xué)報, 2008,37 (2): 168-171.CHEN Y, WU Z, CHEN J, et al. Implementation of equivalent power consumption coding secure against side channel attack[J]. Journal of University of Electronic Science and Technology of China, 2008,37(2):168-171.

[12] 陳運. 信息加密原理[M]. 成都:電子科技大學(xué)出版社, 1996.CHEN Y. The Principle of Information Encryption[M]. University of Electronic Science and Technology of China Press, 1996.

[13] 吳震, 陳運, 陳俊等. 真實硬件環(huán)境下冪剩余功耗軌跡指數(shù)信息提取[J]. 通信學(xué)報, 2010, 31(2): 17-21.WU Z, CHEN Y, CHEN J, et al. Exponential information’s extraction from power traces of modulo exponentiation implemented on FPGA[J].Journal on Communications, 2010,31(2): 17-21.