真實硬件環境下冪剩余功耗軌跡指數信息提取

吳震，陳運，陳俊，王敏

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

1 引言

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

目前，針對密碼設備運行時邊信道信息泄露的攻擊發展迅速，從計時攻擊(TA,timing analysis)[1,2]到簡單功耗分析(SPA,simple power analysis)[3]和差分功耗分析(DPA,differential power analysis)[4]，現在又發展出地址差分功耗分析攻擊(ADPA,address-bit differential power analysis)[5,6]等各類基于功耗軌跡進行分析攻擊的技術，此類攻擊對密碼體制算法的實現與運行時硬件安全都提出了新的挑戰。

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

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

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

2 冪剩余運算的實現方法簡析

冪剩余運算基本運算表達式為

其中，指數K為敏感信息，在RSA中，可為私鑰的一部分，泄露其值或相關內容的信息實質即為泄露密鑰信息。

對于冪剩余運算的實現，現已提出眾多實用快速算法，基本的快速算法有如下。

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

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

具體算法細節與其他快速算法請參閱文獻[13]。

經過對各類快速實現算法的綜合考察，得到以下結論。

1) 冪剩余運算是用復雜度較低的模乘運算循環迭代來實現快速計算。迭代次數與指數的二進制長度相關，甚至相等。

2) 在每次循環內部，對應指數位Ki的不同取值會執行不同的操作，并產生不同的中間結果。

3) 在循環之間，執行條件判斷操作，不同于循環內部的操作。

由于實現算法在操作上有這些特征，發展出了下述攻擊方法。

3 冪剩余運算的功耗分析攻擊

3.1 冪剩余實現算法中操作功耗與指數相關性分析

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

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

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

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

3) 從功耗情況上看，Ki取值不同時，對應的功耗情況也不同。根據測量每輪循環對應的功耗的不同可反推出 Ki的取值，也可成功獲得指數的二進制表示。

3.2 真實硬件環境下的功耗分析模型與操作相關性信息的提取技術

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

在實測了大量功耗曲線的基礎上，根據總體功耗變化與各類功耗分量之間關系的綜合分析，被測設備的總功耗可抽象簡化成如下模型。

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

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

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

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

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

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

經過以上信號處理后，功耗信號Pn(t)近似等于∑ f(O,t)，其中f(O,t)為t時刻某項操作O執行時密碼運算設備所產生的動態功耗。而通過分析P(t)，就可以獲取指數與操作之間的相關性信息。

4 實測結果及其分析

4.1 測試平臺的構架

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

圖1 測試平臺框圖

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

4.2 操作相關性信號提取技術的實測結果

在上節所述構架的測試平臺上運行指數 K為0x0f0f0f0f的冪剩余運算，在不同的信號處理模式下，獲得不同的實測結果。

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

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

2) 增加了去靜態功耗處理后所獲得的功耗軌跡如圖3所示，經觀察可發現有效信號已被放大。

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

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

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

4) 對該信號進行降噪處理后的結果如圖 5所示，該實測結果直接顯示了對應指數的操作對功耗變化的影響。

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

4.3 實測功耗信號與指數相關性分析

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

圖6～圖9為不同指數下經過信息處理后的冪剩余運算功耗軌跡圖。

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

圖6是指數為0時產生的功耗軌跡圖，此軌跡圖可作為 SDPA（簡單差分功耗分析）攻擊的基準軌跡。

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

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

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

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

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

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

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

圖10為增加了抵抗SPA攻擊靜態掩蓋算法的冪剩余運算對應功耗軌跡圖，指數K=0x12345678。

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

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

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

5 結束語

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

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

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

致謝

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

[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] 陳運,吳震,陳俊,萬武南,呂永其.防范邊信道攻擊的等功耗編碼實現算法[J].電子科技大學學報,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] 陳運.信息加密原理[M].成都:電子科技大學出版社,1996.CHEN Y.The Principle of Information Encryption[M].Chengdu:University of Electronic Science and Technology of China Press,1996.