AES相關(guān)故障注入攻擊

王省欣，胡 偉，譚 靜，朱嘉誠(chéng)，唐時(shí)博

(西北工業(yè)大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，陜西 西安 710072)

密碼算法實(shí)現(xiàn)在執(zhí)行過(guò)程中通常會(huì)泄漏一些算法功能規(guī)范之外的信息，如加密時(shí)間、能量消耗、電磁輻射和出錯(cuò)情況等。根據(jù)這些信息進(jìn)行數(shù)學(xué)分析來(lái)獲取秘密信息，即側(cè)信道分析[1-2]。如通過(guò)對(duì)非對(duì)稱(chēng)加密算法(Rivest-Shamir-Adleman，RSA)的時(shí)序攻擊來(lái)獲取密鑰[3]。常見(jiàn)的側(cè)信道分析方法包括時(shí)序分析、能量分析、電磁分析和故障分析等[4]。其中，故障注入攻擊通過(guò)向密碼算法實(shí)現(xiàn)執(zhí)行過(guò)程中引入故障，并通過(guò)觀(guān)測(cè)故障效應(yīng)和數(shù)學(xué)分析來(lái)恢復(fù)算法密鑰。故障分析是一種針對(duì)對(duì)稱(chēng)和非對(duì)稱(chēng)加密算法非常有效的密碼分析技術(shù)[5-7]。

當(dāng)高級(jí)加密標(biāo)準(zhǔn)(Advanced Encryption Standard，AES)被普遍采用后，研究者提出了大量針對(duì)AES的故障注入攻擊方法[8-15]。PARK等在字節(jié)變換中注入故障，分析S盒輸入和S盒輸出之間的關(guān)系，破解密鑰[8]。一些研究通過(guò)向AES加密變換注入單字節(jié)故障來(lái)破解密鑰[9-11]，也有學(xué)者提出了針對(duì)密鑰擴(kuò)展的故障注入攻擊方法[12]。GHALATY等提出利用差分故障強(qiáng)度分析，通過(guò)平均7次對(duì)AES的故障注入攻擊，重建完整的128位加密密鑰[13]。通過(guò)引發(fā)2字節(jié)故障，ZHANG等利用差分故障分析方法破解密鑰[14]。POGUE等提出用增量故障分析的方法對(duì)不同密鑰長(zhǎng)度的AES加密算法進(jìn)行破解[15]。然而，上述故障注入攻擊方法大多對(duì)故障注入的位置、時(shí)機(jī)和數(shù)量有嚴(yán)格要求，且密鑰恢復(fù)過(guò)程需要復(fù)雜的數(shù)學(xué)分析，或需要大量時(shí)間來(lái)訓(xùn)練故障攻擊模板。

筆者提出一種針對(duì)AES的相關(guān)故障注入攻擊方法，利用AES故障效應(yīng)傳播中的相關(guān)關(guān)系恢復(fù)密鑰。該攻擊方法對(duì)故障注入位置和數(shù)量要求更為靈活，在不同密鑰長(zhǎng)度AES算法實(shí)現(xiàn)倒數(shù)第3輪(Nr- 2)列混合變換前至S盒變換之間任意位置注入隨機(jī)故障后，分析最后一輪S盒輸入的故障效應(yīng)相關(guān)關(guān)系，即可恢復(fù)最后一輪的輪密鑰；在192位和256位AES算法實(shí)現(xiàn)倒數(shù)第4輪(Nr- 3)列混合變換前至S盒變換之間任意位置注入隨機(jī)故障后可恢復(fù)倒數(shù)第2輪(Nr- 1)列的輪密鑰。該方法的密鑰搜索復(fù)雜度為216，只需2個(gè)正確-錯(cuò)誤密文對(duì)或同一明文下的4條錯(cuò)誤密文即可恢復(fù)128位AES初始密鑰；只需4個(gè)正確-錯(cuò)誤密文對(duì)或同一明文下的8條錯(cuò)誤密文即可恢復(fù)192和256位AES初始密鑰。

1 背 景

1.1 AES算法結(jié)構(gòu)

圖1 AES加密算法流程示意圖

AES是一種分組密碼算法，數(shù)據(jù)分組長(zhǎng)度為128 bit，密鑰支持128 bit、192 bit和256 bit 3種長(zhǎng)度。圖1為AES算法結(jié)構(gòu)，其中，r表示加密輪數(shù)，Nr(Nr= 10，12，14)表示加密迭代的總輪數(shù)。

AES是一種典型的迭代算法結(jié)構(gòu)，由輪函數(shù)和密鑰擴(kuò)展構(gòu)成。輪函數(shù)包括4種基本變換，字節(jié)代替(S-Box，SB)，行移位(ShiftRows，SR)，列混淆(MixColumns，MC)和輪密鑰加(AddRoundKey，ARK)。值得注意的是，AES加密算法中最后一輪加密不包含列混淆變換。

字節(jié)代替是AES中的非線(xiàn)性部件，各字節(jié)通過(guò)8位的S盒進(jìn)行轉(zhuǎn)換，其每位輸入對(duì)多位輸出存在影響。行移位是一種線(xiàn)性移位操作，不改變中間狀態(tài)的值，只是對(duì)128 bit的中間狀態(tài)按算法定義的規(guī)則以字節(jié)為單位進(jìn)行移位。列混淆會(huì)通過(guò)狀態(tài)字節(jié)之間的線(xiàn)性變換將字節(jié)代替的非線(xiàn)性混淆效應(yīng)在狀態(tài)字節(jié)之間進(jìn)行擴(kuò)散。輪密鑰加變換通過(guò)與輪密鑰的線(xiàn)性異或操作來(lái)引入混淆。

1.2 AES故障效應(yīng)傳播

AES的數(shù)據(jù)分組和加密中間狀態(tài)通常表示為4×4的狀態(tài)字節(jié)矩陣S，矩陣中每一個(gè)元素(S0～S15)為1個(gè)字節(jié)。如圖2，狀態(tài)矩陣中某字節(jié)發(fā)生故障，則故障會(huì)通過(guò)輪變換傳播擴(kuò)散，增大故障的影響范圍。

圖2 第r輪內(nèi)單字節(jié)故障傳播示意圖

圖2以輪內(nèi)各變換輸入狀態(tài)矩陣中字節(jié)S1發(fā)生故障為例，帶顏色表示故障字節(jié)，展示了輪內(nèi)變換單字節(jié)故障傳播效應(yīng)。在不同狀態(tài)字節(jié)注入故障，傳播過(guò)程與此相似，但最后影響的狀態(tài)字節(jié)位置有所不同。

字節(jié)代替是以字節(jié)為單位的變換，故障只影響相應(yīng)字節(jié)代替中相應(yīng)的輸出字節(jié)。由于字節(jié)代替為非線(xiàn)性部件，因此，無(wú)法確定輸出的故障位置和數(shù)量。行移位變換為線(xiàn)性移位，不改變故障類(lèi)型，僅是故障字節(jié)在狀態(tài)矩陣中的位置發(fā)生變化。列混淆變換雖為線(xiàn)性變換，但會(huì)通過(guò)狀態(tài)字節(jié)的線(xiàn)性變換將單字節(jié)的故障效應(yīng)擴(kuò)散到一列的4個(gè)狀態(tài)字節(jié)，且該4個(gè)狀態(tài)字節(jié)的故障效應(yīng)滿(mǎn)足線(xiàn)性相關(guān)關(guān)系。輪密鑰加變換將狀態(tài)字與輪密鑰進(jìn)行線(xiàn)性異或，不會(huì)對(duì)狀態(tài)字的故障類(lèi)型造成影響，因此在r-1輪輪密鑰加注入故障和在r輪字節(jié)代替注入故障效果一致，可將在r-1輪輪密鑰加攻擊和在第r輪字節(jié)代替注入故障歸為同一類(lèi)攻擊。由圖2可知，在每輪列混淆變換之前注入單字節(jié)故障，經(jīng)輪內(nèi)變換后故障都傳播到4個(gè)狀態(tài)字節(jié)。

由上述分析可知，列混淆變換的故障傳播效應(yīng)相對(duì)復(fù)雜，列混淆變換的線(xiàn)性特性會(huì)使4個(gè)輸出字節(jié)之間的故障效應(yīng)存在線(xiàn)性相關(guān)關(guān)系。在第r+1輪加密中，第r輪中每個(gè)字節(jié)的故障效應(yīng)繼續(xù)傳播至4個(gè)字節(jié)，經(jīng)過(guò)該輪列混淆變換后，每個(gè)錯(cuò)誤字節(jié)各自影響該列的4個(gè)字節(jié)，因此，4個(gè)狀態(tài)字節(jié)的故障進(jìn)一步傳播和擴(kuò)散到16個(gè)狀態(tài)字節(jié)，但每列4個(gè)字節(jié)的故障效應(yīng)仍然具有良好的線(xiàn)性相關(guān)關(guān)系。利用這種故障效應(yīng)相關(guān)關(guān)系，提出了一種針對(duì)AES的簡(jiǎn)單相關(guān)故障注入攻擊方法。

2 故障注入攻擊模型

假設(shè)攻擊者擁有運(yùn)行的加密設(shè)備，但不知道加密密鑰。攻擊者能夠?yàn)榧用茉O(shè)備施加明文，并觀(guān)測(cè)加密結(jié)果。集成電路正常工作依賴(lài)于穩(wěn)定的時(shí)鐘和電壓信號(hào)，因此攻擊者可通過(guò)調(diào)節(jié)電壓、改變時(shí)鐘頻率，或向電源和時(shí)鐘信號(hào)中注入毛刺來(lái)進(jìn)行故障注入攻擊。另外，攻擊者也可用激光照射或高能粒子擾亂密碼設(shè)備的正常運(yùn)行，實(shí)現(xiàn)故障注入攻擊。

假設(shè)攻擊者掌握了加密設(shè)備上AES算法實(shí)現(xiàn)的細(xì)節(jié)信息，能夠準(zhǔn)確地在第Nr-1至Nr-3輪的任一運(yùn)算注入單字節(jié)的隨機(jī)故障。攻擊者不知道故障注入的具體位置或者故障類(lèi)型及數(shù)量，并且任意兩次注入的故障都可能是不同的(隨機(jī)故障)。

如圖3所示，對(duì)虛框中的運(yùn)算實(shí)施故障注入攻擊，觀(guān)測(cè)注入故障后的加密結(jié)果。攻擊者可利用獲得的錯(cuò)誤加密結(jié)果與對(duì)應(yīng)的正確加密結(jié)果進(jìn)行對(duì)比相關(guān)性分析，從而恢復(fù)算法的加密密鑰。

圖3 故障注入位置示意圖

文中提出的故障注入攻擊方法利用了AES加密算法的結(jié)構(gòu)特征和故障傳播效應(yīng)內(nèi)在的線(xiàn)性相關(guān)關(guān)系，與現(xiàn)有故障注入攻擊方法相比，無(wú)需復(fù)雜的數(shù)學(xué)推導(dǎo)和故障攻擊模型訓(xùn)練過(guò)程，且對(duì)故障類(lèi)型要求更為靈活，可以為隨機(jī)故障。

首先以128位AES為例，介紹相關(guān)故障注入攻擊方法，然后討論將該攻擊手段擴(kuò)展至192和256位AES的方法。

3 相關(guān)故障注入攻擊

基于1.2節(jié)討論的AES故障效應(yīng)傳播特征，文章提出了一種針對(duì)AES實(shí)現(xiàn)的相關(guān)故障注入分析方法。對(duì)于128位AES實(shí)現(xiàn)，該方法在A(yíng)ES算法第Nr-1和第Nr-2輪任意位置注入隨機(jī)故障后，分析最后一輪字節(jié)代替輸入的故障效應(yīng)相關(guān)關(guān)系即可恢復(fù)最后一輪的輪密鑰。

3.1 故障效應(yīng)相關(guān)性分析

以在S0中注入故障為例(如圖4所示)，不同顏色代表無(wú)關(guān)的故障類(lèi)型，相同顏色代表線(xiàn)性相關(guān)的故障類(lèi)型。由圖可知，在第Nr-1輪實(shí)施攻擊，故障傳播到4字節(jié)，在第Nr-2輪實(shí)施攻擊，故障傳播至16字節(jié)，但每列4字節(jié)的故障效應(yīng)存在線(xiàn)性相關(guān)關(guān)系，區(qū)別在于第Nr-1輪注入故障后只經(jīng)歷1次列混淆變換。

圖4 第Nr-2輪和第Nr-1輪故障傳播過(guò)程示意圖

假設(shè)在第Nr-2輪狀態(tài)矩陣的S0注入的隨機(jī)故障為ε，經(jīng)過(guò)該輪的字節(jié)代替后，錯(cuò)誤信息變?yōu)棣?。由于故障注入位置為S0，此時(shí)行移位對(duì)故障傳播無(wú)影響。如式(1)所示，表示該輪列混淆變換后故障傳播的結(jié)果，其中，ε0，ε1和ε2代表不同故障。

(1)

狀態(tài)矩陣S經(jīng)過(guò)第Nr-2輪的字節(jié)代替和行移位變換后，4個(gè)字節(jié)的故障發(fā)生變化且相互獨(dú)立，分別用α0，β0，γ0，δ0表示。如式(2)所示，列混淆變換后故障擴(kuò)到全部16個(gè)字節(jié)，但各列4個(gè)字節(jié)之間故障的位置和數(shù)量仍存在線(xiàn)性相關(guān)關(guān)系。

(2)

根據(jù)AES加密算法的特點(diǎn)，最后一輪不存在列混淆變換，因此，可通過(guò)假設(shè)最后一輪的輪密鑰，逆向構(gòu)造最后一輪字節(jié)代替輸入(即第Nr-1輪輸出)的故障效應(yīng)，并檢驗(yàn)狀態(tài)矩陣每列4個(gè)字節(jié)的故障效應(yīng)的線(xiàn)性相關(guān)關(guān)系來(lái)確定正確密鑰。

(3)

(4)

(5)

然后，當(dāng)d1最高比特位未發(fā)生故障時(shí)，通過(guò)測(cè)試式(6)所示的線(xiàn)性關(guān)系來(lái)恢復(fù)d2對(duì)應(yīng)的密鑰字節(jié)，否則測(cè)試式(7)。

d2=d1或d2=(d1?1) 。

(6)

d2=(d1?1)⊕0×1B 。

(7)

最后，測(cè)試式(8)來(lái)恢復(fù)d3對(duì)應(yīng)的密鑰。

d1=d2⊕d3。

(8)

如圖5所示，在第Nr-1和第Nr-2輪狀態(tài)字節(jié)S0隨機(jī)注入單字節(jié)故障，正確-錯(cuò)誤密文對(duì)或2條錯(cuò)誤密文各自在第Nr-1輪的加密結(jié)果通過(guò)進(jìn)行異或運(yùn)算獲取故障信息Di。圖中以對(duì)虛框中內(nèi)容進(jìn)行異或運(yùn)算為例，獲得錯(cuò)誤信息D0。

圖5 故障效應(yīng)傳播的錯(cuò)誤信息示意圖

3.2 密鑰搜索算法

由3.1節(jié)可知，僅需分析第Nr-1輪加密結(jié)果故障效應(yīng)的相關(guān)關(guān)系，即可破解Nr輪加密密鑰。由于Nr輪加密行移位變換改變了輸入狀態(tài)矩陣中故障字節(jié)的位置，如表1所示，可將AES的加密結(jié)果分為4組目標(biāo)字節(jié)Bi(0≤i≤3)。通過(guò)分析對(duì)應(yīng)目標(biāo)字節(jié)Bi的正誤密文，獲取第i列密鑰信息。

表1 目標(biāo)字節(jié)Bi的分組

攻擊者能夠通過(guò)觀(guān)察密文中故障字節(jié)的數(shù)量和位置，并根據(jù)表1、式(3)～(8)來(lái)恢復(fù)密鑰。所采用的密鑰恢復(fù)算法如下。

算法1密鑰恢復(fù)算法。

輸入：密文對(duì)(C，C′)。

輸出：最后一輪輪密鑰Kr。

① 根據(jù)C和C′選擇字節(jié)組合Sw，Sx，Sy，Sz

③ forSi，Sj字節(jié)組合對(duì)應(yīng)的Nr輪輪密鑰字節(jié)ki，kjin 0 ：216DO

④Si= S-Box-1(Ci⊕ki)

⑤Sj= S-Box-1(Cj⊕kj)

⑥Si′= S-Box-1(Ci′⊕ki)

⑦Sj′= S-Box-1(Cj′⊕kj)

⑧εi=Si⊕Si′

⑨εj=Sj⊕Sj′

⑩ IFεi和εj滿(mǎn)足式(3)～(5) THEN

該算法通過(guò)相關(guān)性分析方法，恢復(fù)Nr輪加密密鑰。先在密文對(duì)中選出目標(biāo)字節(jié)Bi，猜測(cè)Bi對(duì)應(yīng)的密鑰字節(jié)，然后對(duì)Bi執(zhí)行逆輪密鑰加和逆字節(jié)代替變換，恢復(fù)2條密文對(duì)應(yīng)的第Nr-1輪加密結(jié)果，對(duì)比可得故障信息Di。若密鑰字節(jié)猜測(cè)正確，則Di的對(duì)應(yīng)字節(jié)滿(mǎn)足式(3)～(8)中的相關(guān)關(guān)系，否則無(wú)顯著相關(guān)關(guān)系。

3.3 192位和256位AES攻擊方法

不同密鑰長(zhǎng)度的AES最后一輪加密變換相同，因此可通過(guò)算法1方法對(duì)192位和256位AES進(jìn)行攻擊，獲得輪密鑰Kr。然而，僅根據(jù)最后一輪128位的輪密鑰不足以恢復(fù)192和256位AES的原始加密密鑰，需再恢復(fù)Nr-1輪的64位或者128位輪密鑰之后才能完全實(shí)現(xiàn)192和256位AES密鑰的破解。

為了恢復(fù)第Nr-1輪的輪密鑰，進(jìn)一步向第Nr-3輪的列混淆變換之前注入隨機(jī)故障，然后，利用第Nr-1輪的字節(jié)代替輸入的故障效應(yīng)相關(guān)關(guān)系，采用類(lèi)似的相關(guān)故障分析方法來(lái)恢復(fù)密鑰。如圖6所示，利用已破解的輪密鑰Kr，重構(gòu)第Nr-1輪的中間加密結(jié)果。對(duì)該中間加密結(jié)果進(jìn)行逆列混淆變換，通過(guò)算法1每次分析破解4字節(jié)加密密鑰，然后對(duì)破解的密鑰再進(jìn)行對(duì)應(yīng)的列混淆變換即可恢復(fù)第Nr-1輪的密鑰字節(jié)。

圖6 恢復(fù)第Nr-1輪密鑰

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

4.1 AES相關(guān)故障注入攻擊實(shí)驗(yàn)

由3.1和3.2節(jié)可知，可在第r-1輪和第r-2輪進(jìn)行故障注入攻擊，獲取第r輪加密密鑰。第r-1輪一次攻擊只可破解32位第r輪密鑰，需在狀態(tài)矩陣各列進(jìn)行一次攻擊，才可破解128位輪密鑰信息。而第r-2 輪一次攻擊即可破解128位第r輪密鑰。表2顯示了不同AES加密算法故障注入位置與可恢復(fù)密鑰數(shù)量之間的關(guān)系。

4.2 故障注入攻擊結(jié)果

4.2.1 128位AES故障注入攻擊結(jié)果

在第8輪和第9輪加密變換輸入的第0至15字節(jié)注入單字節(jié)的隨機(jī)故障破解第10輪密鑰，執(zhí)行單字節(jié)隨機(jī)故障注入攻擊960次，故障注入攻擊分析結(jié)果如表3所示。當(dāng)分析1個(gè)密文對(duì)時(shí)，可選密鑰較多，當(dāng)有2個(gè)密文對(duì)時(shí)，僅少數(shù)情況有多于1個(gè)密鑰猜測(cè)，備選密鑰數(shù)量已處于可測(cè)試驗(yàn)證范圍內(nèi)。

4.2.2 192位AES故障注入攻擊結(jié)果

與128位AES故障攻擊類(lèi)似，在192位AES算法的第10輪和第11輪進(jìn)行攻擊，破解第12輪加密密鑰。利用破解的第12輪加密密鑰，在第9輪和第10輪進(jìn)行第二次故障注入攻擊，破解64位的第11輪加密密鑰，執(zhí)行單字節(jié)隨機(jī)故障注入攻擊1 280次，故障注入攻擊分析結(jié)果如表4所示。分析1個(gè)密文對(duì)時(shí)，最大備選密鑰數(shù)量和最小備選密鑰數(shù)量差異較大，分析2個(gè)密文對(duì)時(shí)，備選密鑰已處于可測(cè)試驗(yàn)證范圍內(nèi)。

表4 192位AES故障注入攻擊結(jié)果

4.2.3 256位AES故障注入攻擊結(jié)果

256位AES也需進(jìn)行兩次故障注入攻擊破解第14輪和第13輪密鑰。在第12輪和第13輪進(jìn)行攻擊破解第14輪密鑰后，再通過(guò)在第11輪和第12輪注入故障，分析第13輪密文的相關(guān)關(guān)系，破解第13輪加密密鑰，執(zhí)行單字節(jié)隨機(jī)故障注入攻擊1 280次，故障注入攻擊分析結(jié)果如表5所示。與192位和128位攻擊結(jié)果類(lèi)似，當(dāng)有2個(gè)密文對(duì)時(shí)，僅少數(shù)情況有多于1個(gè)密鑰猜測(cè)，能夠通過(guò)測(cè)試驗(yàn)證恢復(fù)全部密鑰。

表5 256位AES故障注入攻擊結(jié)果

利用文章所提出的攻擊分析方法，可通過(guò)匹配式(3)～(8)所示的4種相關(guān)關(guān)系判斷猜測(cè)密鑰的準(zhǔn)確性，不需大量的數(shù)學(xué)推導(dǎo)，通過(guò)有限域GF(28)的逆運(yùn)算即可恢復(fù)密鑰。以上實(shí)驗(yàn)結(jié)果驗(yàn)證了利用單字節(jié)隨機(jī)故障實(shí)施相關(guān)故障分析來(lái)恢復(fù)不同長(zhǎng)度AES算法密鑰方法的有效性。只需2個(gè)正確-錯(cuò)誤密文對(duì)或同一明文下的4條錯(cuò)誤密文即可恢復(fù)128位AES初始密鑰；需4個(gè)正確-錯(cuò)誤密文對(duì)或同一明文下的8條錯(cuò)誤密文即可恢復(fù)192和256位AES初始密鑰。

5 結(jié)束語(yǔ)

筆者利用AES密碼算法的結(jié)構(gòu)特征和故障傳播效應(yīng)的線(xiàn)性相關(guān)關(guān)系，提出一種針對(duì)AES的簡(jiǎn)單相關(guān)故障注入攻擊方法。與其他故障注入攻擊方法相比，該方法無(wú)需復(fù)雜數(shù)學(xué)推導(dǎo)，注入故障的位置和數(shù)量要求靈活，也適用于唯密文攻擊。