時間防護面向分支預測的脆弱性分析*

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

1.武漢大學 國家網絡安全學院,武漢 430072

2.北京語言大學,北京 100191

1 引言

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

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

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

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

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

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

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

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

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

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

2 預備知識

2.1 RSA的模冪算法

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

算法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í)行時間取決于第3行的條件分支,當e的第i位取值為1時,將多進行一次模乘操作.當攻擊者從時間側信道上對算法的執(zhí)行行為進行觀測時,分支的選擇泄漏了秘密指數e的值.為了保證算法的安全性,研究者提出程序轉換方案[12-15],通過對程序中的條件分支進行修改來彌補不同分支方向時間上的不平衡性.

2.2 時間攻擊防護方案

(1)Cross-copying方案

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

(2)Transactional branching方案

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

(3)Unification方案

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

(4)Conditional assignment方案

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

2.3 分支預測機制

在計算機架構中,分支預測器[25]是指一塊用來猜測一個分支結構(例如if-else語句)分支方向的數字電路,這一猜測在準確知道分支結果之前完成.

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

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

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

2.4 符號說明

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

表1 符號定義Table 1 Symbol definition

3 基于分支預測機制的時間泄漏

3.1 RSA模冪算法的時間側信道防護

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

(1)CC方案在RSA中的實現

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

?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中的實現

對于TB方案,我們使用x′:=x來實現一個BeginT事務,并且置AbortT事務為空(不做任何修改的提交),同時使用x′:=x來實現一個CommitT事務.分支每個方向上的事務鏈均為:BeginT-AbortTBeginT-CommitT.在額外添加的語句中,因為包裝在BeginT-AbortT中的額外語句不會對修改進行提交,對臨時變量x′的修改不會作用到x上.那么算法1的第3-5行轉換為:

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中的實現

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

(4)CA方案在RSA中的實現

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

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

3.2 時間防護中的分支預測泄漏

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

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

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

其中,t為目標程序的實際運行時間,brj為第j次分支結果,即第j次分支預測成功與否.brj的取值是與分支條件和分支預測相關的函數.

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

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

4 分支預測時間泄漏的評估

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

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

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

圖3 時間側信道面向分支預測泄漏評估框架Figure 3 Timing leakage assessment framework for branch prediction

4.1 Welch t檢驗

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

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

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

則Welcht檢驗的統計量t以及自由度v為:

基于雙側Welcht檢驗,通過Student’st概率密度函數估算接受零假設的置信度為:

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

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

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

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

反之,如果猜測e k是錯誤的,有:

圖4 錯誤猜測的時延擴散效應Figure 4 Delay spreading effect of incorrect guessing

算法2基于分支預測狀態(tài)注入的時間側信道攻擊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 實驗

5.1 實驗平臺

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

5.2 實驗結果

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

(1)防護方案的時間代價分析

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

表2 不同算法實現的性能影響Table 2 Performance impact of different algorithms

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

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

圖5 不同防護方案的時間泄漏量Figure 5 Timing leakage of different defense schemes

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

圖6 分支預測機制下的constant-time程序運行時間差異Figure 6 Runtime difference of constant-time program under branch prediction

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

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

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

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

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

6 總結

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