針對AES最后一輪加密的Cache攻擊方法

陸 垚，陳開顏，王寅龍

(陸軍工程大學, 石家莊 050000)

1997年1月，美國國家標準技術研究所宣布開發AES加密標準，使其成為新的聯邦信息處理標準，取代舊的數據加密標準DES和3DES[1]。在AES 算法中，除最后一輪外，其他每一輪都要執行這4 種變換:字節替換、行移位、列混淆和輪密鑰加，最后一輪不執行列混淆變換，且常采用流水線模式進行加密，這種加密模式需要消耗大量的運算資源且效率低下，尤其是在加密大文件或大數據量時,缺點體現更加明顯。在傳統PC環境下，實現對大文件的AES加密變成了查表操作，雖然需要占用內存容量，但卻很大程度節省了計算單元，加快了運行速度。

Cache是位于CPU與主存DRAM間的高速緩沖存儲器，是為了協調CPU處理速度快而主存儲器傳送數據慢的硬件結構，當進程被執行時，根據替換算法策略將循環使用的數據載入到Cache中，再次使用時從Cache中快速調用，現代CPU通常有2～3個層次的緩存結構，一級緩存、二級緩存和三級緩存，與主存地址的三種映射方法：全相聯、直接映射、組組映射[2]；而Cache 計時攻擊又是旁路攻擊中一種重要的方法，是利用一個與密碼進程共享Cache的間諜進程監測密碼進程對Cache 的訪問情況從而獲取密鑰，與其他旁路攻擊手段相比，具有無需物理接觸密碼設備、可通過網絡遠程獲取密鑰的優點,側通道攻擊初期，最常見的攻擊目標是單核CPU內的L1緩存[3-4]。2014年，Yarom等[5]首次實現了跨內核/vm的Flush+Reload攻擊，在GnuPG中RSA上實現，恢復超過90%的密鑰位。而后Flush+Reload攻擊被應用于更多的加密庫和加密算法。例如，Benger等[6]推測了對OpenSSL的ECDSA簽名實現上Flush+Reload攻擊的方法。同年，Irazoqui等[7]提出了更快的攻擊，在云平臺中，用不到一分鐘的時間內恢復整個密鑰位。不久之后，Zhang等[8]在PaaS云中驗證了Flush+ Reload攻擊的適用性，并獲得一個用戶購物車的條目數。在2015年，Irazoqui等[9]展示了從錯誤填充cbc的TLS包中恢復隱私數據—幸運13攻擊。而后，Gruss等[10]提出了在LLC緩存上應用Flush+Reload攻擊檢測受害者鍵擊的方法，他們的攻擊中往往需要依賴特殊手段中斷加密進程才能精確計時，本文的工作是對前人工作的拓展，將flush+reload攻擊方法運用于AES最后一輪加密，并提出了一種不需要干預加密進程正常執行的攻擊方法。

1 AES查表實現及flush+reload緩存攻擊原理

1.1 AES查表法的實現

AES加密在OpenSSL0.9.8.b[11]中的實現方法，實際就是將AES輪加密轉換為查找T表的操作，查找Te0～Te3四個表，最后一輪加密查找Te4表，解密運算需要查找表Td0～Td4，每個表都是256項的32 bits大小的值構成，即用10個1 kb大小的查找表操作代替了AES的流水線運算。在明文異或初始密鑰后，共進行了9輪輪加密操作，在源代碼1中展示了OpenSSL0.9.8.b中的輪加密操作，以第一輪為例，每一輪的4個32 bits的輸出值，由16個查找表操作完成。

#ifdef FULL_UNROLL

/* round 1:*/

t0 = Te0[s0 >> 24] ^ Te1[(s1 >> 16) & 0xff] ^ Te2[(s2 >> 8) & 0xff] ^ Te3[s3 & 0xff] ^ rk[ 4];

#由明文異或初始密鑰后的狀態值s0～s3四個32 bits值作為輸入；

以s0的高8bits為索引值查找Te0表，得到32 bits表項值，同理查找Te1～Te3；

之后4個表項值與輪密鑰前32 bits值rk[4]進行異或運算，得到該輪輸出的前32 bits值。

t1 = Te0[s1 >> 24] ^ Te1[(s2 >> 16) & 0xff] ^ Te2[(s3 >> 8) & 0xff] ^ Te3[s0 & 0xff] ^ rk[5];

t2 = Te0[s2 >> 24] ^ Te1[(s3 >> 16) & 0xff] ^ Te2[(s0 >> 8) & 0xff] ^ Te3[s1 & 0xff] ^ rk[6];

t3 = Te0[s3 >> 24] ^ Te1[(s0 >> 16) & 0xff] ^ Te2[(s1 >> 8) & 0xff] ^ Te3[s2 & 0xff] ^ rk[7];

以128 bits的輸入值中的8 bits為索引16次查找Te0～Te3表，與密鑰擴展得到的輪密鑰進行異或，得到4個32 bits的表項值，連接成為128 bits就得到了單輪的輸出值，并作為下一輪的輸入值。

#endif /* ?FULL_UNROLL */

/*

* apply last round and

* map cipher state to byte array block:

*/

s0 =

(Te4[(t0 >> 24) ] & 0xff000000) ^

(Te4[(t1 >> 16) & 0xff] & 0x00ff0000) ^

(Te4[(t2 >> 8) & 0xff] & 0x0000ff00) ^

(Te4[(t3 ) & 0xff] & 0x000000ff) ^

rk[0];

PUTU32(out,s0);

#以第9輪加密輸出t0～t3四個32 bits為輸入值，取其高8 bits為索引值查找Te4表得到32 bits的表項值，而后提取表項值的前8 bits；

以t1中間16～23 bit為索引查找Te4表得到32 bits的表項值，提取中間的8 bits值，同理索引t2、t3提取另外兩個8bits的表項值；

四個8 bits的表項值連接為32 bits值與輪密鑰r[0]異或運算，得到32 bits的密文值，同理s1～s3。

在第9輪加密操作執行之后，源代碼2展示了OpenSSL0.9.8.b中實現的最后一輪加密操作，只執行了16次查找Te4表的操作，而實際Te4表就是將8 bits表項值重復4次擴展成為32 bits長度的表項值，在源代碼3中展示了OpenSSL 0.9.8b中Te4表的一部分。

最后一輪加密就是將第9輪加密輸出作為本輪的輸入按8 bits大小劃分，以8 bits為索引查找表Te4，得到32 bits大小的表項值，并壓縮到8 bits大小，然后由16個8 bits的表項值連接成為128 bits的值，異或最后一輪密鑰值得到密文輸出值。

1.2 flush+reload的攻擊原理

在當代操作系統和管理程序中允許不同進程/用戶共享相同的物理內存的。所有Linux操作系統都實現了內核相同頁面的合并Kernel Samepage Merging(KSM)機制，它合并屬于不同進程的重復只讀內存頁，KSM內核守護進程ksmd掃描用戶內存，尋找可能在用戶之間共享的頁面，為這些頁面創建簽名。這些簽名保存在重復數據刪除表中。當發現兩個或多個具有相同簽名的頁面時，將對它們進行完全交叉檢查，以確定它們是否相同。為了創建簽名,當在候選項中發現重復的頁面簽名并對內容進行交叉檢查時，ksmd會自動使用寫時復制(COW)標記其中一個重復的頁面，并在進程/用戶之間共享它，同時刪除另一個副本。此外，VMware實現的透明的頁面共享Transparent Page Sharing(TPS)，這是與KSM類似的機制，也允許不同的vm共享內存。

攻擊的先決條件：

① 由于KSM機制，間諜進程和受害者(加密進程)實現主存或頁面共享。

② 支持clflush指令，能夠從所有緩存層次結構中驅逐數據。

③ 使用rdtsc指令能夠得到精準的時間戳，或者在屏蔽指令mfence/lfence指令下得到的精確CPU周期。

圖1展示了flush+reload的攻擊方法，在step1中的Cache中數據塊是在間諜進程和受害者間主存或頁共享的，step2間諜進程通過clflush指令將該數據塊從緩存中清除，step3中受害者執行加密進程，會將加密進程所使用的數據從共享主存中加載到緩存中，在step4中間諜進程重載了該數據塊的主存地址，在step3之前和step4之后使用rdtsc指令記錄時時間戳，如果這個數據塊被加密進程所使用的，那么發生命中，檢測為低的重載計時值，否則被監測到高的重載計時差值，進而遍歷所有的共享地址空間，就能夠得到加密時使用數據對應的活動地址集，即Te表的地址集(由于輪密鑰生成操作與明文無關，輪密鑰生成運算只執行一次后就直接使用，而加密查找Te表的操作要持續執行，所以在連續執行加密進程時，不用考慮Td0～Td4進入到cache中)。

2 攻擊原理及步驟

攻擊步驟：

① 在加密進程持續執行時，使用flush+reload基本方法判斷共享主存中活動的地址集，即加密進程數據的地址，通過對源代碼的學習，可以知道加密進程的數據就是表Td0～Td4、Te0～Te4、rcon的數據，rcon是擁有10個32 bits表項值的小表，加密進程不加載表Td0～Td4(Td表用于解密)，可以得到Te0～Te4地址；

② 對Te4表中第一個cacheline大小的數據塊進行監控，使用flush+reload方法，記錄重載監控內存塊的和時間和對應的密文()；

③ 篩選計時小于閾值即發生cache命中的密文，與監控地址內的數據Te4，共同恢復最后一輪的密鑰。

圖1 flush+reload攻擊方法

2.1 獲得加密進程活動地址集方法

使用mmap函數映射共享空間，在共享空間地址中查看加密操作的活動地址集。

在算法1中描述了如何獲取Te0～Te4的表地址；其中，rdtsc函數由mfence/lfence屏障指令和rdtsc計時指令構成，確保指令順序執行。

2.2 利用flush+reload方法求解密文值對應的監測計時

間諜進程對Te4表中一個Cacheline長度的數據塊進行監控，在加密進程執行前對其flush操作，在加密進程執行后測量reload該Cacheline的用時t，常用加密庫中加密用到的數據都經過優化，幾乎都是對齊的，故不需要求解偏移地址，如果未對齊也可以選擇監控Te4表中占用的第二個Cacheline數據進行實驗，在實驗中只需要監測Te4表中一個Cacheline大小的數據塊，共16個32 bits的表項值的數據塊，存儲在密文字節向量()，使用字典中鍵值對X= dict(′Cι[]′:t)的數據類型的采集，在算法2描述了求解該鍵值對的過程。

1:Input:byte *Te4[0], #以*Te4地址為例獲取計時

long unsigned int Plaintext[] #明文

2:Output:X= dict(′Cι[16]′:t) #使用鍵值對dict的數據結構，采集密文及對應監測地址的重載時間

3:P[16]= Plaintext.split(16) #將明文按16個字節長度分割

4:flush(*Te4[0]) #將*Te4[0]地址數據從cache中驅逐

5:Cι[16] =Encryption(P[16]) #執行加密進程

6:st =rdtsc() #記錄時間戳

7:reload(*Te4[0]) #重新將*Te4[0]地址數據載入到cache中

8:ed =rdtsc() #記錄時間戳

9:t=ed-st #記錄重載時間

10:returnX=dict(′Cι[16]′:t) #返回密文和其對監控地址的重載計時

2.3 密鑰恢復算法

Cι表示M組密文中的第ι組密文，定義一個閾值，提取小于時間閾值的多組密文值Cι′，這些密文在最后一輪加密時使用了監控的Cacheline內的數據，即發生了Cache命中，Cι′=(c0,…,c15),在源代碼2中以s0為例展開：

s0 =(Te4[(t0 >> 24)] & 0xff000000) ^(Te4[(t1 >> 16) & 0xff] & 0x00ff0000) ^(Te4[(t2 >> 8) & 0xff] & 0x0000ff00) ^(Te4[(t3) & 0xff] & 0x000000ff) ^rk[0];

s0=(c0,c1,c2,c3,);

rk[0]代表32 bits的密鑰值，按8 bits長度展開，則

rk[0]=(k0,k1,k2,k3)；

代入k0到s0中，以32 bits分割s0則

c0= Te4[(t0 >> 24)] & 0xff000000^k0；

在源代碼3中，由于采取重復值擴展，可得

byte(Te4[(t)])=

Te4[(t)] & 0xff000000= Te4[(t)] & 0x00ff0000=

Te4[(t)] & 0x0000ff00=Te4[(t)] & 0x000000ff；

用16個8 bits長度的A0…A15代替最后一輪四個32 bits 輸入值t0～t3，那么t0 >> 24代表最后一輪輸入的第一個byte值，可表示為A0，則

c0= byte(Te4[(A0)])^k0，那么有

k0= byte(Te4[(A0)])^c0

得到了恢復最后一輪密鑰值一般公式：

ki=byte(Te4(Aj))^ci，其中ki代表最后一輪第i位byte密鑰值，Aj代表行移位操作產生的偏移。

恢復密鑰簡碼如算法3所示，對于每組發生命中的密文值，需要在被監控Cacheline數據塊中的16個表項值和16個密鑰位置間進行定位，會產生256個算數值。

1:Input:long unsigned intX[],long unsigned int Threshold

2:Output:byteK[]

3:int Count_key[] #定義密鑰值的統計數

4:byteY[][16] #定義一個m行16列的密文數組

5:Cι[16] = Ciphertext.split(16) #將密文按16字節長度分割

6:forι= 0toM do #篩選發生cache命中的密文

8:Y[m][16] ←Cι[16]

9:end

10:fori=0 to 15 do#循環恢復最后一輪16位密鑰字節

11: int Count_key[16]={0}

12:forι′ = 0tom do #使用m個命中密文計算

13:forj= 0to15 do

#每次命中，可能來源于被監控cacheline大小的內存塊中的16個字節，每個內存塊中字節都要計算

14: Count_key[Y[ι′][i] ^ Te4[0][j]]++

#統計相同密鑰值的計數

15:end

16:end

17:k[i] = Count_key.index(max(Count_key[])) #最大計數值對應的索引數據，就為第i個密鑰字節的正確值

18:end

19:returnK9[]={k[0],k[1],…,k[15]}#K9最后一輪的密鑰值

圖2展示了對最后一輪密鑰的第二個字節k1的攻擊，對Te4表的第1組64 byte大小的數據塊Te4[0]進行監控，在加密進程執行后，從M組密文中收集reload時間小于閾值的m組，即發生命中，這些密文在加密的最后一輪使用了被監控的數據塊，對這些密文值進行圖2中的運算， 其中只有一個是正確的數值，通過對計算值Count_key[Y[ι′][i] ^ Te4[0][j]]的統計，最多的共有解max(Count_key[])對應的Y[ι′][i]^Te4[0][j]為正確的密鑰值，如下：

圖2 恢復k1的密鑰byte值

3 實驗結果

實驗是在Ubuntu16.04.3系統中，以OpenSSL0.9.8.b加密庫中AES算法為攻擊目標，實驗設備為Intel i5-4590四核心、3.3 GHz的CPU處理器，該處理器有3層Cache結構，每個core上的存儲結構相同，一個L1數據緩存和L1指令緩存，都為32 kb大小、一個256 kb大小的L2緩存，四個core共用一個6 MB大小的L3緩存。其每個Cacheline大小為64 bytes，每個Te4表中的元素為4 bytes，所以1次攻擊可以檢測16個表值是否發生命中，圖3展示了對命中、未命中兩種情況各10 000次攻擊數量的計時分布，通過實驗可以觀測到Cached數據重載計時相對集中，主要因為緩存技術成熟，L1、L2、L3緩存速度差異不明顯，導致緩存不同層級間的計時差異不到5個CPU周期，Cached數據計時平均值在5個周期，而Uncached數據重載計時相對分散，平均值在26個周期，差距在11個周期，取閾值(2tCached+tUncached)/3等于11，恰好能區分97%以上的計時值，這個閾值是通過圖4中實驗得出的最優解。

圖3 對i5-4590進行50 000次flush-reload計時攻擊(區分命中、未命中)

為了獲得準確的密鑰值，本實驗取103量級的共有解作為密鑰值，圖4表示了恢復正確密鑰與密文數據量之間的關系，在獲得280×103組密文數據量后，就能夠完整的恢復最后一輪密鑰值，而理論需要256×103組密文，是實際值的91.5%，對比圖3的97%分辨率差距6.5%左右，證明在加密進程不同于單純的數據替換，在加密進程執行時，系統的其他進程會產生額外的噪聲影響，且密文數據在280×103之前顯示為逐漸上升的曲線，證明最后一輪16個密鑰字節中的部分密鑰字節先達到103量級，優先被確認恢復，不同于理想的所有密鑰字節的平行恢復，這是因為產生命中密文的相關密鑰位置是隨機的，命中密文不是平均使用16個密鑰字節的，更加符合實際情況。

圖4 獲得最后一輪密鑰值對應的密文量

4 結論

本文工作是從OpenSSL0.9.8.b的AES加密實現代碼中找到了可實施Cache攻擊的薄弱點，提出了一種通用性強、不依賴偏移地址、不需干預加密進程、不需加密前明文數據預處理的攻擊方法。實驗表明對比使用Flush+Flush攻擊方法，Flush+Reload攻擊具有更好的分辨率，FF方法的數據替換只能區分93%的計時，本文提出的攻擊方法能夠分辨97%以上的計時值，且Cached與Uncached數據計時差異明顯。不需要特殊手段中斷加密進程，使得此攻擊更加有效、更加適用于真實的加密環境。在加密進程執行時進入緩存的數據只有明文和T表的數據，也可對明文進行標記，使其區別于T表的數據作為明文輸入，執行更加精準的攻擊，然而此攻擊依賴于加密算法單次訪問Te4表，如果多次訪問，就要去除更大體量的噪音值，下一步將完善此進程，應用與其他加密算法庫實現的AES查表法。