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