基于歐式距離的AES算法模板攻擊

李志明，唐永中

河西學院 信息技術中心，甘肅 張掖 734000

21世紀，科技發(fā)展已經滲透到人們生活的方方面面，計算機、智能手機和智能家居已經成為每個人生活的必需品。與此同時，安全問題成為了人們關注的重點，尤其是個人信息安全和智能家居的安全問題。2018年計算機爆發(fā)的Meltdown和Spectre漏洞[1-3]，利用旁路攻擊方法分析硬件泄露的信息獲取私密信息。該組漏洞給行業(yè)帶來巨大的損失，盡管各大廠商從軟件層面封堵漏洞，但硬件設計缺陷卻難以用軟件的方式來彌補。旁路攻擊是近年來密碼分析的研究重點問題之一，主要利用設備在運行時泄露的物理信息來獲取重要私密數(shù)據(jù)，這些物理信息通常為電磁、電流、聲音、時間等[4-5]，這種攻擊方式實現(xiàn)時不易被發(fā)現(xiàn)，且不會阻礙設備的正常運行，在破解密碼算法時，有著良好的效果。

加密是保護信息安全的方式之一，現(xiàn)在的加密算法主要有對稱加密和非對稱加密算法，AES算法就是典型的對稱加密算法。由于DES算法密鑰較短，隨著計算機計算能力的不斷提升，DES算法很容易被計算機暴力破解，盡管3DES算法增強了DES算法的密鑰長度，但不是一個全新設計的算法，沒有解決根本問題[6]。AES算法的提出解決了DES算法的困境，算法提供128、192和256位密鑰，算法強度也得到加強，在有限的時間內通過暴力破解AES算法是幾乎不可能實現(xiàn)的。相對于非對稱密鑰，AES具有快速高效的特點，在眾多領域使用都較為廣泛。即使算法設計再完美，在硬件或軟件實現(xiàn)時，算法運行的態(tài)勢也可能會被硬件的缺陷而泄露出來，密碼分析者就能夠通過分析泄露的物理信息獲取算法的密鑰。

Cache計時攻擊屬于旁路攻擊的一種，通過利用計算機進程共享的Cache來獲取密碼算法運行時從Cache中泄露的計時信息來分析加密算法的密鑰，并且能夠在進程建立隱蔽信道，通過隱蔽信道將獲取的密鑰傳輸?shù)焦暨M程中，達到獲取加密算法密鑰的目的[7]。Cache計時攻擊的關鍵則是如何區(qū)分Cache命中與Cache失效，但在現(xiàn)在的計算機中，通過利用rdtsc或rdtscp指令能夠輕易地獲取進程運行某一個片段消耗的CPU時鐘周期，從而使Cache計時攻擊成為可能。由于Cache計時攻擊實現(xiàn)的基礎是基于計算機硬件設計的缺陷，所以很難去防御，這種攻擊方式很早被提出，但在最近幾年仍對計算機造成巨大的威脅[8-10]。

模板攻擊是旁路攻擊方法的一種，攻擊過程分為建模和匹配兩個階段，建模階段是通過已知明文攻擊，建立Cache泄露的計時信息與密鑰之間的依賴關系，匹配階段是將采集的Cache計時信息與模板之間進行匹配，相關性越大，恢復密鑰的成功性越高。2020年，樊昊鵬等人僅使用10條相同密鑰加密所產生的能量即恢復出AES-128算法正確的密鑰[11]；2020年，Luo等人利用模板攻擊從硬件角度評估混沌分組密碼系統(tǒng)的安全性，并證實模板攻擊能夠用于攻擊混沌密碼系統(tǒng)[12]。但實現(xiàn)模板攻擊的前提較為苛刻，需要相同或者類似硬件設備，針對Cache而言，模板攻擊只需要相同的處理器就能恢復出密鑰的相關信息，與運行的系統(tǒng)關系不大，故針對Cache的模板攻擊具有一定的通用性。

分析現(xiàn)有的AES算法Cache計時攻擊，都會驅逐密碼進程在Cache中的數(shù)據(jù)，并進行二次訪問，以確認該Cache行是否被加密算法使用，這種攻擊算法的缺點是會引起大量的Cache失效，從而易被計算機檢測出來以阻止攻擊。通過利用Flush+Flush攻擊模型，只需要計算flush指令的時間，不會造成大量的Cache失效。將這種采集計時信息的方法用于模板攻擊，使得攻擊更為隱蔽，不易被發(fā)現(xiàn)。

1 相關基礎知識

1.1 Cache信息泄露原理

在計算機的存儲體系中，由于CPU和存儲的不對稱發(fā)展，普通存儲無法滿足CPU高速運轉的需求，Cache的提出較好地解決了這一問題，但因為高速存儲Cache的造價昂貴，在計算機中通常采用三級Cache，且容量都較小，所以Cache中只存儲CPU常用或即將使用的數(shù)據(jù)。替換策略是如何從內存中合理將數(shù)據(jù)加載到Cache中，減少發(fā)生Cache失效的次數(shù)，以提高CPU的運行效率。在X86處理器中，常用的替換算法有最不經常使用（LFU）、近期最少使用（LRU）和隨機替換算法[13]。

當CPU從Cache中讀取數(shù)據(jù)失敗時，數(shù)據(jù)會從內存加載到Cache中，從而導致讀取數(shù)據(jù)的時間較長。密碼程序加解密時，由于頻繁使用S盒，在程序運行時則會將S盒數(shù)據(jù)加載到Cache中，以提高CPU運行效率。在intel處理器中，使用rdtsc或rdtscp指令能夠提供CPU時鐘周期級別的精準計時，這為Cache計時攻擊提供了工具。不考慮指令消耗的CPU時鐘周期，Cache命中與失效的時間消耗如圖1所示。從圖1中，很容易區(qū)分Cache命中與失效，在命中與失效的時間消耗之間設置一個閾值，時間消耗高于閾值為Cache失效時消耗的時鐘周期，低于閾值為Cache命中時消耗的時鐘周期。通過使用clflush指令來刷新指定的Cache行，針對一個確切的Cache行地址，利用Cache命中或失效確認該地址是否被密碼進程使用。

圖1 Cache命中與失效的時間消耗Fig.1 Time consumption of Cache hits and failures

1.2 AES算法快速實現(xiàn)

AES算法是對稱密鑰算法的一種，算法的加密和解密流程是相反的操作。在AES算法運行過程中，除了第一輪和最后一輪略有不同外，算法每一輪加密由字節(jié)代替（SubBytes）、行移位（ShiftRows）、列混淆（MixColumns）和輪密鑰加（AddRoundKey）4個步驟組成[14]。Cache計時攻擊的目標是算法實現(xiàn)過程中的字節(jié)替換，計時攻擊能夠獲取算法運行時使用S盒的軌跡，通過分析密文生成過程和輸入已知的明文，來獲取AES算法的密鑰[15]。

但是在AES算法軟件實現(xiàn)過程中存在矩陣運算，導致效率較低，所以現(xiàn)代的計算機一般不采用這種實現(xiàn)方式，而采用AES算法快速實現(xiàn)來代替原有的實現(xiàn)方式?？焖賹崿F(xiàn)算法主要通過將AES算法每一輪的3個操作（字節(jié)代替、行移位、列混淆）合并成一個查詢T-tables操作來提高運行效率，由于傳統(tǒng)實現(xiàn)最后一輪加密操作中沒有列混淆操作，最后一輪則單獨生成一個單表，所以T-tables一般有5個表，分別為T0、T1、T2、T3、T4，并且T4表能夠通過掩碼的方式由T0、T1、T2、T3計算得到。在主流的開源密碼庫OpenSSL中，v.0.9.7-v.0.9.8b版本中的AES算法實現(xiàn)使用了5個查詢表，在之后的實現(xiàn)中，T-tables由4個表組成，T4表直接從其他表中得到[16]。分析OpenSSL的T-tables實現(xiàn)，得到T0、T1、T2、T3中的每一個表共有256個元素，且每個元素占用4個字節(jié)，將T-tables加載到Cache中，將占用4 KB的Cache空間。一個Cache大小為64 B，則存儲整個T-tables將消耗64個Cache行。

設一個16個字節(jié)的明文為p=(p0,p1,…,p15)和16個字節(jié)的密鑰為k=(k0,k1,…,k15)，r為加密的輪數(shù)，Kr為第r輪加密的一個密鑰單詞（32位），且：

在算法加密的開始，先將明文與密鑰進行異或，得到初始狀態(tài)x=(x0,x1,…,x15)：

在128位密鑰的AES算法中，前9輪加密過程中包括字節(jié)代替、行移位和列混淆，所以前9輪需要查詢的T-tables有T0、T1、T2、T3，第r+1輪的狀態(tài)值x與第r輪加密的狀態(tài)值關系為：

在第10輪加密中，由于沒有列混淆操作，所以要使用T4表，AES快速實現(xiàn)方法在整個加密過程中只需要160次T表查詢操作和160次異或操作，相比原始AES算法的實現(xiàn)而言，效率非常高[15]。

綜合分析AES快速實現(xiàn)的過程，查詢表索引與原始密鑰有著很強的聯(lián)系，在算法加密開始，明文與密文異或后得到初始狀態(tài)值x，然后進行第一輪加密，如果能夠獲取第一輪加密查詢T表的索引值，加上又能夠控制明文p，通過索引值與明文p異或將直接得到密鑰。

1.3 歐式距離

歐式距離是兩點之間的直線距離，設X(x1,x2,…,xn)，Y(x1,x2,…,xn)是N維空間中的兩個點，用d表示兩點之間的歐式距離，則有：

歐式距離能夠用來計算不同樣本之間的絕對距離來衡量樣本之間的相似性。在Cache計時攻擊過程中，樣本為地址行的命中與失效序列，且只有命中和失效兩種可能，將命中置為1，失效置為0，形成樣本序列，通過計算采集的樣本與密鑰模板之間的歐式距離，得到樣本與每一個密鑰模板的相關性，利用相關性強弱來分析密鑰。

2 攻擊原理與實現(xiàn)

2.1 Flush+Flush攻擊模型

Flush+Flush攻擊模型是對Flush+Reload攻擊模型的改進，F(xiàn)lush+Reload攻擊模型攻擊步驟有3步：

（1）利用clflush指令刷新攻擊進程與密碼進程共享的Cache行。

（2）然后觸發(fā)運行密碼進程。

（3）訪問共享的Cache行并判斷是否發(fā)生Cache失效。

這種攻擊模型準確度很高，但面臨的一個問題就是會觸發(fā)大量的Cache失效，使得攻擊容易被硬件計數(shù)器檢測出來，從而阻斷攻擊。Flush+Flush攻擊模型只需要通過測量clflush指令的執(zhí)行時間來判斷某個Cache行是否緩存S盒數(shù)據(jù)，不會觸發(fā)大量的Cache失效。Flush+Reload攻擊模型需要多次重載數(shù)據(jù)，這種操作可能會引發(fā)預處理，提前將數(shù)據(jù)加載到Cache中，從而使測量方法失效。而Flush+Flush攻擊模型不需要多次觸發(fā)運行密碼進程，不會引發(fā)CPU預處理，攻擊步驟如圖2所示，首先間諜程序找到與密碼進程的共享主存地址，如圖2步驟1所示；然后觸發(fā)運行密碼進程，使用的相應S盒數(shù)據(jù)則會加載到相應的Cache中，間諜程序通過刷新每一個被監(jiān)控的Cache行，利用Cache命中和失效來判斷Cache行是否被加載數(shù)據(jù)，確認AES算法進程查詢T-tables的情況，如圖2步驟2所示，灰色代表被驅逐的Cache行，且該Cache行表示為密碼進程從內存加載到Cache中的數(shù)據(jù)。

圖2 Flush+Flush模型攻擊步驟Fig.2 Step of Flush+Flush model attack

與Flush+Reload攻擊模型相比較，F(xiàn)lush+Flush攻擊模型能夠在攻擊的時候監(jiān)視同一頁中的多個地址，并且攻擊過程中不會引發(fā)大量的Cache失效，從而難以被性能計數(shù)器檢測出。通過多次實驗證明，一次clflush指令消耗的時鐘周期大概在100~200個，然而觸發(fā)一次Cache失效則需要250個時鐘周期，與Flush+Reload攻擊模型相比，因為不會觸發(fā)大量的Cache失效，攻擊過程消耗的時鐘周期會更少。

2.2 模板建立與攻擊實現(xiàn)

攻擊的對象為OpenSSL 1.02算法庫，該版本中的AES算法實現(xiàn)的方式是基于T-tables表快速實現(xiàn)的，并且只有4個T表[17]。當AES算法查詢S盒時，就需要將S盒加載到Cache中，通過Cache計時攻擊，利用Cache命中與失效的關系，獲取加密時查詢S盒的值，即pi⊕ki，再利用S和工作原理xi=pi⊕ki，攻擊的目標為加密的第一輪，故i=0，且p0為已知明文，故能夠得到初始密鑰k0。

首先獲取OpenSSL地址活動情況，利用mmap函數(shù)映射OpenSSL地址到共享內存中，然后通過觸發(fā)AES算法并檢測OpenSSL地址數(shù)據(jù)是否被緩存到Cache中，如算法1所示。

算法1檢測活動地址

輸入：OpenSSL映射初始地址*addr，OpenSSL地址空間addr_space

輸出：OpenSSL活動地址*addr_live

由于OpenSSL加密庫包含多種算法，所以不能確定AES算法的地址，使用算法1確定AES算法的地址。為了簡化實驗獲取準確的結果，算法運行在單核中，不使用并行運算來對算法進行加速，將OpenSSL加密庫映射到內存中，在Cache行對齊的情況下，首先在不加密的情況下獲取OpenSSL地址的Cache使用情況，然后使用16字節(jié)的隨機明文和密鑰進行100次加密操作，在Intel i7-4720HQ處理器、Kali Linux 2017.3的版本中平均一次加密所需要的時間約為340個CPU周期，如果發(fā)生Cache失效，則會對加密的時間影響很大，因為每一次失效至少需要消耗200個左右CPU周期，通過這個明顯的時間差異就能夠準確地獲取查詢T表的索引值信息。通過檢測OpenSSL的地址，比較加密和無加密兩次采集得到的Cache活動，得到82個Cache行的活動與加密有關，并且在這82個Cache行中，有18個Cache行在每次加密中的命中率都為100%，因此這18個Cache行與查詢的T表沒有直接關系。剩下的64個Cache行的命中率基本在92%左右，通過分析AES算法快速實現(xiàn)的方法，在加密的時候，不是T表每一個地址都需要被訪問，并且訪問的地址取決于明文。4個T表在內存中需要占用4 KB的存儲空間，每一個Cache行為64 Byte，故4個T表在Cache中需要占用64個Cache行，所以剩下的64個Cache行一定是AES算法的4個T表。

確認AES算法的T表的位置后，使用Flush+Flush模型進行攻擊，因為T表占用64個Cache行，一個Cache行能夠容納16個字節(jié)，分析查詢T表的索引值，通過監(jiān)視64個Cache行來獲取每次加密時Cache訪問的情況，通過固定密鑰，使用隨機明文進行加密，采集64個地址的Cache計時信息來建立密鑰模板。建立模板如算法2所示。

算法2建立模板

輸入：AES算法初始地址*addr，地址空間addr_space，隨機明文p，循環(huán)攻擊次數(shù)N

輸出：檢測地址命中與失效狀況template[256][256]，初始值0

算法2中循環(huán)攻擊次數(shù)N要滿足8位大小明文的所有可能都出現(xiàn)一次，以消除未知明文帶來的不確定性，在模板最后階段需要設置一個閾值，將值大于1的視為Cache命中并置為1，否則為0。通過算法2監(jiān)控指定的地址，并使用隨機明文不斷地觸發(fā)AES算法加密操作，來獲取在密鑰不變的情況下的密鑰模板。在現(xiàn)實攻擊過程中，首先使用算法1檢測AES算法初始地址，然后通過算法2獲取目標運行時的計時信息，最后計算與已知的AES算法密鑰的Cache模板的歐式距離，距離最小即為算法的密鑰，如算法3所示。

算法3攻擊實現(xiàn)

輸入：AES算法初始地址*addr，地址空間addr_space，隨機明文p，循環(huán)攻擊次數(shù)N

輸出：與每個密鑰模板的距離Distance[256][256]，初始值0

3 實驗與結果分析

實驗環(huán)境為kali linux 2017.3版本操作系統(tǒng)，硬件平臺CPU為4核8線程的Intel i7-4720HQ，內存為16 GB，攻擊的目標為OpenSSL 1.02版本的AES算法，采用選擇明文攻擊方式。一個Cache行有16個查詢表，首先攻擊第一個Cache行，通過使用隨機的明文和固定的密鑰，采集有效的Cache計時信息來建立模板，一個明文字節(jié)有8位，確保每一個明文信息出現(xiàn)一次，即至少需要觸發(fā)28=256次加密操作，并建立相應的密鑰模板。通過改變密鑰的值，建立256個密鑰模板，在攻擊AES算法時，監(jiān)控64個Cache行，獲取的Cache計時模板，通過與模板進行對比，從而獲取AES算法的密鑰。

為了建立一個準確的模板，實驗通過觸發(fā)10 000次加密操作，當密鑰字節(jié)k0=0x00時獲取的Cache計時模板如圖3所示，縱坐標表示明文，橫坐標表示監(jiān)測地址，黑色表示在該監(jiān)測的地址中發(fā)生Cache命中。當密鑰字節(jié)k0=0xA5時獲取的Cache計時模板如圖4所示。

圖3 k0=0x00的Cache計時模板Fig.3 Cache timing template of k0=0x00

圖4 k0=0xA5的Cache計時模板Fig.4 Cache timing template of k0=0xA5

選擇采集的任意一個Cache計時信息，計算與所有模板的歐式距離，如圖5所示，與0x8A模板的距離最小，且遠小于其他值，可斷定該值為AES算法的密鑰。

圖5 Cache計時信息與模板之間的距離Fig.5 Distance between Cache timing information and template

攻擊AES算法時，準確度取決于模板的準確性，當使用少量的加密操作來建立模板時，由于攻擊過程中，容易受到其他進程的影響，并且存在系統(tǒng)和硬件的干擾，攻擊的準確率較低，通過提高觸發(fā)加密操作的次數(shù)，來建立更精準的模板。在上述實驗中，獲取每一個密鑰模板需要10 000次加密操作，顯然這種方式效率很低，為了找到最小加密次數(shù)，以256次加密次數(shù)為基數(shù)進行實驗，實驗結果如圖6所示，模板攻擊準確率達到100%需要6×28次加密操作。

圖6 模板攻擊準確率與采集樣本數(shù)量關系Fig.6 Relationship between template attack accuracy rate and number of samples collected

Flush+Flush攻擊模型不會觸發(fā)大量的Cache失效，在Intel i7-4720HQ處理器中，在相同的時間內，運行攻擊程序觸發(fā)的Cache失效如表1所示。

表1 不同攻擊模型觸發(fā)Cache失效次數(shù)Table 1 Times of Cache miss in different attack models

無攻擊情況下由于其他進程的影響，也會發(fā)生Cache失效，然而使用Flush+Flush攻擊模型攻擊時，發(fā)生Cache失效的次數(shù)不到無攻擊時的4倍，然而在Flush+Reload攻擊模型中，發(fā)生Cache失效次數(shù)為無攻擊時的22倍，是Flush+Flush攻擊模型的5.86倍，通過實驗證明，F(xiàn)lush+Flush攻擊模型不會觸發(fā)大量的Cache失效。

4 結論與展望

研究以OpenSSL算法庫中的AES算法快速實現(xiàn)為對象，利用Flush+Flush攻擊模型采集Cache計時信息，建立AES算法每一個密鑰的模板，基于歐式距離度量樣本與密鑰模板之間的相關性來獲取算法的密鑰。實驗證明，在采集的模板足夠準確時，攻擊準確率能達到100%，且觸發(fā)Cache失效次數(shù)僅為Flush+Reload攻擊模型的17%，而且攻擊更為隱蔽，不易被檢測出。建立準確的模板時，需要大量地觸發(fā)加密操作，如果在目標機建立模板很容易被檢測出來，為了防止這種問題就需要在攻擊前建立模板，如果攻擊對象的系統(tǒng)或者OpenSSL的版本不一樣，就容易造成模板失效，下一步研究重點應放在如何提高攻擊的普適性，以適應不同的系統(tǒng)和OpenSSL版本，達到攻擊的目的。