一種抗側信道攻擊的隨機功耗方法

李子臣　孫亞飛　楊亞濤　梁　斕　湯永利

1(西安電子科技大學通信工程學院　陜西 西安 710071) 2(北京印刷學院　北京 102600) 3(北京電子科技學院　北京 100070) 4(河南理工大學計算機科學與技術學院　河南 焦作 454000)

0　引　言

RSA密碼算法是由Ron Rivest、Adi Shamir和Leonard Adleman[1]于1978年提出的著名公鑰密碼體制。目前關于RSA密碼算法的研究已經(jīng)相當成熟，且廣泛應用在多個行業(yè)內。同時，也正是由于其應用的廣泛性，有大量的研究人員對其算法進行漏洞分析。傳統(tǒng)的數(shù)學分析方法包括：RSA小指數(shù)攻擊[2]、非共模攻擊及共模攻擊[3]、循環(huán)攻擊[4]等。有別于傳統(tǒng)攻擊方法的是文獻[5]提出的計時攻擊，也從此開辟了關于RSA的側信道攻擊。

近年來，國內外針對RSA密碼算法的側信道攻擊與防御研究主要有：文獻[6]針對部分密鑰泄露，給出攻擊方法，并提出相應的防御策略。文獻[7]指出常規(guī)的模冪運算并不能達到其聲稱的抵抗計時攻擊效果。文獻[8]針對采用盲化策略的RSA密碼算法進行能量攻擊，通過采用多條能量跡成功對RSA實現(xiàn)攻擊。

本文通過分析基于大整數(shù)分解困難問題及基于橢圓曲線離散對數(shù)問題的核心運算，詳細介紹側信道攻擊中的計時攻擊與能量攻擊技術，結合運算本身的性質及側信道攻擊的關鍵點，提出一種隨機功耗的思想來提高密碼算法的安全性及效率。

與RSA類似的橢圓曲線公鑰密碼體制[9]，其核心運算均為如下：y=mxmodn。為便于計算，針對此冪指數(shù)運算，我們一般采用從左向右、從右向左及隨機指數(shù)三種方法進行運算?？紤]到運算效率，我們采用蒙哥馬利模乘器來加速其運算。下面敘述從左向右、從右向左算法及隨機算法的蒙哥馬利實現(xiàn)算法。首先，計算x=ak(modn)，將k表示成二進制形式k=(1kt-1…k1k0)2。

算法1從左向右算法

ak=(…((a2·akt-1)2·akt-2)2·…·ak1)2·ak0。

Input:t,k0,k1,…,kt-1,a,n

Setx=a

Fori=t-1,t-2,…,1,0repeat

Setx=x2(modn)

Ifki=1thensetx=xa(modn)

Output:x

算法2從右向左。

ak=a2t·((a2t-1)kt-1·…·((a22)k2·((a2)k1·(ak0·1)))…)。

Input:t,k0,k1,…,kt-1,a,n

Setx=1,y=a

Fori=0,1,…,t-1repeat

Ifki=1thensetx=xy(modn)

Sety=y2(modn)

Setx=xy(modn)

Output:x

算法3隨機指數(shù)。

Input:t,k0,k1,…,kt-1,a,n

Setx=1,y=a,z=random(1,n-2)

Fori=z,…,n-2repeat

Ifki=1thensetx=xy(modn)

Sety=y2(modn)

Setx=xy(modn)

Fori=z-1,…,0repeat

x=x2modn

Ifki=1thensetx=xy(modn)

Output:x

1　側信道攻擊及防御技術

通過上述模冪運算，可知，當對應bit位為1的時候，與bit位為0相比較，多了一個乘法同余運算。因此，其運算時間和能量消耗明顯增多，利用此信息，能夠方便、快速、有效地實施計時攻擊及能量攻擊。

1.1　計時攻擊

計時攻擊[5]通過獲得一系列經(jīng)密碼芯片處理后的信息及處理時間，根據(jù)應答時序差來進行密鑰的推斷。計時攻擊模型如圖1所示。

圖1　計時攻擊模型

其中，m：消息，k：密鑰，S：輸出，A：算法。A(m,k)=m*k,*指算法，T：算法計算需要的時間，T(m,k)=t[A(m,k)]。

假定計算中密鑰恒定，且監(jiān)聽者已經(jīng)破解一組消息及計算時間T，現(xiàn)為了攻擊密鑰的第i個比特ki，當監(jiān)聽者捕獲時間T(m,ki)，則可建立函數(shù)判斷比特位的值。

假定隨機變量v0,v1的分布是不同的，通過觀察實際的T(m,0)與T(m,1)的分布，則有可能推測出ki，進而推測出完整的密鑰值。

1.2　能量攻擊

能量攻擊[10]主要有：簡單能量攻擊SPA(Simple Power Analysis)和差分能量攻擊DPA(Differential Power Analysis)。

簡單能量攻擊：通過分析硬件電路加密時釋放出的能量特征獲取與密鑰相關的信息，根據(jù)能量曲線的特征及分析者的經(jīng)驗就可直觀分析出指令執(zhí)行的順序。程序運行時，能量曲線有明顯的不同，通常情況下軌跡較寬且能量消耗較多對應密鑰位“1”，否則，對應密鑰位“0”。逐位逐比特對密鑰位進行猜測，即可完成對算法的破譯。

差分能量攻擊：根據(jù)能量曲線的差分信號分析出所需的關鍵信息，并采集多組能量曲線及每條曲線對應的明密文，需要大量的信息及一定的SPA分析經(jīng)驗和長時間分析運算。DPA需要采集多組能量曲線，將其作為先驗函數(shù)，而將猜測的密鑰組根據(jù)一定規(guī)則進行分類作為后驗函數(shù)，通過找出兩組函數(shù)所具有信息量的相關性，若相關性強，則密鑰猜測正確，反之，重新采集數(shù)據(jù)并作比對。

1.3　防御措施

針對側信道攻擊技術的特點，主要是防御思想是通過增加冗余信息、延長算法執(zhí)行時間、加入固定(隨機)噪聲及擾亂能量曲線等。常用的側信道攻擊防御措施主要有：掩碼技術[11]、功耗平衡技術[12]及功耗擾亂技術。其中掩碼技術分為布爾掩碼、多項式掩碼及內積掩碼，都是通過變換掩蓋明文信息或中間結果，即使破譯成功，得到的也不是原始明文信息。功耗技術主要是通過增加時間或者能量的消耗，加大噪聲功率，減少信噪比，提高信息提取難度，從而達到防御目的。

2　隨機功耗算法實現(xiàn)

信息的泄露主要是由于時序差及能量的消耗所引起，理論上講，設計一種算法，增加執(zhí)行代碼，使得對于“0”和“1”執(zhí)行相同的動作，這樣就能使得每一次計算消耗的能量就無法區(qū)分，且計算過程的時間相同。因此，通過此方法能很好地防御SPA和DPA。

根據(jù)上述基本思想，本文提出隨機功耗算法，并給出編碼實現(xiàn)如下,以從左向右算法為例：

對于計算x=ak(modn)，將k表示成二進制形式k=(1kt-1…k1k0)2。

算法4從左向右隨機功耗算法

ak=(…((a2·akt-1)2·akt-2)2·…·ak1)2·ak0。

Input:t,k0,k1,…,kt-1,a,n

Setx=a

Fori=t-1,t-2,…,1,0repeat

Setx=x2(modn)

Ifki=1thensetx=xa(modn)

Ifr=random(0,1)=1thensetx=rx(modn)

Output:x

其中r=random(0,1)表示r為隨機從{0,1}中選取。對于從右向左及隨機算法，有類似的改進。

3　方案分析

3.1　抗計時攻擊

在每輪的迭代運算中，當比特位不為1而隨機數(shù)r為1的時候，算法包含偽操作，耗時增加。由于隨機數(shù)的存在，造成時序差的混亂，即對于比特位為0的運算，耗時是不固定的，同時也混淆了0和1的時間消耗，這樣攻擊者就無法通過對比迭代運算的時序差獲取相應的密鑰信息。

假設密鑰比特位出現(xiàn)“0”和“1”的概率是完全隨機的，對于全“0”字段，其對應的操作是重復進行的，由于隨機數(shù)的參與，或造成其消耗的時間類似于有比特位為1的運算參與。攻擊者無法通過計時獲取密鑰的具體內容。

綜合以上分析，本文提出的隨機功耗算法能夠有效地達到抗計時攻擊的目的。

3.2　抗能量攻擊

對于抗簡單能量攻擊：在隨機功耗算法中，當滿足隨機數(shù)為1時，存在偽操作運算。偽操作運算在多精度算法相同的情況下，消耗的平均能量是相同，由于隨機數(shù)的存在，攻擊者無法根據(jù)全“0”時的曲線有效分析出原比特值。

雖說偽操作運算在一定程度上會存在泄露信息的風險，但可以使用簡單的時序控制屏蔽信息泄露，加之隨機數(shù)的混淆作用，可以有效地防御SPA攻擊。

對于抗差分能量攻擊：差分能量攻擊能夠通過差分計算將噪聲和偽操作剔除，然后通過簡單能力分析即可破譯密碼。

隨機功耗算法則不同，由于當偽隨機操作被過濾之后，攻擊者可以區(qū)分全“1”字段，然而這樣的字段概率是很小的。通過模冪運算的操作步驟可知，密鑰比特位猜測的關鍵是本輪迭代中是否有乘同余操作，若有，則對應指數(shù)為“1”，否則為“0”。平方剩余的計算則與指數(shù)位取值無關。

對于n比特長的密鑰，若要成功破譯密碼算法，則其關鍵是確定非全“0”指數(shù)段的取值。而這樣的情況有2n-1種，而對于比特位為“1”的字節(jié)，其每次計算消耗的能量也是隨機的，因此無法有效地區(qū)分取值。若要從相同的操作中分析出對應比特位的具體值，則攻擊者需要采用高階攻擊的方法。導致所需采集和處理的數(shù)據(jù)呈指數(shù)增長，而根據(jù)文獻[13]的結果，三階以上的DPA實施起來都是相當困難。

綜上所述，該隨機功耗算法能夠有效地混淆能量曲線，加大分析破譯難度。從而達到防御側信道攻擊的效果。

4　效率分析

本節(jié)從算法消耗的時間及運行過程消耗的能量進行分析。算法設計本身就是采用運算效率較高的蒙哥馬利形式的算法，因此，運算效率相比較傳統(tǒng)的算法[14]，有明顯的提高。

在運行效率上，假設密鑰長度為n比特長，其中0、1各占50%，執(zhí)行一次模平方操作消耗的時間為T，一次模乘操作消耗時間為T。對于未加保護的原始方案，當比特位為1時，需要執(zhí)行模平方與模乘計算，需要的執(zhí)行時間為n/2×(T+T)=nT；當比特位為0時，僅有一次模乘運算，需要的執(zhí)行時間為nT/2，共計需要執(zhí)行的時間為3nT/2。對于等功耗編碼的實現(xiàn)方式，當比特位為1時，每次均需要執(zhí)行一次模平方計算和模乘計算，則需要執(zhí)行的時間為：n/2×(T+T)=nT；對于比特位為0時，每次計算時同樣需要執(zhí)行一次模平方計算和模乘計算，則需要執(zhí)行的時間為：n/2×(T+T)=nT，共計需要執(zhí)行的時間為2nT。針對本文提出的方法，當比特位為1時，計算時間為n/2×(T+T)=nT，當比特位為0時，有一半的需要執(zhí)行模平方操作，需要執(zhí)行時間為nT/2，另一半需要的時間為nT/4，因此，需要的總運算時間為：nT+nT/2+nT/4=7nT/4。

在能量消耗方面，假設執(zhí)行一次模平方操作消耗能量為P/2，一次模乘操作消耗能量為P/2。對于未加保護的原始方案，當比特位為1時，需要消耗的能量為nP，當比特位為0時，均需要進行模乘操作，需消耗能量為nP/2，共需消耗能量為3nP/2。等功耗編碼方式，對于所有的0比特位時，均執(zhí)行模平方操作，使得0比特位與1比特位消耗的能量相同，共需消耗能量為2nP，提高了方案的安全性，但是增大了能量的消耗。本文所提出的方案對比特位為0時進行處理，當比特位為0時，以一定的概率進行模平方操作，假設n長比特中0、1各占50%，比特位為0的字節(jié)中，有50%的做模平方操作。當比特位為0時，均需要進行模乘操作，需消耗能量為nP/2，存在一半的比特位執(zhí)行模平方操作，即能量消耗為1/2×nP/2=nP/4，則共需消耗的能量為7nP/4。

通過分析比較，本文提出的方案，比原始方案增加了15%左右的時間和能耗開銷，但是提高了方案的安全性；對比等功耗編碼實現(xiàn)方式節(jié)省了15%左右的時間和能耗開銷，但同樣的能保證方案的安全性。針對目前RSA密碼算法的安全密鑰長度至少為2 048比特，文獻[12]中的算法至少增加1 000次模乘，而本文所設計的算法，與文獻[12]相比較節(jié)約了至少500次模乘，在效率上有大幅度的提高。

由此可以看出，改進后的隨機功耗算法能夠有效地節(jié)省運算時間，提高執(zhí)行效率。同時，也正是由于隨機數(shù)的引入，對能量的消耗起到一個很好的混淆效果，使得能量攻擊難度加大。表1給出本文算法與蒙哥馬利算法及靜態(tài)掩蓋法的效率對比。

表1　算法效率對比分析

其中，P為消耗的單位能量。

5　結　語

本文通過設計一種隨機功耗算法，既能提高模冪運算的安全性，同時還能保證其效率相對較高。該算法能夠有效地抵抗計時攻擊及能量攻擊，在運行效率上，能夠提高15%左右；在功耗上能夠節(jié)省15%左右。該方法便于應用在橢圓曲線公鑰密碼體制，對所有涉及模冪運算的算法都有一定的借鑒意義。

[1] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the Acm, 1978, 26(2):96-99.

[2] 韓立東,王小云,許光午. RSA密碼系統(tǒng)小CRT解密指數(shù)的攻擊分析[J]. 中國科學:信息科學,2011,41(2):173-180.

[3] Zou H. An Prime Generating Scheme to Avoid Effectively Common Modulus Attack on RSA[J]. Computer Engineering & Applications, 2004, 40(27):88-91.

[4] 姜正濤,懷進鵬,王育民. RSA推廣循環(huán)攻擊實效性與弱模問題的研究與分析[J]. 通信學報,2009,30(6):70-74.

[5] Kocher P C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[C]//International Cryptology Conference on Advances in Cryptology. Springer-Verlag, 1996:104-113.

[6] Cimato S, Mella S, Susella R. Partial Key Exposure Attacks on RSA with Exponent Blinding[C]//International Conference on E-Business and Telecommunications. Springer International Publishing, 2015:364-385.

[7] Schindler W. Exclusive Exponent Blinding May Not Suffice to Prevent Timing Attacks on RSA[M]//Cryptographic Hardware and Embedded Systems-CHES 2015. Springer Berlin Heidelberg, 2015: 229-247.

[8] Schindler W, Wiemers A. Power attacks in the presence of exponent blinding[J]. Journal of Cryptographic Engineering, 2014, 4(4):213-236.

[9] Menezes A J. Elliptic Curve Public Key Cryptography[J]. International Course on the State of the Art & Evolution of Computer Security & Industrial Cryptography Location Leuven Be Date, 1993(3):76-79.

[10] Kocher P, Jaffe J, Jun B. Differential Power Analysis[C]//International Cryptology Conference on Advances in Cryptology. Springer-Verlag, 1999:388-397.

[11] 任燕婷,烏力吉,李翔宇,等. 抗攻擊低功耗RSA處理器設計與實現(xiàn)[J]. 清華大學學報(自然科學版),2016,56(1):1-6.

[12] 陳運,吳震,陳俊,等. 防范邊信道攻擊的等功耗編碼實現(xiàn)算法[J]. 電子科技大學學報,2008,37(2):168-171.

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

[14] 陳運,龔耀寰. 大數(shù)冪剩余的二進制冗余數(shù)Montgomery算法[J]. 電子科技大學學報,2000,29(6):587-590.