陸 垚,陳開顏,王寅龍
(陸軍工程大學(xué), 石家莊 050000)
1997年1月,美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所宣布開發(fā)AES加密標(biāo)準(zhǔn),使其成為新的聯(lián)邦信息處理標(biāo)準(zhǔn),取代舊的數(shù)據(jù)加密標(biāo)準(zhǔn)DES和3DES[1]。在AES 算法中,除最后一輪外,其他每一輪都要執(zhí)行這4 種變換:字節(jié)替換、行移位、列混淆和輪密鑰加,最后一輪不執(zhí)行列混淆變換,且常采用流水線模式進(jìn)行加密,這種加密模式需要消耗大量的運(yùn)算資源且效率低下,尤其是在加密大文件或大數(shù)據(jù)量時(shí),缺點(diǎn)體現(xiàn)更加明顯。在傳統(tǒng)PC環(huán)境下,實(shí)現(xiàn)對(duì)大文件的AES加密變成了查表操作,雖然需要占用內(nèi)存容量,但卻很大程度節(jié)省了計(jì)算單元,加快了運(yùn)行速度。
Cache是位于CPU與主存DRAM間的高速緩沖存儲(chǔ)器,是為了協(xié)調(diào)CPU處理速度快而主存儲(chǔ)器傳送數(shù)據(jù)慢的硬件結(jié)構(gòu),當(dāng)進(jìn)程被執(zhí)行時(shí),根據(jù)替換算法策略將循環(huán)使用的數(shù)據(jù)載入到Cache中,再次使用時(shí)從Cache中快速調(diào)用,現(xiàn)代CPU通常有2~3個(gè)層次的緩存結(jié)構(gòu),一級(jí)緩存、二級(jí)緩存和三級(jí)緩存,與主存地址的三種映射方法:全相聯(lián)、直接映射、組組映射[2];而Cache 計(jì)時(shí)攻擊又是旁路攻擊中一種重要的方法,是利用一個(gè)與密碼進(jìn)程共享Cache的間諜進(jìn)程監(jiān)測(cè)密碼進(jìn)程對(duì)Cache 的訪問情況從而獲取密鑰,與其他旁路攻擊手段相比,具有無需物理接觸密碼設(shè)備、可通過網(wǎng)絡(luò)遠(yuǎn)程獲取密鑰的優(yōu)點(diǎn),側(cè)通道攻擊初期,最常見的攻擊目標(biāo)是單核CPU內(nèi)的L1緩存[3-4]。2014年,Yarom等[5]首次實(shí)現(xiàn)了跨內(nèi)核/vm的Flush+Reload攻擊,在GnuPG中RSA上實(shí)現(xiàn),恢復(fù)超過90%的密鑰位。而后Flush+Reload攻擊被應(yīng)用于更多的加密庫(kù)和加密算法。例如,Benger等[6]推測(cè)了對(duì)OpenSSL的ECDSA簽名實(shí)現(xiàn)上Flush+Reload攻擊的方法。同年,Irazoqui等[7]提出了更快的攻擊,在云平臺(tái)中,用不到一分鐘的時(shí)間內(nèi)恢復(fù)整個(gè)密鑰位。不久之后,Zhang等[8]在PaaS云中驗(yàn)證了Flush+ Reload攻擊的適用性,并獲得一個(gè)用戶購(gòu)物車的條目數(shù)。在2015年,Irazoqui等[9]展示了從錯(cuò)誤填充cbc的TLS包中恢復(fù)隱私數(shù)據(jù)—幸運(yùn)13攻擊。而后,Gruss等[10]提出了在LLC緩存上應(yīng)用Flush+Reload攻擊檢測(cè)受害者鍵擊的方法,他們的攻擊中往往需要依賴特殊手段中斷加密進(jìn)程才能精確計(jì)時(shí),本文的工作是對(duì)前人工作的拓展,將flush+reload攻擊方法運(yùn)用于AES最后一輪加密,并提出了一種不需要干預(yù)加密進(jìn)程正常執(zhí)行的攻擊方法。
AES加密在OpenSSL0.9.8.b[11]中的實(shí)現(xiàn)方法,實(shí)際就是將AES輪加密轉(zhuǎn)換為查找T表的操作,查找Te0~Te3四個(gè)表,最后一輪加密查找Te4表,解密運(yùn)算需要查找表Td0~Td4,每個(gè)表都是256項(xiàng)的32 bits大小的值構(gòu)成,即用10個(gè)1 kb大小的查找表操作代替了AES的流水線運(yùn)算。在明文異或初始密鑰后,共進(jìn)行了9輪輪加密操作,在源代碼1中展示了OpenSSL0.9.8.b中的輪加密操作,以第一輪為例,每一輪的4個(gè)32 bits的輸出值,由16個(gè)查找表操作完成。

#ifdef FULL_UNROLL
/* round 1:*/
t0 = Te0[s0 >> 24] ^ Te1[(s1 >> 16) & 0xff] ^ Te2[(s2 >> 8) & 0xff] ^ Te3[s3 & 0xff] ^ rk[ 4];
#由明文異或初始密鑰后的狀態(tài)值s0~s3四個(gè)32 bits值作為輸入;
以s0的高8bits為索引值查找Te0表,得到32 bits表項(xiàng)值,同理查找Te1~Te3;
之后4個(gè)表項(xiàng)值與輪密鑰前32 bits值rk[4]進(jìn)行異或運(yùn)算,得到該輪輸出的前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表,與密鑰擴(kuò)展得到的輪密鑰進(jìn)行異或,得到4個(gè)32 bits的表項(xiàng)值,連接成為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四個(gè)32 bits為輸入值,取其高8 bits為索引值查找Te4表得到32 bits的表項(xiàng)值,而后提取表項(xiàng)值的前8 bits;
以t1中間16~23 bit為索引查找Te4表得到32 bits的表項(xiàng)值,提取中間的8 bits值,同理索引t2、t3提取另外兩個(gè)8bits的表項(xiàng)值;
四個(gè)8 bits的表項(xiàng)值連接為32 bits值與輪密鑰r[0]異或運(yùn)算,得到32 bits的密文值,同理s1~s3。

在第9輪加密操作執(zhí)行之后,源代碼2展示了OpenSSL0.9.8.b中實(shí)現(xiàn)的最后一輪加密操作,只執(zhí)行了16次查找Te4表的操作,而實(shí)際Te4表就是將8 bits表項(xiàng)值重復(fù)4次擴(kuò)展成為32 bits長(zhǎng)度的表項(xiàng)值,在源代碼3中展示了OpenSSL 0.9.8b中Te4表的一部分。

最后一輪加密就是將第9輪加密輸出作為本輪的輸入按8 bits大小劃分,以8 bits為索引查找表Te4,得到32 bits大小的表項(xiàng)值,并壓縮到8 bits大小,然后由16個(gè)8 bits的表項(xiàng)值連接成為128 bits的值,異或最后一輪密鑰值得到密文輸出值。
在當(dāng)代操作系統(tǒng)和管理程序中允許不同進(jìn)程/用戶共享相同的物理內(nèi)存的。所有Linux操作系統(tǒng)都實(shí)現(xiàn)了內(nèi)核相同頁(yè)面的合并Kernel Samepage Merging(KSM)機(jī)制,它合并屬于不同進(jìn)程的重復(fù)只讀內(nèi)存頁(yè),KSM內(nèi)核守護(hù)進(jìn)程ksmd掃描用戶內(nèi)存,尋找可能在用戶之間共享的頁(yè)面,為這些頁(yè)面創(chuàng)建簽名。這些簽名保存在重復(fù)數(shù)據(jù)刪除表中。當(dāng)發(fā)現(xiàn)兩個(gè)或多個(gè)具有相同簽名的頁(yè)面時(shí),將對(duì)它們進(jìn)行完全交叉檢查,以確定它們是否相同。為了創(chuàng)建簽名,當(dāng)在候選項(xiàng)中發(fā)現(xiàn)重復(fù)的頁(yè)面簽名并對(duì)內(nèi)容進(jìn)行交叉檢查時(shí),ksmd會(huì)自動(dòng)使用寫時(shí)復(fù)制(COW)標(biāo)記其中一個(gè)重復(fù)的頁(yè)面,并在進(jìn)程/用戶之間共享它,同時(shí)刪除另一個(gè)副本。此外,VMware實(shí)現(xiàn)的透明的頁(yè)面共享Transparent Page Sharing(TPS),這是與KSM類似的機(jī)制,也允許不同的vm共享內(nèi)存。
攻擊的先決條件:
① 由于KSM機(jī)制,間諜進(jìn)程和受害者(加密進(jìn)程)實(shí)現(xiàn)主存或頁(yè)面共享。
② 支持clflush指令,能夠從所有緩存層次結(jié)構(gòu)中驅(qū)逐數(shù)據(jù)。
③ 使用rdtsc指令能夠得到精準(zhǔn)的時(shí)間戳,或者在屏蔽指令mfence/lfence指令下得到的精確CPU周期。
圖1展示了flush+reload的攻擊方法,在step1中的Cache中數(shù)據(jù)塊是在間諜進(jìn)程和受害者間主存或頁(yè)共享的,step2間諜進(jìn)程通過clflush指令將該數(shù)據(jù)塊從緩存中清除,step3中受害者執(zhí)行加密進(jìn)程,會(huì)將加密進(jìn)程所使用的數(shù)據(jù)從共享主存中加載到緩存中,在step4中間諜進(jìn)程重載了該數(shù)據(jù)塊的主存地址,在step3之前和step4之后使用rdtsc指令記錄時(shí)時(shí)間戳,如果這個(gè)數(shù)據(jù)塊被加密進(jìn)程所使用的,那么發(fā)生命中,檢測(cè)為低的重載計(jì)時(shí)值,否則被監(jiān)測(cè)到高的重載計(jì)時(shí)差值,進(jìn)而遍歷所有的共享地址空間,就能夠得到加密時(shí)使用數(shù)據(jù)對(duì)應(yīng)的活動(dòng)地址集,即Te表的地址集(由于輪密鑰生成操作與明文無關(guān),輪密鑰生成運(yùn)算只執(zhí)行一次后就直接使用,而加密查找Te表的操作要持續(xù)執(zhí)行,所以在連續(xù)執(zhí)行加密進(jìn)程時(shí),不用考慮Td0~Td4進(jìn)入到cache中)。
攻擊步驟:
① 在加密進(jìn)程持續(xù)執(zhí)行時(shí),使用flush+reload基本方法判斷共享主存中活動(dòng)的地址集,即加密進(jìn)程數(shù)據(jù)的地址,通過對(duì)源代碼的學(xué)習(xí),可以知道加密進(jìn)程的數(shù)據(jù)就是表Td0~Td4、Te0~Te4、rcon的數(shù)據(jù),rcon是擁有10個(gè)32 bits表項(xiàng)值的小表,加密進(jìn)程不加載表Td0~Td4(Td表用于解密),可以得到Te0~Te4地址;
② 對(duì)Te4表中第一個(gè)cacheline大小的數(shù)據(jù)塊進(jìn)行監(jiān)控,使用flush+reload方法,記錄重載監(jiān)控內(nèi)存塊的和時(shí)間和對(duì)應(yīng)的密文(
③ 篩選計(jì)時(shí)小于閾值即發(fā)生cache命中的密文,與監(jiān)控地址內(nèi)的數(shù)據(jù)Te4,共同恢復(fù)最后一輪的密鑰。

圖1 flush+reload攻擊方法
使用mmap函數(shù)映射共享空間,在共享空間地址中查看加密操作的活動(dòng)地址集。

在算法1中描述了如何獲取Te0~Te4的表地址;其中,rdtsc函數(shù)由mfence/lfence屏障指令和rdtsc計(jì)時(shí)指令構(gòu)成,確保指令順序執(zhí)行。
間諜進(jìn)程對(duì)Te4表中一個(gè)Cacheline長(zhǎng)度的數(shù)據(jù)塊進(jìn)行監(jiān)控,在加密進(jìn)程執(zhí)行前對(duì)其flush操作,在加密進(jìn)程執(zhí)行后測(cè)量reload該Cacheline的用時(shí)t,常用加密庫(kù)中加密用到的數(shù)據(jù)都經(jīng)過優(yōu)化,幾乎都是對(duì)齊的,故不需要求解偏移地址,如果未對(duì)齊也可以選擇監(jiān)控Te4表中占用的第二個(gè)Cacheline數(shù)據(jù)進(jìn)行實(shí)驗(yàn),在實(shí)驗(yàn)中只需要監(jiān)測(cè)Te4表中一個(gè)Cacheline大小的數(shù)據(jù)塊,共16個(gè)32 bits的表項(xiàng)值的數(shù)據(jù)塊,存儲(chǔ)在密文字節(jié)向量(

1:Input:byte *Te4[0], #以*Te4地址為例獲取計(jì)時(shí)
long unsigned int Plaintext[] #明文
2:Output:X= dict(′Cι[16]′:t) #使用鍵值對(duì)dict的數(shù)據(jù)結(jié)構(gòu),采集密文及對(duì)應(yīng)監(jiān)測(cè)地址的重載時(shí)間
3:P[16]= Plaintext.split(16) #將明文按16個(gè)字節(jié)長(zhǎng)度分割
4:flush(*Te4[0]) #將*Te4[0]地址數(shù)據(jù)從cache中驅(qū)逐
5:Cι[16] =Encryption(P[16]) #執(zhí)行加密進(jìn)程
6:st =rdtsc() #記錄時(shí)間戳
7:reload(*Te4[0]) #重新將*Te4[0]地址數(shù)據(jù)載入到cache中
8:ed =rdtsc() #記錄時(shí)間戳
9:t=ed-st #記錄重載時(shí)間
10:returnX=dict(′Cι[16]′:t) #返回密文和其對(duì)監(jiān)控地址的重載計(jì)時(shí)

Cι表示M組密文中的第ι組密文,定義一個(gè)閾值,提取小于時(shí)間閾值的多組密文值Cι′,這些密文在最后一輪加密時(shí)使用了監(jiān)控的Cacheline內(nèi)的數(shù)據(jù),即發(fā)生了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長(zhǎng)度展開,則
rk[0]=(k0,k1,k2,k3);
代入k0到s0中,以32 bits分割s0則
c0= Te4[(t0 >> 24)] & 0xff000000^k0;
在源代碼3中,由于采取重復(fù)值擴(kuò)展,可得
byte(Te4[(t)])=
Te4[(t)] & 0xff000000= Te4[(t)] & 0x00ff0000=
Te4[(t)] & 0x0000ff00=Te4[(t)] & 0x000000ff;
用16個(gè)8 bits長(zhǎng)度的A0…A15代替最后一輪四個(gè)32 bits 輸入值t0~t3,那么t0 >> 24代表最后一輪輸入的第一個(gè)byte值,可表示為A0,則
c0= byte(Te4[(A0)])^k0,那么有
k0= byte(Te4[(A0)])^c0
得到了恢復(fù)最后一輪密鑰值一般公式:
ki=byte(Te4(Aj))^ci,其中ki代表最后一輪第i位byte密鑰值,Aj代表行移位操作產(chǎn)生的偏移。
恢復(fù)密鑰簡(jiǎn)碼如算法3所示,對(duì)于每組發(fā)生命中的密文值,需要在被監(jiān)控Cacheline數(shù)據(jù)塊中的16個(gè)表項(xiàng)值和16個(gè)密鑰位置間進(jìn)行定位,會(huì)產(chǎn)生256個(gè)算數(shù)值。

1:Input:long unsigned intX[],long unsigned int Threshold
2:Output:byteK[]
3:int Count_key[] #定義密鑰值的統(tǒng)計(jì)數(shù)
4:byteY[][16] #定義一個(gè)m行16列的密文數(shù)組
5:Cι[16] = Ciphertext.split(16) #將密文按16字節(jié)長(zhǎng)度分割
6:forι= 0toM do #篩選發(fā)生cache命中的密文
8:Y[m][16] ←Cι[16]
9:end
10:fori=0 to 15 do#循環(huán)恢復(fù)最后一輪16位密鑰字節(jié)
11: int Count_key[16]={0}
12:forι′ = 0tom do #使用m個(gè)命中密文計(jì)算
13:forj= 0to15 do
#每次命中,可能來源于被監(jiān)控cacheline大小的內(nèi)存塊中的16個(gè)字節(jié),每個(gè)內(nèi)存塊中字節(jié)都要計(jì)算
14: Count_key[Y[ι′][i] ^ Te4[0][j]]++
#統(tǒng)計(jì)相同密鑰值的計(jì)數(shù)
15:end
16:end
17:k[i] = Count_key.index(max(Count_key[])) #最大計(jì)數(shù)值對(duì)應(yīng)的索引數(shù)據(jù),就為第i個(gè)密鑰字節(jié)的正確值
18:end
19:returnK9[]={k[0],k[1],…,k[15]}#K9最后一輪的密鑰值

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

圖2 恢復(fù)k1的密鑰byte值

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

圖3 對(duì)i5-4590進(jìn)行50 000次flush-reload計(jì)時(shí)攻擊(區(qū)分命中、未命中)
為了獲得準(zhǔn)確的密鑰值,本實(shí)驗(yàn)取103量級(jí)的共有解作為密鑰值,圖4表示了恢復(fù)正確密鑰與密文數(shù)據(jù)量之間的關(guān)系,在獲得280×103組密文數(shù)據(jù)量后,就能夠完整的恢復(fù)最后一輪密鑰值,而理論需要256×103組密文,是實(shí)際值的91.5%,對(duì)比圖3的97%分辨率差距6.5%左右,證明在加密進(jìn)程不同于單純的數(shù)據(jù)替換,在加密進(jìn)程執(zhí)行時(shí),系統(tǒng)的其他進(jìn)程會(huì)產(chǎn)生額外的噪聲影響,且密文數(shù)據(jù)在280×103之前顯示為逐漸上升的曲線,證明最后一輪16個(gè)密鑰字節(jié)中的部分密鑰字節(jié)先達(dá)到103量級(jí),優(yōu)先被確認(rèn)恢復(fù),不同于理想的所有密鑰字節(jié)的平行恢復(fù),這是因?yàn)楫a(chǎn)生命中密文的相關(guān)密鑰位置是隨機(jī)的,命中密文不是平均使用16個(gè)密鑰字節(jié)的,更加符合實(shí)際情況。

圖4 獲得最后一輪密鑰值對(duì)應(yīng)的密文量
本文工作是從OpenSSL0.9.8.b的AES加密實(shí)現(xiàn)代碼中找到了可實(shí)施Cache攻擊的薄弱點(diǎn),提出了一種通用性強(qiáng)、不依賴偏移地址、不需干預(yù)加密進(jìn)程、不需加密前明文數(shù)據(jù)預(yù)處理的攻擊方法。實(shí)驗(yàn)表明對(duì)比使用Flush+Flush攻擊方法,F(xiàn)lush+Reload攻擊具有更好的分辨率,F(xiàn)F方法的數(shù)據(jù)替換只能區(qū)分93%的計(jì)時(shí),本文提出的攻擊方法能夠分辨97%以上的計(jì)時(shí)值,且Cached與Uncached數(shù)據(jù)計(jì)時(shí)差異明顯。不需要特殊手段中斷加密進(jìn)程,使得此攻擊更加有效、更加適用于真實(shí)的加密環(huán)境。在加密進(jìn)程執(zhí)行時(shí)進(jìn)入緩存的數(shù)據(jù)只有明文和T表的數(shù)據(jù),也可對(duì)明文進(jìn)行標(biāo)記,使其區(qū)別于T表的數(shù)據(jù)作為明文輸入,執(zhí)行更加精準(zhǔn)的攻擊,然而此攻擊依賴于加密算法單次訪問Te4表,如果多次訪問,就要去除更大體量的噪音值,下一步將完善此進(jìn)程,應(yīng)用與其他加密算法庫(kù)實(shí)現(xiàn)的AES查表法。