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

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

1 引言

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

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

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

2 相關(guān)理論

2.1 瞬時功耗

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

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

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

2.2 模板攻擊

典型的模板攻擊是在密碼設(shè)備運行過程中獲取其功耗曲線,利用該曲線中某種特征構(gòu)建與指數(shù)相關(guān)的模板。然后利用同樣的方法提取未知指數(shù)功耗曲線特征,并結(jié)合相應(yīng)的配置算法攻擊得到最終結(jié)果。

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

2.3 分支預(yù)測攻擊

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

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

3 數(shù)據(jù)分析與模板建構(gòu)

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

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

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

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

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

輸出：C=MdmodN

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

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

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

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

圖1 瞬時功耗說明圖

圖2 漢明重量信息泄漏

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

3.2 時間序列與指數(shù)對應(yīng)關(guān)系

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

圖3 指數(shù)A0時間序列

圖4 匯編代碼比較

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

表1 不同數(shù)據(jù)執(zhí)行時間差異

圖5 分支語句與數(shù)據(jù)之間關(guān)系

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

針對圖5指數(shù)1001,則其時序即為：

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

某個字節(jié)內(nèi)功耗曲線,可以表達成一個時間序列：

3.3 時序深入分析

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

3.3.1 條件分支語句時耗統(tǒng)計特性

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

圖6 T0時間差異

圖7 T1時間差異

圖8 T2時間差異

圖9 T3時間差異

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

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

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

在相同的采樣點數(shù)下,采樣率的不同造成了時序模板之間的差異。圖中曲線A為基礎(chǔ)采樣率,曲線B為2倍基礎(chǔ)采樣率,曲線C為3倍基礎(chǔ)采樣率?？梢缘贸鲞@樣的結(jié)論：采樣率較低時可能會將淹沒一些重要信息。圖10中4、5、6基礎(chǔ)采樣率下持平,而在較高采樣率下其特征明顯不同。

3.4 模板構(gòu)建

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

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

3.5 模板匹配

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

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

圖10 不同采樣率時序?qū)Ρ?/p>

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

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

4 實測結(jié)果

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

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

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

圖12中時序曲線A代表數(shù)據(jù)為0x42,時序曲線B代表的數(shù)據(jù)為0x44,而被攻數(shù)據(jù)時序曲線代表真實數(shù)據(jù)為0x42,但它體現(xiàn)出的特征與0x44非常相近,可見先建模板的不足,其中原因?qū)⒘碜脑斒觥?/p>

鑒于圖12表現(xiàn)出的模板特性,拋棄了傳統(tǒng)的先驗?zāi)０鍢?gòu)建方法,引入了SDPA思想實時構(gòu)建模板。即在攻擊時首先獲取被攻擊指數(shù)的模板信息,依據(jù)模乘個數(shù)獲取所有可能的取值,并獲取這些可能取值的模板,最后進行匹配。引入SDPA思想就是為了消除數(shù)據(jù)帶來的先驗?zāi)０宀町?實驗表明該方法提高了攻擊的正確性,正確率可達100%。圖13顯示了傳統(tǒng)模板構(gòu)建方法與SDPA構(gòu)建方式之間正確率的對比。

圖11 匹配結(jié)果

圖12 傳統(tǒng)方法模板與真實數(shù)據(jù)之間差異

圖13 兩種模板構(gòu)建方法攻擊結(jié)果對比

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

5 結(jié)束語

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

致謝：感謝成都市“十一五”重點科技專項(09GGZD988GX-033);成都市科技攻關(guān)項目(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]周俐莎,陳運.真實環(huán)境下對冪剩余指數(shù)的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]鄧高明,吳恒旭,張鵬.旁路模板在密碼芯片指令分析中的應(yīng)用[J].微電子學(xué)與計算機,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]陳運,吳震,陳俊,等.防范邊信道攻擊的等功耗編碼實現(xiàn)算法[J].電子科技大學(xué)學(xué)報,2008,37(2)：168-171.

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

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

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

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