rsacache計攻擊原理及實現(xiàn)

rsacache計攻擊原理及實現(xiàn)

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