rsacache計(jì)攻擊原理及實(shí)現(xiàn)

rsacache計(jì)攻擊原理及實(shí)現(xiàn)

1基于cache戰(zhàn)時(shí)攻擊的分析在密碼分析領(lǐng)域，文獻(xiàn)提出了一種新的邊路分析，即所謂的微結(jié)構(gòu)分析。該技術(shù)理論上利用現(xiàn)代高性能超線程CPU體系結(jié)構(gòu)中的某些部件內(nèi)部的功能,可以潛在地發(fā)現(xiàn)密碼系統(tǒng)執(zhí)行過(guò)程中幾乎所有的數(shù)據(jù)或指令訪問順序,進(jìn)而根據(jù)訪問的數(shù)據(jù)或指令推斷出密鑰。數(shù)據(jù)Cache、指令Cache和分支預(yù)測(cè)分析是微架構(gòu)分析的3種類型。Cache計(jì)時(shí)攻擊是利用訪問數(shù)據(jù)Cache命中和失效特征所表現(xiàn)出來(lái)的執(zhí)行時(shí)間差異,進(jìn)而分析密鑰的一種計(jì)時(shí)攻擊方式。這種攻擊利用CPU內(nèi)部組件,即使采用了沙盒和虛擬化保護(hù)措施,由于內(nèi)部組件在這些安全機(jī)制之下,也無(wú)法避免Cache計(jì)時(shí)攻擊。文獻(xiàn)提出通過(guò)構(gòu)建隱通道監(jiān)控密碼進(jìn)程,測(cè)量和記錄執(zhí)行的時(shí)間差異,推斷密碼進(jìn)程執(zhí)行過(guò)程中訪問的數(shù)據(jù)序列,進(jìn)一步分析從而推出密鑰。文獻(xiàn)所做的攻擊平均可以正確分析出512bit密鑰中的310bit。在Cache計(jì)時(shí)攻擊方面,針對(duì)AES、Camellia等密碼算法都已經(jīng)取得成功,由于RSA為公鑰密碼,不同于對(duì)稱密碼算法的實(shí)現(xiàn),實(shí)施起來(lái)更為困難。本文在文獻(xiàn)的攻擊理論基礎(chǔ)上,基于Cache命中和失效原理,設(shè)計(jì)一種新的針對(duì)滑動(dòng)窗口算法的Cache計(jì)時(shí)攻擊方法,提高攻擊的可行性。以O(shè)penSSL0.9.8a實(shí)現(xiàn)的RSA密碼算法簽名過(guò)程為攻擊對(duì)象,根據(jù)Cache在執(zhí)行過(guò)程中遺留的痕跡,測(cè)量和記錄執(zhí)行時(shí)間,推斷密碼進(jìn)程在執(zhí)行過(guò)程中訪問過(guò)的初始化表數(shù)據(jù),通過(guò)對(duì)這些數(shù)據(jù)的分析推斷出密鑰,這種攻擊方式具有抗干擾能力強(qiáng)、執(zhí)行效率高等特點(diǎn)。2ria公鑰密碼算法2.1rsa的密鑰計(jì)算RSA是一個(gè)基于模冪運(yùn)算的公鑰密碼算法。加密過(guò)程為C=MemodN,解密過(guò)程為M=CdmodN,其中,M表示明文;C表示密文;N為模數(shù);e為加密指數(shù);d為解密指數(shù)。RSA產(chǎn)生密鑰的過(guò)程如下:首先產(chǎn)生2個(gè)大素?cái)?shù)(一般512bit以上)p和q,選擇公鑰e(通常是3、17或65537)并且滿足gcd(e,(p-1)(q-1))=1;令N=p×q,通過(guò)d=e-1mod(p-1)(q-1)計(jì)算解密指數(shù)d。RSA加解密的核心運(yùn)算是模冪運(yùn)算,常用的模冪算法是平方-乘法算法。2.2窗口滑動(dòng)的持續(xù)過(guò)程OpenSSL是目前使用較為廣泛的開源SSL庫(kù)。為提高RSA執(zhí)行效率,OpenSSL采用了中國(guó)剩余定理、蒙哥馬利乘法及滑動(dòng)窗口算法來(lái)完成求冪操作?；瑒?dòng)窗口算法采用一個(gè)固定大小為k的窗口,在二進(jìn)制模冪指數(shù)d上從左到右(也可以從右到左)滑動(dòng)?；瑒?dòng)過(guò)程直到窗口最右邊第一次碰到“1”結(jié)束,然后再創(chuàng)建一個(gè)窗口從上次結(jié)束的地方開始另一次滑動(dòng),這樣的過(guò)程一直持續(xù)到d的二進(jìn)制表達(dá)中沒有“1”為止。滑動(dòng)窗口算法需要反復(fù)計(jì)算一張乘數(shù)表,對(duì)于窗口大小為k的需要計(jì)算2k-1次。因此,為平衡重復(fù)計(jì)算時(shí)消耗時(shí)間和實(shí)際求冪消耗時(shí)間,存在一個(gè)最優(yōu)的窗口大小。對(duì)于1024bit的模數(shù)OpenSSL采用的窗口大小為6,因此,每次滑動(dòng)d的位數(shù)不超過(guò)6個(gè)?；瑒?dòng)窗口算法如算法1所描述,其中k表示窗口的大小。算法滑動(dòng)窗口算法輸入m,d=(dtdt-1…d1d0)2,其中,dt=1,整數(shù)k≥1輸出md當(dāng)窗口大小k=1時(shí),滑動(dòng)窗口算法等同于平方-乘法算法。因此,滑動(dòng)窗口算法可看成是“平方-乘法”算法的一種改進(jìn),其主要思想是通過(guò)預(yù)計(jì)算來(lái)提高運(yùn)算速度。本文以滑動(dòng)窗口算法中的初始化乘法表為突破點(diǎn),闡述針對(duì)RSA算法的Cache計(jì)時(shí)攻擊。3基于cache滑動(dòng)窗口算法的rsa檢測(cè)Cache是位于主存和中央處理器之間的一個(gè)小的緩存器,為處理器提供一種快速方便地訪問最頻繁訪問的數(shù)據(jù)和指令的方式。當(dāng)處理器需要從主存讀取數(shù)據(jù)時(shí),它首先檢測(cè)這些數(shù)據(jù)是否存在Cache中,如果存在(Cache命中),處理器立即讀取這些數(shù)據(jù),而不需要訪問主存;否則,處理器必須從主存中讀取數(shù)據(jù)(Cache失效),同時(shí)將數(shù)據(jù)的副本存儲(chǔ)在Cache中。每次Cache失效都會(huì)產(chǎn)生對(duì)更高一級(jí)存儲(chǔ)器的訪問,這將導(dǎo)致額外的存取延遲時(shí)間,本文只考慮L1Cache。Cache計(jì)時(shí)攻擊就是基于上述原理,即Cache失效增加了訪問數(shù)據(jù)的時(shí)間?，F(xiàn)代CPU多使用高速共享存儲(chǔ)器技術(shù)和同步多線程技術(shù),由于進(jìn)程切換時(shí)并沒有清空Cache中的數(shù)據(jù),其他進(jìn)程就可以對(duì)Cache中共享數(shù)據(jù)進(jìn)行訪問。在密碼進(jìn)程的執(zhí)行過(guò)程中,由于對(duì)Cache的共享,會(huì)留下一些痕跡或中間數(shù)據(jù)。攻擊者只要通過(guò)對(duì)Cache中私有數(shù)據(jù)進(jìn)行訪問,找到密碼進(jìn)程執(zhí)行中與密鑰相關(guān)特定Cache集合,進(jìn)而根據(jù)Cache失效或命中的組集合與密鑰的索引關(guān)系,可推斷出密鑰值。本文針對(duì)采用滑動(dòng)窗口算法實(shí)現(xiàn)的RSA建立了Cache計(jì)時(shí)攻擊模型,如圖1所示。該模型首先構(gòu)造一個(gè)與Cache(L1Cache)空間大小相等的數(shù)組,用來(lái)進(jìn)行清空Cache操作(見圖1(b));接著執(zhí)行一次RSA簽名操作,采用滑動(dòng)窗口算法的RSA簽名操作在每次窗口滑動(dòng)過(guò)程中會(huì)訪問初始化表的元素,訪問過(guò)的元素將會(huì)被加載到Cache中(見圖1(c));然后在每次窗口滑動(dòng)結(jié)束后,利用計(jì)時(shí)手段采集二次訪問初始化表導(dǎo)致Cache命中和失效的時(shí)間信息,由于對(duì)那些已經(jīng)被加載到Cache中的數(shù)據(jù)進(jìn)行訪問會(huì)發(fā)生Cache命中(見圖1(d)),而未被加載到Cache中的數(shù)據(jù)將會(huì)發(fā)生Cache失效,通過(guò)Cache命中與失效表現(xiàn)出來(lái)的時(shí)間差異推斷訪問過(guò)的初始化表中元素的索引值,而索引值與密鑰信息密切相關(guān),通過(guò)分析可以推斷出密鑰。4滑動(dòng)窗口算法的隱私時(shí)間攻擊4.1基于cache中性的滑動(dòng)窗口算法OpenSSL在采用滑動(dòng)窗口算法的RSA實(shí)現(xiàn)過(guò)程中,密鑰被分離為序列片段,冪運(yùn)算也是由一序列的平方乘法運(yùn)算組成。同時(shí),對(duì)于每次乘法運(yùn)算,其中一個(gè)乘數(shù)是從先前已經(jīng)計(jì)算的存儲(chǔ)在表中的數(shù)據(jù)獲得,在查找表中數(shù)據(jù)時(shí),密鑰的一個(gè)二進(jìn)制片段對(duì)應(yīng)的十進(jìn)制值被用來(lái)作為索引檢索表中的元素。由于表中的數(shù)據(jù)是存儲(chǔ)在內(nèi)存中的,當(dāng)訪問表中的元素時(shí)需要將其加載到Cache中,通過(guò)精確計(jì)時(shí)二次訪問表中所有元素,已經(jīng)加載到Cache中的表元素將會(huì)產(chǎn)生Cache命中,而其他元素導(dǎo)致Cache失效,利用Cache命中和失效的時(shí)間差異,攻擊者能夠推斷表中的哪一個(gè)元素被訪問過(guò),這就使得攻擊者知道了查找表時(shí)用到的索引值,該索引值對(duì)應(yīng)著密鑰的一個(gè)片段。通過(guò)多次訪問進(jìn)而獲取整個(gè)密鑰的所有片斷,推出密鑰。在滑動(dòng)窗口算法中,當(dāng)滑動(dòng)窗口的大小為6時(shí),預(yù)計(jì)算乘法表TABLE[0,1,…,31]={g2,g3,…,g63}={m2,m3,…,m63},如果TABLE[i]=gk,那么k=2i+1,其中i>0(i=0時(shí),k=2)。就像平方乘法算法一樣,從左到右滑動(dòng)窗口算法執(zhí)行過(guò)程中首先執(zhí)行平方操作。然而,實(shí)際上每次執(zhí)行多位,那么在窗口大小內(nèi)的這些值將會(huì)被檢測(cè)。如果連續(xù)6位是(100001)2,那么中間結(jié)果通過(guò)查初始化表乘以TABLE,即m33;如果是(10001)2,那么中間結(jié)果通過(guò)查初始化表TABLE,即m17;后面以此類推。初始化表每個(gè)元素大小與模數(shù)N的大小(例如對(duì)1024bit的模數(shù)N,那么每個(gè)元素大小為128Byte)。x86的CPU上每個(gè)Cache行大小為64Byte,攻擊者在計(jì)時(shí)攻擊的過(guò)程中,通過(guò)重復(fù)執(zhí)行一些清空Cache指令使這些預(yù)計(jì)算值從Cache中清除,在查表操作結(jié)束后,再次訪問預(yù)計(jì)算值,如果預(yù)計(jì)算表中的第2個(gè)元素訪問時(shí)間很短,可以認(rèn)為訪問該元素時(shí)“Cache命中”,那么簽名進(jìn)程訪問了預(yù)計(jì)算值m3,因此,此次窗口滑動(dòng)對(duì)應(yīng)的密鑰片段為(11)2。4.2納第三，存儲(chǔ)了解構(gòu)機(jī)制的時(shí)間戳值從上面的分析中可知,為獲得私鑰d的信息,必須精確獲得在簽名過(guò)程中,Cache命中與失效導(dǎo)致的時(shí)間差異信息。因此,在仿真實(shí)驗(yàn)中還需要解決以下關(guān)鍵問題:(1)高精度精確計(jì)時(shí)。本文采用CPU中一個(gè)稱為時(shí)間戳的部件,它以64bit無(wú)符號(hào)整型數(shù)的格式記錄了自CPU上電以來(lái)經(jīng)過(guò)的時(shí)鐘周期。在Pentium以上的CPU中,提供了一條機(jī)器指令RDTSC(ReadTimeStampCounter)來(lái)讀取這個(gè)時(shí)間戳值,通過(guò)這一方法,可以達(dá)到納秒級(jí)的計(jì)時(shí)精度。(2)清空Cache。實(shí)驗(yàn)中需要在每次新的窗口滑動(dòng)過(guò)程中清空L1數(shù)據(jù)Cache。實(shí)驗(yàn)使用的CPU中L1數(shù)據(jù)Cache大小為64KB,Cache行大小為64Byte,因此,定義一個(gè)大小為64KB的數(shù)組intdata[16*1024],當(dāng)進(jìn)行清空Cache操作時(shí),對(duì)該數(shù)組每隔64Byte進(jìn)行一次訪問,這樣即可保證每一個(gè)Cache行都被替換為data數(shù)組的內(nèi)容。(3)進(jìn)程的干擾。通常除了理想的解密算法本身產(chǎn)生的計(jì)時(shí)差別外,在系統(tǒng)中還會(huì)存在其他運(yùn)行的進(jìn)程和密碼進(jìn)程搶占CPU資源,會(huì)對(duì)解密計(jì)時(shí)精度產(chǎn)生影響。盡管通過(guò)大量取樣平均化處理可能減少這些誤差影響,但這使攻擊所需要的樣本量大幅增加。在本文實(shí)驗(yàn)中,盡可能減少其他進(jìn)程,以便提高攻擊準(zhǔn)確度。5基于cache不同密鑰片的保護(hù)機(jī)制Cache計(jì)時(shí)攻擊的實(shí)驗(yàn)環(huán)境如下:操作系統(tǒng)為WindowsXPProfessional;OpenSSL為OpenSSLv.0.9.8a;CPU為Athlon643000+1.81GHz;L1Cache容量為64KB,相聯(lián)度為2way,Cache行大小為64Byte。筆者在上述實(shí)驗(yàn)環(huán)境下編寫Cache計(jì)時(shí)攻擊仿真程序,利用間諜進(jìn)程采集每次窗口滑動(dòng)過(guò)程中二次訪問初始化表的時(shí)鐘周期,攻擊流程如圖2所示。在仿真實(shí)驗(yàn)中,通過(guò)調(diào)用OpenSSL密碼庫(kù)函數(shù)隨機(jī)產(chǎn)生1024bit密鑰,滑動(dòng)窗口大小為6,初始化表長(zhǎng)度為32,表中每個(gè)元素大小為128Byte。圖3給出了第1次窗口滑動(dòng)后,2次訪問初始化表中每個(gè)元素時(shí)需要的訪問時(shí)間?？梢钥闯?訪問表中索引值為17的元素需要時(shí)鐘周期只有76,所需時(shí)間最少,因此,可以判定第一次滑動(dòng)窗口過(guò)程中訪問了表中的元素TABLE,即m35,對(duì)應(yīng)的密鑰片段為(100011)2。通過(guò)仿真實(shí)驗(yàn)可以得到每次滑動(dòng)窗口對(duì)應(yīng)的密鑰片段,由滑動(dòng)窗口算法的3.1步可知,當(dāng)di=0時(shí),不需要進(jìn)行查找表操作,因此,在獲得的密鑰片段間可能填充有二進(jìn)制的0。在實(shí)際的一次攻擊實(shí)驗(yàn)中,對(duì)于1024bit的密鑰,窗口大小為6,理想情況下滑動(dòng)1024/6=171次,實(shí)際中滑動(dòng)140次~150次,通過(guò)Cache計(jì)時(shí)攻擊可以得到700bit以上的密鑰,這已大幅減少了密鑰搜索空間,根據(jù)文獻(xiàn)的理論,通過(guò)數(shù)學(xué)計(jì)算,則可以獲得完整的密鑰。Cache計(jì)時(shí)攻擊利用了Cache命中和失效特征導(dǎo)致的時(shí)間信息差異,而基于統(tǒng)計(jì)方法的計(jì)時(shí)攻擊需要大量的樣本。研究人員能夠在大約2h內(nèi)從一個(gè)RSA加密服務(wù)程序中解析出1024bit的RSA私鑰。攻擊需要大約350000個(gè)時(shí)間樣本。而在本文的攻擊實(shí)驗(yàn)中,窗口滑動(dòng)146次,獲得了802位密鑰片段,只需要150×32=4672個(gè)時(shí)間樣本。因此,需要的時(shí)間樣本量大幅減少。6基于cache防高模型的攻擊本文研究了基于Cache命中和失效的RSA計(jì)時(shí)攻擊,由于Cache資源的共享,Cache在讀取數(shù)據(jù)時(shí)具有命中和失效2種特性,產(chǎn)生不同的時(shí)間信息。這種攻擊利用了CPU內(nèi)