李志峰 高玉琢

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

關鍵詞：AES;側信道攻擊;碰撞攻擊;模板攻擊

0 引言

傳統(tǒng)的密碼分析是通過數學理論對密碼的數學結構進行分析，而側信道攻擊主要是對密碼系統(tǒng)的實現以及運行過程中產生的側信息，如運算時間、電磁波、能量功耗等進行攻擊?；诟咚倬彺妫–ache）的側信道攻擊是利用了在加密過程中對Cache訪問時系統(tǒng)所泄露的信息來對密碼算法進行攻擊，從而獲得算法的密鑰。自2002年Page[1]提出了基于高速緩存的側信道攻擊方法以來，研究者們分析了Cache訪問時所能利用到的不同信息，包括Cache訪問軌跡、整體加密時間或者Cache訪問模式。時序驅動的Cache攻擊是利用密碼算法執(zhí)行時間所反映出的與密鑰信息的相關性來對密碼系統(tǒng)進行攻擊。根據其在數據采集和處理方式上的不同，可以將這種時序驅動攻擊方法分為基于碰撞的攻擊和基于模板的攻擊。本文將針對AES加密算法分析研究這兩種攻擊方法的具體實現。

1 Cache信息泄露原理

1.1? Cache結構

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

1.2? Cache信息泄露

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

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

2 AES加密算法

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

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

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

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

3?時序驅動Cache攻擊

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

3.1 通用模型分析

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

3.2 碰撞攻擊

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

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

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

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

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

當考慮到Cache訪問的局部性原理時，實際可獲取12×（8-logδ2）位密鑰。因為主存和緩存的數據交換單位為Cache line大小，所以在實際查找表的過程中，發(fā)生碰撞的索引項高位（8-logδ2）總是相同的，其中δ表示每個Cache line中可存儲查找表元素的個數。

3.3 模板攻擊

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

3.3.1 模板搭建

攻擊者使用一臺與目標密碼服務器相同配置的加密設備，在已知密鑰和明文的前提下，進行加密操作。

（1）用已知密鑰K'對大量隨機明文進行加密，明文數量為n，收集加密時間并將其存儲在數組S[i]（0≤i≤n）中。

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

3.3.2 獲取目標密碼服務器實際加密操作時間信息

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

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

3.3.3 模板匹配

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

（1）計算匹配矩陣0≤k≤255同模板矩陣0≤j≤255的相關性，得到的256個候選值對應的相關性系數矩陣R[a]（0≤a≤255）。

（2）將相關性系數矩陣R[a]繪制一條相關性曲線，曲線中的最高點對應的a值即為正確的ki值。

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

4?結語

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

[參考文獻]

[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]趙新杰，王韜，矯文成，等.一種新的針對AES的訪問驅動Cache攻擊[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].軍械工程學院學報，2011（2）：65-68.

（編輯 何 琳）