針對AES和CLEFIA的改進Cache蹤跡驅動攻擊

趙新杰，郭世澤，王韜，劉會英

(1. 軍械工程學院 計算機工程系，河北 石家莊 050003；

2. 北方電子設備研究所，北京 100083)

1 引言

傳統(tǒng)的密碼分析視密碼算法實現(xiàn)為黑盒，密碼算法安全性完全取決于實現(xiàn)的數(shù)學函數(shù)以及密鑰的安全性，通過線性和差分分析方法結合明文、密文和算法結構推測密鑰。隨著密碼設計復雜度和密鑰長度的增加，其在設計之初就經(jīng)受了大量數(shù)學分析考驗，安全性得到了極大的提高，傳統(tǒng)的線性和差分分析已經(jīng)很難實現(xiàn)密碼破解。然而密碼算法實現(xiàn)需依附一個物理設備平臺，由于平臺自身的一些物理特性，在加解密過程中會泄露出各種中間狀態(tài)相關的物理效應信息（如時間、功耗、電磁輻射、聲音、錯誤、Cache訪問信息等），又稱之為旁路信息或邊信道信息，利用旁路信息對密碼算法實現(xiàn)進行分析的過程稱為旁路攻擊，主要的攻擊類型有計時攻擊[1]、功耗攻擊[2]、電磁分析[3]、聲音攻擊[4]、故障攻擊[5]、Cache攻擊[6]等。目前大部分密碼算法實現(xiàn)的安全性均面臨旁路攻擊的嚴重威脅，隨著先進的測試儀器和計量手段的出現(xiàn)和發(fā)展，旁路攻擊已經(jīng)具備實際攻擊可行性。本文主要研究利用密碼算法在Cache訪問時泄露的蹤跡信息進行密鑰分析的方法。

Cache攻擊大體分為Cache信息采集和信息分析2個階段，根據(jù)采集信息不同，可將其分為時序驅動、訪問驅動和蹤跡驅動3種，本文給出了一種改進的 Cache蹤跡驅動信息分析方法，并對 AES和 CLEFIA抗 Cache攻擊安全性進行了分析。在Cache蹤跡驅動攻擊方面，文獻[7～10]利用該方法對AES進行了安全性分析，最近，文獻[11]也利用其對CLEFIA進行了安全性分析，但現(xiàn)有文獻均不能在第1輪分析中直接恢復AES和CLEFIA完整擴展密鑰。本文分析方法同文獻[10]類似，利用“Cache失效”蹤跡驅動信息進行密鑰分析，但本文研究發(fā)現(xiàn)，由于分組密碼S盒在Cache中的不對齊分布特性，通過對AES和CLEFIA加密的“Cache失效”蹤跡驅動信息進行分析，其第1輪完整擴展密鑰可在有效樣本下快速恢復。表1給出了本文攻擊同前人工作的比較，其中，H表示Cache命中，M表示Cache失效，第4列H/M表示攻擊中利用的信息是Cache命中還是失效。

表1 128bit AES和CLEFIA蹤跡驅動攻擊比較

本文結構如下：第2節(jié)對Cache訪問信息泄露和Cache攻擊分析模型進行了研究，給出了Cache蹤跡驅動分析模型，分析了分組密碼S盒在Cache中的分布特性，提出了改進的Cache蹤跡驅動分析思想；第3、4節(jié)分別給出了針對AES和CLEFIA的改進Cache蹤跡驅動分析方法，并給出了攻擊實驗結果與比較；第5節(jié)是結束語。

2 Cache攻擊分析模型*

2.1 Cache信息泄露分析與Cache攻擊分析模型

高速緩存Cache主要用于解決CPU與主存之間速度不匹配的問題。為提高算法非線性度和軟件執(zhí)行效率，現(xiàn)代分組密碼大都使用 S盒查表訪問Cache。Cache訪問命中和失效會帶來時間和能量消耗差異，而分組密碼加密使用了S盒進行查表操作需要訪問Cache，其Cache訪問特征信息可通過時間或能量消耗特征信息泄露出來，惡意攻擊者通過Cache攻擊可采集到分組密碼運行過程中泄露的Cache訪問信息，這些訪問信息同查找S盒索引、明文、密文和密鑰有緊密關系，可以用來進行相關密鑰恢復。隨著高精度和復雜精密測試計量儀器及技術的發(fā)展，精確采集Cache泄露的時間和能量消耗差異已經(jīng)具備實際可行性。根據(jù)攻擊者的Cache信息采集能力，可將 Cache攻擊分為時序驅動[6,12～14]、訪問驅動[15～19]和蹤跡驅動[7～11]3 種。

1) 時序驅動 Cache攻擊需采集一次加解密過程的整個時間，結合高級統(tǒng)計分析方法推測密鑰，常需百萬計的攻擊樣本，分析方法復雜；

2) 訪問驅動 Cache攻擊需通過間諜進程采集密碼進程加解密中訪問的Cache組集合，使用直接或排除分析方法推測密鑰，同時序驅動攻擊相比，其對攻擊者的信息采集能力要求比較高，但分析方法簡單；

3) 蹤跡驅動 Cache攻擊需采集密碼加解密過程中每次Cache訪問命中和失效信息的一個序列，結合明文或密文進行密鑰推測，分析效率非常高，通常 Cache訪問蹤跡信息的采集主要通過采集Cache訪問能量消耗信息來實現(xiàn)。

2.2 Cache蹤跡驅動分析模型

在蹤跡驅動Cache攻擊中，攻擊者需獲取加密樣本每次Cache訪問的命中和失效序列，并利用其進行密鑰分析。以AES加密第1輪為例，MHHM,MMHH, MHHH, MHMH 為16次查表訪問的Cache命中和失效序列，其中，H和M分別表示“Cache命中”和“Cache失效”。

圖1表示同一次加密中對S盒的2次查表訪問，2次查表索引分別為x0⊕k0、x1⊕k1，一般來說，如果x0⊕k0是第1次訪問Cache，常會發(fā)生Cache失效，根據(jù)第2次查表訪問Cache是命中還是失效，可將分析分為2種情況。

圖1 蹤跡驅動攻擊模型

1) 二次訪問Cache命中。

此時，x0⊕k0=x1⊕k1，二次 Cache訪問需較短時鐘周期或較低能量消耗，并且可直接泄漏部分密鑰字節(jié)的異或結果可能值k0⊕k1=x0⊕x1。

2) 二次訪問Cache失效。

此時，x0⊕k0≠x1⊕k1，二次 Cache訪問需較長時鐘周期或較高能量消耗，可直接泄漏部分密鑰字節(jié)的異或結果的不可能值k0⊕k1≠x0⊕x1。

通過以上分析，看起來可直接得到k0⊕k1的唯一候選值，假定一個Cache行包含δ個Cache元素，每次Cache失效都會從主存中將整個內存塊的δ個元素加載到Cache中，對于Athlon 3000+ CPU處理器來說，每個Cache元素為4byte，每個Cache行大小為 64byte，δ=16，常用的分組密碼如 AES、Camellia、CLEFIA每個S盒元素為4byte，16個元素常位于同一個Cache行中。每次Cache訪問命中時，2次訪問對應的元素地址a和b拋開低lb δ bit相等，可表示為＜a＞=＜b＞。對于8bit的查表索引和δ=16來說，如果第2次查表Cache訪問發(fā)生Cache命中，常滿足＜x0⊕k0＞= ＜x1⊕k1＞（高 4bit相同，低4bit不一定相同），一次分析可直接得到k0⊕k1的高4bit值，但低4bit值未知；反之，如果二次查表發(fā)生 Cache 失效，可得到＜x0⊕k0＞≠ ＜x1⊕k1＞，此時可得到＜x0⊕k0＞的高 4bit的不可能值，多次分析得到k0⊕k1的高4bit值，但低4bit值仍未知。

2.3 分組密碼S盒在Cache中分布特性

大多數(shù)現(xiàn)有攻擊均假定分組密碼S盒在Cache中是對齊分布的，以AES的S盒為例，S盒大小為1kbyte，共256個元素，每個S盒行對應16個元素，對于Athlon 3000+ CPU處理器來說，定義u為S盒的第1個元素對應某個Cache行的第u個元素(0≤u＜16)，如果AES的S盒在Cache中是對齊分布的，即u=0，一個S盒會恰好對應16個Cache行，如圖2(a)所示。但是，在Windows系統(tǒng)中，分組密碼的S盒在Cache中通常是不對齊分布的，S盒的第1個元素常常不對應某個Cache行中第1個元素（u≠0），一個S盒會恰好對應17個Cache行，如圖 2(b)所示（u=12），利用該不對齊特性，對 AES[17]、Camellia[18]、ARIA[19]、SMS4[20]等分組密碼成功進行了訪問驅動攻擊。

圖2 S盒在Cache中的分布特性

2.4 改進的Cache蹤跡驅動分析思想

以圖1為例，如果S盒在Cache行中是對齊分布的，第2次Cache訪問如果Cache命中，可直接得到k0⊕k1的高4bit值，否則得到一個k0⊕k1高4bit的不可能值，多次分析得到高4bit的正確候選值，這種情況下不可能得到k0⊕k1的低4bit值。但如果S盒在Cache行中是不對齊分布的，x1⊕k1可能等于 x0⊕k0所在的Cache行中的16個連續(xù)元素，但這16個元素可能位于不同的Cache行中，即16個索引值的高4bit不一定全相同，假設 k0=0x01，則 k1=x1⊕x0⊕k0，可得到16個高4bit不同，低4bit也不同的k1候選值集合，如果k0預測正確，多次分析后的交集即可得到唯一的k1值；否則會得到k1的一個空集。

3 針對AES的改進Cache蹤跡驅動分析

3.1 AES算法

AES[21]作為DES的替代者，2001年被美國國家技術標準局(NIST)選用，算法支持 128bit、192bit、256bit密鑰的不同版本，本文主要關注128bit密鑰的AES，分析方法可適用于192bit和256bit密鑰的AES。

AES是一個基于有限域運算的迭代密碼，首先輸入16byte明文 P，輸入的16byte密鑰被擴展成44個32bit字所組成的數(shù)組w[r]，P同初始密鑰K進行異或作為初始輸入狀態(tài)變量，然后第r輪迭代根據(jù)16byte的輸入狀態(tài)xr-1和一個16byte的子密鑰Kr，產(chǎn)生一個16byte輸出狀態(tài)xr。除最后1輪，每一輪迭代都包括對xr-1的4個代數(shù)運算：字節(jié)代換、行移位、列混淆和輪子密鑰Kr異或。

為提高加密速度，AES加密快速實現(xiàn)算法在每一輪中，將除與輪密鑰異或以外的操作合并為 16次查表操作，預先進行計算，計算結果存儲在多個查找表中。整個AES加密由160次查表和176次異或操作組成，執(zhí)行效率非常高，但是頻繁的查表操作訪問數(shù)據(jù)Cache也為其帶來了嚴重的Cache計時攻擊威脅。攻擊者如果采集到足夠多的 AES加密Cache計時信息，將其轉換為查表索引，結合明文或密文就可推斷出某一輪擴展密鑰信息，由于AES密鑰擴展結構具有可逆性，攻擊者只要恢復了中間任意輪擴展密鑰就相當于恢復了初始密鑰。

3.2 相關工作

Bertoni等[7]首先提出密碼實現(xiàn)功耗軌跡可能會泄漏Cache訪問命中和失效信息，利用功耗仿真工具對AES加密功耗進行了仿真，成功獲取了AES加密第1輪每次Cache訪問和命中序列，然后對Cache命中信息進行分析獲取 48bit AES-128密鑰。O.Ac?i?mez[8,9]將Bertoni攻擊延伸到了AES加密第2輪，也是通過對Cache命中信息進行分析，成功獲取94.5bit AES-128密鑰；Joseph Bonneau[10]將 O.Ac?i?mez 攻擊轉移到加密最后1輪，通過分析Cache失效信息進行分析，使用50個樣本成功獲取128bitAES密鑰。

3.3 第1輪分析

攻擊中使用的算法為OpenSSL v. 0.9.8.(a)密碼庫中AES優(yōu)化實現(xiàn)，在加密前9輪使用了4個1kbit的查找表T0、T1、T2、T3，在第10輪僅使用了一個1kbit的T4查找表。AES前9輪加密公式如式(1)所示。可以看出，每輪對T0、T1、T2、T34個查找表分別進行4次查表，共16次查表操作。

第1輪查表索引可表示為

Pi和 Ki分別表示明文和初始密鑰的第 i個字節(jié)，i∈[0,15]。第1輪中查T0表的4個索引值為

第2次查T0表的Cache訪問命中和失效信息結合查表索引P4⊕K4，可推斷出K0和K4的相關信息。如果第2次訪問發(fā)生Cache失效，則滿足

{＜P0⊕K0＞}表示同 P0⊕K0在同一個 Cache 行的16個索引值，如果S盒在Cache中是對齊分布的（如圖2(a)所示），每個查表行對應一個Cache行16個元素，如果 P0=0x61，P4=0x73，假設 K0=0x00，{＜P0⊕K0＞}對應16個高4bit相同的字節(jié)，第2次訪問的失效信息可得出K4的16個不可能值。

使用更多樣本，如果K0預測值為正確的，多次分析后的交集即可得到16個高4bit相同的K4值；否則會得到K4的一個空集。

但是，如果S盒在Cache中是不對齊分布的（如圖 2(b)所示），如每個 S盒查表行對應一個 Cache行的后4個元素和下一個Cache行的前12個元素(u=12)，如果P0=0x61, P4=0x73, 假設K0=0x00，{＜P0⊕K0＞}對應高4bit和低4bit不同的16byte，第2次訪問的失效信息可得出K4的16個不可能值

一次Cache失效信息可排除掉 K4的高4bit和低4bit值不完全相同的16個候選值，如果K0預測正確，K4多次分析后的交集即可得到唯一值；否則會得到K4的一個空集。

將該方法應用到其他 2次查 T0表可恢復K8,K12，其他12次查T1,T2,T3表可恢復其他12個K字節(jié)值。需要注意的是，第j次(j＞1)查Ti表Cache失效一次理論上最多排除掉16(j-1)個錯誤候選值，故后續(xù)密鑰分析效率會越來越高，但前提是前面密鑰字節(jié)分析正確。

3.4 最后1輪分析

OpenSSL v. 0.9.8.(a)中AES最后1輪僅使用T4表進行了16次查表操作，最后1輪加密公式如下

如果第2次查T4表發(fā)生Cache失效，可得到

3.5 實驗結果與比較分析

在 Athlon 3000+ 處理器下（Cache行大小為64byte）進行了攻擊仿真試驗。Cache訪問蹤跡信息采集并不是本文的研究重點，實驗中通過修改算法由其自動輸出Cache訪問命中和失效序列。AES第 1輪攻擊中樣本大小同密鑰搜索空間如圖 3所示?？梢钥闯?，如果S盒在Cache中是對齊分布的，第1輪攻擊只能將其密鑰搜索空間降低到80bit，而在不對齊情況下，大約200個樣本即可將其搜索空間降低到216左右，經(jīng)簡單暴力破解恢復128bit AES密鑰，在仿真環(huán)境下，整個攻擊過程（包括信息采集與分析）可在1s內完成。

圖3 AES第1輪攻擊中樣本大小同密鑰搜索空間關系

AES最后1輪攻擊Cache行大小同攻擊成功所需樣本量關系如圖 4所示?？梢钥闯?，不論 AES的S盒在Cache中是否對齊，128bit完整密鑰都可在有限樣本中恢復，由于S盒的雪崩特性，最后1輪的排除分析效率要高于第1輪攻擊。

圖4 AES最后1輪攻擊中Cache行大小同攻擊成功所需樣本量關系

同前人AES Cache蹤跡驅動攻擊[7～10]比較，前人攻擊都假定S盒在Cache中是對齊的，通過第1輪分析只能獲取 48bit密鑰，而在實際情況下，大多數(shù)情況時S盒元素在Cache中為不對齊分布的，前人攻擊將會失效，本文攻擊則涵蓋了所有情況，在S盒不對齊時分析效率要高于前人攻擊。

4 針對CLEFIA的改進Cache蹤跡驅動分析

4.1 CLEFIA算法

首先給出CLEFIA算法分析使用的符號說明。

P, Xr, C：128bit明文、第r輪中間狀態(tài)、密文；

Pi, Xri, Ci：明文、第r輪中間狀態(tài)、密文的第i個32bit字；

Pi,P(i-j)：明文第i個字節(jié)和明文第i到第j個字節(jié)；

WKi,j, RKi,j：第i個白化密鑰字和擴展密鑰字的第j個字節(jié)；

CONi128：128bit常量；

a|b：a和b相連接；

F0( )i,F1( )i：加密左右輪函數(shù)輸出的第i個字節(jié)；

Li,Ti：密鑰擴展中第i次更新的128bit中間變量；

Ir,i：第r輪對Sj表的第m次查表索引（第iSj,m次查所有表的索引）。

CLEFIA算法是索尼公司在2007年FSE大會上提出的一種分組長度為128bit的密碼[22]，分組長度為128bit，支持長度為128/192/256bit密鑰，采用了廣義Feistel結構，并在算法的開頭和結尾加入了白化處理，整個加密分為3個步驟。

第1步：前期白化。將128bit明文P=(P0,P1, P2,P3)同2個白化密鑰異或，即

第2步：前期r-1輪變換。

圖5 CLEFIA F0和F1函數(shù)

F0和F1函數(shù)由代換函數(shù)S和混淆函數(shù)M組成，如圖5所示，代換函數(shù)均用到了2個不同的8×8的S盒S0和S1，只是使用順序不同，混淆函數(shù)分別使用了4×4的Hadamard型矩陣M0和M1。

第r輪變換和前面變換略有不同：

第3步：后期白化。將128bit(Xr0,Xr1,Xr2,Xr3)與2個白化子密鑰異或，得到密文：

CLEFIA-128密鑰擴展算法分成兩部分：由128bit初始密鑰K和24個32bit常數(shù)CONi128(0≤i＜24)生成128bitL和白化密鑰 WKi(0≤i＜4)；由L和 36個 32bit常數(shù) CONi128(24≤i＜60)經(jīng)擴展得到子密鑰RKj(0≤j＜36)。下面是CLEFIA-128的具體密鑰擴展算法：

4.2 相關工作

2009年，Chester等對CLEFIA進行了時序驅動 Cache計時分析[14]，使用了 226.64個樣本成功恢復121bit CLEFIA-128密鑰；2010年，Chester等對CLEFIA進行了蹤跡驅動Cache分析[11]，將Bertoni攻擊中[7]利用Cache命中蹤跡信息的分析思想應用到CLEFIA分析中，假定可獲取到CLEFIA加密中每次 Cache訪問的命中和失效蹤跡信息，使用 243個樣本1.5h左右恢復CLEFIA-128密鑰。本節(jié)給出了一種改進的Cache蹤跡驅動分析方法，利用S盒的不對齊特性，通過對CLEFIA加密前3輪的Cache失效蹤跡信息進行分析，220次加密經(jīng)分析1s內可恢復CLEFIA-128密鑰。

4.3 第1輪分析

CLEFIA第1輪對S0和S1分別進行了4次查表訪問，8次查表索引為

如果第2次查找S0發(fā)生Cache失效，可得到

對于每個 RK0,0預測值和已知的 P0和 P2字節(jié)值，如果 RK0,0預測正確，則多個樣本排除后可得到唯一的RK0,2值，否則得到一個空集。這樣當?shù)趍次(1≤m＜4)查Sj表發(fā)生Cache失效時，最多可排除相關密鑰字節(jié)的16m個候選值。根據(jù)2.4節(jié)方法和式(13)，通過分析第1輪4次查S0的Cache失效信息，RK0,0, RK0,2, RK1,1, RK1,3值可被依次恢復，通過分析4次查S1的Cache失效信息，RK0,1, RK0,3, RK1,0,RK1,2可被依次恢復。

4.4 第2輪分析

利用 4.3節(jié)恢復的 RK0和 RK1，CLEFIA第 2輪8次查表索引值為

如果第2輪第1次（整個CLEFIA加密第5次）查找S0發(fā)生Cache失效，可得到

根據(jù)式(13)、式(15)和式(16)，由于P,RK0和RK1為已知，多個樣本排除后可得到唯一的WK0,0⊕RK2,0值。當?shù)趍次(4≤m＜8)查Sj表發(fā)生Cache失效時，最多可排除相關密鑰字節(jié)的16m個候選值。這樣，根據(jù)2.4節(jié)方法和式(15)，通過分析第2輪4次查S0的 Cache失效信息，WK0,0⊕RK2,0, WK0,2⊕RK2,2,WK1,1⊕RK3,1和WK1,3⊕RK3,3可被依次恢復；通過分析4次查S1Cache失效信息，WK0,1⊕RK2,1, WK0,3⊕RK2,3, WK1,0⊕RK3,0和WK1,2⊕RK3,2可被依次恢復。

4.5 第3輪分析

利用前2輪分析恢復的RK0, RK1, RK2⊕WK0,RK3⊕WK1值，CLEFIA第3輪8次查表索引值為

如果第3輪第1次（整個CLEFIA加密第9次）查找S0發(fā)生Cache失效，可得到

根據(jù)式(13)、式(15)、式(17)和式(18)，由于 P、RK0、RK1、RK2⊕WK0和 RK3⊕WK1為已知，多個樣本排除后可得到唯一的RK4,0值。根據(jù)2.4節(jié)方法和式(17)，通過分析4次查S0Cache失效信息，RK4,0, RK4,2,RK5,1和RK5,3可被依次恢復；通過分析4次查S1Cache失效信息，RK4,1, RK4,3, RK5,0和RK5,2可被依次恢復。

4.6 主密鑰恢復

根據(jù)CLEFIA密鑰擴展算法[22]，利用前3輪攻擊恢復 RK0、RK1、RK2⊕WK0、RK3⊕WK1、RK4、RK5，每個組合值可將CLEFIA-128主密鑰空間降低到27。圖6(a)給出了生成CLEFIA密鑰擴展生成子密鑰RKi（0≤i≤7）的過程，圖6(b)給出了前3輪攻擊的結果，圖6(c)給出了利用前3輪攻擊結果恢復主密鑰K（即WKi，0≤i＜4）的過程。具體算法如下：

1) 根據(jù)常量 CON0和第 1輪攻擊結果計算CON0⊕(RK0,RK1)恢復 L0(0,7)；

2) 分析CLEFIA密鑰擴展中ReveseDoubleSwap函數(shù)∑-1(L0(0,7))恢復L1的64bit；

圖6 CLEFIA-128主密鑰恢復過程

3) 計算 CON0⊕L1(0,7)恢復 T1的 64bit；

4) 根據(jù)T1的64bit和RK4,RK5計算T1(0,7)⊕(RK4,RK5)恢復 32bit WK0,25bit WK1(0,2)；

5) 計算(WK0,WK1(0,24))⊕(WK0⊕RK2, WK1⊕RK3)恢復 32bit RK2, 25bit RK3(0,2)；

6) 計算 GFN4INV(RK0,RK1,RK2,RK3(0,2),CON)恢復K的121bit值，其余7bit可通過暴力破解獲取。

4.7 實驗結果與比較分析

對于64byte Cache行大小，CLEFIA-128第1輪攻擊樣本大小同RK0, RK1密鑰搜索空間關系如圖7所示?？梢钥闯觯绻鸖盒在Cache中對齊分布，RK0, RK1密鑰搜索空間可降低到 240，但是在不對齊情況下 80個樣本可將RK0、RK1密鑰搜索空間分別降低到216。

圖7 不同u值第1輪攻擊中樣本量同相關密鑰搜索空間關系

圖8 為u=7時前2輪攻擊樣本量同(RK0, RK1,RK2⊕WK0, RK3⊕WK1)密鑰搜索空間關系，可以看出100個樣本即可將其密鑰搜索空間降低到216。

圖8 u=7時前2輪攻擊中樣本量大小同相關密鑰搜索空間關系

圖9 為u=7時前2輪攻擊樣本量同(RK0, RK1, RK2⊕WK0, RK3⊕WK1, RK4and RK5)密鑰搜索空間關系，可以看出 220個樣本即可將其密鑰搜索空間降低到29，由于通過分析前3輪相關密鑰恢復CLEFIA主密鑰還需 27次暴力破解，故 220個樣本即可將CLEFIA-128主密鑰空間降低到216，在仿真環(huán)境下，整個攻擊過程（包括信息采集與分析）可在1s內完成。

同現(xiàn)有CLEFIA Cache蹤跡驅動攻擊[11]比較，本文攻擊有以下優(yōu)點：

圖9 u=7時前3輪攻擊中樣本量大小同相關密鑰搜索空間關系

1) 文獻[11]假定在加密之前Cache被清空，如果加密前有部分S盒元素被加載到Cache中，將會導致文獻[11]利用“Cache命中”蹤跡信息的分析方法失效，而本文利用“Cache失效”蹤跡信息進行分析，即使加密前部分S盒元素提前被加載到Cache中，分析方法依然有效，文獻[10]中分析也可證實了該觀點。

2) 文獻[11]中分析方法僅適用于分組密碼S盒在Cache中對齊分布這種情況，S盒在Cache中不對齊分布時，該分析方法將會失效，而本文分析方法則適用于各種情況。

3) 文獻[11]利用CLEFIA加密中的“Cache命中”蹤跡信息進行密鑰分析，本文則主要利用“Cache失效”蹤跡信息，攻擊樣本量要遠小于同文獻[11]的243個樣本量，攻擊僅需220個樣本即可在1s內恢復CLEFIA-128密鑰。

5 結束語

本文通過分析“Cache失效”蹤跡信息和 S盒在Cache中的不對齊分布特性，提出了一種改進的蹤跡驅動攻擊方法，并對AES和CLEFIA進行了分析?，F(xiàn)有AES、CLEFIA第1輪蹤跡驅動攻擊均不能直接獲取輪密鑰，而本文研究表明，在大多數(shù)情況下，S盒在 Cache中的分布是不對齊的，利用加密過程中的“Cache失效”蹤跡信息，可在有限樣本內快速恢復AES和CLEFIA第1輪擴展密鑰。

以下 2個方面將很值得在將來研究和關注：1) 搭建硬件環(huán)境實驗平臺，通過采集 AES和CLEFIA的硬件實現(xiàn)功耗信息得到 Cache訪問命中和失效蹤跡；2) 開展Cache蹤跡驅動攻擊檢測與防御技術研究。

[1] PAUL C, KOCHER. Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems[A]. CRYPTO 96[C]. LNCS,Springer, 1996. 104-113.

[2] KOCHER P, JAFFE J, JUN B. Differential power analysis[A]. Proc of Advances in Cryptology-CRYPTO '99[C]. LNCS, Springer, 1999.388-397.

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

[4] SHAMIR A, TROMER E. Acoustic cryptanalysis: on nosy people and noisy machines[EB/OL]. http://www.wisdom. weizmann.ac.il/～ tromer/acoustic/, 2004.

[5] BONEH D, DEMILLO R A, LIPTON R J. On the importance of checking cryptographic protocols for faults[A]. Fumy, W Ed EUROCRYPT 1997[C]. Springer, 1997.37-51.

[6] TSUNOO, TERUO S, TOMOYASU S, et al. Cryptanalysis of DES implemented on computers with cache[A]. CHES 2003[C]. Springer,2003.62-76.

[7] BERTONI G, ZACCARIA V, BREVEGLIERI L, et al. AES power attack based on induced cache miss and countermeasure[A].ITCC(2005)[C]. IEEE Computer Society, 2005.586-591.

[8] ACIICMEZ O C, ETINKAYA K. Trace-driven cache attacks on AES[EB/OL]. http://eprint.iacr.org/2006/138.pdf, 2006.

[9] ACII?MEZ O, KOC C K. Trace driven cache attack on AES[A]. Proc International Conference on Information and Communications Security (ICICS) 2006[C]. Springer, 2006. 112-121.

[10] JOSEPH B. Robust final-round cache-trace attacks against AES[EB/OL]. http://eprint.iacr.org/2006/374.pdf, 2006.

[11] CHESTER R, DEBDEEP M. Differential cache trace attack against CLEFIA[EB/OL]. http://eprint.iacr.org/2010/012.pdf, 2010.

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

[13] JOSEPH BONNEAU, ILYA M. Cache-collision timing attacks against AES[A]. Louis Goubin and Mitsuru Matsui Eds Cryptographic Hardware and Embedded Systems - CHES 2006[C]. Springer, 2006. 201-215.

[14] REBEIRO C, MUKHOPADHYAY D, TAKAHASHI J, et al. Cache timing attacks on CLEFIA[A]. Roy, B, Sendrier, N Eds INDOCRYPT 2009[C]. Springer, 2009. 104-118.

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

[16] MICHAEL N, SEIFERT J P. Advances on access-driven cache attacks on AES[A]. Proc of the Selected Areas in Cryptography-SAC2006[C].Springer, 2007. 147-162.

[17] ZHAO X J, WANG T, MI D. Robust first two rounds access driven cache timing attack on AES[A]. Proc of the International Conference on Computer Science and Software Engineering - CSSE 2008[C].2008, 3:785-788.

[18] 趙新杰, 王韜, 鄭媛媛. Camellia訪問驅動Cache計時攻擊研究[J].計算機學報, 2010, 33(7): 1153-1164.ZHAO X J, WANG T, ZHENG Y Y. Research on access driven cache timing attacks against camellia[J]. Chinese Journal of Computers,2010, 33(7): 1153-1164.

[19] 趙新杰, 郭世澤, 王韜等. ARIA訪問驅動Cache計時模板攻擊[J].華中科技大學學報（自然科學版）, 2011, 39(6): 62-65.ZHAO X J, GUO S Z, WANG T, et al. Access driven Cache timing template attack on ARIA[J]. Journal of Huazhong University of Science and Technology (Nature Sciences Edition), 2011, 39(6): 62-65.

[20] 趙新杰, 王韜, 鄭媛媛. 針對SMS4密碼算法的Cache計時攻擊[J].通信學報, 2010, 31(6): 89-98.ZHAO X J, WANG T, ZHENG Y Y. Cache timing attack on SMS4[J].Journal on Communications, 2010, 31(6): 89-98.

[21] JOAN D, VINCENT R. The Design of Rijndael: AES—the Advanced Encryption Standard[M]. Springer-Verlag, 2002.

[22] SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128bit block cipher CLEFIA[A]. Biryukov, A Ed FSE 2007[C]. Springer, 2007.181-195.