針對(duì)AES加密算法的時(shí)序驅(qū)動(dòng)Cache攻擊研究

李志峰 高玉琢

摘 要：時(shí)序驅(qū)動(dòng)Cache攻擊是指通過分析處理器中加密算法的不同執(zhí)行時(shí)間來恢復(fù)密鑰，從而實(shí)現(xiàn)對(duì)密碼系統(tǒng)的攻擊。文章針對(duì)AES加密算法進(jìn)行時(shí)序驅(qū)動(dòng)Cache攻擊分析：首先介紹了Cache結(jié)構(gòu)和信息泄露原理，指明對(duì)算法執(zhí)行過程中泄露信息的利用，描述了AES算法，對(duì)基于碰撞的時(shí)序驅(qū)動(dòng)Cache攻擊和基于模板的時(shí)序驅(qū)動(dòng)Cache攻擊進(jìn)行針對(duì)AES算法的攻擊分析。需要特別指出的是，AES查表操作的實(shí)現(xiàn)方式是主流計(jì)算機(jī)硬件系統(tǒng)的固有特性，目前對(duì)這類攻擊難以規(guī)避，且攻擊可以應(yīng)用于大多數(shù)的AES實(shí)現(xiàn)軟件。

關(guān)鍵詞：AES;側(cè)信道攻擊;碰撞攻擊;模板攻擊

0 引言

傳統(tǒng)的密碼分析是通過數(shù)學(xué)理論對(duì)密碼的數(shù)學(xué)結(jié)構(gòu)進(jìn)行分析，而側(cè)信道攻擊主要是對(duì)密碼系統(tǒng)的實(shí)現(xiàn)以及運(yùn)行過程中產(chǎn)生的側(cè)信息，如運(yùn)算時(shí)間、電磁波、能量功耗等進(jìn)行攻擊。基于高速緩存（Cache）的側(cè)信道攻擊是利用了在加密過程中對(duì)Cache訪問時(shí)系統(tǒng)所泄露的信息來對(duì)密碼算法進(jìn)行攻擊，從而獲得算法的密鑰。自2002年P(guān)age[1]提出了基于高速緩存的側(cè)信道攻擊方法以來，研究者們分析了Cache訪問時(shí)所能利用到的不同信息，包括Cache訪問軌跡、整體加密時(shí)間或者Cache訪問模式。時(shí)序驅(qū)動(dòng)的Cache攻擊是利用密碼算法執(zhí)行時(shí)間所反映出的與密鑰信息的相關(guān)性來對(duì)密碼系統(tǒng)進(jìn)行攻擊。根據(jù)其在數(shù)據(jù)采集和處理方式上的不同，可以將這種時(shí)序驅(qū)動(dòng)攻擊方法分為基于碰撞的攻擊和基于模板的攻擊。本文將針對(duì)AES加密算法分析研究這兩種攻擊方法的具體實(shí)現(xiàn)。

1 Cache信息泄露原理

1.1? Cache結(jié)構(gòu)

CPU緩存（Cache）是CPU中的快速存儲(chǔ)區(qū)域，位于CPU和內(nèi)存之間，用來存儲(chǔ)應(yīng)用程序的數(shù)據(jù)和指令，作用是減少內(nèi)存訪問，提高程序的執(zhí)行速度。緩存中的數(shù)據(jù)是CPU即將訪問的，因此避免了直接從內(nèi)存讀取而耗費(fèi)大量時(shí)間。在現(xiàn)代計(jì)算機(jī)中，Cache以層次結(jié)構(gòu)方式實(shí)現(xiàn)。一般Cache分為3級(jí)，分別為L(zhǎng)1 Cache、L2 Cache和L3 Cache（last level Cache，LLC），其中L1 Cache是最接近CPU的一層，所以對(duì)L1 Cache的訪問是最快的。一般情況下，L1 Cache又分為指令Cache和數(shù)據(jù)Cache，分別存放進(jìn)程的指令和數(shù)據(jù)，而L2和L3 Cache不作區(qū)分。高級(jí)別的Cache比低級(jí)Cache大得多，并且包含低級(jí) Cache 的內(nèi)容。

1.2? Cache信息泄露

CPU通過使用Cache緩存數(shù)據(jù)來對(duì)訪問內(nèi)存加速。當(dāng)CPU讀取數(shù)據(jù)時(shí)，訪問Cache的速度與訪問內(nèi)存的速度相差約兩個(gè)數(shù)量級(jí)[4]，從而造成訪問數(shù)據(jù)時(shí)由于數(shù)據(jù)所在位置不同（Cache命中與否）出現(xiàn)顯著的時(shí)間差異。Cache側(cè)信道攻擊就是利用密碼系統(tǒng)運(yùn)算在執(zhí)行過程中Cache命中與否時(shí)產(chǎn)生的側(cè)信道信息結(jié)合算法實(shí)現(xiàn)的特性進(jìn)而分析獲得算法的密鑰。當(dāng)CPU需要進(jìn)行內(nèi)存讀寫時(shí)，它首先訪問Cache，在Cache中進(jìn)行查找相關(guān)數(shù)據(jù)。如果訪問的數(shù)據(jù)在Cache中，則直接對(duì)Cache讀寫，這就是一次Cache命中（hit）。如果在Cache中沒有找到所需數(shù)據(jù)，則訪問內(nèi)存，同時(shí)將數(shù)據(jù)讀入Cache中，以備下次訪問，這就是一次Cache失效（miss）。因此，當(dāng)Cache命中時(shí)，它的訪問時(shí)間比Cache失效時(shí)短很多（見圖1）。

時(shí)序驅(qū)動(dòng)Cache攻擊利用了密碼算法運(yùn)行時(shí)整體執(zhí)行時(shí)間由于Cache活動(dòng)而造成的時(shí)間差異進(jìn)而恢復(fù)出密鑰，且不同方法的利用方式不同。內(nèi)部碰撞攻擊利用同一個(gè)Cache line中查找表?xiàng)l目的訪問會(huì)產(chǎn)生內(nèi)部碰撞，內(nèi)部碰撞的發(fā)生導(dǎo)致更多的Cache命中，從而使得執(zhí)行時(shí)間更短。攻擊者通過控制輸入的明文信息，根據(jù)執(zhí)行時(shí)間即可推斷出密鑰部分比特信息。模板攻擊是通過在與目標(biāo)機(jī)器完全相同的機(jī)器上運(yùn)行相同的密碼算法實(shí)現(xiàn)，針對(duì)查找表的每個(gè)輸入，在學(xué)習(xí)機(jī)器上獲取加密時(shí)的極值點(diǎn)對(duì)應(yīng)的輸入值，以確定目標(biāo)機(jī)器上的密鑰信息[2]。

2 AES加密算法

AES（Advanced Encryption Standard）加密算法[3]支持128，192或256比特的不同長(zhǎng)度的密鑰。本文將研究128比特的密鑰。AES加密是一個(gè)迭代過程：每輪接受一個(gè)16字節(jié)的輸入分組Xi和一個(gè)16字節(jié)的輪密鑰Ki來生成一個(gè)16字節(jié)的輸出Xi+1。每一輪都在Xi上執(zhí)行代數(shù)操作：字節(jié)替換、行移位和列混淆（最后一輪沒有列混淆），以及和輪密鑰進(jìn)行異或。在迭代固定的輪數(shù)之后，最終的輸出Xi+1即為密文。

在實(shí)現(xiàn)時(shí)，使用查找表方法來計(jì)算AES，總共需要使用 5個(gè)查找表：T0，T1，T2，T3，T4。除最后一輪使用表T4之外，其余AES每一輪的計(jì)算都使用表T0，T1，T2，T3。因此，每輪AES加密可以通過將Xi拆分為16個(gè)字節(jié)x0，x1，…，x15，將Ki拆分成16字節(jié)k0，k1，…，k15，并通過下面的公式進(jìn)行計(jì)算：

對(duì)于最后一輪的AES，將T0，T1，T2，T3替換成表T4，得到密文C。

近年來的研究表明，由于AES的查找表結(jié)構(gòu)，即在執(zhí)行加密操作時(shí)需要查表的操作，使其面臨著基于時(shí)序驅(qū)動(dòng)的Cache攻擊威脅。

3?時(shí)序驅(qū)動(dòng)Cache攻擊

時(shí)序驅(qū)動(dòng)Cache攻擊通過分析密碼設(shè)備的緩存活動(dòng)泄露出來的已經(jīng)執(zhí)行的一組操作和操作所消耗的時(shí)間來推導(dǎo)加密系統(tǒng)在計(jì)算中涉及的參量。由于時(shí)序驅(qū)動(dòng)的Cache攻擊所需要的設(shè)備和測(cè)量的較為簡(jiǎn)單，使得該類攻擊適用范圍較廣。

3.1 通用模型分析

時(shí)序驅(qū)動(dòng)的Cache攻擊在實(shí)際操作中是研究分組密碼查表時(shí)Cache訪問命中和失效所泄露的側(cè)信道信息與表項(xiàng)數(shù)據(jù)的函數(shù)依賴關(guān)系進(jìn)而分析出密鑰[4]。側(cè)信道泄露信息M是可以采集的，通過尋找M和x之間的某種函數(shù)關(guān)系可以建立函數(shù)M=f（x），此時(shí)可以得到逆函數(shù)x=f-1（M），對(duì)M進(jìn)行分析可以預(yù)測(cè)查表索引x。由x、明文P、密文C、相關(guān)密鑰k以及他們之間存在的函數(shù)關(guān)系g（P/C，x）可以推斷出相關(guān)密鑰k，結(jié)合密鑰擴(kuò)展恢復(fù)主密鑰K。攻擊通用模型如圖2所示。

3.2 碰撞攻擊

時(shí)序驅(qū)動(dòng)Cache碰撞攻擊原理為，攻擊者利用加密AES算法某次查找同一個(gè)查找表時(shí)Cache中會(huì)發(fā)生的訪問命中或者失效導(dǎo)致的顯著時(shí)間區(qū)別對(duì)加密整體執(zhí)行時(shí)間的差異的影響來進(jìn)行密鑰分析[5-6]。AES加密算法兩次查表操作如圖3所示。圖中pi和pj為明文的兩個(gè)字節(jié)，ki和ki為兩次查表操作的相關(guān)密鑰字節(jié)，xi和xj為兩次查同一個(gè)查找表的索引。攻擊者首先要獲取大量明文樣本的加密時(shí)間，即大量xi和xj的加密執(zhí)行時(shí)間，然后將兩次查找同一個(gè)查找表的pi和pj的所有可能異或值作為橫坐標(biāo)，共256種可能值，同時(shí)計(jì)算每種可能值對(duì)應(yīng)的平均加密執(zhí)行時(shí)間作為縱坐標(biāo)的函數(shù)值，繪制一條曲線。平均執(zhí)行時(shí)間最短即函數(shù)值最小的點(diǎn)對(duì)應(yīng)的橫坐標(biāo)值即為這兩次查表操作相關(guān)的兩個(gè)密鑰字節(jié)的異或值。這是因?yàn)閳?zhí)行第一次查表操作時(shí)發(fā)生Cache miss，系統(tǒng)將對(duì)應(yīng)的Cache line加載到緩存中，當(dāng)?shù)诙尾楸聿僮鲿r(shí)，如果兩次查表操作的索引值相同，即xi=xj，則會(huì)發(fā)生Cache hit，在大量樣本的情況下，此時(shí)的平均執(zhí)行時(shí)間最小。

本文將分析AES加密操作的第一輪攻擊實(shí)現(xiàn)。加密的? ? ? ? ?16次查表操作索引可以表示為：

式中，pi，ki，xi分別為第i次查表相關(guān)的明文字節(jié)、密鑰字節(jié)和索引字節(jié)。

AES加密第一輪分別查找4次T0，T1，T2和T3表，共16次查表操作。在T0表中，如果兩次查表索引相同，則第二次查表發(fā)生Cache hit，此時(shí)便有：

因?yàn)閜i⊕pj已知，所以此時(shí)獲得了ki⊕kj的值，此時(shí)可以恢復(fù)查找T0表的相關(guān)的任意4個(gè)密鑰字節(jié)6組異或值結(jié)果，即k0⊕k4，k0⊕k8，k0⊕k12，k4⊕k8，k4⊕k12。同樣，對(duì)于查找T1，T2，T3表，由式（1）所執(zhí)行的查表操作，可以分別恢復(fù)出每個(gè)表中的6組值，這樣第一輪攻擊共可以獲得24組密鑰相關(guān)字節(jié)異或值，最后通過窮舉等方法可以實(shí)現(xiàn)密鑰的恢復(fù)。

當(dāng)考慮到Cache訪問的局部性原理時(shí)，實(shí)際可獲取12×（8-logδ2）位密鑰。因?yàn)橹鞔婧途彺娴臄?shù)據(jù)交換單位為Cache line大小，所以在實(shí)際查找表的過程中，發(fā)生碰撞的索引項(xiàng)高位（8-logδ2）總是相同的，其中δ表示每個(gè)Cache line中可存儲(chǔ)查找表元素的個(gè)數(shù)。

3.3 模板攻擊

模板攻擊主要利用AES加密算法查找S盒時(shí)不同索引時(shí)對(duì)應(yīng)的執(zhí)行時(shí)間對(duì)整體執(zhí)行時(shí)間的影響進(jìn)行密鑰分析[7-8]。在時(shí)序驅(qū)動(dòng)的Cache模板攻擊中，攻擊者需要搭建一臺(tái)同目標(biāo)密碼服務(wù)器相同配置環(huán)境，采集在已知密鑰前提下的大量樣本的平均加密時(shí)間，并計(jì)算每個(gè)查表索引對(duì)應(yīng)256個(gè)可能值的平均時(shí)間下的標(biāo)準(zhǔn)差，得到一條模板曲線;然后在相同配置環(huán)境下的目標(biāo)密碼服務(wù)器環(huán)境上，在未知密鑰情況下采集大量的樣本的加密時(shí)間，再預(yù)測(cè)每個(gè)密鑰字節(jié)候選值，計(jì)算每個(gè)查表索引的256個(gè)可能值的平均時(shí)間下的標(biāo)準(zhǔn)差，得到另外一條實(shí)際加密的曲線;最后通過計(jì)算這兩條曲線的匹配度相似度，從而得到正確密鑰的候選值，因?yàn)檎_密鑰的候選值對(duì)應(yīng)的兩條曲線匹配相似度較高。下面對(duì)AES加密算法的第一輪加密操作進(jìn)行模板攻擊分析。

3.3.1 模板搭建

攻擊者使用一臺(tái)與目標(biāo)密碼服務(wù)器相同配置的加密設(shè)備，在已知密鑰和明文的前提下，進(jìn)行加密操作。

（1）用已知密鑰K'對(duì)大量隨機(jī)明文進(jìn)行加密，明文數(shù)量為n，收集加密時(shí)間并將其存儲(chǔ)在數(shù)組S[i]（0≤i≤n）中。

（2）密鑰K'共16個(gè)字節(jié)，AES第一輪加密共進(jìn)行16次pi⊕ki（0≤i≤15）索引值的查表操作，根據(jù)每個(gè)索引的候選值將S[i]劃分為256個(gè)值，并計(jì)算每個(gè)值的平均加密時(shí)間同所有256個(gè)值的平均加密時(shí)間的差，將其存儲(chǔ)在平均加密時(shí)間標(biāo)準(zhǔn)差二維模板矩陣S'[i][j]中，其中0≤i≤15，（0≤j≤255）。

3.3.2 獲取目標(biāo)密碼服務(wù)器實(shí)際加密操作時(shí)間信息

（1）對(duì)目標(biāo)密碼服務(wù)器，在未知密鑰前提下對(duì)大量隨機(jī)明文執(zhí)行加密操作，明文數(shù)量為n，把采集到的加密時(shí)間存儲(chǔ)在數(shù)組T[i]（0≤i≤n）中。

（2）第一輪加密操作共進(jìn)行16次索引查表，首先預(yù)測(cè)每次查表操作時(shí)的密鑰字節(jié)ki，共有256個(gè)候選值。對(duì)于每個(gè)ki候選值，計(jì)算n個(gè)明文樣本對(duì)應(yīng)的pi⊕ki值，并將T[i]劃分為? ? ? ? 256個(gè)值，計(jì)算每個(gè)值的平均加密時(shí)間和所有256個(gè)值的平均加密時(shí)間的差，并將其存儲(chǔ)在平均加密時(shí)間標(biāo)準(zhǔn)差三維匹配矩陣T'[i][j][k]，其中0≤i≤15，0≤j≤255，0≤k≤255。

3.3.3 模板匹配

匹配方法如下，如果kj=a（0≤a≤255），則有：

（1）計(jì)算匹配矩陣0≤k≤255同模板矩陣0≤j≤255的相關(guān)性，得到的256個(gè)候選值對(duì)應(yīng)的相關(guān)性系數(shù)矩陣R[a]（0≤a≤255）。

（2）將相關(guān)性系數(shù)矩陣R[a]繪制一條相關(guān)性曲線，曲線中的最高點(diǎn)對(duì)應(yīng)的a值即為正確的ki值。

（3）按照上面的步驟依次獲取所有的ki值，通過進(jìn)一步分析恢復(fù)初始密鑰K。

4?結(jié)語

時(shí)序驅(qū)動(dòng)的Cache攻擊由于其采集方法簡(jiǎn)單，平臺(tái)適用性強(qiáng)，因此可以沖破外界環(huán)境條件的限制完成攻擊。但其所需樣本量大，一般要百萬計(jì)，同時(shí)數(shù)據(jù)處理和分析比較復(fù)雜，如模板攻擊需要大量的數(shù)據(jù)樣本制作模板曲線。近些年隨著Cache攻擊研究的深入，越來越多的數(shù)學(xué)方法應(yīng)用到側(cè)信道信息處理和密鑰分析中，如用隱馬爾科夫模型、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)等，這些方法的引入不僅提高了數(shù)據(jù)分析精度以及密鑰推算的準(zhǔn)確度，還提高了密鑰分析效率，是未來訪問驅(qū)動(dòng)的Cache攻擊的重要研究方向。

[參考文獻(xiàn)]

[1]PAGE D.Theoretical use of cache memory as a cryptanalytic side-channel[J].IACR Cryptology ePrint Archive，2002（169）：1-23.

[2]IRAZOQUI G，EISENBARTH T，SUNAR B.Cross processor cache attacks[C].Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security，2016：353-364.

[3]JOAN D，VINCENT R.The design of Rijndael：AES-the advanced encryption standard[M].Berlin：Springer，2002.

[4]BOGDANOV A，EISENBARTH T，PAAR C，et al.Differential cache-collision timing attacks on AES with applications to embedded CPUs：//Cryptographers Track at the RSA Conference[C].Berlin：Springer，2010：235-251.

[5]趙新杰，王韜，矯文成，等.一種新的針對(duì)AES的訪問驅(qū)動(dòng)Cache攻擊[J].小型微型計(jì)算機(jī)系統(tǒng)，2009（4）：797-800.

[6]BONNEAU J，MIRONOV I.Cache-collision timing attacks against AES[C].International Workshop on Cryptographic Hardware and Embedded Systems.Springer，Berlin，Heidelberg，2006：201-215.

[7]BERNSTEIN D J.Cache-timing attacks on AES[EB/OL].（2005-04-14）[2021-05-20].http：//cr.yp.to/antiforgery/cachetiming-20050414.pdf.

[8]吳克輝，王韜，趙新杰，等.一種基于Cache的AES計(jì)時(shí)模板攻擊方法[J].軍械工程學(xué)院學(xué)報(bào)，2011（2）：65-68.

（編輯 何 琳）