智能卡加密算法的微分能量分析方法研究
文章出處：http://m.botanicstilllife.com 作者：胡勇, 沈庭芝, 郭濤, 李守鵬 人氣： 發(fā)表時(shí)間：2011年09月30日
1 引言
智能卡作為一種安全可靠的高技術(shù)產(chǎn)品, 在我國(guó)正逐步取代磁卡而廣泛應(yīng)用于金融行業(yè)以及其他相關(guān)產(chǎn)業(yè)。但部分用戶在對(duì)智能卡產(chǎn)品的認(rèn)識(shí)上存在著一些誤區(qū), 片面地認(rèn)為所有擁有微處理器的智能卡都具有高安全性和高可靠性, 從而忽略了這方面的要求。事實(shí)上針對(duì)智能卡的攻擊方法伴隨著智能卡的發(fā)展而發(fā)展, 一直威脅著智能卡的安全。
目前比較流行的是稱作能量分析的攻擊方法, 它分為兩類: 簡(jiǎn)單能量分析( SPA)和微分能量分析( DPA)。SPA是一種直接解釋能量消耗測(cè)定值的技術(shù)。系統(tǒng)消耗能量的大小隨微處理器執(zhí)行的指令不同而不同, 當(dāng)微處理器在對(duì)加密算法的不同部分執(zhí)行運(yùn)算時(shí), 能量消耗變化有的會(huì)很明顯。借助這種特征, 攻擊者能區(qū)分出單條指令, 達(dá)到破解算法的目的。DPA 的攻擊力比SPA 強(qiáng)得多, 而且更加難以防范, 它不像SPA從系統(tǒng)的能量消耗直觀地作出判斷, 而是借助統(tǒng)計(jì)方法來(lái)提取與密鑰有關(guān)的信息。盡管實(shí)現(xiàn)的過(guò)程更加復(fù)雜, 但降低了對(duì)攻擊者的智能卡專業(yè)技術(shù)水平的要求。
2 微分能量分析
在密碼的運(yùn)算過(guò)程中, 智能卡執(zhí)行一條指令所消耗的能量與指令的操作數(shù)相關(guān)。如果用PI 表示指令I(lǐng) 執(zhí)行過(guò)程中平均消耗的能量, op1 , op2 , ..., opn 表示I 的操作數(shù), 當(dāng)op1 取不同值時(shí), 有
稱PI 與op1 相關(guān), 即PI ( 0) ≠ PI ( 1) 。微分能量分析正是從這種相關(guān)性著手, 最終實(shí)現(xiàn)對(duì)加密密鑰的破解。設(shè)PI ( 0 ) , PI ( 1)的差值為DI , DI 越大, 對(duì)作DPA 分析越有利。一階微分能量分析往往采用以下步驟:
( 1) 確立類似于op1 的操作數(shù)或中間變量, 取值為α。要求根據(jù)已知智能卡信息( 明文、密文) D 和未知的密鑰信息能夠推導(dǎo)出它的值, 即α= f( K, D) 。
( 2) 對(duì)多組不同明文分別進(jìn)行加密, 對(duì)相應(yīng)的能量信號(hào)進(jìn)行采樣并記錄波形。
( 3) 對(duì)K 的值進(jìn)行猜測(cè), 計(jì)算出相應(yīng)的α, 將( 2) 中的采樣結(jié)果按照α= 0 和α= 1 分成兩組, 求兩組的均值差( 即構(gòu)建統(tǒng)計(jì)函數(shù)) 。α時(shí)刻均值差最大時(shí), K猜測(cè)正確。從以上步驟我們可以看出, 攻擊者要發(fā)動(dòng)DPA 攻擊, 需要具備以下條件: 熟悉智能卡中采用的加密算法原理結(jié)構(gòu); 知道智能卡處理的明文或者是處理后的密文; 有相應(yīng)的硬件條件,用于測(cè)量能量消耗軌跡。圖1 就是實(shí)施DPA 攻擊的基本電路。
3 智能卡常用加密算法的DPA 攻擊
根據(jù)加密機(jī)制的不同, 加密算法可以分為兩類: 對(duì)稱加密算法和非對(duì)稱加密算法。智能卡中常用的加密算法, 如DES,3DES, RSA 和ECC 等都可以歸結(jié)到這兩類算法中。DPA 最先是在針對(duì)智能卡的對(duì)稱加密算法的破解方法研究中發(fā)現(xiàn)的, 但隨后就發(fā)現(xiàn)它對(duì)破解非對(duì)稱加密算法同樣有效。下面我們分別就這兩類算法中最具代表性的算法: DES 和ECC 來(lái)對(duì)DPA攻擊進(jìn)行分析。
3. 1 DES 的DPA 攻擊
DES 是對(duì)稱密碼體制中最典型的一個(gè)例子, 它是由IBM 公司公布的一種加密算法, 1977 年被美國(guó)國(guó)家標(biāo)準(zhǔn)局確立為 聯(lián)邦數(shù)據(jù)加密標(biāo)準(zhǔn)后完全公開(kāi), 是世界上技術(shù)最成熟的加密算 法。DES 在加密時(shí), 將明文分成長(zhǎng)度為64 位的由0、1 組成的 串, 使用的密鑰長(zhǎng)度為64 位。DES 采用了Feistel 網(wǎng)絡(luò)結(jié)構(gòu), 有 16 個(gè)迭代周期, 每個(gè)周期按照公式( 1) 迭代:
其中, f( R i - 1 , K i ) = P( S( E( R i - 1 ) ī K I ) ) , K i 表示第i 個(gè)迭代周期的密鑰。迭代過(guò)程如圖2 所示。
在對(duì)DES 進(jìn)行DPA 分析時(shí), 我們選定的中間操作數(shù)是第16 輪迭代過(guò)程輸入L15 值中的一位, 設(shè)為d。d 與已知信息、待求密鑰之間的關(guān)系如下式所示:
其中, b 為R 16 中由d 經(jīng)過(guò)加密得到的二進(jìn)制位。C* 為R15 中輸入S* 的比特位。在每個(gè)迭代過(guò)程中, 密鑰被分成了八個(gè)二進(jìn)制密鑰塊, 分別對(duì)應(yīng)一個(gè)S 盒, S* 是d 對(duì)應(yīng)的S 盒。K*16 是輸入S* 的六位二進(jìn)制密鑰塊, K 16 中的一部分。K*16 是破解的對(duì)象, 作為六位的二進(jìn)制密鑰塊, 它的取值無(wú)非有64 種, 這其中當(dāng)然包括正確的密鑰。下面的工作就是要結(jié)合實(shí)際觀測(cè)找出該密鑰。
假設(shè)DES 算法加密不同的明文時(shí)觀測(cè)到的能量信號(hào)為Sij( i 表示明文編號(hào), j 表示時(shí)間) 。明文數(shù)量為N 時(shí), 針對(duì)K*16 的每一種猜測(cè)就會(huì)有N 個(gè)觀測(cè)結(jié)果, 由式( 2) 計(jì)算出d 值, 根據(jù)d值對(duì)觀測(cè)結(jié)果分類, 如下所示:
假定S0 和S1 的均值差為T(mén)[ j] , 考慮到S0 和S1 是隨機(jī)能量信號(hào)集合分出的兩個(gè)子集, 唯一的區(qū)別是加密進(jìn)行到d 時(shí)d的取值不同, 因而S0 和S1 的均值是有差異的。對(duì)于T[ j] , 如果猜測(cè)密鑰正確, 則在d 處理時(shí)刻T[ j] 會(huì)出現(xiàn)一個(gè)峰值, 與d無(wú)關(guān)的時(shí)刻, T[ j] 趨于零; 如果密鑰錯(cuò)誤, 由函數(shù)D 得出的d值可能與真值不符, 導(dǎo)致部分Sij 不能正確歸入S0 和S1 , 削弱了d 時(shí)刻應(yīng)有的能量差異性, T[ j] 在這個(gè)時(shí)刻即使有峰值, 也無(wú)法與密鑰正確時(shí)相比。不過(guò)相同的是在d 以外的點(diǎn), T[ j] 仍然趨于零。因此, 找出64 個(gè)當(dāng)中含有最大峰值的T[ j] 軌跡,其對(duì)應(yīng)的密鑰塊即為K*16 。重復(fù)上述過(guò)程對(duì)其余七個(gè)S 盒進(jìn)行分析, 就可以得出第16 輪使用的48 位密鑰。要破解整個(gè)DES 密鑰, 只需對(duì)前面各輪進(jìn)行同樣分析即可。
3. 2 ECC 的DPA 攻擊
公開(kāi)密鑰算法通?；谝粋€(gè)數(shù)學(xué)上的難題, 橢圓曲線加密算法也不例外?？紤]等式K = kG( K, G 是橢圓曲線上的點(diǎn), k為小于G 的階的整數(shù)) , 不難發(fā)現(xiàn), 給定k 和G, 根據(jù)橢圓曲線加法法則, 計(jì)算K 很容易; 但給定K 和G, 求k 就相對(duì)困難了。
我們把點(diǎn)G 稱為基點(diǎn), k 稱為私有密鑰, K 稱為公開(kāi)密鑰。ECC 主要涉及的是類似kG 的點(diǎn)乘運(yùn)算, 該運(yùn)算在智能卡芯片中用指令實(shí)現(xiàn)時(shí), k 往往寫(xiě)成二進(jìn)制擴(kuò)展形式, 即k = k n - 1 k n - 2...k0 , 而kG 則用連加的形式代替, 如下列代碼所示:
其中, “+ ”是橢圓曲線上的加法, 運(yùn)算法則與普通加法不同。從代碼可以看出當(dāng)循環(huán)運(yùn)算進(jìn)行到i 時(shí), X[ 0] 的值僅與k的二進(jìn)制擴(kuò)展表示中的( k n - 1 , ..., k i ) 有關(guān)。如果X[ 0] 的中間結(jié)果用pM表示( p 是整型系數(shù), 隨For 循環(huán)遞增, 可能的取值取決于k i ) , 那么運(yùn)算過(guò)程中的能量消耗將與pM 二進(jìn)制表示中的位相關(guān)。例如, 為了獲取k 的二進(jìn)制位k n - 2 , 我們可以考查4M中的位與能量信號(hào)的相關(guān)性。對(duì)N 個(gè)不同的M分別執(zhí)行上述指令操作, 觀測(cè)它們的能量信號(hào)軌跡, 記作S i。選定4M二進(jìn)制表示中的一個(gè)比特位( 如第二位b2 ) 作為對(duì)S i 進(jìn)行分組的依據(jù):
S0 = < Si | b2 = 0 >
S1 = < Si |b2 = 1 >
設(shè)S0 和S1 的均值差為C( t) , 從它的軌跡就可以判斷出k n - 2的值。原因在于: d n- 2 = 0 時(shí), 4M是中間結(jié)果, Si 與b2 相關(guān), 在b2 對(duì)應(yīng)時(shí)刻C( t) 出現(xiàn)峰值; d n - 2 = 1 時(shí), 4M不是中間結(jié)果, S0 和S1 的均值不再有明顯差異, C( t) 不會(huì)出現(xiàn)峰值。依此類推, 我們可以獲取k 二進(jìn)制表示中剩余各位的值。
4 AES 候選算法與DPA 攻擊
DES 使用的密鑰因?yàn)樘? 無(wú)法滿足安全要求, 正逐步走向末路。AES是美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所( NIST) 發(fā)起征集的旨在取代DES 的高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)。它的基本要求是: 必須是私鑰分組加密算法, 密鑰長(zhǎng)度至少為128 位。本文提到的AES 候選算法特指入圍第二輪評(píng)選的五種算法( Twofish ,Rijndael , Serpent , MARS, RC6 ) , 它們都有自己獨(dú)特的設(shè)計(jì)思路和風(fēng)格, 對(duì)許多目前流行的攻擊方法有相當(dāng)?shù)牡挚鼓芰? 但這并不包括DPA 攻擊。
( 1) Twofish 加密算法使用16 輪的Feistel 網(wǎng)絡(luò)結(jié)構(gòu), 在網(wǎng)絡(luò)的輸入和輸出運(yùn)用了白化處理技術(shù)。這種技術(shù)原理比較簡(jiǎn)單, 就是將待隱藏?cái)?shù)據(jù)和特定密鑰進(jìn)行“加”或“異或”運(yùn)算, 但產(chǎn)生的加密效果很強(qiáng), 攻擊者因此而得不到核心部分的輸入輸出。在利用DPA 對(duì)Twofish 進(jìn)行分析時(shí), 關(guān)鍵在于獲取白化過(guò)程中采用的密鑰。統(tǒng)計(jì)分析建立在如下基礎(chǔ)上: 當(dāng)白化密鑰位是0 時(shí), 對(duì)應(yīng)輸入的明文二進(jìn)制位保持不變; 當(dāng)白化密鑰位是1 時(shí), 對(duì)應(yīng)輸入的明文二進(jìn)制位取反。我們可以對(duì)多組明文進(jìn)行加密, 采集能量信號(hào), 求出128 位白化密鑰對(duì)應(yīng)的明文二進(jìn)制位與能量信號(hào)的協(xié)方差函數(shù), 由于兩者主要是在異或前讀取數(shù)據(jù), 異或和異或后寫(xiě)入結(jié)果時(shí)刻相關(guān), 故協(xié)方差函數(shù)波形中有不多的幾個(gè)峰值。主要觀察的是異或前讀取數(shù)據(jù)和異或后寫(xiě)入結(jié)果時(shí)刻對(duì)應(yīng)的峰值, 兩個(gè)峰值方向相同表示密鑰是0,反之則表示密鑰是1。在獲取白化過(guò)程使用的密鑰后, 接下來(lái)是希望通過(guò)Twofish 密鑰生成算法推導(dǎo)出核心過(guò)程密鑰, 但這無(wú)法直接實(shí)現(xiàn), 只能是結(jié)合密鑰生成算法和白化過(guò)程密鑰將核心過(guò)程密鑰取值范圍縮小后逐一驗(yàn)證。
( 2) Rijndael 采用的是代替/ 置換網(wǎng)絡(luò), 當(dāng)加密分組和密鑰長(zhǎng)度都為128 位時(shí), 加密輪數(shù)是10。加密開(kāi)始時(shí), 輸入分組的各字節(jié)按特定的方式裝入一個(gè)矩陣State 中, 接下來(lái)是一個(gè)與密鑰的異或操作, 不僅僅是在輪加密開(kāi)始之前, 在每輪加密之中和輪加密之后都有類似的操作, 只是采用的密鑰不同, 但它們都是由Rijndael 密鑰生成算法統(tǒng)一生成。第一次的異或操作密鑰完全可以通過(guò)DPA 攻擊獲取, 然后根據(jù)Rijndael 密鑰生成算法直接推出其余各輪的密鑰, 這與Twofish 相比要簡(jiǎn)單得多。
( 3) Serpent 是一個(gè)在初始置換和末尾置換之間安排有32輪加密操作的算法, 沒(méi)有采用白化技術(shù), 每一輪包含密鑰混合運(yùn)算、S- 盒及線性變換。針對(duì)Serpent 完全可以采用前面介紹的針對(duì)DES 類似的DPA 分析?？紤]到利用Serpent 的密鑰生成算法推出其余各輪密鑰, 必須預(yù)知兩輪以上的子密鑰, 這就意味著攻擊者至少要破解32 輪中前面至少兩輪以上的加密過(guò)程。
由此可見(jiàn), Twofish, Rijndael, Serpent 只要利用簡(jiǎn)單的幾輪DPA 分析得來(lái)的子密鑰, 結(jié)合統(tǒng)一的相對(duì)獨(dú)立的密鑰生成算法, 就可以用來(lái)破解主密鑰和其他的子密鑰。但同樣的方法對(duì)MARS 和RC6 并不適用, 這主要在于它們的密鑰生成算法設(shè)計(jì)獨(dú)特, 使得密鑰間的遞推難以實(shí)現(xiàn), 這就迫使攻擊者必須對(duì)這兩種算法的核心加密過(guò)程展開(kāi)分析。加密算法總是由基本操作組成的, 這些操作抵御能量攻擊的能力差異較大, 與Twofish, Rijndael, Serpent 相比, MARS 和RC6 包含了較多比較脆弱的操作, 如異或、查表、輪移、算術(shù)運(yùn)算( 加、減、乘) 等, 有些更適合用SPA 進(jìn)行分析。MARS 和RC6 算法設(shè)計(jì)者采用白化技術(shù)的初衷就是為了增強(qiáng)對(duì)核心過(guò)程的保護(hù)。攻擊者一旦采用DPA 技術(shù)解除了這種保護(hù)功能, 便能結(jié)合SPA, DPA 直接對(duì)核心部分展開(kāi)分析, 破解其中的密鑰。
(文/1. 北京理工大學(xué)電子工程系, 北京100081; 2. 華中科技大學(xué)計(jì)算機(jī)科學(xué)系, 湖北武漢430074; 3. 中國(guó)信息安全測(cè)評(píng)認(rèn)證中心, 胡勇1 , 沈庭芝1 , 郭濤2 , 李守鵬3)
