RSA算法時序模板SDPA攻擊研究

許 森, 陳 運, 陳 俊, 饒金濤, 孫敦燦

(成都信息工程學院信息安全研究所,四川成都610225)

1 引言

自從1996年Paul Kocher[1-2]首次公開發表功耗分析攻擊理論開始,密碼學界就對這種新型的攻擊方法進行了廣泛的研究。實施功耗分析攻擊時,需要監測電子密碼設備(如智能卡)一條或多條非常規信道,該信道會泄漏密碼設備運行時功耗信息,并使用與密碼設備連接的示波器中獲取該功耗曲線,根據該功耗曲線恢復出加密時使用的密鑰。

在功耗分析理論發展的過程中,先后出現了針對功耗曲線的時間攻擊[1-2](TA)、簡單功耗分析攻擊[3](SPA)、差分功耗分析攻擊[4](DPA)、模板攻擊[5-7](Template Attack)、簡單差分功耗分析攻擊[8](SDPA)以及簡單分支預測攻擊[9-10](SBPA)等。其中模板攻擊又被稱為功耗分析攻擊中最具威脅的攻擊手段,它能在較少的樣本曲線下,恢復出功耗曲線中的指數信息。

現以支持ISO7816協議的8位8051核心芯片和自主研發的攻擊平臺,分析功耗泄露原理,結合泄露功耗信息特征、模板攻擊、SDPA攻擊、分支預測攻擊等思想,提出以時間序列模板的SDPA攻擊方法,恢復芯片加密時的密鑰信息。

2 相關理論

2.1 瞬時功耗

電子密碼設備功耗泄漏原理,可參考文獻[11-12],這里不再累述。監測芯片運算可以獲取芯片加密時的瞬時功耗曲線,以P(t)表示在 t時刻的功耗情況,它包含了動態功耗和靜態功耗的瞬時值,可用下面公式表示：

其中R是獲取功耗信息時在芯片上外接的電阻,而 I(t)和U(t)表示當前t時刻經過R的電流值或電壓值。加密時間段內得到的功耗曲線就可以用瞬時功耗序列表示：

所有泄漏信息都保存在功耗曲線序列中,通過對其分析進而實施攻擊。

2.2 模板攻擊

典型的模板攻擊是在密碼設備運行過程中獲取其功耗曲線,利用該曲線中某種特征構建與指數相關的模板。然后利用同樣的方法提取未知指數功耗曲線特征,并結合相應的配置算法攻擊得到最終結果。

文獻[5]最先提出一種高斯噪聲模板,并利用概率統計方法進行匹配。該方法一個重要的缺點就是數量極其龐大,攻擊周期較長。

2.3 分支預測攻擊

文獻[9-10]描述的分支預測攻擊方法,是針對建立在多級流水線基礎上超級CPU的攻擊。超級CPU為了提高執行效率,在條件分支語句執行前會將可能的執行地址(自動預測)存入一個名為分支目標緩存中(Branch Target Buffer,BTB),執行分支時,如果CPU預測正確,將會直接跳轉到緩存中地址,執行后續執行,其執行時間就會相對較短,否則分支執行時間將相對較長。

雖然8051芯片不是多級流水線的CPU,但利用分支語句與指數的相關性,有助于破解RSA密鑰。

3 數據分析與模板建構

3.1 RSA冪剩余算法信息泄露分析

公鑰密碼算法中進行大數模乘的基本運算為冪剩余算法,其基本表達式為：

其中d為敏感信息,在RSA中可為私鑰的一部分,泄露其值或相關內容的信息實質即為泄露密鑰信息。基于冪剩余的RSA算法實現有很多種,其基本的快速算法有3種[13]：從左向右(LR)、從右向左(RL)和隨機指數(randomized exponentiation)。這里只介紹從左向右二進制表示求冪剩余算法。

算法1 從左向右二進制表示求冪剩余算法

輸入：明文 M,指數 ＜d=(didi-1…d1d0)＞

輸出：C=MdmodN

經過對密碼芯片功耗泄露的原理、RSA冪剩余算法以及示波器采集到波形的綜合考察,可以得到以下結論：

(1)RSA冪剩余算法中進行模乘部分整體瞬時功耗大于執行循環語句和判斷語句瞬時功耗。如圖1所示。

可以看到圖中存在高低瞬時功耗的差異,其中較高瞬時功耗為模乘運算,較低的瞬時功耗為判斷和循環語句,這與前面分析一致。

(2)每次循環的內部,對應指數di不同的取值會執行不同的操作,模乘運算部分瞬時功耗,會被瞬時功耗較低的判斷語句分割開,從而造成漢明重量信息泄露。圖2顯示了指數為A0時漢明重量泄漏情況。

圖1 瞬時功耗說明圖

圖2 漢明重量信息泄漏

(3)算法1中循環語句和循環體內部判斷語句具有相同水平的瞬時功耗,但其執行時間會有略微差異,是模板建立的基礎,圖3統計了指數為0xA0的時間序列。

3.2 時間序列與指數對應關系

for、if等條件分支語句在芯片中執行首先轉化成匯編語言的形式,圖4是匯編語言中典型的for、if分支語句形式：

圖3 指數A0時間序列

圖4 匯編代碼比較

通過對兩種語句匯編語言代碼比較,可以得到for語句和if語句在執行時間上有差異,在某種條件下可以量化該時間。表1顯示了不同語句可能相關的指數信息及其執行時間。

表1 不同數據執行時間差異

圖5 分支語句與數據之間關系

for、if等條件分支語句的瞬時功耗在同一水平,其執行的順序與指數密切相關,圖5顯示了分支語句與指數之間的關系,其中C2對應RSA算法中平方模乘,MC為乘積模乘。

針對圖5指數1001,則其時序即為：

就一般情況而言,一個字節內漢明重量取值為0到8,不同漢明重量在功耗曲線上對于不同的模乘個數,設一個字節內漢明重量為HW,模乘個數為N,該字節可能的取值為NofBytes,則3者之間有如下關系：

某個字節內功耗曲線,可以表達成一個時間序列：

3.3 時序深入分析

由于芯片自身、采集設置及其他原因,每次采集的功耗曲線會存在一定差異,進而統計出來時間序列不盡相同,下面介紹一些主要的影響因素及對策。

3.3.1 條件分支語句時耗統計特性

由于密碼設備本身可能存在抖動等問題,如圖6～圖9分別顯示了 T0、T1、T2和 T3在1000條樣本下的統計情況。

圖6 T0時間差異

圖7 T1時間差異

圖8 T2時間差異

圖9 T3時間差異

由前面統計信息可以看到,單樣本不能完全體現時序特性,鑒于功耗曲線之間差異,利用時序的均值向量組成模板元素

3.3.2 采樣率對時間序列的影響

采樣率的不同可能會對時間序列產生一定的影響,而時間序列內各元素之間關系表達其代表的指數信息,如果采樣率較低則可能無法表達出指數信息,進而造成無法正確匹配。如圖10顯示了相同數據的3種采樣率下的時間序列。

在相同的采樣點數下,采樣率的不同造成了時序模板之間的差異。圖中曲線A為基礎采樣率,曲線B為2倍基礎采樣率,曲線C為3倍基礎采樣率。可以得出這樣的結論：采樣率較低時可能會將淹沒一些重要信息。圖10中4、5、6基礎采樣率下持平,而在較高采樣率下其特征明顯不同。

3.4 模板構建

根據前面分析,在特定采樣率下獲得的功耗曲線可對其構建模板,則模板定義了一個二元組：

模板中N是模乘個數,ˉt是分支語句執行序列的時間特征,通過大量功耗曲線樣本,統計得出。

3.5 模板匹配

文獻[5]中描述模板匹配原則為縮減,即利用模板將可能的指數取值集合縮減到盡可能小,最終利用匹配方式確定指數。文中攻擊方法進行兩次,首先利用模板中 N值進行縮減密鑰取值空間(最多只有70個值,最少只有一個值)得到結果集合,然后利用集合中元素進行匹配得到最終結果。

匹配時利用了歐式距離,公式為[14]：

圖10 不同采樣率時序對比

利用上式計算攻擊模板與猜測模板之間的距離,得到一個集合：

集合中存在一個最小值Dmin,因此其對應的就是最可能的正確密鑰。

4 實測結果

測試平臺的搭建可參考文獻[15],其中使用到的關鍵技術及實現見文獻[16]。按照之前論述的攻擊思想對某1024位指數實施攻擊,圖11給出了某一字節A0各猜測值的匹配結果,由于A0漢明重量為2,則該字節內模乘個數為10,時序長度為10。猜測密鑰時,可能取值集合個數為28。

通過實驗可以看到,利用前面構建的模板和匹配算法,密鑰為A0的數據具有最小的匹配值,從而可以確定它就是被攻擊字節的數據。

實驗表明,依據傳統方法首先對所有可能的密鑰取值構建模板,然后對指數進行攻擊得到平均正確率為85%,由此可知傳統的模板匹配方法仍然有提高的空間。圖12給出了傳統方法中模板匹配錯誤的數據。

圖12中時序曲線A代表數據為0x42,時序曲線B代表的數據為0x44,而被攻數據時序曲線代表真實數據為0x42,但它體現出的特征與0x44非常相近,可見先建模板的不足,其中原因將另撰文詳述。

鑒于圖12表現出的模板特性,拋棄了傳統的先驗模板構建方法,引入了SDPA思想實時構建模板。即在攻擊時首先獲取被攻擊指數的模板信息,依據模乘個數獲取所有可能的取值,并獲取這些可能取值的模板,最后進行匹配。引入SDPA思想就是為了消除數據帶來的先驗模板差異,實驗表明該方法提高了攻擊的正確性,正確率可達100%。圖13顯示了傳統模板構建方法與SDPA構建方式之間正確率的對比。

圖11 匹配結果

圖12 傳統方法模板與真實數據之間差異

圖13 兩種模板構建方法攻擊結果對比

實驗室已經對類似使用分支泄漏信息進行攻擊的方法,提出了防御策略具體參考文獻[17]。

5 結束語

文中結合模板攻擊原理和SDPA思想,利用密碼芯片加密時循環語和判斷語句功耗泄漏時間特征和單字節內模乘個數特征構成模板,利用歐式距離匹配實施攻擊。通過在真實智能卡RSA二進制模冪算法環境下進行實驗分析,證實了該攻擊方法的正確性和有效性。同時,該方法也具有缺點,就時攻擊時的指數越長,需要的功耗曲線越多。

致謝：感謝成都市“十一五”重點科技專項(09GGZD988GX-033);成都市科技攻關項目(10GGYB368GX-023)對本文的資助。

[1]KOCHER P.Timing attacks On implementations of diffe-hellman,RSA,DES,and other system[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 smarteards[A].Proc USENIX Workshop Smarteard 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]Suresh Chari,Josyula R.Rao,and Pankaj Rohatgi.Template Attacks[A].CHES 2002,LNCS 2523,2003：13-28.

[6]C.Archambeau,E.Peters et al.Template Attacks in Principal Subspaces[A].CHES 2006,LNCS 4249,2006：1-14.

[7]Francois-Xavier Standaert et al.and Cedric Archambeau.Using Subspace-Based Template Attacks to Compare and Combine Power and Electromagnetic Information Leakages[A].CHES 2008,LNCS 5154,2008：411-425.

[8]周俐莎,陳運.真實環境下對冪剩余指數的SDPA攻擊[J].計算機工程,2010,36(7)：156-158.

[9]O Acicmez,J P Seifert,C K Koc.Predicting secret keys via branch prediction[J].Topics in Cryptology-CTRSA 2007.

[10]O Aclicmez,C K Koc,J P Seifert.On the power of simple branch prediction analysis[J].Cryptology ePrint Archive,2006：351.

[11]鄧高明,吳恒旭,張鵬.旁路模板在密碼芯片指令分析中的應用[J].微電子學與計算機,2011,28(2)：1837-1839.

[12]Stefan.Mangard,Elisabeth Oswald,Thomas Popp.Power Analysis Attacks-Revealing the Secrets of Smart Cards[M].Springer Science Business Media,LLC,2007：30-32.

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

[14]孫即祥.現代模式識別[M].北京：高等教育出版社,2088：19-20.

[15]吳震,陳運,陳俊,等.真實硬件環境下冪剩余功耗軌跡指數信息提取[J].通信學報,2010,(2).

[16]孫敦燦,陳運,萬武南,等.功耗分析平臺中混合編程的應用研究[J].成都信息工程學院學報,2011,126(2)：127-131.

[17]饒金濤,陳運,吳震,等.一種抗簡單功耗分析攻擊的模冪算法[J].成都信息工程學院學報,2011,126(2)：123-126.