智能卡加密算法的微分能量分析方法研究
文章出處：http://m.coolbang.cn 作者：胡勇, 沈庭芝, 郭濤, 李守鵬 人氣： 發(fā)表時(shí)間：2011年09月30日
1 引言
智能卡作為一種安全可靠的高技術(shù)產(chǎn)品, 在我國正逐步取代磁卡而廣泛應(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ì)方法來提取與密鑰有關(guān)的信息。盡管實(shí)現(xiàn)的過程更加復(fù)雜, 但降低了對(duì)攻擊者的智能卡專業(yè)技術(shù)水平的要求。
2 微分能量分析
在密碼的運(yùn)算過程中, 智能卡執(zhí)行一條指令所消耗的能量與指令的操作數(shù)相關(guān)。如果用PI 表示指令I(lǐng) 執(zhí)行過程中平均消耗的能量, 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 來對(duì)DPA攻擊進(jìn)行分析。
3. 1 DES 的DPA 攻擊
DES 是對(duì)稱密碼體制中最典型的一個(gè)例子, 它是由IBM 公司公布的一種加密算法, 1977 年被美國國家標(biāo)準(zhǔn)局確立為 聯(lián)邦數(shù)據(jù)加密標(biāo)準(zhǔn)后完全公開, 是世界上技術(shù)最成熟的加密算 法。DES 在加密時(shí), 將明文分成長度為64 位的由0、1 組成的 串, 使用的密鑰長度為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è)迭代周期的密鑰。迭代過程如圖2 所示。
在對(duì)DES 進(jìn)行DPA 分析時(shí), 我們選定的中間操作數(shù)是第16 輪迭代過程輸入L15 值中的一位, 設(shè)為d。d 與已知信息、待求密鑰之間的關(guān)系如下式所示:
其中, b 為R 16 中由d 經(jīng)過加密得到的二進(jìn)制位。C* 為R15 中輸入S* 的比特位。在每個(gè)迭代過程中, 密鑰被分成了八個(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)制密鑰塊, 它的取值無非有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[ 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無關(guān)的時(shí)刻, T[ j] 趨于零; 如果密鑰錯(cuò)誤, 由函數(shù)D 得出的d值可能與真值不符, 導(dǎo)致部分Sij 不能正確歸入S0 和S1 , 削弱了d 時(shí)刻應(yīng)有的能量差異性, T[ j] 在這個(gè)時(shí)刻即使有峰值, 也無法與密鑰正確時(shí)相比。不過相同的是在d 以外的點(diǎn), T[ j] 仍然趨于零。因此, 找出64 個(gè)當(dāng)中含有最大峰值的T[ j] 軌跡,其對(duì)應(yīng)的密鑰塊即為K*16 。重復(fù)上述過程對(duì)其余七個(gè)S 盒進(jìn)行分析, 就可以得出第16 輪使用的48 位密鑰。要破解整個(gè)DES 密鑰, 只需對(duì)前面各輪進(jìn)行同樣分析即可。
3. 2 ECC 的DPA 攻擊
公開密鑰算法通?；谝粋€(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 稱為公開密鑰。ECC 主要涉及的是類似kG 的點(diǎn)乘運(yùn)算, 該運(yùn)算在智能卡芯片中用指令實(shí)現(xiàn)時(shí), k 往往寫成二進(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)算過程中的能量消耗將與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)樘? 無法滿足安全要求, 正逐步走向末路。AES是美國國家標(biāo)準(zhǔn)技術(shù)研究所( NIST) 發(fā)起征集的旨在取代DES 的高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)。它的基本要求是: 必須是私鑰分組加密算法, 密鑰長度至少為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)鍵在于獲取白化過程中采用的密鑰。統(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ù), 異或和異或后寫入結(jié)果時(shí)刻相關(guān), 故協(xié)方差函數(shù)波形中有不多的幾個(gè)峰值。主要觀察的是異或前讀取數(shù)據(jù)和異或后寫入結(jié)果時(shí)刻對(duì)應(yīng)的峰值, 兩個(gè)峰值方向相同表示密鑰是0,反之則表示密鑰是1。在獲取白化過程使用的密鑰后, 接下來是希望通過Twofish 密鑰生成算法推導(dǎo)出核心過程密鑰, 但這無法直接實(shí)現(xiàn), 只能是結(jié)合密鑰生成算法和白化過程密鑰將核心過程密鑰取值范圍縮小后逐一驗(yàn)證。
( 2) Rijndael 采用的是代替/ 置換網(wǎng)絡(luò), 當(dāng)加密分組和密鑰長度都為128 位時(shí), 加密輪數(shù)是10。加密開始時(shí), 輸入分組的各字節(jié)按特定的方式裝入一個(gè)矩陣State 中, 接下來是一個(gè)與密鑰的異或操作, 不僅僅是在輪加密開始之前, 在每輪加密之中和輪加密之后都有類似的操作, 只是采用的密鑰不同, 但它們都是由Rijndael 密鑰生成算法統(tǒng)一生成。第一次的異或操作密鑰完全可以通過DPA 攻擊獲取, 然后根據(jù)Rijndael 密鑰生成算法直接推出其余各輪的密鑰, 這與Twofish 相比要簡(jiǎn)單得多。
( 3) Serpent 是一個(gè)在初始置換和末尾置換之間安排有32輪加密操作的算法, 沒有采用白化技術(shù), 每一輪包含密鑰混合運(yùn)算、S- 盒及線性變換。針對(duì)Serpent 完全可以采用前面介紹的針對(duì)DES 類似的DPA 分析?？紤]到利用Serpent 的密鑰生成算法推出其余各輪密鑰, 必須預(yù)知兩輪以上的子密鑰, 這就意味著攻擊者至少要破解32 輪中前面至少兩輪以上的加密過程。
由此可見, Twofish, Rijndael, Serpent 只要利用簡(jiǎn)單的幾輪DPA 分析得來的子密鑰, 結(jié)合統(tǒng)一的相對(duì)獨(dú)立的密鑰生成算法, 就可以用來破解主密鑰和其他的子密鑰。但同樣的方法對(duì)MARS 和RC6 并不適用, 這主要在于它們的密鑰生成算法設(shè)計(jì)獨(dú)特, 使得密鑰間的遞推難以實(shí)現(xiàn), 這就迫使攻擊者必須對(duì)這兩種算法的核心加密過程展開分析。加密算法總是由基本操作組成的, 這些操作抵御能量攻擊的能力差異較大, 與Twofish, Rijndael, Serpent 相比, MARS 和RC6 包含了較多比較脆弱的操作, 如異或、查表、輪移、算術(shù)運(yùn)算( 加、減、乘) 等, 有些更適合用SPA 進(jìn)行分析。MARS 和RC6 算法設(shè)計(jì)者采用白化技術(shù)的初衷就是為了增強(qiáng)對(duì)核心過程的保護(hù)。攻擊者一旦采用DPA 技術(shù)解除了這種保護(hù)功能, 便能結(jié)合SPA, DPA 直接對(duì)核心部分展開分析, 破解其中的密鑰。
(文/1. 北京理工大學(xué)電子工程系, 北京100081; 2. 華中科技大學(xué)計(jì)算機(jī)科學(xué)系, 湖北武漢430074; 3. 中國信息安全測(cè)評(píng)認(rèn)證中心, 胡勇1 , 沈庭芝1 , 郭濤2 , 李守鵬3)
