分組密碼算法能量分析攻擊中效率與容錯(cuò)問(wèn)題研究.pdf

1、分組密碼是目前應(yīng)用最為廣泛的密碼體制之一，它是一類對(duì)稱密碼算法，使用同一密鑰進(jìn)行加密和解密運(yùn)算。本質(zhì)上，分組密碼是一種帶密鑰的置換，它將明文數(shù)據(jù)劃分為多個(gè)長(zhǎng)度相等的分組，并轉(zhuǎn)換為相同長(zhǎng)度的密文。目前主流的分組密碼算法在數(shù)學(xué)結(jié)構(gòu)方面具有較高的安全性，很難被數(shù)學(xué)分析的方法破解。然而，數(shù)學(xué)分析方法主要針對(duì)明文和密文進(jìn)行分析，在算法通過(guò)密碼設(shè)備實(shí)現(xiàn)的安全性分析方面具有一定局限性。
　　自從1996年Kocher提出了研究操作時(shí)間的計(jì)時(shí)攻擊

2、以來(lái)[1]，側(cè)信道攻擊及防御逐漸成為密碼學(xué)的一個(gè)重要分支。有別于傳統(tǒng)的暴力破解，或者針對(duì)密碼理論的弱點(diǎn)進(jìn)行研究，側(cè)信道攻擊分析密碼算法物理實(shí)現(xiàn)過(guò)程中某些中間值泄露的信息，從而獲取密鑰。時(shí)間、電磁波、乃至聲音等信息均可以作為攻擊密碼系統(tǒng)的側(cè)信道信息，除此之外，能量消耗分析是側(cè)信道攻擊最有效的手段之一。在實(shí)際應(yīng)用中，這些攻擊通常會(huì)借助密碼芯片，如微處理器、FPGA(Field-Programmable Gate Array)、ASIC(Ap

3、plication Specific Integrated Circuit)[2]等來(lái)實(shí)現(xiàn)。1999年，Kocher等人提出了能量分析攻擊[3，4]，這種攻擊能夠通過(guò)密碼芯片執(zhí)行過(guò)程中的瞬時(shí)能量消耗來(lái)獲取中間值信息，從而推導(dǎo)出密鑰。之后Chari等人于2002年提出了模板攻擊[5]。模板攻擊根據(jù)密碼設(shè)備泄露的信息數(shù)據(jù)以及相關(guān)操作的特征來(lái)構(gòu)建模板，尋找與獲取的信息最匹配的模板，從而有效縮小密鑰搜索空間。2004年，Brier等人提出了相關(guān)

4、能量分析，這種攻擊建立在差分能量分析的基礎(chǔ)上，采用相關(guān)系數(shù)模型來(lái)恢復(fù)密鑰[6]。
　　本文重點(diǎn)研究針對(duì)分組密碼算法的能量分析攻擊，以AES(Advanced Encryption Standard)算法為例，提出了比現(xiàn)有攻擊方法更為有效的容錯(cuò)線性碰撞攻擊和基于二階距離的比特碰撞攻擊。并使用比特碰撞攻擊改進(jìn)容錯(cuò)線性碰撞攻擊，進(jìn)而得到容錯(cuò)比特碰撞攻擊。最后針對(duì)幾種經(jīng)典算法的S盒結(jié)構(gòu)，進(jìn)行了相關(guān)能量分析、模板攻擊、以及比特碰撞攻擊的效率

5、研究。
　　1.容錯(cuò)線性碰撞攻擊
　　相關(guān)能量分析[6]和碰撞攻擊都是常見(jiàn)的能量分析攻擊方法。Bogdanov等人將相關(guān)能量分析與碰撞攻擊結(jié)合，提出了測(cè)試鏈的概念[7]，并指出這種方法的攻擊效率高于獨(dú)立的相關(guān)能量分析或碰撞攻擊。然而，測(cè)試鏈攻擊只能糾正相關(guān)能量分析部分出現(xiàn)的錯(cuò)誤，對(duì)碰撞攻擊部分出現(xiàn)的錯(cuò)誤無(wú)能為力。換句話說(shuō)，一旦在測(cè)試鏈的一條路徑中出現(xiàn)錯(cuò)誤，它將導(dǎo)致隨后連續(xù)出現(xiàn)錯(cuò)誤，乃至整條路徑錯(cuò)誤，造成攻擊失敗。并且由于實(shí)際

6、上碰撞攻擊的效率低于相關(guān)能量分析，這使得Bogdanov等人的方法可能不切實(shí)際。
　　我們以測(cè)試鏈思想為基礎(chǔ)，提出了容錯(cuò)鏈的概念。以AES第一個(gè)密鑰字節(jié)k1為例，容錯(cuò)鏈選取k1作為唯一的自由變量，即從k1出發(fā)，通過(guò)碰撞攻擊構(gòu)造k1與其它15個(gè)密鑰字節(jié)之間的關(guān)系k1⊕ki=△1,i(2≤i≤16).(1)這15個(gè)關(guān)系式相互獨(dú)立，因此如果一個(gè)關(guān)系式出錯(cuò)，其錯(cuò)誤結(jié)果不會(huì)影響其它關(guān)系式。在攻擊的具體實(shí)現(xiàn)中我們采用相關(guān)強(qiáng)化碰撞攻擊構(gòu)造容錯(cuò)鏈

7、。
　　在容錯(cuò)線性碰撞攻擊中，我們不僅構(gòu)造一個(gè)容錯(cuò)鏈，同時(shí)還采用相關(guān)能量分析對(duì)密鑰候選值進(jìn)行排序，并給定一個(gè)閾值ThCPA，篩選出每個(gè)密鑰字節(jié)的候選值集合。滿足容錯(cuò)鏈關(guān)系式(1)且屬于密鑰候選集合的密鑰，可以判定為正確密鑰。由于除k1外的其它密鑰字節(jié)互不影響，因此可以給定一個(gè)碰撞攻擊部分的閾值ThCA，使得攻擊成功返回的密鑰可以包含至多ThCA個(gè)錯(cuò)誤的字節(jié)。隨后通過(guò)少量搜索能夠找到正確的密鑰。
　　我們通過(guò)仿真實(shí)驗(yàn)對(duì)容錯(cuò)線性

8、碰撞攻擊和測(cè)試鏈攻擊進(jìn)行了效率比對(duì)。實(shí)驗(yàn)結(jié)果表明，當(dāng)兩種攻擊的成功率均在90％以上時(shí)，容錯(cuò)線性碰撞攻擊所需能量跡數(shù)量少于測(cè)試鏈攻擊。
　　為了進(jìn)一步縮小密鑰搜索空間，我們給出一個(gè)糾錯(cuò)機(jī)制，能夠較為精確的識(shí)別錯(cuò)誤密鑰字節(jié)的位置。隨后討論了錯(cuò)誤發(fā)生在相關(guān)能量分析部分和碰撞攻擊部分的可能性，并通過(guò)實(shí)驗(yàn)給出了ThCPA的取值范圍。最后我們分析了ThCPA的取值對(duì)攻擊成功率的影響，根據(jù)實(shí)驗(yàn)數(shù)據(jù)建議ThCPA=10為最有效取值。
　　2

9、.基于二階距離的比特碰撞攻擊
　　2010年，Moradi等人提出了針對(duì)AES硬件實(shí)現(xiàn)的相關(guān)強(qiáng)化碰撞攻擊[8]。然而，他們的攻擊方法在實(shí)際操作中存在效率問(wèn)題。相關(guān)強(qiáng)化碰撞攻擊按字節(jié)進(jìn)行操作，因此每次攻擊至少需要256條平均能量跡。攻擊者需要在示波器上對(duì)采集的原始能量跡進(jìn)行平均，然后手動(dòng)存儲(chǔ);或者將大量原始能量跡存儲(chǔ)到計(jì)算機(jī)中，再使用MATLAB進(jìn)行平均。其中采集、存儲(chǔ)、以及平均能量跡的過(guò)程極為繁瑣且耗費(fèi)時(shí)間。
　　攻擊者通常

10、希望攻擊實(shí)現(xiàn)盡可能快速有效，我們以此為出發(fā)點(diǎn)提出了較為靈活的基于二階距離的比特碰撞攻擊，它使用能量跡距離模型和逐比特比較的思想?yún)^(qū)分碰撞。以AES算法為例，選定一個(gè)全零明文P0和8個(gè)特殊明文Pα(α=1，2,…，8)，每個(gè)Pα包含16個(gè)同樣的字節(jié)Pα，其第α比特為1，其它比特為0。Pα與密鑰進(jìn)行異或運(yùn)算得到S盒的輸入值，每個(gè)S盒的輸入值即為第α比特發(fā)生變化的密鑰字節(jié)，并且運(yùn)算前后的漢明重量也隨之變化。由于輸入P0不會(huì)引發(fā)任何比特改變，因此

11、輸入Pα后，通過(guò)比較不同S盒輸入值的漢明重量之差是否與輸入P0相同，可以推斷對(duì)應(yīng)的密鑰字節(jié)的第α比特是否相等。以P0和P1為例，令△HW0和△HW1分別表示選擇P0或P1前兩個(gè)S盒輸入值漢明重量的差值，可以通過(guò)條件(2)和(3)判斷k1和k2第一個(gè)比特u1和v1是否相等。
　　·當(dāng)且僅當(dāng)u1=v1時(shí)，|△HW0-△HW1|=0.(2)
　　·當(dāng)且僅當(dāng)u1≠v1時(shí)，|△HW0-△HW1|=2.(3)在實(shí)際攻擊中，我們使用能量跡

12、距離模型逼近漢明重量模型，因此可以成功區(qū)分出碰撞和非碰撞。
　　本文還給出另外一個(gè)距離模型。如果用△HW0和△HW1表示漢明重量之和，即一階距離的減法運(yùn)算替換為加法運(yùn)算，而二階距離保持不變，此時(shí)同樣可以實(shí)現(xiàn)比特碰撞攻擊。其碰撞與否與上述結(jié)論(2)和(3)恰好相反。
　　我們對(duì)比特碰撞攻擊進(jìn)行了實(shí)際操作和仿真實(shí)驗(yàn)。在實(shí)際操作中給出了差分能量跡和二階距離的比較圖示，證明比特碰撞攻擊切實(shí)有效。仿真實(shí)驗(yàn)分別研究了能量跡數(shù)量、操作時(shí)間

13、以及采樣點(diǎn)數(shù)量等指標(biāo)，對(duì)比特碰撞攻擊與相關(guān)強(qiáng)化碰撞攻擊進(jìn)行了效率比對(duì)。由實(shí)驗(yàn)數(shù)據(jù)得知，比特碰撞攻擊優(yōu)于相關(guān)強(qiáng)化碰撞攻擊，尤其在實(shí)際操作中，前者所需時(shí)間僅為后者的8％。
　　由于比特碰撞攻擊與相關(guān)強(qiáng)化碰撞攻擊的返回結(jié)果均為密鑰字節(jié)的異或值，而前者效率更高，因此我們使用比特碰撞攻擊構(gòu)造容錯(cuò)鏈，完成容錯(cuò)線性碰撞攻擊中的碰撞攻擊部分。改進(jìn)后的攻擊稱之為容錯(cuò)比特碰撞攻擊。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可知，容錯(cuò)比特碰撞攻擊的攻擊效率高于容錯(cuò)線性碰撞攻擊。

14、r>　　3.S盒位寬與能量分析攻擊效率的關(guān)系研究
　　數(shù)據(jù)加密標(biāo)準(zhǔn)DES(Data Encryption Standard)于1976年被美國(guó)聯(lián)邦政府的國(guó)家標(biāo)準(zhǔn)局確定為聯(lián)邦資料處理標(biāo)準(zhǔn)[9,10]，其安全性依賴于破解算法的計(jì)算難度大和計(jì)算時(shí)間長(zhǎng)。隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的發(fā)展，目前所擁有的計(jì)算能力已經(jīng)對(duì)DES造成了威脅。1997年，美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所發(fā)起征集高級(jí)加密標(biāo)準(zhǔn)AES的活動(dòng)，并于2000年確定了Rijndael算法為AE

15、S。Serpent算法也是AES的候選算法之一[11]。目前分組密碼的設(shè)計(jì)主要關(guān)注于非線性S盒、置換方法以及密鑰擴(kuò)展方案。S盒首次出現(xiàn)于Lucifer算法中，由于DES的深遠(yuǎn)影響而被廣泛應(yīng)用。S盒是許多分組密碼算法中唯一的非線性部件，因此算法的安全強(qiáng)度很大程度上取決于S盒的安全強(qiáng)度。
　　在一輪運(yùn)算中，DES使用8個(gè)S盒，輸入6比特輸出4比特;AES使用16個(gè)S盒，輸入輸出均為8比特;Serpent使用32個(gè)S盒，輸入輸出均為4比

16、特。由于實(shí)驗(yàn)中使用的AES和Serpent的分組長(zhǎng)度為128比特，而DES為64比特，為合理比較攻擊效率，我們假設(shè)一個(gè)DES的擴(kuò)展結(jié)構(gòu)DES-E，其數(shù)據(jù)長(zhǎng)度為128比特，且一輪使用16個(gè)DES結(jié)構(gòu)的S盒。
　　我們?cè)谙嗤膶?shí)驗(yàn)環(huán)境下研究三種能量分析攻擊方法針對(duì)一輪加密算法中單個(gè)S盒的攻擊效率。假設(shè)一輪攻擊的成功率高于50％，可以推出:DES單個(gè)S盒的成功率應(yīng)達(dá)到0.9170，DES-E和AES單個(gè)S盒的成功率應(yīng)達(dá)到0.9576，S

17、erpent單個(gè)S盒的成功率應(yīng)達(dá)到0.9786。
　　在相關(guān)能量分析中，S盒打亂了數(shù)據(jù)的線性規(guī)律，其輸出值能更好的體現(xiàn)數(shù)據(jù)相關(guān)性，因此選取S盒的輸出值作為攻擊對(duì)象。由于計(jì)算相關(guān)系數(shù)需要多條能量跡，因此每條能量跡上選取1個(gè)采樣點(diǎn)即可實(shí)現(xiàn)攻擊。由實(shí)驗(yàn)數(shù)據(jù)得知，達(dá)到期望成功率針對(duì)Serpent所需能量跡數(shù)量最多，其抗攻擊性最強(qiáng)。AES抗攻擊性最弱，低位寬S盒的安全強(qiáng)度高于高位寬S盒。
　　在模板攻擊中，由于構(gòu)建模板需要知道精確的漢

18、明重量，因此選取S盒的輸入值作為攻擊對(duì)象。為了較為精確的匹配模板，我們使用簡(jiǎn)化模板攻擊方法并選取10個(gè)采樣點(diǎn)。由實(shí)驗(yàn)數(shù)據(jù)得知，此時(shí)AES抗攻擊性最強(qiáng)，DES最弱。
　　在基于二階距離的比特碰撞攻擊中，由于攻擊思想也依賴于中間值具體的漢明重量，因此選取S盒的輸入值作為攻擊對(duì)象。為了衡量能量跡間距離，每條能量跡選取10個(gè)采樣點(diǎn)。由實(shí)驗(yàn)數(shù)據(jù)得知，此時(shí)AES抗攻擊性最強(qiáng)，Serpent最弱，高位寬S盒的安全強(qiáng)度高于低位寬S盒。