程志煒,陳財(cái)森,邱雪歡

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

0 概述

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

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

1 DES算法計(jì)時(shí)攻擊原理

1.1 DES算法原理

DES算法是一種分組對(duì)稱加密算法,以64位為分組,密鑰長(zhǎng)度為64位,參與運(yùn)算的密鑰有56位,其余8位屬于密鑰的校驗(yàn)位,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)鍵,也是計(jì)時(shí)攻擊的對(duì)象。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個(gè)S盒,每個(gè)S盒的輸入是6位輸出是4位,整個(gè)S盒的輸出32位值與Li-1進(jìn)行異或得到Ri。

攻擊主要針對(duì)S盒替換,假設(shè)輸入已知明文P經(jīng)過置換后的右32位為Ri,算法第一輪密鑰為K1,E為擴(kuò)展函數(shù)。針對(duì)第一輪加密,通過基于訪問驅(qū)動(dòng)的Cache計(jì)時(shí)攻擊獲得查詢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個(gè)輪密鑰Ki,其中每個(gè)輪密鑰Ki都是48位。

1.2 Cache信息泄露原理

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

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

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

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

1.3 Flush+Reload計(jì)時(shí)攻擊分析

文獻(xiàn)[4]提出基于clflush指令實(shí)現(xiàn)更高效的訪問驅(qū)動(dòng)攻擊,其利用clflush指令把數(shù)據(jù)從Cache中驅(qū)逐到主存中,當(dāng)密碼算法執(zhí)行一小部分指令時(shí),重新檢測(cè)被驅(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命中信息來檢測(cè)前面刷新的目標(biāo)地址是否重新被載入Cache中,如圖4(d)所示。

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

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

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

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

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

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

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

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

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

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

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

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

在DES算法實(shí)際運(yùn)算環(huán)境中,S盒查找表在Cache中不都是對(duì)齊分布,根據(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盒一個(gè)元素的大小。當(dāng)發(fā)生Cache不對(duì)齊時(shí),刷新的地址和S盒查詢的地址在同一Cache行時(shí),間諜進(jìn)程第2次訪問刷新的地址時(shí)會(huì)發(fā)生Cache命中,反之,不在同一Cache行時(shí),就會(huì)發(fā)生Cache失效。對(duì)算法攻擊T次,S盒查找表在Cache中會(huì)發(fā)生多次不對(duì)齊,設(shè)間諜進(jìn)程發(fā)生Cache失效的次數(shù)為n,如果刷新地址不是查詢使用的S盒元素,則有n>0;如果刷新的地址剛好是查詢使用的S盒元素,則有n=0。算法實(shí)現(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ò)展的第一個(gè)密鑰;然后根據(jù)數(shù)學(xué)關(guān)系演算推出DES算法的密鑰;最后使用密鑰對(duì)密文進(jìn)行解密,以驗(yàn)證出密鑰的正確性。

3 實(shí)驗(yàn)與結(jié)果分析

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

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

圖6 S盒的行位置

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

圖7 Cache失效次數(shù)

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

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

4 結(jié)束語(yǔ)

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