AES相關故障注入攻擊

王省欣，胡 偉，譚 靜，朱嘉誠，唐時博

(西北工業大學 網絡空間安全學院，陜西 西安 710072)

密碼算法實現在執行過程中通常會泄漏一些算法功能規范之外的信息，如加密時間、能量消耗、電磁輻射和出錯情況等。根據這些信息進行數學分析來獲取秘密信息，即側信道分析[1-2]。如通過對非對稱加密算法(Rivest-Shamir-Adleman，RSA)的時序攻擊來獲取密鑰[3]。常見的側信道分析方法包括時序分析、能量分析、電磁分析和故障分析等[4]。其中，故障注入攻擊通過向密碼算法實現執行過程中引入故障，并通過觀測故障效應和數學分析來恢復算法密鑰。故障分析是一種針對對稱和非對稱加密算法非常有效的密碼分析技術[5-7]。

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

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

1 背 景

1.1 AES算法結構

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

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

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

字節代替是AES中的非線性部件，各字節通過8位的S盒進行轉換，其每位輸入對多位輸出存在影響。行移位是一種線性移位操作，不改變中間狀態的值，只是對128 bit的中間狀態按算法定義的規則以字節為單位進行移位。列混淆會通過狀態字節之間的線性變換將字節代替的非線性混淆效應在狀態字節之間進行擴散。輪密鑰加變換通過與輪密鑰的線性異或操作來引入混淆。

1.2 AES故障效應傳播

AES的數據分組和加密中間狀態通常表示為4×4的狀態字節矩陣S，矩陣中每一個元素(S0～S15)為1個字節。如圖2，狀態矩陣中某字節發生故障，則故障會通過輪變換傳播擴散，增大故障的影響范圍。

圖2 第r輪內單字節故障傳播示意圖

圖2以輪內各變換輸入狀態矩陣中字節S1發生故障為例，帶顏色表示故障字節，展示了輪內變換單字節故障傳播效應。在不同狀態字節注入故障，傳播過程與此相似，但最后影響的狀態字節位置有所不同。

字節代替是以字節為單位的變換，故障只影響相應字節代替中相應的輸出字節。由于字節代替為非線性部件，因此，無法確定輸出的故障位置和數量。行移位變換為線性移位，不改變故障類型，僅是故障字節在狀態矩陣中的位置發生變化。列混淆變換雖為線性變換，但會通過狀態字節的線性變換將單字節的故障效應擴散到一列的4個狀態字節，且該4個狀態字節的故障效應滿足線性相關關系。輪密鑰加變換將狀態字與輪密鑰進行線性異或，不會對狀態字的故障類型造成影響，因此在r-1輪輪密鑰加注入故障和在r輪字節代替注入故障效果一致，可將在r-1輪輪密鑰加攻擊和在第r輪字節代替注入故障歸為同一類攻擊。由圖2可知，在每輪列混淆變換之前注入單字節故障，經輪內變換后故障都傳播到4個狀態字節。

由上述分析可知，列混淆變換的故障傳播效應相對復雜，列混淆變換的線性特性會使4個輸出字節之間的故障效應存在線性相關關系。在第r+1輪加密中，第r輪中每個字節的故障效應繼續傳播至4個字節，經過該輪列混淆變換后，每個錯誤字節各自影響該列的4個字節，因此，4個狀態字節的故障進一步傳播和擴散到16個狀態字節，但每列4個字節的故障效應仍然具有良好的線性相關關系。利用這種故障效應相關關系，提出了一種針對AES的簡單相關故障注入攻擊方法。

2 故障注入攻擊模型

假設攻擊者擁有運行的加密設備，但不知道加密密鑰。攻擊者能夠為加密設備施加明文，并觀測加密結果。集成電路正常工作依賴于穩定的時鐘和電壓信號，因此攻擊者可通過調節電壓、改變時鐘頻率，或向電源和時鐘信號中注入毛刺來進行故障注入攻擊。另外，攻擊者也可用激光照射或高能粒子擾亂密碼設備的正常運行，實現故障注入攻擊。

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

如圖3所示，對虛框中的運算實施故障注入攻擊，觀測注入故障后的加密結果。攻擊者可利用獲得的錯誤加密結果與對應的正確加密結果進行對比相關性分析，從而恢復算法的加密密鑰。

圖3 故障注入位置示意圖

文中提出的故障注入攻擊方法利用了AES加密算法的結構特征和故障傳播效應內在的線性相關關系，與現有故障注入攻擊方法相比，無需復雜的數學推導和故障攻擊模型訓練過程，且對故障類型要求更為靈活，可以為隨機故障。

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

3 相關故障注入攻擊

基于1.2節討論的AES故障效應傳播特征，文章提出了一種針對AES實現的相關故障注入分析方法。對于128位AES實現，該方法在AES算法第Nr-1和第Nr-2輪任意位置注入隨機故障后，分析最后一輪字節代替輸入的故障效應相關關系即可恢復最后一輪的輪密鑰。

3.1 故障效應相關性分析

以在S0中注入故障為例(如圖4所示)，不同顏色代表無關的故障類型，相同顏色代表線性相關的故障類型。由圖可知，在第Nr-1輪實施攻擊，故障傳播到4字節，在第Nr-2輪實施攻擊，故障傳播至16字節，但每列4字節的故障效應存在線性相關關系，區別在于第Nr-1輪注入故障后只經歷1次列混淆變換。

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

假設在第Nr-2輪狀態矩陣的S0注入的隨機故障為ε，經過該輪的字節代替后，錯誤信息變為ε0。由于故障注入位置為S0，此時行移位對故障傳播無影響。如式(1)所示，表示該輪列混淆變換后故障傳播的結果，其中，ε0，ε1和ε2代表不同故障。

(1)

狀態矩陣S經過第Nr-2輪的字節代替和行移位變換后，4個字節的故障發生變化且相互獨立，分別用α0，β0，γ0，δ0表示。如式(2)所示，列混淆變換后故障擴到全部16個字節，但各列4個字節之間故障的位置和數量仍存在線性相關關系。

(2)

根據AES加密算法的特點，最后一輪不存在列混淆變換，因此，可通過假設最后一輪的輪密鑰，逆向構造最后一輪字節代替輸入(即第Nr-1輪輸出)的故障效應，并檢驗狀態矩陣每列4個字節的故障效應的線性相關關系來確定正確密鑰。

(3)

(4)

(5)

然后，當d1最高比特位未發生故障時，通過測試式(6)所示的線性關系來恢復d2對應的密鑰字節，否則測試式(7)。

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

(6)

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

(7)

最后，測試式(8)來恢復d3對應的密鑰。

d1=d2⊕d3。

(8)

如圖5所示，在第Nr-1和第Nr-2輪狀態字節S0隨機注入單字節故障，正確-錯誤密文對或2條錯誤密文各自在第Nr-1輪的加密結果通過進行異或運算獲取故障信息Di。圖中以對虛框中內容進行異或運算為例，獲得錯誤信息D0。

圖5 故障效應傳播的錯誤信息示意圖

3.2 密鑰搜索算法

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

表1 目標字節Bi的分組

攻擊者能夠通過觀察密文中故障字節的數量和位置，并根據表1、式(3)～(8)來恢復密鑰。所采用的密鑰恢復算法如下。

算法1密鑰恢復算法。

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

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

① 根據C和C′選擇字節組合Sw，Sx，Sy，Sz

③ forSi，Sj字節組合對應的Nr輪輪密鑰字節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滿足式(3)～(5) THEN

該算法通過相關性分析方法，恢復Nr輪加密密鑰。先在密文對中選出目標字節Bi，猜測Bi對應的密鑰字節，然后對Bi執行逆輪密鑰加和逆字節代替變換，恢復2條密文對應的第Nr-1輪加密結果，對比可得故障信息Di。若密鑰字節猜測正確，則Di的對應字節滿足式(3)～(8)中的相關關系，否則無顯著相關關系。

3.3 192位和256位AES攻擊方法

不同密鑰長度的AES最后一輪加密變換相同，因此可通過算法1方法對192位和256位AES進行攻擊，獲得輪密鑰Kr。然而，僅根據最后一輪128位的輪密鑰不足以恢復192和256位AES的原始加密密鑰，需再恢復Nr-1輪的64位或者128位輪密鑰之后才能完全實現192和256位AES密鑰的破解。

為了恢復第Nr-1輪的輪密鑰，進一步向第Nr-3輪的列混淆變換之前注入隨機故障，然后，利用第Nr-1輪的字節代替輸入的故障效應相關關系，采用類似的相關故障分析方法來恢復密鑰。如圖6所示，利用已破解的輪密鑰Kr，重構第Nr-1輪的中間加密結果。對該中間加密結果進行逆列混淆變換，通過算法1每次分析破解4字節加密密鑰，然后對破解的密鑰再進行對應的列混淆變換即可恢復第Nr-1輪的密鑰字節。

圖6 恢復第Nr-1輪密鑰

4 實驗結果

4.1 AES相關故障注入攻擊實驗

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

4.2 故障注入攻擊結果

4.2.1 128位AES故障注入攻擊結果

在第8輪和第9輪加密變換輸入的第0至15字節注入單字節的隨機故障破解第10輪密鑰，執行單字節隨機故障注入攻擊960次，故障注入攻擊分析結果如表3所示。當分析1個密文對時，可選密鑰較多，當有2個密文對時，僅少數情況有多于1個密鑰猜測，備選密鑰數量已處于可測試驗證范圍內。

4.2.2 192位AES故障注入攻擊結果

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

表4 192位AES故障注入攻擊結果

4.2.3 256位AES故障注入攻擊結果

256位AES也需進行兩次故障注入攻擊破解第14輪和第13輪密鑰。在第12輪和第13輪進行攻擊破解第14輪密鑰后，再通過在第11輪和第12輪注入故障，分析第13輪密文的相關關系，破解第13輪加密密鑰，執行單字節隨機故障注入攻擊1 280次，故障注入攻擊分析結果如表5所示。與192位和128位攻擊結果類似，當有2個密文對時，僅少數情況有多于1個密鑰猜測，能夠通過測試驗證恢復全部密鑰。

表5 256位AES故障注入攻擊結果

利用文章所提出的攻擊分析方法，可通過匹配式(3)～(8)所示的4種相關關系判斷猜測密鑰的準確性，不需大量的數學推導，通過有限域GF(28)的逆運算即可恢復密鑰。以上實驗結果驗證了利用單字節隨機故障實施相關故障分析來恢復不同長度AES算法密鑰方法的有效性。只需2個正確-錯誤密文對或同一明文下的4條錯誤密文即可恢復128位AES初始密鑰；需4個正確-錯誤密文對或同一明文下的8條錯誤密文即可恢復192和256位AES初始密鑰。

5 結束語

筆者利用AES密碼算法的結構特征和故障傳播效應的線性相關關系，提出一種針對AES的簡單相關故障注入攻擊方法。與其他故障注入攻擊方法相比，該方法無需復雜數學推導，注入故障的位置和數量要求靈活，也適用于唯密文攻擊。