一種基于選擇明文 -時間差異的邊信道攻擊方法*

孫春輝 李暉 楊旸 呂超

(西安電子科技大學計算機網絡與信息安全教育部重點實驗室,陜西西安 710071)

邊信道攻擊是利用密碼設備在工作時的泄漏信息來恢復密鑰的方法[1],常見的邊信道攻擊主要有時間攻擊[1-3]、功耗分析攻擊[1,4-5]、電磁攻擊[6-7]和故障攻擊[1,8-9]等.

目前,廣泛使用Square攻擊[10]來衡量分組密碼的安全性,而時間攻擊多用于針對公鑰密碼體制. Kocher在文獻[2]中介紹了針對Diffie-Hellman、RSA、數(shù)字簽名標準(DSS)的時間攻擊,并指出時間攻擊可以用來攻擊其它密碼系統(tǒng)(包括分組密碼),特別是可以通過檢測DES的輪密鑰生成過程中,因移動密鑰中非零位而引起執(zhí)行時間的不同,來揭示密鑰的漢明重量,其所能提供的密鑰信息為 3.95b.文獻[3]中根據Kocher的觀點,在一臺主頻為120MHz、運行單任務操作系統(tǒng)MSDOS的計算機上,檢測RSA-DES和L-DES在固定輸入全零明文和設置不同漢明重量的密鑰進行加密時,輪密鑰生成過程和整個加密過程所需的時間,得到不同漢明重量的密鑰與時間之間的關系.文獻[3]中認為時間攻擊能找出DES全部的密鑰而不僅僅是其漢明重量,并用精心選擇的消息輸入DES,通過分析加密時間(不計子密鑰生成時間)的差異得到DES密鑰.

為了研究密碼算法的安全性能,文中提出一種基于選擇明文-時間差異的邊信道攻擊(簡稱選擇明文-時間攻擊)方法,并以分組密碼DES算法為例來說明選擇明文 -時間攻擊的具體實現(xiàn).通過在單片機上的實際攻擊驗證,只需 49個明文即可直接恢復出智能卡DES算法的第一輪48位子密鑰而不僅僅是其漢明重量.最后,分析了密碼算法在實現(xiàn)過程中,出現(xiàn)執(zhí)行時間差異的原因,給出了相應的抵抗措施,并對其性能進行了分析和比較.

1 DES算法簡介

1.1 DES加密標準

DES作為美國國家標準學會(ANSI)的數(shù)據加密算法(DEA)和國際標準化組織(ISO)的DEA-1,成為一個世界范圍內的標準已經 30多年了[11]. DES算法在衛(wèi)星通信、網關服務器、智能卡等領域中有著廣泛的應用.

DES密鑰的長度為 56位(密鑰通常表示為 64位的數(shù),但每個字節(jié)的第 8位都用作奇偶校驗,可以忽略)[11],所有的保密性依賴于密鑰.密鑰通過密鑰置換并移位,然后從 56位中通過壓縮置換選出 48位.E盒將通過初始置換(IP)后的數(shù)據的右半部分Ri-1擴展成 48位,再與 48位子密鑰進行異或運算,然后通過8個 S盒將這 48位替代成新的 32位數(shù)據,并用P盒置換一次.這4步運算構成了函數(shù)f.然后,使用另一個異或運算將函數(shù)f的輸出與數(shù)據的左半部分 Li-1相結合,其結果作為下一輪運算的右半部分Ri,原來數(shù)據的右半部分交換成為下一輪運算的左半部分Li,如圖1所示.該操作重復16次,即可實現(xiàn)DES的16輪運算[11].

圖1 一輪DES運算示意圖Fig.1 Schematic diagram of one round DESoperation

非線性的S盒是 DES算法安全的核心所在[11].E盒擴展出的數(shù)據與子密鑰異或后,輸出的48位按順序分成 8組,分別通過 S1,S2,…,S8盒后壓縮為 32位,即每個 S盒輸入為 6位,輸出為 4位,如圖2所示.

圖2 Si盒的輸入與輸出Fig.2 Input and output of Si box

設Si盒的輸入端為a1a2a3a4a5a6,輸出端為b1b2b3b4,需要在 Si盒中查找并輸出 a1a6行、a2a3a4a5列的值,即Si(a1a6,a2a3a4a5).在程序實現(xiàn)的DES算法中,若調整S盒輸入端每一位的順序,則對標準S表進行查表操作,這部分代碼執(zhí)行所消耗的時間,與 S盒輸入端每一位的漢明重量密切相關.通過精心選擇明文輸入,測量執(zhí)行時間,可以分析推算出子密鑰.

1.2 智能卡中的DES算法

DES算法廣泛應用于智能卡中,文中用文獻

[12]中的智能IC卡DES算法,該算法采用匯編語言編寫,代碼簡潔緊湊,執(zhí)行效率高,占用存儲空間小于 4 kB,運行所需內存小于 256 B,可以在與80C52兼容的微控制器單元(MCU)上運行,適用于8位CPU的智能卡.其密鑰為 64位,以 8位為一組存儲,共占用 8 B,密鑰由低位到高位的位順序為k8…k1,k16…k9,…,k64…k57,其中 k8、k16、k24、k32、k40、k48、k56、k64為奇偶校驗位.明文及密文的位順序也和密鑰的一致.E盒擴展輸出的數(shù)據與48位子密鑰異或的結果存儲在 8個字節(jié)中(每字節(jié)中高 6位有效),對應8個S盒的輸入.以第一輪運算為例,R0經過E盒擴展后與第一輪子密鑰K1異或,得到 48位值,按每字節(jié) 6位存儲,對應 8個 S盒.其中對應任一S盒的字節(jié)內部存儲形式為

要對標準的S表進行查表,程序將對應 S盒的輸入位順序調整為

對應S盒中S1查表算法如下所示:

其中S_BOXES_DATA是標準S表的首地址,S1查表算法將對應 S1表的輸入位順序調整為可以直接查標準S表的形式存入累加器A,并通過MOVC A, @A+DPTR查表指令進行查表.程序執(zhí)行時,會因為數(shù)據比特位的不同而選擇不同的分支,從而存在執(zhí)行時間差,可以用來進行時間攻擊.當采用高級語言編寫時,使用不同的優(yōu)化等級得到的機器代碼是不同的.

2 選擇明文-時間攻擊方法

2.1 選擇明文-時間攻擊的定義及假設

定義1 選擇明文 -時間攻擊是一種只需精心選擇與密鑰長度相當數(shù)量的明文,將其輸入加密系統(tǒng),并測量加密算法中相關敏感部分代碼的執(zhí)行時間,通過比較分析這些時間差,從而分析出密鑰的方法.

2.2 攻擊方法

在選擇明文 -時間攻擊方法中,選擇合適的明文很重要.選擇正確合理的明文后,在攻擊中就能快捷、高效地反映出不同漢明重量密鑰在密碼運算過程中的時間特征,進而準確地分析推斷出密鑰.反之,選擇明文不合適,會造成時間特征不明顯,因而難以分析甚至無法分析出密鑰.

通用的明文選擇標準為:每組明文的相應位與密鑰作用后,能夠引起密碼算法相應部分運算時間的不同,并可以通過對該部分運算時間的比較推斷出不同密鑰位的值.

在選擇了合適的明文后,通用的攻擊方法為:依次向密碼系統(tǒng)輸入選擇的明文,分別測量密碼算法相應部分代碼的執(zhí)行時間,根據所攻擊的具體密碼算法的實現(xiàn)細節(jié),確定出可行的比較分析方案,進而根據測量的執(zhí)行時間逐步推斷出密鑰.

文中以攻擊智能卡DES算法的第一輪對應S1盒的 6位子密鑰為例[12],具體說明兩種不同的明文選擇方法及相應的時間攻擊分析方法.

2.2.1 第一種攻擊方法的具體操作步驟

(1)觀察第一輪中E盒輸出的前 6位與 K1對應的6位進行的異或操作.首先可以讓 E盒輸出的6位全部為 0,讓子密鑰 K1直接進行位順序調整,將對S1盒查表所消耗的時間作為一個時間基準.再通過選擇特殊的 6位與 K1異或,并檢測位順序調整操作后對S1盒查表所消耗的時間.將測得的時間與時間基準比對,即可分析出K1中對應位的比特值.選擇攻擊S1盒需要的7個6位特殊值(二進制)為

000000、100000、010000、001000、000100、000010、000001.

通過這7個 6位特殊值可以分別對 K1對應S1盒的6位進行測試.設這7個6位的值為Xi(i=0, 1,…,6),根據式(1)進行向上逆推即可求得對應明文.

式中:E-1、IP-1分別為E盒擴展和IP初始置換的逆運算,E-1(Xi)=R0.求出對應的7個明文(十六進制)為

0000000000000000、0000000100000000、

0000000001000000、0000000000010000、

0000000000000100、0000000000000001、

4000000000000000.

(2)輸入第一個測試明文,測得第一輪中進入S1盒的執(zhí)行時間,作為基準時間.再輸入后 6個明文,分別得到6個執(zhí)行時間.由于S盒輸入的數(shù)據為E盒擴展輸出的數(shù)據與子密鑰異或的結果,當 E盒輸出全為 0時,密鑰直接作用于 S盒,故將第一個全0輸入作為時間基準.后 6個測試明文對應到 S1盒的 6位輸入端,各有一位為 1.根據異或規(guī)則,即 1 0=1、0 1=1、1 1=0、0 0=0,當 E輸入位對應S1盒某位為 1,與對應位子密鑰作用后,執(zhí)行時間比基準時間長,說明異或后產生了 1,子密鑰在該位上是 0;反之,若執(zhí)行時間比基準時間短,則說明異或后產生了0,子密鑰在該位上是1.

(3)通過計算剩余的 7個 S盒對應的選擇明文,作類似的攻擊,即可通過總共 49組明文分析出48位第一輪子密鑰.剩下的 8位只需通過 256次窮舉即可獲得,這樣就得到了密鑰K(K中剩余的 k8、k16、k24、k32、k40、k48、k56、k64為奇偶校驗位,無需處理).

2.2.2 第二種攻擊方法的具體操作步驟

第一種攻擊方法要求時間檢測的觸發(fā)起點精確位于 E盒輸出與子密鑰異或后的位置.為降低對觸發(fā)起點位置選擇的要求,可將時間檢測的觸發(fā)點置于初始置換前.這時,由于增加了其它額外的操作,作為時間基準使用的第一個全零明文的漢明重量為0,無法起到基準的作用,所以剔除這組明文而使用剩下的6個明文.改進后第二種攻擊方法的具體操作步驟如下:

(1)選擇測試明文為

0000000100000000、0000000001000000、

0000000000010000、0000000000000100、

0000000000000001、4000000000000000.

(2)由于 6個明文的漢明重量均為 1,故在經過初始置換后,所消耗的時間是一致的.而后面的 E盒將 32位輸入擴展為 48位,其重復操作的16位對應于明文中的 16位,即這些位要比其它位多操作一次.其中,選擇的明文中為 1的位,分別對應第 25、33、57、7位,即第一個、第二個、第五個和第六個明文.這4個明文中為 1的位,會比第三個、第四個明文中為 1的位多操作一次,故將檢測的 6個明文對應的執(zhí)行時間劃分為兩個集合,即

A={第一個時間,第二個時間,第五個時間,第六個時間},

B={第三個時間,第四個時間}.

(3)根據時間值接近程度,將 A、B集合再分別劃分為兩個子集,子集中數(shù)值大的即對應密鑰位 0,數(shù)值小的對應密鑰位 1.時間值的接近程度可以通過以下方法來判別.

以集合A為例,首先對集合 A中元素進行從大到小的排序,得到

對排序后集合A中元素求差值,

將根據式(3)求得的差值按從大到小排序,得到

為便于后面的比較分析,Δti可以適當進行等比放大,一般以Δt0放大到整數(shù)時的倍數(shù)即可.當最大差值Δt0滿足

時,將以最大差值Δt0為界進行后續(xù)分析.其中α的值可取 3～5或根據實際的執(zhí)行時間差異作調整.文中設,將排序后集合 A中元素以為界分成兩個子集{t0,t1,t2}、{t3},子集{t0,t1,t2}中為執(zhí)行時間相對較長的元素,分別對應密鑰位為0,子集{t3}中為執(zhí)行時間相對較短的元素,對應密鑰位為 1.集合B中只有兩個元素,對其進行判別時,可將集合B中元素的差值ΔtB與集合A中的Δt0作比較,若ΔtB與 Δt0很接近,Δt0為集合 A分界的依據,則集合 B中數(shù)值大的元素對應密鑰位為 0,數(shù)值小的對應密鑰位為1.最后,將集合A、B中元素恢復到原來 6位的順序,代入推算出對應的 0或 1值,即可得到對應的6位密鑰.

可能存在的特殊情況是,若集合中元素的差值都很接近,無法劃分子集,則說明這幾位元素對應的子密鑰位可能全為 1或 0.可以進一步通過產生對應的基準時間來比較判斷,要求產生基準時間的明文中有一位為 1,此 1在 E盒中的處理次數(shù),與需要判斷的集合中 1的處理次數(shù)相同,而在 E盒的輸出端,要求1出現(xiàn)在正在判斷的S盒后.這樣通過與基準時間的比較,即可分析出是全為 1或全為 0.由于此時每個S盒分為兩個集合,最多的情況每盒需要2個基準明文.當最后一個 S盒出現(xiàn)這種情況時,可以與剩余的 8位密鑰一起窮舉,計算量最小為 2× 256次,最大為 4×256次.

(4)計算剩余的 7個S盒對應的選擇明文,作類似的攻擊,使用最少 48組最多 64組明文,即可分析出 48位第一輪子密鑰.剩下的 8位只需通過 256次窮舉即可獲得,這樣就得到了密鑰K.

3 選擇明文-時間攻擊實驗

3.1 實驗方案

在與80C52兼容的STC89C51RC單片機中使用智能卡 DES算法[12],在算法中相應位置嵌入了觸發(fā)信號的控制代碼,用來精確觸發(fā)示波器進行采集,以測試相應程序段的執(zhí)行時間.

選擇明文-時間攻擊的測試實驗裝置如圖3所示.計算機(CPU2.8GHz,150GB硬盤,1GB內存, LAN及RS-232口)通過交換機(TP-LINK,10/100Mb自適應)與數(shù)字存儲示波器(Tektronix DPO7254, 2個有源探頭TAP2500)的LAN口相連,自動采集分析軟件可以控制示波器自動進行連續(xù)的數(shù)據采集并以一定格式存儲.被測加密電路板(STC89C51RC單片機)由數(shù)字穩(wěn)壓電源(LPS-305)供電.示波器CH2作為示波器的觸發(fā)信號使用,用于在需要的程序段觸發(fā)示波器進行數(shù)據采集.

圖3 實驗裝置示意圖Fig.3 Schematic diagram of experimental device

示波器通過網絡接口與計算機相連,由邊信道攻擊分析軟件來控制采集.通過單片機執(zhí)行智能IC卡DES算法來進行實際攻擊測試,由RS-232接口接收計算機輸出測試明文,并返回密文和解密得到的明文.示波器設置為每條軌跡1000點,選擇CH2上升沿觸發(fā).測試明文輸入后,由觸發(fā)代碼來控制示波器在DES代碼相應位置進行數(shù)據采集.文中設置觸發(fā)起點為E盒輸出與子密鑰異或后的位置,觸發(fā)結束點為對應 S1盒輸入值的位順序調整程序后的位置.由于不同明文在程序中運行的時間不同,故從觸發(fā)起點到觸發(fā)結束點的時間也不同,這段時間示波器采集到的數(shù)據點數(shù),即可表示觸發(fā)區(qū)間內程序執(zhí)行的時間.實際測試例中,密鑰設置全為 0x66,可以算出對應子密鑰K1的前6位為000111.當 E盒輸出前 6位中有且只有一位為 1時,測得這部分代碼的執(zhí)行時間大于基準時間,說明 E盒輸出中對應1的位與對應部分子密鑰異或運算后產生了 1,根據異或運算的規(guī)則,可以判定該子密鑰在 E盒輸出中對應 1位置上的值為 0;反之,當測得的執(zhí)行時間小于基準時間,可以判定子密鑰在該位置上的值為 1.

3.2 實驗結果及分析

第一種攻擊方法的測量時間及分析結果見表1.將表 1中 100000至 000001對應的測量時間與000000對應的基準時間比較,按第一種攻擊方法的步驟(2)進行分析,例如 40.15μs大于基準時間39.10μs,說明異或后產生了 1,從而推斷出子密鑰在該位上的值為 0.這樣便可以得到這 6位子密鑰000111.同理,可以推算后 7個 S盒對應的測試明文,進行類似的測試分析即可得到子密鑰,最后可得到48位的子密鑰 K1.通過對 K1反推,可以得到密鑰 K的 48位,剩下的 8位只需通過256次窮舉即可獲得,從而得到密鑰K(K中剩余8位為奇偶校驗位,無需處理).

表1 第一種攻擊方法的測量時間及分析結果Table 1 Measured time and analysis resu lts of the first attack method

進一步觀察可以看出,前面基本分析得到的數(shù)據較為準確,一致性也比較好,為了降低對前觸發(fā)點的要求,將時間檢測的觸發(fā)點置于初始置換前.這時由于觸發(fā)中增加了其它操作消耗的時間,可能會引入噪聲,故將示波器設置為每條軌跡 5000點,以提高時間分辨率.按第二種攻擊方法進行兩次時間測量,結果如表2所示.

表2 第二種攻擊方法的測量時間Table 2 Measured time of the second attack methodμs

對于表 2中數(shù)據,按照第二種攻擊方法中的步驟(2),將第一次測量時間劃分為集合A={824.75, 825.00,819.50,819.50}和B={822.00,816.75}.按照式(2),將A中元素按從大到小的順序排列后得到A={825.00,824.75,819.50,819.50}.按照式(3),計算得到差值為{0.025,5.25,0},按從大到小排序得到{5.25,0.025,0}.顯然有5.25＞5×0.025和5.25＞5×0,滿足式(5),則集合A中元素對應{0,0,1,1}.集合B中兩個元素的差值為5.25,此值與集合A的最大差值5.25相等,而5.25為集合A的分界參考值,故B中元素對應{0,1}.將集合A、B中元素恢復到原來 6位的順序,代入推算出對應位的 0或 1值,得到對應于第一輪 S1盒的 6位子密鑰000111.同樣,將第二次測量時間進行類似處理分析,也可以得到對應于第一輪 S1盒的 6位子密鑰000111.

通過以上實驗可以看出,選擇明文-時間攻擊方法的攻擊效率較高,僅需與所要攻擊密鑰長度相當數(shù)量的明文(如第一種攻擊方法僅需 49個明文、第二種攻擊方法僅需 48個明文即可攻擊出48位子密鑰)進行簡單的比較判斷,而無需復雜的統(tǒng)計運算,即可恢復出密鑰,對密碼系統(tǒng)的安全性具有較大的威脅.與選擇明文 -時間攻擊相比,差分功耗攻擊(DPA)[1,4-5]、差分電磁攻擊(DEMA)[6-7]需要數(shù)千至數(shù)萬組明文輸入和采集對應的功率及電磁輻射信息,運行時間長,所需存儲量大,并需要進行一系列復雜的統(tǒng)計運算方可獲取密鑰,運算量很大.

4 抵抗選擇明文 -時間攻擊的措施

針對選擇明文 -時間攻擊,可以通過改進算法,使不同漢明重量的變量執(zhí)行時間相同.然而如果使用高級語言,由于編譯器及其優(yōu)化等級的不同,直接看到的結果與實際編譯后的結果并不一致,可能帶來安全隱患.下面以單片機C語言為例(Keil環(huán)境),給出一個實例進行具體分析.

圖4 未增加等時操作的 C代碼及其部分反匯編代碼Fig.4 C code without time equivalent operation and its part of disassembled code

包含if語句的C代碼及其部分反匯編代碼如圖4所示.從圖4中可以看出,if語句選擇不同的分支,由于不同分支的代碼數(shù)量不同,即符合 if條件時,需額外執(zhí)行=0x20語句(對應的匯編代碼為ORL 0x10,#0x20),因而執(zhí)行時間有所不同.在包含if語句后加上else等時操作=0,使不同分支代碼數(shù)量一致,其C代碼如圖5所示.

圖5 增加等時操作的C代碼Fig.5 C code with time equivalentoperation

圖6 不同優(yōu)化等級下增加等時操作的C代碼的反匯編代碼Fig.6 Disassembled code of C code with time equivalent operation and different levels of compiler optimization

事實上,高級語言在編譯器設置不同的優(yōu)化等級下,編譯產生的機器代碼并不完全一致,這將導致某種不確定性,對密碼系統(tǒng)帶來潛在的威脅.在不同優(yōu)化等級下,增加等時操作的 C代碼的反匯編代碼如圖 6所示.從圖 6中可以看出,當編譯器設置的優(yōu)化等級大于等于 3時,增加的等時操作代碼被優(yōu)化掉,沒能起到作用.對照沒有增加等時操作指令的反匯編代碼,編譯器給增加等時操作語句的代碼在if語句有效的分支后自動增加了一條跳轉指令.這樣不僅沒有改善算法的執(zhí)行時間均衡性,反而擴大了程序選擇不同分支執(zhí)行時間的差異,而且降低了整個密碼系統(tǒng)的效率.當編譯器設置的優(yōu)化等級小于等于 2時,增加的等時操作代碼有效,但對照沒有增加等時操作指令的反匯編代碼,編譯器仍是給增加等時操作語句的代碼在 if語句有效的分支后自動增加了一條跳轉指令.

匯編指令執(zhí)行所需要的機器周期見表3.從表3可知,增加的等時操作代碼與編碼器自動增加的跳轉指令執(zhí)行所需的機器周期相同,所以改進后并沒有增加密碼系統(tǒng)的安全性,卻降低了執(zhí)行效率.

表3 指令的機器周期Table 3 Machine cycles of instructions

根據以上分析,在編碼器設置的優(yōu)化等級小于等于 2的情況下,可以增加兩條等時操作代碼,如重復執(zhí)行兩次,來達到平衡兩個分支的執(zhí)行時間的目的.可見,僅僅通過增加等時操作代碼,并不能像直觀看到的那樣有效,增加的等時操作代碼受到編程語言、編譯器及其優(yōu)化設置等情況的影響,不確定因素很多.這些潛伏在算法實現(xiàn)過程中的具體問題很可能會為選擇明文-時間攻擊提供機會.

根據以上分析,在軟件實現(xiàn)的密碼系統(tǒng)中,由于設計過程中設計者可能未考慮到如何抵抗選擇明文 -時間攻擊,或即使考慮到了抵抗該攻擊,但因受到編程語言、編譯器及其優(yōu)化設置的不同影響,故很容易造成程序在不同分支的不同.當這樣的問題出現(xiàn)在處理密碼系統(tǒng)的敏感量時,會導致執(zhí)行時間因敏感量的漢明重量不同而不同,即為選擇明文 -時間攻擊提供了機會.攻擊者可以通過精心選擇合適的明文消息,輸入密碼系統(tǒng)進行加密,再檢測密碼算法相關部分的代碼執(zhí)行時間,然后根據具體密碼算法的實現(xiàn)細節(jié)確定分析方案,從而根據測得的執(zhí)行時間進行分析攻擊,這種攻擊就有可能破譯密碼系統(tǒng)的密鑰,導致密碼系統(tǒng)被攻破.

這類問題在密碼系統(tǒng)中是普遍存在的,例如在HDL語言硬件實現(xiàn)的密碼系統(tǒng)中,由于設計或綜合優(yōu)化過程的不同,會給密碼系統(tǒng)帶來毀滅性的安全隱患.由此可以看出,選擇明文-時間攻擊的主要思想是通過檢測密碼系統(tǒng)因敏感量的漢明重量不同而導致的不同時間差異來獲得其密鑰.

文獻[1]中提出,可以通過在程序中加入隨機延遲來達到掩蓋執(zhí)行時間差異的目的,但在一定程度上會降低密碼系統(tǒng)的效率.同時,攻擊者可采用增加測量次數(shù)進行統(tǒng)計平均等方法來減小隨機延遲對攻擊的影響.

文中提出一種更為有效的方法,即通過重組S表中的元素位置,使之不用對輸入S盒的值進行位調整即可直接查表.對應于標準 S表的S1表如表 4所示,標準S表對輸入位要求按 a1a6行、a2a3a4a5列進行查表,由于S盒為DES算法安全的核心所在,且其設計準則至今尚未完全公開,重新設計 S盒不一定能保證達到原有的安全級別,故在不改變S表安全性能并按原規(guī)則查表的前提下,變換 S表中元素的順序,使其可直接用a6a5a4a3a2a1的位順序對改進后的 S表進行線性查表,同時查表結果與按a1a6行、a2a3a4a5列方式對標準 S表查表的結果相同.改進后的 S1表如表 5所示.這樣,對于智能卡DES算法中的結果,只需統(tǒng)一右移兩位或之前的處理均按靠右端存儲,即可直接對改進后的S表進行線性查表,而無需按標準 S表查表時需要調整輸入比特位,因而不存在執(zhí)行時間差的問題,且不損失代碼的執(zhí)行效率.

表4 標準S表中的S1表Tab le 4 S1 in standard S table

表5 改進后的S1表Tab le 5 Improved S1 Table

5 結語

文中提出了一種選擇明文-時間攻擊方法,并在單片機上進行了實際的攻擊驗證,結果表明:只需精心選擇與密鑰長度相當數(shù)量的明文輸入密碼系統(tǒng),通過分析相關部分代碼的執(zhí)行時間即可恢復出密鑰;密碼算法的安全性除了與其本身密碼體制的安全性有關外,還與密碼算法的具體實現(xiàn)細節(jié)密切相關,不適當?shù)膶崿F(xiàn)過程盡管能完成算法的相應功能,但會帶來致命的隱患.文中最后給出了幾種抵抗該攻擊的措施,并對其性能進行了分析和比較.文中雖然以DES算法為例,但選擇明文-時間攻擊方法同樣適用于其它的分組密碼或公鑰密碼系統(tǒng).

[1] Bar-EIHagai.Introduction to side channel attacks[EB/ OL].[2009-07-16].http:∥www.discretix.com/PDF/Introduction%20to%20Side%20Channel%20Attacks.pdf.

[2] Kocher P.Timing attacks on imp lementations of Diffie-Hellman,RSA,DSS,and other systems[M]∥Advances in Cryptology.Berlin/Heidelberg:Springer-Verlag,1996: 104-113.

[3] Hevia A,Kiwi M.Strength of two data encryption standard implementations under timing attacks[C]∥Proceedings of the Third Latin American Symposium on Theoretical Informatics.Berlin/Heidelberg:Springer-Verlag,1998:192-205.

[4] Mangard Stefan,Oswald Elisabeth,Popp Thomas.Power analysis attacks:revealing the secrets of smart cards [M].Berlin/Heidelberg:Springer-Verlag,2007:6-12.

[5] Chu Jie,Zhao Qiang,Ding Guoliang,et al.Differential power analysis for cryp tographic ICs[C]∥Proceedings of International Con ference on Electronic Measurement＆Instruments.Xi'an:IEEE,2007:292-295.

[6] Gandolfi Karine,Mourtel Christophe,Olivier Francis.Electromagnetic analysis:concrete results[C]∥Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems.Berlin/Heidelberg:Springer-Verlag,2001:251-261.

[7] Quisquater Jean-jacques,Samyde David.Electromagnetic analysis(EMA):measures and counter-measures forsmart cards[C]∥Proceedings of International Con fe-rence on Research in Smart Cards.Berlin/Heidelberg:Sp ringer-Verlag,2001:200-210.

[8] 李瑋,谷大武.基于密鑰編排故障的SMS4算法的差分故障分析[J].通信學報,2008,29(10):135-142.

LiWei,Gu Da-wu.Differential faultanalysis on the SMS4 cipher by inducing fau lts to the key schedule[J].Journal on Communications,2008,29(10):135-142.

[9] 張蕾,吳文玲.SMS 4密碼算法的差分故障攻擊 [J].計算機學報,2006,29(9):2596-2602. Zhang Lei,Wu Wen-ling.Differential fault analysis on SMS4[J].Chinese Journal of Computers,2006,29(9): 2596-2602.

[10] 王美一,唐學海,李超,等.3D密碼的Square攻擊[J].電子與信息學報,2010,32(1):157-161.

Wang Mei-yi,Tang Xue-hai,Li Chao,et al.Square attacks on 3D cipher[J].Journal of Electronics＆Information Technology,2010,32(1):157-161.

[11] Bruce Schneier.應用密碼學:協(xié)議、算法與C源程序[M].2版.吳世忠,祝世雄,張文政,譯.北京:機械工業(yè)出版社,2000:185-201.

[12] Chen Kiwi.DES encryption/decryption used in IC smart cards[CP/OL].[2009-07-03].http:∥www.8052. com/codelib/files/des.asm.