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

程志煒,陳財森,邱雪歡

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

0 概述

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

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

1 DES算法計時攻擊原理

1.1 DES算法原理

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

圖1 DES算法加密流程

DES算法加密的運算步驟如下:

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

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

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

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

圖2 f函數原理示意圖

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

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

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

Li=Ri-1

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

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

1.2 Cache信息泄露原理

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

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

圖3 Cache命中和失效的區別信息

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

1.3 Flush+Reload計時攻擊分析

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

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

Flush+Reload算法執行步驟如下:

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

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

3)調用密碼程序進程執行。

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

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

2 基于Cache不對齊特征的攻擊實現

針對DES算法的8個S盒,根據S盒的結構,實現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系統調用函數mmap映射DES算法加密共享庫到間諜進程SP中,運行加密算法進程后刷新指定Cache行,因為一次會刷新64 Byte,所以如果S盒在Cache中對齊分布,使用該方法只能確定訪問的S盒所在行。DES算法有8個S盒,只對第一輪加密進行攻擊,使用Flush+Reload方法進行一輪攻擊,能夠確定加密時使用的S盒所在的Cache行。

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

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

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

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

輸出行偏移地址失效次數

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.}

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

3 實驗與結果分析

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

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

圖6 S盒的行位置

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

圖7 Cache失效次數

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

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

4 結束語

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