真實(shí)硬件環(huán)境下冪剩余功耗軌跡指數(shù)信息提取

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

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

1 引言

冪剩余運(yùn)算是目前許多種流行公鑰算法或協(xié)議的核心運(yùn)算，若該運(yùn)算運(yùn)行時在邊信道泄露出信息，則可獲取密碼體制中密鑰的部分信息，嚴(yán)重者可直接破譯出密鑰。

目前，針對密碼設(shè)備運(yùn)行時邊信道信息泄露的攻擊發(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]等各類基于功耗軌跡進(jìn)行分析攻擊的技術(shù)，此類攻擊對密碼體制算法的實(shí)現(xiàn)與運(yùn)行時硬件安全都提出了新的挑戰(zhàn)。

研究者根據(jù)功耗分析攻擊的特性提出的各種防范方案主要從減小可測量的功耗差異、時間差異或破除功耗、時間差異與取值間的相關(guān)性等方面入手，如門電路級的防范[7]、抗測量技術(shù)[8]、重編碼技術(shù)[9]、隨機(jī)操作技術(shù)[10]以及綜合優(yōu)化壓縮等功耗技術(shù)[11]等。

目前國內(nèi)外對功耗分析攻擊和抵抗措施的研究大量集中在分組密碼體制上，同時由于實(shí)驗(yàn)條件的限制，研究以理論分析為主，輔之以計算機(jī)仿真結(jié)果作為支撐數(shù)據(jù)，缺乏在真實(shí)硬件環(huán)境下對公鑰密碼實(shí)施功耗攻擊的研究、分析和實(shí)測結(jié)果。Messerges等曾斷言，使用SPA攻擊難以在真實(shí)硬件環(huán)境下直接獲取RSA密鑰[12]。

下面對真實(shí)硬件環(huán)境下冪剩余運(yùn)算功耗信息泄露進(jìn)行綜合分析，其研究結(jié)果對所有使用冪剩余運(yùn)算作為核心運(yùn)算的公鑰密碼體制均適用（如RSA密碼體制），亦可移植到橢圓曲線密碼算法。

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

冪剩余運(yùn)算基本運(yùn)算表達(dá)式為

其中，指數(shù)K為敏感信息，在RSA中，可為私鑰的一部分，泄露其值或相關(guān)內(nèi)容的信息實(shí)質(zhì)即為泄露密鑰信息。

對于冪剩余運(yùn)算的實(shí)現(xiàn)，現(xiàn)已提出眾多實(shí)用快速算法，基本的快速算法有如下。

算法1 從左至右（L-R,left to right）二進(jìn)制表示求冪剩余算法[13]。

算法2 從右至左（R-L,right to left）二進(jìn)制表示求冪剩余算法[13]。

具體算法細(xì)節(jié)與其他快速算法請參閱文獻(xiàn)[13]。

經(jīng)過對各類快速實(shí)現(xiàn)算法的綜合考察，得到以下結(jié)論。

1) 冪剩余運(yùn)算是用復(fù)雜度較低的模乘運(yùn)算循環(huán)迭代來實(shí)現(xiàn)快速計算。迭代次數(shù)與指數(shù)的二進(jìn)制長度相關(guān)，甚至相等。

2) 在每次循環(huán)內(nèi)部，對應(yīng)指數(shù)位Ki的不同取值會執(zhí)行不同的操作，并產(chǎn)生不同的中間結(jié)果。

3) 在循環(huán)之間，執(zhí)行條件判斷操作，不同于循環(huán)內(nèi)部的操作。

由于實(shí)現(xiàn)算法在操作上有這些特征，發(fā)展出了下述攻擊方法。

3 冪剩余運(yùn)算的功耗分析攻擊

3.1 冪剩余實(shí)現(xiàn)算法中操作功耗與指數(shù)相關(guān)性分析

在實(shí)現(xiàn)算法中，主要的運(yùn)行指令有3類：數(shù)據(jù)傳輸、條件判斷和模乘（模平方）運(yùn)算，這 3類指令對應(yīng)的功耗大小、運(yùn)算時間均不相同，特征明顯。

通過觀察大量功耗曲線與硬件電路功耗原理分析，有以下結(jié)論。

1) 在功耗軌跡上，每輪循環(huán)的邊界是可分辨的，通過分析循環(huán)的次數(shù)，可得到指數(shù)的位數(shù)信息。

2) 從運(yùn)算時間上看，在功耗軌跡圖中每輪循環(huán)對應(yīng)的功耗部分不同長短時間對應(yīng)不同的 Ki值。將所有循環(huán)對應(yīng)的 Ki值都推斷出來，便可直接破解出指數(shù)的二進(jìn)制表示。

3) 從功耗情況上看，Ki取值不同時，對應(yīng)的功耗情況也不同。根據(jù)測量每輪循環(huán)對應(yīng)的功耗的不同可反推出 Ki的取值，也可成功獲得指數(shù)的二進(jìn)制表示。

3.2 真實(shí)硬件環(huán)境下的功耗分析模型與操作相關(guān)性信息的提取技術(shù)

在進(jìn)行實(shí)際功耗分析攻擊時，設(shè)備自身、環(huán)境等產(chǎn)生的噪聲均會與功耗信號混合，使得真實(shí)功耗測量值與軟件仿真環(huán)境下獲得的數(shù)值相差甚遠(yuǎn)。因此，在測量和分析時，需采取一定信號處理手段，將噪聲信號壓制，從而更有效地獲取信息。

在實(shí)測了大量功耗曲線的基礎(chǔ)上，根據(jù)總體功耗變化與各類功耗分量之間關(guān)系的綜合分析，被測設(shè)備的總功耗可抽象簡化成如下模型。

在模型中，Ps為靜態(tài)功耗；f(O,D,t)為t時刻某項(xiàng)操作O在處理數(shù)據(jù)D時密碼運(yùn)算設(shè)備所產(chǎn)生的動態(tài)功耗；N(t)為t時刻的噪聲總功耗；P(t)為在t時刻被測電路的總功耗。其中本文所關(guān)注的有效信息的信號為操作O的函數(shù)。

從模型中可以看出，靜態(tài)功耗Ps和噪聲總功耗N(t)是妨礙有效信息提取的信號，應(yīng)盡量抑制；信號f(O,D,t)中含有操作和數(shù)據(jù)這2部分對總功耗的影響，為更好地提取操作與功耗間的相關(guān)性，需抑制數(shù)據(jù)變化部分造成的動態(tài)功耗。

利用式(2)，針對被測信號的特征，可對其進(jìn)行以下處理。

1) 靜態(tài)功耗 Ps可利用一般濾靜處理即可消除其影響；

2) 噪聲中對測量影響比較大的為高斯白噪聲，因此利用去白噪方法去除大部分的N(t)；

3) 根據(jù)數(shù)據(jù)傳輸時采集到的信號特征制成數(shù)據(jù)信號抑制器來抑制數(shù)據(jù)D對總功耗的影響。

經(jīng)過以上信號處理后，功耗信號Pn(t)近似等于∑ f(O,t)，其中f(O,t)為t時刻某項(xiàng)操作O執(zhí)行時密碼運(yùn)算設(shè)備所產(chǎn)生的動態(tài)功耗。而通過分析P(t)，就可以獲取指數(shù)與操作之間的相關(guān)性信息。

4 實(shí)測結(jié)果及其分析

4.1 測試平臺的構(gòu)架

根據(jù)式(2)和功耗分析需求而設(shè)計的測試平臺框架如圖1所示。其基本流程為由信息處理服務(wù)器將測試案例傳輸至邊信道攻擊平臺，通過協(xié)議轉(zhuǎn)換將數(shù)據(jù)送至受攻擊單元，在受攻擊單元正常運(yùn)行時，由功耗檢測電路采集功耗信號送至信號處理單元進(jìn)行各類信號處理，處理后的結(jié)果由示波器顯示，并通過示波器將數(shù)據(jù)返回至信息處理服務(wù)器。

圖1 測試平臺框圖

在實(shí)現(xiàn)中密碼算法協(xié)處理單元使用 Cyclone II系列的EP2C8Q208C8 FPGA芯片為核心運(yùn)算芯片，片上實(shí)現(xiàn)了數(shù)據(jù)總線寬度為 8bit的冪剩余 R-L算法，其中底數(shù)、指數(shù)、模數(shù)均為32bit。本文演示成果所使用的算法為R-L增加預(yù)處理的模平方與模乘并行運(yùn)算結(jié)構(gòu)，其中模平方與模乘均用蒙哥馬利算法實(shí)現(xiàn)。其他算法實(shí)現(xiàn)也可得相似結(jié)果。

4.2 操作相關(guān)性信號提取技術(shù)的實(shí)測結(jié)果

在上節(jié)所述構(gòu)架的測試平臺上運(yùn)行指數(shù) K為0x0f0f0f0f的冪剩余運(yùn)算，在不同的信號處理模式下，獲得不同的實(shí)測結(jié)果。

1) 無任何信號處理下所獲得的原始功耗軌跡如圖2所示。觀察該圖可發(fā)現(xiàn)無法直接獲取操作的相關(guān)信息。

圖2 K=0x0f0f0f0f時的原始功耗軌跡示波器截圖

2) 增加了去靜態(tài)功耗處理后所獲得的功耗軌跡如圖3所示，經(jīng)觀察可發(fā)現(xiàn)有效信號已被放大。

圖3 K=0x0f0f0f0f時，抑制Ps的功耗軌跡示波器截圖

3) 對該信號再進(jìn)行抑制數(shù)據(jù) D的處理，其功耗軌跡如圖4所示，從圖中可看出功耗總體變化較明顯，但細(xì)節(jié)仍被噪聲覆蓋。

圖4 指K=0x0f0f0f0f時，抑制Ps和D的功耗軌跡示波器截圖

4) 對該信號進(jìn)行降噪處理后的結(jié)果如圖 5所示，該實(shí)測結(jié)果直接顯示了對應(yīng)指數(shù)的操作對功耗變化的影響。

圖5 K=0x0f0f0f0f時，抑制Ps、D和白噪聲后的功耗軌跡示波器截圖

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

由于信號處理已抑制了數(shù)據(jù)傳輸信號對動態(tài)功耗Pn(t)的影響干擾，因此以下對功耗軌跡圖的分析均忽略底數(shù)、模數(shù)的差異。圖示均為實(shí)測結(jié)果的截屏。

圖6～圖9為不同指數(shù)下經(jīng)過信息處理后的冪剩余運(yùn)算功耗軌跡圖。

經(jīng)過圖像對比，各功耗軌跡圖上均有 33個界限分明的周期，正對應(yīng)于冪剩余運(yùn)算算法中的33輪迭代，其中第 1個周期對應(yīng)蒙哥馬利預(yù)處理，后 32個周期按時序從右到左一一對應(yīng)指數(shù)的 32bit。

圖6是指數(shù)為0時產(chǎn)生的功耗軌跡圖，此軌跡圖可作為 SDPA（簡單差分功耗分析）攻擊的基準(zhǔn)軌跡。

圖7為K=0x0f0f0f0f時的功耗軌跡，通過對比圖 8 可以看出，第 2～5、10～13、18～21、26～29 個上升型周期間隔對應(yīng)指數(shù)K中取值為1的位數(shù)，余下的平坦型周期間隔正對應(yīng)指數(shù)K中取值為0的位數(shù)。根據(jù)功耗模型可知，上升型周期間隔的形成原因就是在指數(shù)取值為1時，2個蒙哥馬利模乘器同時工作，其功耗比一個模乘器工作要大。

同理在圖 8（K=0x12345678）、圖 9（K=0xffffffff）中，功耗變化較大的位置正是 2個模乘器同時工作時，對應(yīng)指數(shù)取值為 1；功耗變化較小的位置對應(yīng)指數(shù)取值為0。

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

圖6 K=0x00000000時的冪剩余運(yùn)算功耗軌跡示波器截圖

圖7 K=0x0f0f0f0f時的冪剩余運(yùn)算功耗軌跡示波器截圖

圖8 K=0x12345678時的冪剩余運(yùn)算功耗軌跡示波器截圖

圖9 K=0xffffffff時的模剩余計算功耗軌跡示波器截圖

圖10為增加了抵抗SPA攻擊靜態(tài)掩蓋算法的冪剩余運(yùn)算對應(yīng)功耗軌跡圖，指數(shù)K=0x12345678。

圖10 K=0x12345678時增加抗SPA攻擊算法的功耗軌跡示波器截圖

算法3 抗SPA攻擊靜態(tài)掩蓋的R-L算法輸入：正整數(shù)P,N,K=(Kt-1,Kt-2,…,K1,K0)輸出：C=Pkmod N

算法3實(shí)質(zhì)是對應(yīng)不同的指數(shù)取值都做相同的操作，消除因操作差異所產(chǎn)生的功耗差異，獲得抗SPA攻擊效果。從功耗軌跡上看，其功耗變化與圖9（K=0xffffffff）沒有差別，因此具有抗 SPA攻擊能力。

5 結(jié)束語

在對實(shí)測的大量功耗軌跡數(shù)據(jù)進(jìn)行對比觀察和理論分析后，證實(shí)真實(shí)硬件環(huán)境下功耗分析模型的正確性。并應(yīng)用以該模型為基礎(chǔ)的有效信息提取技術(shù)制成測試平臺，在實(shí)際測試中成功實(shí)施了對32bit指數(shù)的冪剩余運(yùn)算的SPA攻擊，成功獲取其對應(yīng)的指數(shù)值，證實(shí)利用SPA攻擊可成功破譯RSA的密鑰，推翻了Messerges等關(guān)于使用SPA攻擊難以在真實(shí)硬件環(huán)境下獲取RSA密鑰的論斷[12]。同時通過對靜態(tài)掩蓋抗 SPA攻擊算法功耗軌跡圖的分析，證實(shí)在算法中添加偽操作能夠使冪剩余運(yùn)算電路抵御針對操作相關(guān)性的SPA攻擊。

文中提出的功耗分析模型和方法對所有使用冪剩余運(yùn)算作為核心運(yùn)算的公鑰密碼體制均適用（如 RSA密碼體制），亦可移植到橢圓曲線密碼算法。

此外，作者利用該模型和信息提取技術(shù)，還成功實(shí)施對冪剩余算法的SDPA、DPA等攻擊，篇幅所限，研究結(jié)果將另文討論。

致謝

作者誠摯感謝成都信息工程學(xué)院信息安全研究所的同仁：萬武南、索望、張金全、陳艾東，研究生杜之波、周俐莎、朱冰、劉鶴、李姍姍等，感謝他（她）們在課題研究進(jìn)行中和論文撰寫期間所做的大量協(xié)助工作和給予的無私幫助！

[1] KOCHER P.Timing attacks on implementations of Diffie-Hellman,RSA,DSS,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[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[M].The Circuit is Under Patenting.US Provisional Patent Application 60/643,165.

[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.

[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 Intergration(VLSI) systems,2006,14(7): 740-753.

[11] 陳運(yùn),吳震,陳俊,萬武南,呂永其.防范邊信道攻擊的等功耗編碼實(shí)現(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] MESSERGES T S,DABBISH E A,SLOAN R H.Power analysis attacks of modular exponentiation in smartcards[A].Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems(CHES,99)[C].1999.144-157.

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