基于Flush+Reload的DES算法Cache計時攻擊

程志煒,陳財森,邱雪歡

(陸軍裝甲兵學(xué)院 a.信息工程系; b.科研學(xué)術(shù)處,北京 100072)

0 概述

傳統(tǒng)密碼算法攻擊方法主要是對密碼算法進(jìn)行強(qiáng)力攻擊以及利用算法設(shè)計缺陷來攻擊,分組密碼算法在數(shù)學(xué)上往往是足夠安全的,因此,利用傳統(tǒng)攻擊方法復(fù)雜度非常高,效率極低。20世紀(jì)末,旁路攻擊概念的出現(xiàn)顛覆了傳統(tǒng)密碼界的攻擊觀念,攻擊者利用密碼算法在運(yùn)行時泄露的旁路信息來破解密碼算法。文獻(xiàn)[1]提出訪問驅(qū)動Cache分析,隨后文獻(xiàn)[2]借鑒這種思想,實現(xiàn)了在特定環(huán)境下針對高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard,AES)算法的訪問驅(qū)動Cache計時分析。傳統(tǒng)的Cache分析[3]主要利用間諜進(jìn)程(Spy Process,SP)清空Cache,當(dāng)密碼算法運(yùn)行時會從Cache中將SP訪問過的Cache行數(shù)據(jù)替換出去,然后再次啟動間諜進(jìn)程SP,利用Cache的命中與失效信息來判斷密碼算法訪問過的Cache行信息,通過S盒索引值與Cache行的對應(yīng)關(guān)系確定訪問的S盒元素,這種方法在實現(xiàn)過程中比較困難,并且效率不高。文獻(xiàn)[4]提出了Flush+Reload計時攻擊方法,與傳統(tǒng)的Cache計時分析不同,這種攻擊方法不需要清空整個Cache,只需要刷新特定的Cache行就能實現(xiàn)攻擊。該方法需要映射密碼算法共享執(zhí)行庫到間諜SP進(jìn)程中,SP使用clflush指令刷新指定地址行,運(yùn)行密碼算法后,再次運(yùn)行SP進(jìn)程來判斷刷新過的地址是否被訪問過。與傳統(tǒng)的訪問驅(qū)動Cache計時攻擊相比,Flush+Reload攻擊更容易實現(xiàn),并且效率更高。該攻擊方法能夠確定密碼進(jìn)程使用了哪些具體指令和訪問了哪些具體數(shù)據(jù),基于Flush+Reload方法在AES算法分析上具有良好的效果[5-6]。文獻(xiàn)[7]利用這種攻擊方法探測出運(yùn)行在主機(jī)上的不同加密算法庫,文獻(xiàn)[8]則利用這種攻擊方法推斷出鍵盤的輸入信息。

Flush+Reload方法對對稱密鑰算法的S盒具有良好的攻擊效果,但是因為clflush指令會刷新整個Cache行,而不是Cache行中的某一個部分,所以基于clflush指令的Flush+Reload計時攻擊方法精度只能定位到Cache行,因此,該方法難以確定S盒元素在Cache行中的偏移位。本文以數(shù)據(jù)加密標(biāo)準(zhǔn)(Data Encryption Standard,DES)算法為研究對象,介紹DES算法和Flush+Reload訪問驅(qū)動攻擊方法的實現(xiàn)原理,以及Cache的結(jié)構(gòu)與信息泄露模型,分析Flush+Reload訪問驅(qū)動Cache計時攻擊方法存在的不足。在此基礎(chǔ)上,利用S盒在Cache中會發(fā)生不對齊分布的特征對DES密碼算法進(jìn)行攻擊。

1 DES算法計時攻擊原理

1.1 DES算法原理

DES算法是一種分組對稱加密算法,以64位為分組,密鑰長度為64位,參與運(yùn)算的密鑰有56位,其余8位屬于密鑰的校驗位,DES算法基本構(gòu)造原件主要包括IP置換及逆置換IP-1、f函數(shù)、E擴(kuò)展置換、S盒代替和密鑰編排[9]。算法加密流程主要如圖1所示。

圖1 DES算法加密流程

DES算法加密的運(yùn)算步驟如下:

1)將64位明文進(jìn)行IP置換,輸出為左32位L0和右32位R0。

2)將上一輪右32位Ri-1和該輪密鑰Ki輸入函數(shù)f中,輸出32位用來加密左半部分Li-1,f函數(shù)數(shù)學(xué)表示為:

f:{0,1}32×{0,1}48→{0,1}32

f函數(shù)是DES算法的關(guān)鍵,也是計時攻擊的對象。f函數(shù)包括擴(kuò)展函數(shù)E()、模2加、S盒置換函數(shù)[10],其原理如圖2所示。

圖2 f函數(shù)原理示意圖

在圖2中,Ri-1是32位,經(jīng)過擴(kuò)展函數(shù)E擴(kuò)展,輸出48位中間值E(Ri-1)與密鑰Ki進(jìn)行異或后得到Mi作為S盒的輸入,S盒置換函數(shù)是f函數(shù)的關(guān)鍵,是一種用于抵抗差分密碼分析的非線性映射表。f函數(shù)有8個S盒,每個S盒的輸入是6位輸出是4位,整個S盒的輸出32位值與Li-1進(jìn)行異或得到Ri。

攻擊主要針對S盒替換,假設(shè)輸入已知明文P經(jīng)過置換后的右32位為Ri,算法第一輪密鑰為K1,E為擴(kuò)展函數(shù)。針對第一輪加密,通過基于訪問驅(qū)動的Cache計時攻擊獲得查詢S盒的信息,得到輸入S盒的值M。依據(jù)DES算法的原理有:E(R1)⊕K1=M1。通過已知明文,從數(shù)學(xué)上推導(dǎo)出E(R1)的值[11],結(jié)合獲得的值M1,最終推導(dǎo)出K1的值,最后通過DES算法密鑰擴(kuò)展關(guān)系逆推得到完整的密鑰。

3)在第一輪加密后,進(jìn)行15輪同樣的操作,最后一輪輸出經(jīng)過IP-1置換,IP-1與IP操作完全相反,最后得到密文。上一輪的輸出與下一輪的輸入關(guān)系為:

Li=Ri-1

Ri=Li-1⊕f(Ri-1,Ki)

密鑰Ki是從原始的56位密鑰中得到16個輪密鑰Ki,其中每個輪密鑰Ki都是48位。

1.2 Cache信息泄露原理

Cache是位于CPU和主存之間的靜態(tài)存儲器,存取速度僅次于CPU寄存器,用以解決CPU與主存之間速度不匹配的問題[12]。Cache只保存內(nèi)存中的一些數(shù)據(jù),在Cache中存有的數(shù)據(jù)同樣也存儲在內(nèi)存中,當(dāng)CPU訪問數(shù)據(jù)D時,如果數(shù)據(jù)D存在Cache中,稱為Cache命中,并取出數(shù)據(jù)D送到CPU中;如果D不在Cache中,就會發(fā)生Cache失效,并從內(nèi)存中讀取數(shù)據(jù),同時將數(shù)據(jù)D載入Cache中[13]。由于程序的局部性特點(diǎn),在Cache失效時,會將內(nèi)存中的整塊數(shù)據(jù)調(diào)入Cache中,目的是為了提高命中率,當(dāng)Cache已經(jīng)填滿時,就會使用替換策略,將Cache中的數(shù)據(jù)逐出。

由于Cache的存取速度遠(yuǎn)大于內(nèi)存,因此從Cache中讀取數(shù)據(jù)的時間小于從內(nèi)存中讀取的時間。密碼算法運(yùn)行時泄露的Cache的命中和Cache失效信息,能夠被利用來獲取密碼加密時使用的S盒信息。RDTSC指令[14]能夠用于獲取CPU上的執(zhí)行周期,利用RDTSC指令可區(qū)分Cache命中和失效信息。在計算執(zhí)行周期時,不考慮RDTSC指令帶來的噪聲影響,Cache命中和失效區(qū)別信息如圖3所示。

圖3 Cache命中和失效的區(qū)別信息

使用clflush指令刷新某一Cache行,如果該Cache行之前的存有加密時使用的S盒,則會發(fā)生Cache失效。Cache和主存之間傳遞數(shù)據(jù)是以“塊”為單位的,當(dāng)發(fā)生Cache失效時,從內(nèi)存中讀取數(shù)據(jù)的時間明顯大于從Cache中讀取數(shù)據(jù)的時間,利用Cache泄露的旁路信息,能夠利用獲取查詢的S盒信息。

1.3 Flush+Reload計時攻擊分析

文獻(xiàn)[4]提出基于clflush指令實現(xiàn)更高效的訪問驅(qū)動攻擊,其利用clflush指令把數(shù)據(jù)從Cache中驅(qū)逐到主存中,當(dāng)密碼算法執(zhí)行一小部分指令時,重新檢測被驅(qū)逐的數(shù)據(jù)是否再次加載到Cache中。假設(shè)Cache有8組4路,Flush+Reload攻擊原理如圖4所示。其中:目標(biāo)地址(共享)映射到密碼程序和間諜程序中,如圖4(a)所示;間諜程序刷新共享的目標(biāo)地址,共享目標(biāo)地址從Cache中被逐出,如圖4(b)所示;然后運(yùn)行密碼進(jìn)程,發(fā)生Cache失效,重新從主存中讀取數(shù)據(jù)并載入Cache中,如圖4(c)所示;最后間諜程序通過利用Cache命中信息來檢測前面刷新的目標(biāo)地址是否重新被載入Cache中,如圖4(d)所示。

圖4 Flush+Reload攻擊原理示意圖

Flush+Reload算法執(zhí)行步驟如下:

1)將二進(jìn)制(共享庫)映射入共享地址空間(進(jìn)入Cache中)。

2)從Cache中使用clflush指令刷新一個共享的Cache行。

3)調(diào)用密碼程序進(jìn)程執(zhí)行。

4)偵測第2個步驟中被刷新的Cache行是否被密碼程序載入到Cache。

在第1個步驟中,使用Linux系統(tǒng)調(diào)用函數(shù)mmap來進(jìn)行映射共享庫;在第2個步驟中,使用clflush指令從Cache中驅(qū)逐的數(shù)據(jù)包括共享的LLC(Last-Level Cache)[15];在訪問驅(qū)動攻擊中,Flush+Reload攻擊是一種更加細(xì)粒度的攻擊[2],能夠確定受害程序使用了哪些具體指令和訪問了哪些具體數(shù)據(jù)。

2 基于Cache不對齊特征的攻擊實現(xiàn)

針對DES算法的8個S盒,根據(jù)S盒的結(jié)構(gòu),實現(xiàn)DES算法的S盒,每個元素占4 Byte,加載一個4行16列的S盒需要256 Byte。在Intel i7-4720HQ處理器中,每個Cache行大小為64 Byte,clflush指令刷新大小為64 Byte。如果S盒查找表在Cache中是對齊分布,則一個S盒需要4個Cache行存儲;如果不對齊,則一個S盒占用了5個Cache行,如圖5所示。

圖5 S盒在Cache中的分布特征

使用Linux系統(tǒng)調(diào)用函數(shù)mmap映射DES算法加密共享庫到間諜進(jìn)程SP中,運(yùn)行加密算法進(jìn)程后刷新指定Cache行,因為一次會刷新64 Byte,所以如果S盒在Cache中對齊分布,使用該方法只能確定訪問的S盒所在行。DES算法有8個S盒,只對第一輪加密進(jìn)行攻擊,使用Flush+Reload方法進(jìn)行一輪攻擊,能夠確定加密時使用的S盒所在的Cache行。

DES在算法查找S盒時,使用6個比特位來確定查找的元素,首尾兩位確定查找行,中間4位用來確定列。經(jīng)過一輪攻擊,確定了行位置,能將DES算法的密鑰搜索空間從256降到232。

在DES算法實際運(yùn)算環(huán)境中,S盒查找表在Cache中不都是對齊分布,根據(jù)這種特征,本文提出一種新的方法,用于準(zhǔn)確獲取查詢的S盒元素在Cache行中的準(zhǔn)確偏移位。

在第一輪攻擊后,確認(rèn)查詢的S盒元素所在的Cache行。設(shè)偏移量為0的地址為V[0],將刷新地址右偏移4×iByte的地址為V[i](其中i∈[0,15]且i為整數(shù)),每次偏移量剛好是S盒一個元素的大小。當(dāng)發(fā)生Cache不對齊時,刷新的地址和S盒查詢的地址在同一Cache行時,間諜進(jìn)程第2次訪問刷新的地址時會發(fā)生Cache命中,反之,不在同一Cache行時,就會發(fā)生Cache失效。對算法攻擊T次,S盒查找表在Cache中會發(fā)生多次不對齊,設(shè)間諜進(jìn)程發(fā)生Cache失效的次數(shù)為n,如果刷新地址不是查詢使用的S盒元素,則有n>0;如果刷新的地址剛好是查詢使用的S盒元素,則有n=0。算法實現(xiàn)過程如下所示。

輸入明文p;密鑰k;Cache行首地址V[0]

輸出行偏移地址失效次數(shù)

1.DES(p,k);

2.int *addr=V[0];

3.int count[16];

4.for(int i=0;i<16;i++)

5.{

6.count[i]=0;

7.for(int j=0;j

8.{

9.clflush(addr+i);

10.DES(p,k);

11.int time=rdtsc();

12.maccess(addr);

13.int delta=rdtsc()-time;

14.if(delta>MAX_CACHE_HIT_CYCLES)

15.count[i]++;

16.}

17.printf(“%d ”,count[i]);

18.}

在準(zhǔn)確獲取查詢S盒的所有索引值M1后,首先通過已知明文擴(kuò)展E(R1),根據(jù)K1=E(R1)⊕M1得到密鑰擴(kuò)展的第一個密鑰;然后根據(jù)數(shù)學(xué)關(guān)系演算推出DES算法的密鑰;最后使用密鑰對密文進(jìn)行解密,以驗證出密鑰的正確性。

3 實驗與結(jié)果分析

攻擊實驗在Ubuntu Kylin 16.04的操作系統(tǒng)下進(jìn)行,分析目標(biāo)為在Ubuntu中編寫的DES算法密碼庫des.so,密鑰為隨機(jī)生成密鑰。CPU為4核Intel i7-4720HQ,每個核的L1 Cache大小為32 KB,相聯(lián)度為8路,Cache行大小為64 Byte,clflush指令刷新大小64 Byte。

在實驗環(huán)境中,在使用已知固定明文情況下,首先確定使用的S盒行位置,實驗過程中進(jìn)行了4次攻擊,實際上只需要一次攻擊就能確定所在行,將密鑰的搜索空間降為232,針對第一個S盒的實驗結(jié)果如圖6所示,確定使用的S盒為第4行。

圖6 S盒的行位置

在確認(rèn)S盒行之后,需要利用S盒在Cache中發(fā)生的不對齊現(xiàn)象來確定偏移位,本文使用上述方法進(jìn)行500次攻擊實驗,采集每次攻擊的偏移位地址發(fā)生Cache失效的次數(shù),針對第一個S盒的實驗結(jié)果如圖7所示。

圖7 Cache失效次數(shù)

實驗結(jié)果顯示,偏移位為4的元素發(fā)生Cache失效的次數(shù)最少,其中由于噪聲影響,在偏移位為4的位置也發(fā)生了Cache失效,不排除附近才是真正的偏移位,選取附近候選值的個數(shù)與獲取密鑰成功率的關(guān)系如表1所示。

表1 不同候選值個數(shù)下獲取密鑰的成功率 %

4 結(jié)束語

本文首先介紹了DES算法的實現(xiàn)原理,針對Flush+Reload方法單次攻擊只能確定S盒行信息,無法確定使用S盒的行偏移位問題,提出一種基于S盒在Cache中會發(fā)生不對齊分布的特性來確定具體偏移位的方法,利用軟件實現(xiàn)時S盒泄露的旁路信息獲取密鑰。相比傳統(tǒng)Cache計時攻擊方法,該攻擊方法具有精準(zhǔn)、高效的特點(diǎn),并且不需要采集大量的旁路信息,能夠有效解決使用窮搜等方法來確定密鑰偏移位的問題。然而Flush+Reload方法依靠clflush指令,如果系統(tǒng)限制clflush指令則會造成攻擊方法失效,因此,下一步將研究更具通用性的數(shù)據(jù)驅(qū)逐方法,使攻擊更具有普遍性。