針對(duì)SMS4密碼算法的Cache計(jì)時(shí)攻擊

趙新杰，王韜，鄭媛媛

（軍械工程學(xué)院 計(jì)算機(jī)工程系，河北 石家莊 050003）

1 引言

密碼算法是密碼學(xué)的重要內(nèi)容，是實(shí)現(xiàn)信息保密的核心體制，其安全性分析一直是密碼研究中非?；钴S的課題。密碼算法的安全性包括2大方面內(nèi)容：一方面是數(shù)學(xué)上的安全性，主要是從密碼算法的設(shè)計(jì)角度來考慮安全性能，將其看作是一個(gè)抽象的數(shù)學(xué)變換，從傳統(tǒng)的代數(shù)、數(shù)論、信息論、計(jì)算復(fù)雜性、邏輯和統(tǒng)計(jì)結(jié)構(gòu)上分析密碼安全性；另一方面是與算法實(shí)現(xiàn)相關(guān)的安全性，主要是利用算法在物理設(shè)備和軟件平臺(tái)上實(shí)現(xiàn)可能泄露的各種中間狀態(tài)信息（如時(shí)間、功耗、電磁輻射、錯(cuò)誤信息等）來進(jìn)行密鑰分析。這種利用中間狀態(tài)信息對(duì)密碼算法實(shí)現(xiàn)進(jìn)行分析的過程稱為旁路攻擊，主要的攻擊類型有計(jì)時(shí)攻擊[1]、功耗攻擊[2]、電磁分析[3]和故障攻擊[4]等。當(dāng)前主流密碼算法在數(shù)學(xué)上都具有較高的安全性，經(jīng)受了大量數(shù)學(xué)分析的考驗(yàn)，幾乎無法破解，而旁路攻擊具有信息采集方法多、分析方法簡(jiǎn)單、密鑰恢復(fù)效率高等優(yōu)點(diǎn)，在密碼分析中屢屢出奇制勝，為密碼和信息安全帶來了新的挑戰(zhàn)和思考。

高速緩沖存儲(chǔ)器Cache的時(shí)間信息，可能作為密碼破解的旁路思想，最早是由 Kocher等人[1]在1996年提出來，其基本原理是：相同的數(shù)據(jù)或指令在訪問存儲(chǔ)器時(shí)，由于涉及到的目標(biāo)數(shù)據(jù)當(dāng)前是否處于Cache中同Cache的歷史狀態(tài)有關(guān)，因此此時(shí)是否發(fā)生Cache命中是不確定的，這將導(dǎo)致數(shù)據(jù)訪問操作的不確定。這種不確定性行為可以通過時(shí)間旁路方式泄露出來。此后，人們從攻擊部件單元、采集時(shí)間點(diǎn)、采集方式、攻擊環(huán)境等角度對(duì) Cache計(jì)時(shí)攻擊進(jìn)行了分類，從性能、效率、攻擊難易程度等方面進(jìn)行研究，并給出了 RSA算法[5,6]、DES算法[7]、AES算法[8～12]等多種密碼體制的 Cache計(jì)時(shí)攻擊方法。

SMS4算法[13]作為國(guó)內(nèi)官方公布的第一個(gè)商用分組密碼算法，中國(guó)無線局域網(wǎng)安全標(biāo)準(zhǔn)WAPI的重要組成部分，其安全性研究具有重要的意義，自2006年提出以來密碼界對(duì)其安全性展開了一系列的研究。在傳統(tǒng)數(shù)學(xué)分析方面，文獻(xiàn)[14,15]根據(jù)SMS4的輪結(jié)構(gòu)特點(diǎn)，構(gòu)建出12、14輪不可能差分區(qū)分器，并分別對(duì)14、17 輪SMS4 進(jìn)行了不可能差分攻擊，但攻擊樣本量和計(jì)算復(fù)雜度很高。在旁路攻擊方面，主要從差分故障分析角度開展，文獻(xiàn)[16]提出，SMS4 算法的安全性對(duì)差分故障攻擊是脆弱的，在選擇明文攻擊下，通過在加密過程中指定存儲(chǔ)單元中導(dǎo)入隨機(jī)單字節(jié)故障，利用非線性變化的差分特性即可恢復(fù)原始密鑰；文獻(xiàn)[17]通過提高故障導(dǎo)入的效率，可以用較少的錯(cuò)誤密文數(shù)恢復(fù)原始密鑰；文獻(xiàn)[18]提出并討論了一種針對(duì) SMS4密鑰編排方案的差分故障攻擊方法，通過在 SMS4算法的密鑰編排方案中導(dǎo)入故障成功恢復(fù)初始密鑰。目前所有針對(duì)SMS4的差分故障分析都是針對(duì)單字節(jié)故障導(dǎo)入進(jìn)行的，現(xiàn)有故障導(dǎo)入方式大都通過計(jì)算機(jī)模擬方式實(shí)現(xiàn)，在真實(shí)環(huán)境下故障信息的精確導(dǎo)入和采集極為困難，攻擊實(shí)用性不強(qiáng)。在針對(duì)SMS4的Cache計(jì)時(shí)攻擊方面，尚未發(fā)現(xiàn)國(guó)內(nèi)外有公開發(fā)表的結(jié)果。

在深入分析和測(cè)試SMS4 算法后，本文提出了針對(duì)SMS4 算法加密前4輪和最后4輪的Cache計(jì)時(shí)分析方法，通過使用間諜進(jìn)程采集SMS4加密過程中訪問的Cache組信息，結(jié)合明文或密文信息，分別設(shè)計(jì)實(shí)現(xiàn)針對(duì)SMS4前4輪和最后4輪的Cache計(jì)時(shí)攻擊，并就攻擊過程、結(jié)果等進(jìn)行了詳細(xì)的描述和分析。理論分析和實(shí)驗(yàn)結(jié)果證明：SMS4算法實(shí)現(xiàn)易遭受Cache計(jì)時(shí)攻擊威脅，前4輪、最后4輪攻擊均在80個(gè)樣本左右成功恢復(fù)128bit SMS4完整密鑰。

本文結(jié)構(gòu)如下：第2 節(jié)簡(jiǎn)單介紹SMS4 算法；第3 節(jié)概述Cache計(jì)時(shí)攻擊方法的基本思想；第4節(jié)詳細(xì)介紹提出的針對(duì)SMS4的Cache計(jì)時(shí)分析方法；第5 節(jié)列出攻擊實(shí)驗(yàn)及實(shí)驗(yàn)結(jié)果對(duì)比；第6 節(jié)是結(jié)束語。

2 SMS4算法

SMS4 密碼是迭代型分組密碼算法，其分組和密鑰長(zhǎng)度均為128bit。加密算法與密鑰編排算法都采用 32 輪非線性迭代結(jié)構(gòu)，解密算法與加密算法的結(jié)構(gòu)相同，只是子密鑰的使用順序相反，以下僅介紹加密算法。

2.1 加密算法

SMS4算法加密過程如圖1所示。設(shè)明文輸入為(X0, X1, X2, X3)∈()4，密文輸出為(Y0, Y1, Y2,Y3)∈()4，輪密鑰為 rki∈(i=0,1,…,31)，則算法加密變換和反序變換為

其中，0≤i≤31，輪函數(shù)F定義為

圖1 SMS4加密算法結(jié)構(gòu)

2.2 密鑰擴(kuò)展算法

SMS4加密算法的輪密鑰由加密密鑰通過密鑰擴(kuò)展算法生成。加密密鑰 MK=(MK0,MK1, MK2,MK3)，MKi∈(i=0,1,2,3)；令 Ki∈(i=0,1,…,35)，輪密鑰為 rki∈(i=0,1,…,31)，輪密鑰生成算法如下：

首先，進(jìn)行初始變換

然后，對(duì)i=0,1,…,31進(jìn)行下列運(yùn)算：

其中，F(xiàn)K=(FK0,FK1,FK2,FK3)和 CK=(CK0,CK1,…,CK31) 為已知系統(tǒng)參數(shù)，其值可參見相關(guān)標(biāo)準(zhǔn)文獻(xiàn)[13]；T'變換和加密算法輪函數(shù)中T基本相同，只將其中的線性變換L修改為以下L'：

3 針對(duì)SMS4的Cache計(jì)時(shí)攻擊概述

3.1 Cache計(jì)時(shí)攻擊原理

高速緩存Cache[19]主要用于解決CPU與主存之間速度不匹配的問題。由Cache訪問命中和失效會(huì)帶來時(shí)間差異，而分組密碼在加密過程中由于使用了S盒進(jìn)行查表操作訪問Cache，其Cache訪問特征信息可通過時(shí)間特征信息泄露出來，可以說，Cache為密碼進(jìn)程加密提供了時(shí)間信息泄露源。而在組映像Cache中，多進(jìn)程在主存中數(shù)據(jù)可能被映射到同一Cache組中，進(jìn)而共享Cache存儲(chǔ)空間。但是這樣就帶來了一個(gè)嚴(yán)重的問題，惡意進(jìn)程可以通過對(duì)其私有數(shù)據(jù)進(jìn)行Cache訪問“命中”和“失效”帶來的時(shí)間差異信息來推測(cè)其他進(jìn)程的 Cache訪問特征。雖然Cache中的數(shù)據(jù)元素是受存儲(chǔ)器保護(hù)的，攻擊者無法直接獲取，但是其元數(shù)據(jù)可泄露Cache訪問地址特征信息，而Cache訪問地址特征信息和分組密碼查找S盒索引有著密切關(guān)系，可被攻擊者利用來進(jìn)行密碼分析。由此可知，Cache也為密碼進(jìn)程提供了時(shí)間信息泄露隱通道。

一般來說，攻擊者通過計(jì)時(shí)手段主要獲取2大類信息：一類是由Cache命中、失效天然條件導(dǎo)致的密碼系統(tǒng)不同輸入的整個(gè)加解密時(shí)鐘周期差異，另外一類就是密碼進(jìn)程加解密訪問過的Cache組信息，由此演化出了2種Cache計(jì)時(shí)分析方法——時(shí)序驅(qū)動(dòng)Cache計(jì)時(shí)分析[5,8,9]、訪問驅(qū)動(dòng)Cache計(jì)時(shí)分析[6,10～12]。相比較而言，時(shí)序驅(qū)動(dòng)信息采集方法比較簡(jiǎn)單，但分析方法比較復(fù)雜，樣本量較大，一般在百萬計(jì)以上，由網(wǎng)絡(luò)傳輸時(shí)延抖動(dòng)帶來的噪聲使得遠(yuǎn)程環(huán)境下計(jì)時(shí)信息的精確采集顯得更加困難，遠(yuǎn)程攻擊適用性不強(qiáng)；訪問驅(qū)動(dòng)分析利用的是密碼算法加解密中訪問的Cache組集合信息，信息采集方法比時(shí)序驅(qū)動(dòng)稍顯復(fù)雜，但分析方法簡(jiǎn)單，所需樣本量較小，在木馬技術(shù)飛速發(fā)展的今天，其在本地和遠(yuǎn)程實(shí)施攻擊的可行性越來越強(qiáng)，越來越受攻擊者青睞。

3.2 攻擊條件

本文主要采用訪問驅(qū)動(dòng)方式對(duì)SMS4分組密碼開展Cache計(jì)時(shí)分析，攻擊需滿足的基本條件為：

1) 攻擊者已知明文或密文信息。對(duì)于針對(duì)SMS4前4輪攻擊來說，攻擊者需已知加密明文；同樣對(duì)于后4輪攻擊來說，攻擊者需已知加密密文。

2) 攻擊者具備采集 SMS4加密部分輪訪問過和未訪問過的Cache組集合信息能力。SMS4前4輪攻擊中，攻擊者能通過一定手段在加密前清空Cache，并在前4輪加密后能夠再次訪問Cache，采集SMS4加密前4輪加密訪問的Cache組集合信息；在SMS4后4輪攻擊中，攻擊者可在加密29輪前清空Cache，并在整個(gè)加密完成后再次訪問Cache，采集加密最后4輪訪問的Cache集合信息。

3.3 攻擊基本思想

對(duì)SMS4密碼算法進(jìn)行訪問驅(qū)動(dòng)Cache計(jì)時(shí)攻擊的基本思想如下。

前4輪攻擊：

1) 產(chǎn)生隨機(jī)明文，得到明文信息；

2) 在加密開始前，使用間諜進(jìn)程清空Cache，并確保在前4輪加密后再次訪問Cache，采集SMS4前4輪加密中沒有訪問過的Cache組信息；

3) 將SMS4加密沒有訪問過的Cache組信息轉(zhuǎn)換為不可能查表索引，結(jié)合明文信息(X0, X1, X2, X3)得到第一輪擴(kuò)展密鑰 rk0的不可能值，多樣本排除分析后得出rk0的唯一值；

4) 將rk0值代入第1輪加密公式，得到每個(gè)明文樣本加密的X4值，利用不可能查表索引和中間狀態(tài)信息（X1, X2, X3, X4）得到rk1的不可能值，多樣本排除分析后得出rk1唯一值；

5) 同樣，利用上述相同方法進(jìn)行推導(dǎo)分析，依次攻擊得到加密第3輪、第4輪擴(kuò)展密鑰rk2、rk3；

6) 使用已經(jīng)恢復(fù)出的加密前4輪擴(kuò)展密鑰，根據(jù)密鑰擴(kuò)展算法，逆向計(jì)算出初始加密密鑰K。

最后4輪攻擊：

1) 產(chǎn)生隨機(jī)明文，加密后獲得相應(yīng)的密文信息；

2) 確保在加密第29輪開始前，使用間諜進(jìn)程清空 Cache，并在 32輪整個(gè)加密完成后再次訪問Cache，采集SMS4最后4輪加密中沒有訪問過的Cache組信息；

3) 將SMS4加密沒有訪問過的Cache組信息轉(zhuǎn)換為不可能查表索引，結(jié)合密文信息(X32, X33, X34,X35)得到第32輪擴(kuò)展密鑰rk31的不可能值，多樣本排除分析后得出rk31的唯一值；

4) 將rk31值代入第32輪加密公式，得到每個(gè)明文樣本加密的 X31值，利用不可能查表索引和中間狀態(tài)信息（X31, X32, X33, X34,）得到rk30的不可能值，多樣本排除分析后得出rk30唯一值；

5) 同樣，利用上述相同方法進(jìn)行推導(dǎo)分析，依次攻擊得到加密第30輪、第29輪擴(kuò)展密鑰rk29、rk28；

6) 使用已經(jīng)恢復(fù)出的最后4輪擴(kuò)展密鑰，根據(jù)密鑰擴(kuò)展算法，逆向計(jì)算出初始加密密鑰K。

4 針對(duì)SMS4的Cache計(jì)時(shí)攻擊過程詳述

4.1 基本記號(hào)和符號(hào)

記(X0, X1, X2, X3)∈()4為明文輸入，(Y0, Y1,Y2, Y3)∈()4為密文輸出，rki∈(i=0,1,…,31)為第i輪擴(kuò)展密鑰。

記(Xi, Xi+1, Xi+2, Xi+3)∈()4(i=0,1,…,31)為第i+1 輪輸入；(Xi+1, Xi+2, Xi+3, Xi+4)∈ ()4(i=0,1,…,31)為第i+1輪輸出。

記 Ai=(a0,i, a1,i, a2,i, a3,i) ∈()4(i=1,2,…,32)為第i輪S盒的輸入；Bi=(b0,i, b1,i, b2,i, b3,i) ∈()4(i=1,2,…,32)為第i輪S盒的輸出，同時(shí)也是第i輪線性變換 L 的輸入；Ci=(c0,i,c1,i,c2,i,c3,i) ∈()4(i=1,2,…,32)為第i輪線性變換L的輸出。

記 Scs為SMS4加密查S盒訪問過的Cache組集合，為SMS4加密查S盒沒有訪問過的Cache組集合；Sy為SMS4加密訪問過的Cache組集合對(duì)應(yīng)的可能查S盒索引值集合，為SMS4加密沒有訪問過的Cache組集合對(duì)應(yīng)的不可能查S盒索引值集合。

下面將詳細(xì)介紹針對(duì)SMS4加密前4輪和最后4輪的攻擊過程。

4.2 信息采集

SMS4加密訪問Cache特征信息的精確采集是信息分析的前提，對(duì)于訪問驅(qū)動(dòng)Cache計(jì)時(shí)攻擊來說，Cache命中和失效時(shí)鐘周期信息的采集和指定加密輪訪問Cache特征信息采集時(shí)機(jī)選取是攻擊成功的關(guān)鍵所在。

計(jì)時(shí)手段選?。河捎诂F(xiàn)代計(jì)算機(jī)時(shí)鐘周期早已達(dá)到納秒級(jí)，Cache命中和失效一般都是100ns以內(nèi)，傳統(tǒng)的計(jì)時(shí)方式會(huì)造成很大誤差，甚至?xí)霈F(xiàn)計(jì)量結(jié)果全部相同情況。因此，本文采用的是Pentium CPU內(nèi)部時(shí)間戳進(jìn)行高精度計(jì)時(shí)，該時(shí)間戳可通過 RDTSC指令來進(jìn)行讀取。由于目前的CPU主頻都非常高，調(diào)用該指令可達(dá)到納秒級(jí)計(jì)時(shí)精度。

Cache信息采集時(shí)機(jī)選?。簽殚g諜程序分配和L1數(shù)據(jù)Cache大小相等的字節(jié)數(shù)組A[0,…, S×W×B-1]，由第3節(jié)可知，前4輪攻擊中，攻擊者需在加密前每隔一個(gè) Cache行訪問數(shù)組 A中元素清空Cache，然后確保在前 4輪加密后再次訪問數(shù)組 A中元素，采集Cache訪問時(shí)鐘周期信息；最后4輪攻擊中，攻擊者需確保在加密 29輪開始前清空Cache，然后在第32輪加密完成后再次訪問數(shù)組A，采集Cache訪問時(shí)鐘周期信息。如何在SMS4加密指定輪前后精確的執(zhí)行Cache訪問操作十分關(guān)鍵。

攻擊中，首先學(xué)習(xí)對(duì)多個(gè)樣本執(zhí)行 SMS加密的平均時(shí)鐘周期t，然后在加密前執(zhí)行RDTSC指令讀取時(shí)間戳t1，加密開始前訪問數(shù)組A清空Cache，然后使用間諜進(jìn)程監(jiān)視SMS4加密過程中系統(tǒng)時(shí)間戳t2變化。在前4輪攻擊中，如果(t2-t1)＞3×t/8則進(jìn)行Cache 2次訪問操作；在最后4輪攻擊中，如果(t2-t1)＞5×t/8則訪問數(shù)組再次清空 Cache，然后在整個(gè)加密完成后再次訪問數(shù)組A，采集Cache訪問時(shí)鐘周期信息。

4.3 信息分析

下面詳細(xì)介紹對(duì)采集的SMS4前4輪Cache旁路信息分析過程。

1) 產(chǎn)生隨機(jī)明文X，并執(zhí)行在未知密鑰K作用下的加密。

2) 攻擊第1輪（如圖2所示），步驟如下。

①首先啟動(dòng)間諜程序，每隔一個(gè)Cache行大小讀取數(shù)組A中數(shù)據(jù)來清空Cache，然后對(duì)明文X在密鑰K作用下加密，在加密前4輪執(zhí)行完畢后再次訪問Cache，采集Cache訪問時(shí)鐘周期信息。此時(shí)如果對(duì)SMS4查找表對(duì)應(yīng)的Cache組訪問所需時(shí)鐘周期較長(zhǎng)，說明在前4輪加密中對(duì)該Cache組對(duì)應(yīng)的查表索引進(jìn)行過訪問操作，將數(shù)組 A中數(shù)據(jù)從Cache中替換出來，間諜進(jìn)程2次訪問Cache失效；否則說明在加密過程中沒有訪問該Cache組對(duì)應(yīng)的查表索引，間諜進(jìn)程2次訪問Cache命中，最終得到SMS4加密前4輪沒有訪問的Cache組集合，如圖3所示，橫坐標(biāo)表示SMS4 S盒對(duì)應(yīng)的16個(gè)Cache組，縱坐標(biāo)表示對(duì)其的訪問時(shí)鐘周期，如果SMS4加密沒有訪問某Cache組，間諜進(jìn)程2次訪問會(huì)發(fā)生Cache命中，時(shí)鐘周期小于5，否則發(fā)生Cache失效，時(shí)鐘周期一般大于10。

② 利用查找表對(duì)應(yīng) Cache組和查表索引之間關(guān)系可知，每一個(gè)加密未訪問的Cache組將對(duì)應(yīng)16個(gè)查表索引值，分析可得加密前4輪沒有訪問的查表索引集合。

③ 由加密第1輪公式（7）可知，第1輪加密的輸入為(X0,X1,X2,X3)，新的中間狀態(tài)變量輸出為X4，擴(kuò)展密鑰為rk0，共進(jìn)行4次查表操作，對(duì)應(yīng)的4個(gè)查表索引分別為(a0,1, a1,1, a2,1, a3,1)。

圖2 第1輪攻擊

圖3 SMS4 查找S盒訪問Cache組時(shí)鐘周期

式(7)又可轉(zhuǎn)化為如式(8)所示。

將每個(gè)加密前 4輪不可能訪問的查表索引值(a'0,1, a'1,1, a'2,1, a'3,1)代入式（8）分別得到輪密鑰rk0的4個(gè)字節(jié)的一組不可能值。理想情況下，如果未訪問的Cache組集合數(shù)目等于NS情況下，可分別將(rk'0,0, rk'1,0, rk'2,0, rk'3,0)的密鑰字節(jié)候選值集合數(shù)量從256降低到256-16×NS，由于正確的密鑰值是不可能被排除掉的，故多樣本排除分析可得到唯一的(rk0,0, rk1,0, rk2,0, rk3,0)，即得到rk0。

3) 攻擊第2輪，步驟如下。

將rk0代入式(7)得到第1輪加密輸出中X4值，由第2輪加密式（9）可知，第2輪加密的輸入為(X1,X2,X3, X4)，新的中間狀態(tài)變量輸出為X5，擴(kuò)展密鑰為 rk1，同樣也進(jìn)行 4次查表操作，對(duì)應(yīng)的 4個(gè)查表索引分別為(a0,2, a1,2, a2,2, a3,2)。

將加密前 4輪不可能訪問的查表索引值(a'0,2,a'1,2, a'2,2, a'3,2)代入式（9）分別得到輪密鑰rk1的4個(gè)字節(jié)的一組不可能值，多次排除分析得到唯一的(rk0,1, rk1,1, rk2,1, rk3,1)，即得到rk1。

4) 攻擊第3、4輪，將rk1代入式（9）得到第2輪加密輸出X5值，然后參考步驟3）方法得到rk2，同樣方法也可得到rk3。

5) 利用密鑰擴(kuò)展算法，由rk0,rk1,rk2,rk3恢復(fù)加密密鑰K。

下面詳細(xì)介紹對(duì)采集的SMS4最后4輪Cache旁路信息分析過程。

1) 產(chǎn)生隨機(jī)明文X，并執(zhí)行在未知密鑰K作用下的加密，并獲取密文C。

2) 攻擊第32輪（如圖4所示），步驟如下。

① 首先啟動(dòng)間諜程序，在加密第29輪執(zhí)行前清空Cache信息，然后在第32輪加密完成后再次訪問Cache，采集Cache訪問時(shí)鐘周期信息。此時(shí)如果對(duì)SMS4查找表對(duì)應(yīng)的Cache組區(qū)域進(jìn)行訪問時(shí)鐘周期較長(zhǎng)，說明在最后4輪SMS4加密中對(duì)該Cache組對(duì)應(yīng)的查表索引進(jìn)行過訪問操作，從而將攻擊者數(shù)組A中數(shù)據(jù)從Cache中替換出來，攻擊者2次訪問發(fā)生Cache失效；否則說明在加密過程中沒有訪問過該Cache組對(duì)應(yīng)的查表索引，攻擊者2次訪問發(fā)生Cache命中。得到SMS4加密前4輪沒有訪問的Cache組集合。

圖4 最后1輪攻擊

② 利用查找表對(duì)應(yīng) Cache組和查表索引之間關(guān)系可知，每一個(gè)加密中未訪問的Cache組將對(duì)應(yīng)16個(gè)查表索引值，分析可得加密前4輪沒有訪問的查表索引集合。

③ 由第32輪加密式（10）可知，加密輸入為(X31,X32,X33,X34)，新的中間狀態(tài)變量輸出為X35，擴(kuò)展密鑰為rk31，共進(jìn)行4次查表操作，對(duì)應(yīng)的4個(gè)查表索引分別為(a0,31, a1,31, a2,31, a3,31)。

式（10）又可轉(zhuǎn)化為如式(11)所示。

將每個(gè)加密最后4輪不可能訪問的查表索引值信息(a'0,32, a'132, a'232, a'3,32)代入式（11）分別得到輪密鑰rk31的4個(gè)字節(jié)的一組不可能值。理想情況下，如果未訪問的Cache組集合數(shù)目為NS的情況下，可分別將(rk'0,31, rk'1,31, rk'2,31, rk'3,31)的密鑰字節(jié)候選值集合數(shù)量從256降低到256-16NS，由于正確的密鑰值是不可能被排除掉的，故多樣本排除分析可得到唯一的(rk0,31, rk1,31, rk2,31, rk3,31)，即得到rk31。

3) 攻擊第31輪，步驟如下。

將rk31代入式（10）得到第31輪加密輸出中X31值，由第31輪加密式（12）可知，第31輪加密的輸入為(X30,X31,X32, X33)，新的中間狀態(tài)變量輸出為X34，擴(kuò)展密鑰為rk30，同樣也進(jìn)行4次查表操作，對(duì)應(yīng)的4個(gè)查表索引分別為(a0,31, a1,31, a2,31, a3,31)。

將加密前 4輪不可能訪問的查表索引值信息(a'0,31, a'1,31, a'2,31, a'3,31)代入式（12）分別得到輪密鑰rk30的4個(gè)字節(jié)的一組不可能值，多次排除分析得到唯一的(rk0,30, rk1,30, rk2,30, rk3,30)，即得到rk30。

4) 依次攻擊第30、29輪，將rk30代入式（12）得到第30輪加密輸出X33值，然后參考步驟3）方法得到rk29，同樣方法也可得到rk28。

5) 利用密鑰擴(kuò)展算法，由 rk28,rk29,rk30,rk31恢復(fù)加密密鑰K。

4.4 復(fù)雜度分析

SMS4算法在4輪加密過程中需要進(jìn)行16次查表操作，令m為查找表在理想情況下（查找表起始元素在Cache行中是對(duì)齊的）對(duì)應(yīng)Cache組個(gè)數(shù)，對(duì)于64byte的Cache行大小來說，m=16，p(b)為查表b次訪問某一Cache組概率，P(b)為在p(b)概率下對(duì)應(yīng)Cache元素個(gè)數(shù)，同樣有，pn(b)為查找表b次沒有訪問某一Cache組概率，Pn(b)為在pn(b)概率下對(duì)應(yīng)Cache元素個(gè)數(shù)。對(duì)于一次查表操作訪問的某個(gè)Cache組來說

則SMS4加密查表16次均未訪問某一Cache組概率為

則16次查表沒有訪問的平均Cache組個(gè)數(shù)為

應(yīng)用4.3節(jié)的排除分析方法，平均每個(gè)加密樣本可以排除掉的密鑰字節(jié)候選值數(shù)目為

令V代表擴(kuò)展密鑰單字節(jié)候選值集合，經(jīng)過對(duì)N個(gè)隨機(jī)樣本進(jìn)行排除分析后，V中元素?cái)?shù)量平均值為

理論上來說，使得NV趨近于1對(duì)應(yīng)的N值為理論上分析該密鑰字節(jié)所需樣本量大小，由式（17）可知14個(gè)樣本左右即可恢復(fù)SMS4一個(gè)密鑰字節(jié)，但由于4.3節(jié)排除分析利用的是加密沒有訪問過的Cache組集合并轉(zhuǎn)化為不可能查表索引信息，每一個(gè)Cache組對(duì)應(yīng)16個(gè)連續(xù)的索引值，故每個(gè)Cache組排除的密鑰字節(jié)為連續(xù)的 16個(gè)值，排除分析的發(fā)散效果不好，因而攻擊所需樣本量比理論值要大些。

5 攻擊實(shí)驗(yàn)及結(jié)果比較

5.1 實(shí)驗(yàn)環(huán)境

攻擊實(shí)驗(yàn)環(huán)境如表1所示。

表1 SMS4攻擊實(shí)驗(yàn)環(huán)境配置

5.2 實(shí)驗(yàn)結(jié)果

應(yīng)用4.2節(jié)SMS4加密Cache訪問信息采集方法和信息分析原理，對(duì)SMS4加密前4輪和最后4輪分別進(jìn)行了攻擊實(shí)驗(yàn)，攻擊均在 80樣本量左右快速恢復(fù)128bit SMS4密鑰，耗時(shí)不超過1ms。

攻擊樣本量同SMS4部分密鑰字節(jié)搜索空間關(guān)系如圖5所示，每個(gè)樣本量N均進(jìn)行10次攻擊。其中錨節(jié)點(diǎn)形狀為三角形的曲線表示理論上攻擊樣本量同SMS4密鑰字節(jié)搜索空間關(guān)系，錨節(jié)點(diǎn)形狀為菱形的曲線表示攻擊樣本量同第1輪擴(kuò)展密鑰rk0的4個(gè)字節(jié)平均密鑰搜索空間關(guān)系，錨節(jié)點(diǎn)形狀為正方形的曲線表示攻擊樣本量同最后1輪擴(kuò)展密鑰rk31的4個(gè)字節(jié)平均密鑰搜索空間關(guān)系。

圖5 攻擊樣本量N和密鑰搜索空間關(guān)系

由圖5易知，第1輪攻擊和最后1輪攻擊樣本量和對(duì)應(yīng)的擴(kuò)展密鑰字節(jié)搜索空間關(guān)系基本一致；30個(gè)樣本即可將 rk0和 rk31的密鑰搜索空間由 232降低到24，70～80個(gè)樣本即可穩(wěn)定的獲取rk0和rk31唯一值；同時(shí)，實(shí)際攻擊所需樣本量要大于4.4節(jié)理論分析結(jié)果，這主要是由于排除分析中每個(gè)沒有訪問的Cache組將對(duì)應(yīng)16個(gè)連續(xù)的不可能查表索引值，由于其連續(xù)性導(dǎo)致的密鑰字節(jié)排除分析發(fā)散性較差造成的。

5.3 結(jié)果比較

實(shí)驗(yàn)結(jié)果同國(guó)內(nèi)外攻擊比較見表2。文獻(xiàn)[14,15]從數(shù)學(xué)角度對(duì)SMS4算法進(jìn)行差分分析，攻擊所需樣本量極大，計(jì)算復(fù)雜度很高，攻擊的真正實(shí)施不是很現(xiàn)實(shí)；差分故障分析所需樣本量較小，密鑰恢復(fù)效率較高，但現(xiàn)有攻擊[16～18]都是通過修改加密算法在計(jì)算機(jī)上模擬實(shí)現(xiàn)故障導(dǎo)入，實(shí)際上是加密算法自己在進(jìn)行故障導(dǎo)入，真實(shí)環(huán)境下對(duì)SMS4加密固定輪和固定字節(jié)進(jìn)行故障導(dǎo)入極為困難，因此如何實(shí)現(xiàn)故障的精確導(dǎo)入是故障攻擊未來要解決的問題。本文提出的訪問驅(qū)動(dòng)Cache計(jì)時(shí)攻擊，在不修改和干擾加密算法執(zhí)行的前提下，使用間諜進(jìn)程采集SMS4加密過程中訪問的Cache組集合信息，然后結(jié)合明文或密文進(jìn)行分析，攻擊所需樣本量較小，密鑰恢復(fù)效率也較高，攻擊實(shí)用性相對(duì)來說比較強(qiáng)；本文中的分析方法具有普遍適用性，尤其是PC機(jī)上使用 S盒的分組密碼算法，如 AES，Camellia，ARIA，SEED；同時(shí)，本文提出的攻擊方法也很容易在遠(yuǎn)程環(huán)境下得以實(shí)施。

表2 攻擊實(shí)驗(yàn)結(jié)果和國(guó)內(nèi)外已有SMS4攻擊比較

6 結(jié)束語

給出了一種針對(duì)SMS4分組密碼算法的訪問驅(qū)動(dòng)Cache計(jì)時(shí)攻擊方法，并分別對(duì)SMS4加密前4輪和最后4輪進(jìn)行了攻擊實(shí)驗(yàn)。研究結(jié)果表明：在不干擾SMS4加密算法執(zhí)行前提下，前4輪、最后4輪攻擊均可在 80個(gè)樣本左右成功恢復(fù) 128bit SMS4密鑰，此類針對(duì)SMS4的計(jì)時(shí)攻擊手段對(duì)信息安全將帶來突出威脅。

需要特別指出的是，基于Cache的SMS4計(jì)時(shí)攻擊是SMS4分組密碼查表操作實(shí)現(xiàn)方式與現(xiàn)有主流計(jì)算機(jī)硬件系統(tǒng)特征所固有決定的，具有難于規(guī)避的特點(diǎn)，防御這種攻擊可采取去除查找表、進(jìn)程訪問控制、Cache預(yù)熱、調(diào)整Cache結(jié)構(gòu)甚至移除數(shù)據(jù)Cache等策略，但所有的防御措施都是要以犧牲加密速度為代價(jià)的，所以如何在速度和安全性這一對(duì)矛盾的指標(biāo)上進(jìn)行平衡選擇是目前密碼程序?qū)崿F(xiàn)所面臨的巨大挑戰(zhàn)。

[1] PAUL C, KOCHER. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[A]. CRYPTO 1996[C].Springer, 1996.104-113.

[2] 吳文玲, 賀也平, 馮登國(guó)等. MARS和Rijndael的能量攻擊[J]. 軟件學(xué)報(bào), 2002,13(4):532-536.WU W L, HE Y P, FENG D G, et al. Power attack of MARS and Rijndael[J]. Journal of Software, 2002,13(4):532-536.

[3] QUISQUATER J J, SAMYDE D. Electromagnetic analysis (EMA):measures and countermeasures for smart cards[A]. Smart Cards Programming and Security (E-Smart 2001)[C]. Springer, 2001.200-210.

[4] BONEH D, DEMILLO R A, LIPTON R J. On the importance of checking cryptographic protocols for faults[A]. EUROCRYPT’97[C].Konstanz, Germany, 1999. 37-51.

[5] BRUMLEY D, BONEH D. Remote timing attacks are practical[A].Proceedings of the 12th Usenix Security Symposium[C]. Washington,DC, 2003. 1-14.

[6] COLIN P. Cache missing for fun and profit[EB/OL]. http://www.daemonology.net/hyperthreading-considered-harmful/,2005.

[7] YUKIYASU T, TERUO S, TOMOYASU S, et al. Cryptanalysis of DES implemented on computers with Cache[A]. Cryptographic Hardware and Embedded Systems - CHES 2003[C]. Springer, 2003.62-76.

[8] DANIEL J, BERNSTEIN. Cache-timing attacks on AES[EB/OL].http://cr.yp.to/papers.html#Cachetiming, 2004.

[9] JOSEPH B, ILYA M. Cache-collision timing attacks against AES[A].Louis Goubin and Mitsuru Matsui, Editors, CHES 2006[C]. Springer,2006.201-215.

[10] DAG A O, ADI S, ERAN T. Cache attacks and countermeasures: the case of AES[A]. Topics in Cryptology-CT-RSA 2006[C]. Springer,2006.1-20.

[11] MICHAEL N, SEIFERT J P. Advances on access-driven Cache attacks on AES[A]. Selected Areas in Cryptography 2007[C]. Springer,2007.147-162.

[12] ZHAO X J, WANG T, MI D. Robust first two rounds access driven Cache timing attack on AES[A]. International Conference on Computer Science and Software Engineering(CSSE 2008)[C]. Wuhan,Hubei, China, 2008. 785-788.

[13] 國(guó)家商用密碼管理辦公室. 無線局域網(wǎng)產(chǎn)品使用的 SMS4 密碼算法[EB/OL]. http://www.oscca.gov.cn/ UpFile/200622026423297990.pdf, 2006.Office of State Commercial Cipher Administration. Block cipher for WLAN products—SMS4[EB/OL]. http:// www.oscca.gov.cn/ UpFile/200622026423297990.pdf, 2006.

[14] 鐘名富, 胡予濮, 陳杰. 分組加密算法SMS4的14輪Square攻擊[J].西安電子科技大學(xué)學(xué)報(bào),2008,35(1):105-109.ZHONG M F, HU Y P, CHEN J. Square attack on the 14-round block cipher SMS4[J]. Journal of Xidian University, 2008,35(1):105-109.

[15] 陳杰, 胡予濮, 張躍宇. 用不可能差分法分析17輪SMS4算法[J].西安電子科技大學(xué)學(xué)報(bào), 2008,35(3):455-458.CHEN J, HU Y P, ZHANG Y Y. Impossible differential attack on the 17-round block cipher SMS4[J]. Journal of Xidian University,2008,35(3):455-458.

[16] 張蕾, 吳文玲. SMS4 密碼算法的差分故障攻擊[J]. 計(jì)算機(jī)學(xué)報(bào)，2006,29(9): 2596-2602.ZHANG L, WU W L. Differential fault analysis on SMS4[J]. Chinese Journal of Computers, 2006,29(9):2596-2602.

[17] LI W, GU D W. An improved method of differential fault analysis on the SMS4 cryptosystem[A]. The First International Symposium on Data, Privacy, and E-Commerce-ISDPE 2007 [C]. Chengdu, China,2007. 175-180.

[18] 李瑋, 谷大武. 基于密鑰編排故障的SMS4算法的差分故障分析[J].通信學(xué)報(bào), 2008,29(10):135-142.LI W, GU D W. Differential fault analysis on the SMS4 cipher by inducing faults to the key schedule[J]. Journal on Communications,2008,29(10):135-142.

[19] HANDY J. The Cache Memory Book: the Authoritative Reference on Cache Design[M]. Orlando, FL, USA: Academic Press, Inc,1998.