吳震，陳運(yùn)，王敏，陳俊

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

1 引言

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

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

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

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

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

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

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

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

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

設(shè)：

式中，n為K的二進(jìn)制長(zhǎng)度。

輸入：P，K，N；

輸出：C；

步驟：

1) 置初始值C=1；

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

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

4) i ≠ 0 ，返回3)；

5) 輸出結(jié)果。

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

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

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

3.1 冪剩余運(yùn)算的等功耗編碼算法原型

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

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

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

2) 置初始值C= 1；

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

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

5)i≠0 ，返回3)；

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

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

3.2.1 等功耗編碼原型算法的抗攻擊弱點(diǎn)

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

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

3.2.2 等功耗編碼算法的改進(jìn)

針對(duì) ki= 0 時(shí)算法的缺陷，提出以下改進(jìn)方案。

ki= 0 時(shí)：

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

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

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

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

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

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

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

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

輸入：P，K，N；

輸出：C；

步驟：

1) 置初始值C=1 ；

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

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

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

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

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

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

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

6) i ≠ 0 ，返回4)；

7) 進(jìn)行蒙哥馬利運(yùn)算后處理：

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

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

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

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

4 改進(jìn)算法的抗攻擊能力實(shí)測(cè)分析

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

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

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

4.2 功耗測(cè)試平臺(tái)

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

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

圖1 測(cè)試平臺(tái)框架

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

4.3 實(shí)測(cè)信號(hào)與指數(shù)相關(guān)性分析

4.3.1 R-L并行算法的功耗信號(hào)與分析

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

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

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

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

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

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

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

4.3.2 等功耗編碼改進(jìn)快速算法的功耗信號(hào)與抗攻擊分析

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

致謝

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

[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] 陳運(yùn),吳震, 陳俊等. 防范邊信道攻擊的等功耗編碼實(shí)現(xiàn)算法[J].電子科技大學(xué)學(xué)報(bào), 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] 陳運(yùn). 信息加密原理[M]. 成都:電子科技大學(xué)出版社, 1996.CHEN Y. The Principle of Information Encryption[M]. University of Electronic Science and Technology of China Press, 1996.

[13] 吳震, 陳運(yùn), 陳俊等. 真實(shí)硬件環(huán)境下冪剩余功耗軌跡指數(shù)信息提取[J]. 通信學(xué)報(bào), 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.