時(shí)間防護(hù)面向分支預(yù)測的脆弱性分析*

楊 珍,唐 明,程金花,張 堯

1.武漢大學(xué) 國家網(wǎng)絡(luò)安全學(xué)院,武漢 430072

2.北京語言大學(xué),北京 100191

1 引言

側(cè)信道攻擊通過密碼算法在物理設(shè)備上的執(zhí)行信息來獲取密鑰,成為當(dāng)前威脅密碼算法安全的重要因素.這些執(zhí)行信息包括運(yùn)行時(shí)間[1]、cache行為[2]、能耗[3]以及電磁[4]等等.其中,時(shí)間側(cè)信道可以遠(yuǎn)程觀測和測量,是當(dāng)前互聯(lián)網(wǎng)環(huán)境下主要的側(cè)信道威脅.

研究者在對稱和非對稱密碼算法的具體實(shí)現(xiàn)中,都發(fā)現(xiàn)了時(shí)間攻擊的可行性,例如RSA[1,5-8]以及AES[9].這些攻擊利用算法實(shí)現(xiàn)本身在設(shè)計(jì)上的缺陷,通過算法運(yùn)行時(shí)間和秘密信息的依賴關(guān)系破解密鑰.

為了保證密碼算法的安全性,許多針對時(shí)間側(cè)信道攻擊的防護(hù)方案被提出.這些方案主要從兩個(gè)方面入手,一是通過對輸入進(jìn)行盲化(blinding),從而抵抗時(shí)間攻擊[1,5];二是通過對分支結(jié)構(gòu)進(jìn)行調(diào)整,以產(chǎn)生恒定時(shí)間(constant-time)的密碼算法實(shí)現(xiàn)[10].

盲化方案主要打破攻擊者時(shí)間測量值與密鑰之間的相關(guān)性,例如在RSA實(shí)現(xiàn)中通過在解密前對每個(gè)密文進(jìn)行隨機(jī)化[5],以抵抗基于密文與運(yùn)行時(shí)間關(guān)聯(lián)性的側(cè)信道攻擊.然而,尚無盲化相關(guān)的側(cè)信道安全的證明,因此無法保證對所有可能的時(shí)間攻擊的有效性.在測量數(shù)據(jù)足夠大的時(shí)候,盲化實(shí)現(xiàn)甚至可能泄漏全部密鑰[11].相比而言,恒定時(shí)間的防護(hù)方案對所有的時(shí)間攻擊均具有適用性.不少研究者提出通過對源程序進(jìn)行轉(zhuǎn)換以產(chǎn)生constant-time的實(shí)現(xiàn),來消除時(shí)間泄漏.Molnar等人使用位掩碼和按位邏輯運(yùn)算符將分支條件直接編碼到運(yùn)算中,以產(chǎn)生針對側(cè)信道道攻擊可證明安全的程序[12].Barthe等人使用事務(wù)機(jī)制進(jìn)行程序轉(zhuǎn)換,以防止面向?qū)ο箜樞虺绦蛑械臅r(shí)間泄漏[13].Agat提出cross-copying的程序轉(zhuǎn)換方案,并且在理論層面上證明了面向時(shí)間泄漏的安全性[14].Mantel等人提出了一種和cross-copying類似的方案,通過unification計(jì)算程序的轉(zhuǎn)換,來生成安全的程序?qū)崿F(xiàn)[15].

為了評估這些安全方案的有效性,Kastner等人基于信息論的指標(biāo)進(jìn)行了分析[16],表明constanttime防護(hù)方案能夠有效抵抗時(shí)間泄漏,但是此研究只針對硬件設(shè)計(jì).Agat在java實(shí)現(xiàn)上評估了不同時(shí)間防護(hù)方案的安全性和性能表現(xiàn)[14],但是沒有考慮到基于處理器優(yōu)化策略的攻擊對安全性的影響.當(dāng)算法實(shí)現(xiàn)運(yùn)行在計(jì)算機(jī)處理器上時(shí),處理器分支預(yù)測機(jī)制為了提高執(zhí)行效率對分支結(jié)構(gòu)進(jìn)行了優(yōu)化,將引入新的時(shí)間攻擊點(diǎn)[17].Bulygin[18]展示了一個(gè)利用分支預(yù)測的RSB(return stack buffer)來攻擊蒙哥馬利模乘的案例.Spectre[19]攻擊與Meltdown[20]攻擊利用了處理器設(shè)計(jì)中的分支預(yù)測和亂序執(zhí)行的特性非法獲取信息.除此之外,Evtyushkin等人[21]利用分支預(yù)測BTB(branch target buffer)沖突,繞過ASLR找到內(nèi)核級和用戶級虛擬地址空間布局.Ac?i?mez等人對使用分支預(yù)測器和SMT(simultaneous multithreading)處理器進(jìn)行了攻擊,獲取處理器上正在運(yùn)算的密鑰[22].Ac?i?mez等人表明即使是添加了防護(hù)的程序,在分支預(yù)測機(jī)制下仍會泄漏敏感信息[23].

因此,在算法層面上被理論證明安全的防護(hù)方案,受處理器架構(gòu)設(shè)計(jì)的影響,在實(shí)際應(yīng)用場景下是否還能抵御時(shí)間攻擊,是需要去度量和評估的問題.本文通過對分支預(yù)測結(jié)構(gòu)進(jìn)行模型化分析,提出了分支預(yù)測機(jī)制下的泄漏檢測和評估方案.通過對不同時(shí)間防護(hù)方案在分支預(yù)測下的有效性進(jìn)行研究,我們刻畫了分支預(yù)測時(shí)間泄漏特征,為復(fù)雜處理器環(huán)境下的時(shí)間防護(hù)方案設(shè)計(jì)提供了參考.本文主要貢獻(xiàn)如下:

(1)本文對時(shí)間防護(hù)方案在分支預(yù)測機(jī)制下的有效性進(jìn)行了理論研究,論證了constant-time的防護(hù)方案在分支預(yù)測機(jī)制下的時(shí)間泄漏問題;

(2)本文給出時(shí)間防護(hù)方案在分支預(yù)測時(shí)間攻擊下的泄漏評估框架.基于本文的評估方法,我們從泄漏評估和攻擊評估兩方面,對包括cross-copying方案、transactional branching方案、unification方案以及conditional assignment方案在內(nèi)的時(shí)間防護(hù)實(shí)現(xiàn)在分支預(yù)測機(jī)制下的有效性進(jìn)行了評估.

(3)本文給出時(shí)間防護(hù)方案分支預(yù)測泄漏的具體度量方法.從泄漏量評估的角度,我們提出了基于Welcht檢驗(yàn)的時(shí)間泄漏量化方法.從泄漏模型刻畫的角度,我們基于分支泄漏的理論模型,提出了基于分支預(yù)測狀態(tài)注入的時(shí)間攻擊方法.

本文的組織結(jié)構(gòu)如下:第2節(jié)對分支預(yù)測原理和時(shí)間攻擊和防護(hù)進(jìn)行簡單介紹;第3節(jié)詳細(xì)分析時(shí)間防護(hù)策略在面對分支預(yù)測機(jī)制可能存在的泄漏問題;第4節(jié)提出了分支預(yù)測時(shí)間泄漏的評估方案,并基于Welcht檢驗(yàn)和分支預(yù)測攻擊提出了泄漏定量評估;第5節(jié)基于開源處理器的實(shí)驗(yàn)平臺對方案有效性進(jìn)行了實(shí)驗(yàn)評估;第6節(jié)對本文的工作進(jìn)行了總結(jié).

2 預(yù)備知識

2.1 RSA的模冪算法

在RSA[24]中,接收者通過計(jì)算M=C d(modN)來獲取密文C對應(yīng)的明文M.其中d是RSA秘密指數(shù),N是公開的模數(shù).對于給定的底數(shù)c和冪指數(shù)e,right-to-left binary算法通過以下的一個(gè)簡單模冪算法(算法1)計(jì)算R=c e(modn),其中ω是e的二進(jìn)制位長度.

算法1 RSA模冪算法(right-to-left binary算法)Input:c,e,n Output:r=c e(mod n)1 r=1;2 for i=0 toω?1 do 4 3 if(bit i of e)is 1 then r=r×c(mod n);5 end 6 r=r2(mod n);7 end

在RSA的模冪算法中,執(zhí)行時(shí)間取決于第3行的條件分支,當(dāng)e的第i位取值為1時(shí),將多進(jìn)行一次模乘操作.當(dāng)攻擊者從時(shí)間側(cè)信道上對算法的執(zhí)行行為進(jìn)行觀測時(shí),分支的選擇泄漏了秘密指數(shù)e的值.為了保證算法的安全性,研究者提出程序轉(zhuǎn)換方案[12-15],通過對程序中的條件分支進(jìn)行修改來彌補(bǔ)不同分支方向時(shí)間上的不平衡性.

2.2 時(shí)間攻擊防護(hù)方案

(1)Cross-copying方案

Cross-copying(CC)方案的主要思想是通過填充關(guān)鍵條件分支,使得條件分支的兩個(gè)方向運(yùn)行時(shí)間相等[14].分支的填充使用模擬程序的偽指令序列,這些模擬語句具有和另外一個(gè)分支相同的運(yùn)行行為,但是不會更改與原始程序相關(guān)的變量.例如,借助特殊的聲明SkipAsn×e,這個(gè)申明模擬了x:=e語句的執(zhí)行過程,具有相同的執(zhí)行時(shí)間,但是不修改x的值.CC方案對關(guān)鍵分支中每一個(gè)執(zhí)行過程在另一個(gè)分支方向上都添加對應(yīng)SkipAsn申明.

(2)Transactional branching方案

Transactional branching(TB)方案將關(guān)鍵條件分支的每個(gè)方向包裝在事務(wù)執(zhí)行鏈的不同位置中,每個(gè)分支方向的事務(wù)執(zhí)行順序均相同[13].這個(gè)方案和cross-copying方案相同的地方在于,都在不同分支方向上添加相同的運(yùn)行行為.但是TB在事務(wù)中通過中止額外添加的程序語句的提交,來避免對原始程序變量的修改.例如,使用BeginT開始一個(gè)新事務(wù),使用AbortT中止事務(wù)來取消BeginT以來所做的所有修改.同時(shí),CommitT提交事務(wù)使BeginT以來所做的所有修改生效.原始語句包裝在BeginT-CommitT中,而添加的額外語句被包裝在BeginT-AbortT中.

(3)Unification方案

Unification(U)方案[15]和CC方案類似,但是U方案可以做到更細(xì)的粒度.與CC方案中直接將不同分支的模擬語句插入末尾不同,unification方案使用單位時(shí)間的偽語句,可以插入分支的任意位置.unification算法用于確定偽語句應(yīng)該插入的位置.

(4)Conditional assignment方案

Conditional assignment(CA)方案使用編碼刪除分支,通過位掩碼和按位邏輯運(yùn)算符將分支條件在賦值中體現(xiàn)[12].這樣分支被一起執(zhí)行,從而消除分支之間的時(shí)間差異.例如,使用Mask(b)函數(shù)編碼分支條件b的布爾值,其中Mask(true)=0,Mask(false)=2l?1,l是原始程序賦值變量的二進(jìn)制位長度.如果一個(gè)條件分支,當(dāng)分支條件b為true時(shí),為x賦值為e t;當(dāng)分支條件b為false時(shí),為x賦值為e f.程序轉(zhuǎn)換后,這一分支通過(Mask(b)&e t)|(～Mask(b)&e f)進(jìn)行計(jì)算.

2.3 分支預(yù)測機(jī)制

在計(jì)算機(jī)架構(gòu)中,分支預(yù)測器[25]是指一塊用來猜測一個(gè)分支結(jié)構(gòu)(例如if-else語句)分支方向的數(shù)字電路,這一猜測在準(zhǔn)確知道分支結(jié)果之前完成.

分支預(yù)測機(jī)制的目的是提高處理器的性能,如果沒有分支預(yù)測,則處理器將必須等到條件跳轉(zhuǎn)指令通過執(zhí)行階段得出分支目標(biāo)后,下一條指令才能進(jìn)入流水線中的提取階段.因此,處理器引入分支預(yù)測機(jī)制,通過嘗試猜測最有可能發(fā)生的跳轉(zhuǎn)來避免這種時(shí)間浪費(fèi).然后,分支預(yù)測器提前獲取最可能的分支并進(jìn)行推測性執(zhí)行.這種分支預(yù)測和推測執(zhí)行來提高效率的方法也帶來了隱患,例如spectre攻擊就利用此來誘導(dǎo)受害者推測性地執(zhí)行在正常情況下不會執(zhí)行的操作,并通過側(cè)信道將受害者的機(jī)密信息泄漏給攻擊者.如果預(yù)測錯(cuò)誤,則將丟棄推測執(zhí)行的指令,并且流水線將回到分支處重新開始取指,從而導(dǎo)致延遲.我們把分支預(yù)測錯(cuò)誤導(dǎo)致的重新取指時(shí)間記為分支誤預(yù)測時(shí)延.

在分支預(yù)測錯(cuò)誤的情況下,分支誤預(yù)測時(shí)延等于從取指階段到執(zhí)行階段的流水線中的階段數(shù),以典型的MIPS五級流水線為例[26],誤預(yù)測時(shí)延大概為兩個(gè)流水階段,如圖1所示(左圖:預(yù)測錯(cuò)誤;右圖:預(yù)測正確).現(xiàn)代微處理器往往具有很長的流水線,更長的流水線帶來更強(qiáng)的分支錯(cuò)誤懲罰,誤預(yù)測時(shí)延甚至長達(dá)10到20個(gè)時(shí)鐘周期.

圖1 五級流水分支預(yù)測正確/錯(cuò)誤的流水線示例Figure 1 Example of five-stage pipeline with correct/wrong branch prediction

2.4 符號說明

本文使用的符號如表1所示.

表1 符號定義Table 1 Symbol definition

3 基于分支預(yù)測機(jī)制的時(shí)間泄漏

3.1 RSA模冪算法的時(shí)間側(cè)信道防護(hù)

在RSA模冪算法的典型實(shí)現(xiàn)中(如算法1),關(guān)鍵條件分支通過時(shí)間側(cè)信道,泄漏了秘密指數(shù)的取值.我們的算法通過C語言進(jìn)行實(shí)現(xiàn),RSA模冪的防護(hù)算法根據(jù)2.2節(jié)中的方案進(jìn)行實(shí)現(xiàn).

(1)CC方案在RSA中的實(shí)現(xiàn)

對于CC方案,我們通過交叉復(fù)制不同分支的語句,使用交叉復(fù)制的模擬語句使兩分支進(jìn)行相同的操作.在我們的C實(shí)現(xiàn)中,我們對SkipAsn×e這樣的聲明,申請一個(gè)臨時(shí)變量x′,通過x′接受模擬語句產(chǎn)生的中間結(jié)果.我們使用x′:=e實(shí)現(xiàn)SkipAsn×e聲明,分配給臨時(shí)變量x′不會影響程序原始字段中的值,并且產(chǎn)生和原始程序相同的計(jì)時(shí)行為.那么算法1的第3-5行轉(zhuǎn)換為:

?if(bit i of e)is 1 then r=r×c(mod n);end else r′=r×c(mod n);//cross-copying end

(2)TB方案在RSA中的實(shí)現(xiàn)

對于TB方案,我們使用x′:=x來實(shí)現(xiàn)一個(gè)BeginT事務(wù),并且置AbortT事務(wù)為空(不做任何修改的提交),同時(shí)使用x′:=x來實(shí)現(xiàn)一個(gè)CommitT事務(wù).分支每個(gè)方向上的事務(wù)鏈均為:BeginT-AbortTBeginT-CommitT.在額外添加的語句中,因?yàn)榘b在BeginT-AbortT中的額外語句不會對修改進(jìn)行提交,對臨時(shí)變量x′的修改不會作用到x上.那么算法1的第3-5行轉(zhuǎn)換為:

if(bit i of e)is 1 then r′=r; //BeginT//AbortT r′=r; //BeginT r′=r×c(mod n);r=r′; //CommitT end else r′=r; //BeginT r′=r×c(mod n);//AbortT r′=r; //BeginT r=r′; //CommitT end

(3)U方案在RSA中的實(shí)現(xiàn)

對于U方案,由于算法1的else分支缺失,所以添加到else分支上的操作等于if分支,可以使用和CC方案中類似的模擬語句實(shí)現(xiàn)相同的功能.模擬語句可以實(shí)現(xiàn)相同的計(jì)時(shí)行為,并且不會對原始程序狀態(tài)產(chǎn)生影響,能對U方案進(jìn)行正確的實(shí)現(xiàn).在其他場景下,U方案可能比CC方案帶來更少的模擬語句.在RSA模冪算法(算法1)的場景下,經(jīng)CC方案和U方案轉(zhuǎn)換后的程序一致.

(4)CA方案在RSA中的實(shí)現(xiàn)

對于CA方案,條件分支轉(zhuǎn)換成邏輯和布爾運(yùn)算(Mask(b)&e t)|(～Mask(b)&e f),在我們的C實(shí)現(xiàn)中,我們將Mask(b)定義為?b.上述條件分支可以表示為:((?b)&e t)|(～(?b)&e f).布爾型的變量在運(yùn)算時(shí)會自動轉(zhuǎn)換為整型.因此,分支功能被正確實(shí)現(xiàn)的同時(shí),避免了分支時(shí)間泄漏,CA轉(zhuǎn)換方案被正確實(shí)現(xiàn).那么,算法1的第3-5行轉(zhuǎn)換為:

r=((?((bit i of e)is 1))&(r×c(mod n)))|(～(?((bit i of e)is 1))&r)

3.2 時(shí)間防護(hù)中的分支預(yù)測泄漏

對于典型的if(A)-else分支,其執(zhí)行流選擇取決于條件A的布爾值.由于分支預(yù)測機(jī)制的存在,當(dāng)程序運(yùn)行到分支節(jié)點(diǎn)時(shí),處理器會根據(jù)預(yù)測路徑,提前執(zhí)行預(yù)測指令,而不等待執(zhí)行階段計(jì)算的A的布爾值的結(jié)果.一旦實(shí)際A的結(jié)果與預(yù)測路徑不匹配,需要進(jìn)行流水線刷洗.處理器扔掉預(yù)取的指令,重新執(zhí)行正確路徑.這樣A的結(jié)果就決定了是否會產(chǎn)生分支預(yù)測錯(cuò)誤導(dǎo)致的時(shí)間浪費(fèi),即誤預(yù)測時(shí)延.即使分支本身不存在對A的泄漏,我們根據(jù)時(shí)延差異仍然可以對A的運(yùn)算結(jié)果進(jìn)行判斷.

圖2 if(A)-else執(zhí)行流,圖中虛線表示預(yù)測的執(zhí)行分支Figure 2 if(A)-else execution flow,dotted line represents predicted branch

對于if(A)-else分支的執(zhí)行過程,我們用符號tdelay來表示單次分支誤預(yù)測時(shí)延,tef_Alg表示程序有效操作相關(guān)的執(zhí)行時(shí)間.那么,對包含ω次分支的程序執(zhí)行時(shí)間可以表示為:

其中,t為目標(biāo)程序的實(shí)際運(yùn)行時(shí)間,brj為第j次分支結(jié)果,即第j次分支預(yù)測成功與否.brj的取值是與分支條件和分支預(yù)測相關(guān)的函數(shù).

其中,pbj是第j次分支的預(yù)測器分支路徑選擇,b j是第j次條件分支路徑選擇,b j與條件判斷結(jié)果相關(guān).由公式(1)、(2),程序的計(jì)時(shí)行為不僅僅與分支預(yù)測行為(pbj)相關(guān),也跟程序中條件分支方向選擇的(b j)相關(guān).

由上文的分析可知,constant-time時(shí)間防護(hù)方案在分支預(yù)測機(jī)制的作用下,仍可能存在時(shí)間泄漏.對于RSA模冪算法的防護(hù)實(shí)現(xiàn)而言,CC方案、TB方案和U方案由于保留了條件分支,密鑰e的值與分支結(jié)果的依賴關(guān)系仍然存在.這些防護(hù)方案雖然填補(bǔ)了算法層面的時(shí)間差異,構(gòu)造了固定時(shí)間的算法實(shí)現(xiàn).但是,由于分支誤預(yù)測時(shí)延的影響,程序的實(shí)際運(yùn)行時(shí)間仍依賴于敏感的分支數(shù)據(jù).由于不同防護(hù)方案對程序進(jìn)行了不同的修改和添加,分支誤預(yù)測帶來的影響可能存在差異.而CA方案消除了分支語句,不再受分支預(yù)測機(jī)制的影響.但是CA方案增加了邏輯和布爾運(yùn)算,并且同時(shí)執(zhí)行所有分支的內(nèi)容,帶來更大的時(shí)間消耗.

4 分支預(yù)測時(shí)間泄漏的評估

在時(shí)間側(cè)信道攻擊中,密碼算法實(shí)現(xiàn)的防護(hù)方案多通過對源程序進(jìn)行轉(zhuǎn)換以產(chǎn)生constant-time的實(shí)現(xiàn),來消除時(shí)間泄漏.然而,防護(hù)方案安全性評估往往只考慮算法層面上的理論安全性,而忽略其處理器運(yùn)行環(huán)境下各種優(yōu)化策略對程序執(zhí)行流的修改.前文的分析表明,處理器中的分支預(yù)測機(jī)制影響條件分支的計(jì)時(shí)行為.特別地,對于constant-time程序而言,這一影響將更為突顯.因此,本文將重點(diǎn)討論面向分支預(yù)測機(jī)制下的受防護(hù)密碼算法實(shí)現(xiàn)的時(shí)間側(cè)信道安全性.

在分支預(yù)測時(shí)間攻擊中,攻擊者具有如下兩個(gè)合理的能力假設(shè):攻擊者可以控制受害者設(shè)備的分支預(yù)測部件的狀態(tài).在同步多線程系統(tǒng)中,攻擊者程序可以與受害者程序同步運(yùn)行,所以此假設(shè)是合理的.攻擊者可以控制目標(biāo)程序的輸入并獲取受害者程序的計(jì)時(shí)信息.當(dāng)攻擊者可以控制或遠(yuǎn)程控制受害者的計(jì)算機(jī)時(shí),此假設(shè)是完全可以實(shí)現(xiàn)的.基于這些假設(shè),攻擊者隨機(jī)構(gòu)造受害者程序的密文輸入P={p0,p1,···,p n?1}.受害者的程序運(yùn)行在帶有分支預(yù)測機(jī)制的平臺下,整個(gè)加密過程中的時(shí)間側(cè)信道測量值用T={t0,t1,···,t n?1}進(jìn)行表示.程序的計(jì)時(shí)行為除了依賴于程序的操作本身以外,考慮到測量噪聲的影響,我們假設(shè)測量噪聲滿足正態(tài)分布.那么T=TAlg+Tnoise,其中TAlg是程序的運(yùn)行時(shí)間,Tnoise是噪聲對測量時(shí)間的影響.

為了分析分支預(yù)測機(jī)制對時(shí)間側(cè)信道防護(hù)方案的影響,泄漏評估框架對分支預(yù)測時(shí)間特征進(jìn)行刻畫,評估分支預(yù)測機(jī)制對防護(hù)方案的有效性的影響.泄漏評估主要從兩個(gè)方面入手,一是量化分支預(yù)測時(shí)間泄漏,即有多少泄漏是通過分支預(yù)測引起的,為分支預(yù)測時(shí)間攻擊提供側(cè)信道泄漏量度量;二是對泄漏模型的刻畫評估,即找到時(shí)間泄漏和運(yùn)算數(shù)據(jù)或運(yùn)算操作之間的關(guān)聯(lián)性,通過泄漏模型的刻畫獲取密鑰的相關(guān)猜測,為分支預(yù)測時(shí)間攻擊提供側(cè)信道泄漏模型度量.

圖3 時(shí)間側(cè)信道面向分支預(yù)測泄漏評估框架Figure 3 Timing leakage assessment framework for branch prediction

4.1 Welch t檢驗(yàn)

我們使用統(tǒng)計(jì)檢驗(yàn)對密碼算法實(shí)現(xiàn)在分支預(yù)測下的時(shí)間泄漏進(jìn)行檢測和量化.在我們的攻擊場景下,目標(biāo)算法為添加時(shí)間防護(hù)的密碼算法,在算法層面不存在時(shí)間泄漏.我們對分支預(yù)測狀態(tài)進(jìn)行控制,測量分支選擇數(shù)據(jù)e的不同取值下的時(shí)間樣本.

統(tǒng)計(jì)檢驗(yàn)提供一個(gè)置信度來接受(或拒絕)原假設(shè).在考慮兩組樣本?0、?1的情況下,我們設(shè)原假設(shè)為兩組樣本均取自同一總體,即兩組不可區(qū)分.在兩組樣本的樣本數(shù)和方差均不相等時(shí),可以使用Welcht檢驗(yàn).如果檢驗(yàn)統(tǒng)計(jì)量遵循Student’st分布,Welcht檢驗(yàn)通過比較兩個(gè)總體的均值來接受(或拒絕)原假設(shè).樣本?0(?1)的樣本量、樣本方差和樣本均值分別為:n0(n1)、μ0(μ1)和s02(s12).原假設(shè)和備擇假設(shè)分別為:

H0:μ0=μ1,H1:μ0?=μ1

則Welcht檢驗(yàn)的統(tǒng)計(jì)量t以及自由度v為:

基于雙側(cè)Welcht檢驗(yàn),通過Student’st概率密度函數(shù)估算接受零假設(shè)的置信度為:

其中,Γ(.)表示伽瑪函數(shù).我們根據(jù)更小的p值(或者更大的t值)來拒絕原假設(shè),即這兩組樣本來自不同的總體,存在明顯的可區(qū)分度.值得注意的是,在利用Welcht檢驗(yàn)進(jìn)行泄漏檢測時(shí),通常會忽略自由度.

泄漏檢測的目的是衡量有多少有用信息可用作實(shí)施成功的側(cè)信道攻擊,因此為了進(jìn)行準(zhǔn)確的泄漏評估,我們貼合泄漏特征來構(gòu)造檢測集合.在分支預(yù)測的場景下,分支數(shù)據(jù)與運(yùn)行時(shí)間存在相關(guān)關(guān)系,程序可能通過時(shí)間側(cè)信道泄漏敏感的分支選擇數(shù)據(jù).在本文的目標(biāo)算法下,分支選擇與RSA密鑰值相關(guān).本文構(gòu)造以下兩組數(shù)據(jù)來進(jìn)行泄漏的檢測:進(jìn)行固定分支選擇的程序運(yùn)行時(shí)間和進(jìn)行隨機(jī)分支選擇的程序運(yùn)行時(shí)間.

基于TVLA[27,28]的檢測流程,本文對分支預(yù)測的時(shí)間泄漏檢測分為以下四個(gè)步驟,分別是數(shù)據(jù)獲取階段、數(shù)據(jù)處理階段、構(gòu)造檢驗(yàn)數(shù)據(jù)集合階段以及檢驗(yàn)和分析階段.在數(shù)據(jù)獲取階段,我們在分支預(yù)測狀態(tài)的控制下,對不同密鑰下的運(yùn)行時(shí)間數(shù)據(jù)進(jìn)行采集.在數(shù)據(jù)處理階段,目標(biāo)程序受處理器其他進(jìn)程的影響,可能導(dǎo)致其運(yùn)行時(shí)間比正常運(yùn)行時(shí)間大很多,我們對這些異常數(shù)據(jù)進(jìn)行剔除.在構(gòu)造檢驗(yàn)數(shù)據(jù)集合階段,我們以密鑰值對數(shù)據(jù)集合進(jìn)行劃分,選取一個(gè)固定密鑰,其對應(yīng)的所有時(shí)間數(shù)據(jù)形成數(shù)據(jù)集合?0,其他隨機(jī)密鑰對應(yīng)的數(shù)據(jù)形成數(shù)據(jù)集合?1.在檢驗(yàn)和分析階段,我們對獲取到的兩組數(shù)據(jù)集合,應(yīng)用Welcht檢驗(yàn)來評估目標(biāo)算法運(yùn)行過程中的信息泄漏.我們使用統(tǒng)計(jì)量t=4.5作為檢測閾值,當(dāng)統(tǒng)計(jì)量t大于4.5時(shí),我們認(rèn)為存在明顯泄漏.

4.2 基于分支預(yù)測狀態(tài)注入的時(shí)間側(cè)信道攻擊

反之,如果猜測e k是錯(cuò)誤的,有:

圖4 錯(cuò)誤猜測的時(shí)延擴(kuò)散效應(yīng)Figure 4 Delay spreading effect of incorrect guessing

算法2基于分支預(yù)測狀態(tài)注入的時(shí)間側(cè)信道攻擊Input:o Output:e 1 for k=0 toω?1 do 3 o branch_prediction=o j;2 for j=0 to m?1 do j ,t ek=0j ;5 end 6 ΔT ek=0=T?T ek=0;7 ΔT ek=1=T?T ek=1;8 if Var(ΔT ek=0)>Var(ΔT ek=1)then 4 Get t j,t ek=1 e k=1;10 end 11 if Var(ΔT ek=0)

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)平臺

實(shí)驗(yàn)硬件平臺為Xilinx ZedBoard[29],搭載基于RISCV-Rocket[30]開源處理器的實(shí)現(xiàn),其基于開源的指令集架構(gòu)RISC-V[31],采用五級流水結(jié)構(gòu),是單發(fā)射順序執(zhí)行的64位處理器.我們的防護(hù)原始算法為RSA模冪算法(算法1)的C實(shí)現(xiàn).其中,密鑰位長度為128位.我們使用Cycle計(jì)數(shù)器來測量程序的執(zhí)行時(shí)間.

5.2 實(shí)驗(yàn)結(jié)果

我們根據(jù)前文的分析,對RSA模冪算法的防護(hù)方案面向分支預(yù)測時(shí)間攻擊的安全性進(jìn)行實(shí)驗(yàn)評估.為了更好的評估防護(hù)方案的有效性,應(yīng)綜合考慮性能和安全性,因此我們首先對不同防護(hù)方案對原始算法的性能影響進(jìn)行分析.基于分支預(yù)測的泄漏評估框架,我們對不同防護(hù)方案實(shí)現(xiàn)的信息泄漏量進(jìn)行分析,并在分支預(yù)測攻擊下對方案的有效性進(jìn)行實(shí)驗(yàn)評估.

(1)防護(hù)方案的時(shí)間代價(jià)分析

基于RSA模冪算法實(shí)現(xiàn),我們對本文中constant-time時(shí)間防護(hù)方案的計(jì)算時(shí)間開銷進(jìn)行了統(tǒng)計(jì).如表2所示,所有的防護(hù)方案均帶來性能的下降,增加了運(yùn)行時(shí)間開銷.其中,CA方案的防護(hù)代價(jià)最高,超過了原始設(shè)計(jì)時(shí)間消耗的1.6倍.CC方案和U方案在RSA模冪算法的防護(hù)下具有相同的時(shí)間代價(jià),均帶來額外17%的時(shí)間消耗.TB方案的時(shí)間消耗介于CC方案和CA方案之間,相比于原始設(shè)計(jì)約造成1.5倍的性能損耗.

表2 不同算法實(shí)現(xiàn)的性能影響Table 2 Performance impact of different algorithms

(2)防護(hù)方案在分支預(yù)測下的信息泄漏

我們使用Welcht檢驗(yàn)對不同RSA防護(hù)在分支預(yù)測下的泄漏量進(jìn)行評估.在本文的目標(biāo)對象下,我們考慮分支結(jié)構(gòu)的不同條件取值對運(yùn)行時(shí)間的影響.如圖5所示,CA防護(hù)的實(shí)現(xiàn)在不考慮分支預(yù)測的影響時(shí),仍存在時(shí)間泄漏.這是由布爾和邏輯計(jì)算的運(yùn)行優(yōu)化引起的.從3.2節(jié)的理論分析來講,CA方案避免了分支預(yù)測引起的時(shí)間泄漏.但是,由于其算法上仍存在的泄漏,在此基礎(chǔ)上進(jìn)行分支預(yù)測下的泄漏分析是沒有必要的.相比而言,CC方案、TB方案以及U方案的RSA防護(hù)實(shí)現(xiàn)在不受分支預(yù)測機(jī)制影響的情況下,均不存在時(shí)間泄漏.而在分支預(yù)測的作用下,此三種方案均出現(xiàn)不同程度的時(shí)間泄漏.其中CC方案和U方案的泄漏量遠(yuǎn)高于TB方案,約為其的3倍.

圖5 不同防護(hù)方案的時(shí)間泄漏量Figure 5 Timing leakage of different defense schemes

我們對CC方案、TB方案以及U方案受分支預(yù)測機(jī)制的影響進(jìn)行實(shí)驗(yàn)分析.圖6展示了密鑰e的不同取值下,constant-time程序的運(yùn)行時(shí)間差異.

圖6 分支預(yù)測機(jī)制下的constant-time程序運(yùn)行時(shí)間差異Figure 6 Runtime difference of constant-time program under branch prediction

在分支預(yù)測機(jī)制下,128位密鑰e的每一位都決定了一次分支選擇過程.當(dāng)e的不同位之間的分支選擇具有明顯傾向性時(shí),屬于可預(yù)測的分支數(shù)據(jù).對于可預(yù)測分支數(shù)據(jù)和隨機(jī)分支數(shù)據(jù),我們各進(jìn)行連續(xù)的1000次時(shí)間數(shù)據(jù)采集.從圖中可以看出,可預(yù)測分支數(shù)據(jù)帶來的分支誤預(yù)測更少,對應(yīng)的程序運(yùn)行時(shí)間更短.在多次的運(yùn)行過程中,分支預(yù)測部件根據(jù)分支選擇結(jié)果進(jìn)行預(yù)測狀態(tài)的調(diào)整,不同防護(hù)方案均出現(xiàn)兩個(gè)峰值.但是,可預(yù)測分支數(shù)據(jù)的運(yùn)行時(shí)間在不同預(yù)測狀態(tài)下均遠(yuǎn)小于隨機(jī)分支數(shù)據(jù)的運(yùn)行時(shí)間,程序執(zhí)行時(shí)間明顯依賴于敏感的分支數(shù)據(jù).因此,時(shí)間防護(hù)方案在分支預(yù)測機(jī)制的作用下,仍然存在明顯的時(shí)間泄漏.

(3)防護(hù)方案在分支預(yù)測攻擊下的脆弱性

根據(jù)上節(jié)的泄漏量分析,我們基于分支預(yù)測時(shí)間攻擊,對不同防護(hù)方案的有效性進(jìn)行分析.攻擊結(jié)果如圖7所示,由于CA方案本身的時(shí)間泄漏,我們不對其在分支預(yù)測下的泄漏進(jìn)行分析.在N=5000的數(shù)據(jù)量下,攻擊者均能對其他三種不同防護(hù)方案的前20位密鑰進(jìn)行正確的猜測.和泄漏量的實(shí)驗(yàn)結(jié)果對比,U方案和CC方案相比于TB方案有更明顯的正確猜測區(qū)分.與TB方案在分支預(yù)測下的泄漏量更小相對應(yīng)地,TB方案的正確密鑰猜測和錯(cuò)誤密鑰猜測的方差統(tǒng)計(jì)值之間的距離也更小,約為U方案和CC方案的0.5倍.

圖7 正確猜測與錯(cuò)誤猜測的差距Figure 7 Distance between correct guess and wrong guess

我們對不同防護(hù)方案的性能影響、泄漏量以及面向分支預(yù)測攻擊的有效性進(jìn)行綜合分析.不同防護(hù)方案均存在不同程度的時(shí)間泄漏,其中CA方案甚至面臨算法實(shí)現(xiàn)引入的時(shí)間泄漏.同時(shí),即使是本身不存在泄漏的CC方案、TB方案和U方案,在分支預(yù)測機(jī)制的影響下,均出現(xiàn)了新的時(shí)間泄漏.TB方案實(shí)現(xiàn)相比于其它兩個(gè)方案有更高的性能損耗,但是在分支預(yù)測機(jī)制下的時(shí)間泄漏量更少,對于分支預(yù)測攻擊有更好的抵御效果.

6 總結(jié)

本文討論研究了在處理器的分支預(yù)測機(jī)制作用下,constant-time時(shí)間防護(hù)方案的有效性.基于RSA模冪算法的防護(hù)實(shí)現(xiàn),本文對包括cross-copying方案、transactional branching方案、unification方案以及conditional assignment方案在內(nèi)的四種防護(hù)實(shí)現(xiàn)進(jìn)行了分析.我們提出了時(shí)間防護(hù)方案在分支預(yù)測機(jī)制下的評估框架,并基于Welcht檢驗(yàn)對時(shí)間泄漏進(jìn)行了度量.基于本文提出的基于分支預(yù)測狀態(tài)注入時(shí)間攻擊,我們評估了不同防護(hù)方案的抗分支預(yù)測攻擊能力.通過實(shí)驗(yàn)比較,四種防護(hù)方案均存在不同程序的時(shí)間泄漏.CA方案雖然替換掉了分支,但也帶來相比于原始程序1.65倍的時(shí)間代價(jià),而且運(yùn)算本身的優(yōu)化使其在算法層面仍存在時(shí)間泄漏.而CC方案、U方案以及TB方案雖然不存在算法層面的時(shí)間泄漏,但是在分支預(yù)測機(jī)制的影響下,仍然存在實(shí)際運(yùn)行過程的泄漏.其中,CC方案和U方案以1.17倍的時(shí)間代價(jià)略優(yōu)于TB方案的1.56倍.但CC方案和U方案的分支預(yù)測泄漏量約為TB方案的3倍,且在抗分支預(yù)測攻擊上的表現(xiàn)更差.本文的研究結(jié)果表明算法設(shè)計(jì)者應(yīng)從多層次上考慮防護(hù)方案的安全性,為不同算法在分支預(yù)測機(jī)制下的泄漏評估提供了參考.