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

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

1 引言

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

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

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

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

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

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

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

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

對(duì)于冪剩余運(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é)與其他快速算法請(qǐng)參閱文獻(xiàn)[13]。

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

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

2) 在每次循環(huán)內(nèi)部，對(duì)應(yīng)指數(shù)位Ki的不同取值會(huì)執(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類指令對(duì)應(yīng)的功耗大小、運(yùn)算時(shí)間均不相同，特征明顯。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 測(cè)試平臺(tái)的構(gòu)架

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

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

在實(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)性信號(hào)提取技術(shù)的實(shí)測(cè)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖9 K=0xffffffff時(shí)的模剩余計(jì)算功耗軌跡示波器截圖

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

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

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

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

5 結(jié)束語

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

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

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

致謝

作者誠(chéng)摯感謝成都信息工程學(xué)院信息安全研究所的同仁：萬武南、索望、張金全、陳艾東，研究生杜之波、周俐莎、朱冰、劉鶴、李?yuàn)檴櫟?，感謝他（她）們?cè)谡n題研究進(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é)報(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] 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.