ARIA密碼的積分故障分析

沈煜，李瑋,,3,，谷大武，吳益鑫，曹珊，劉亞，劉志強，周志洪

（1. 東華大學計算機科學與技術學院，上海 201620；2. 上海交通大學計算機科學與工程系，上海 200240；3. 上海市可擴展計算與系統(tǒng)重點實驗室，上海 200240；4. 上海市信息安全綜合管理技術研究重點實驗室，上海 200240；5. 上海理工大學計算機科學與工程系，上海 200093）

1 引言

分組密碼作為實現(xiàn)消息保密、數(shù)據(jù)完整性保護和實體認證的核心基礎體制，其設計、分析與實現(xiàn)方法一直是密碼學研究的主流，在信息系統(tǒng)的安全領域發(fā)揮著重要的應用。ARIA算法是韓國國家安全研究所于 2003年提出的一種符合高級加密算法征集標準的分組密碼，并且被商業(yè)部、工業(yè)部和能源部確認為國家標準分組密碼，保障信息系統(tǒng)的數(shù)據(jù)安全[1-3]。研究表明，ARIA算法對差分分析法、線性分析法、截段–高階差分分析法、不可能差分分析法、滑動攻擊法、積分攻擊法等密碼分析方法具有足夠的安全冗余[4-8]，具有優(yōu)良的軟硬件實現(xiàn)效率，在處理器應用上具有良好的實現(xiàn)性能。

然而，在現(xiàn)實環(huán)境中，只從ARIA算法的數(shù)學模型研究其安全性已經(jīng)遠遠不夠，必須從實現(xiàn)角度來考慮，即使密碼算法在傳統(tǒng)密碼分析方法下是安全的，如果不能在運行平臺上安全地加以實現(xiàn)，也不能正常發(fā)揮出預期作用。與傳統(tǒng)的保密通信環(huán)境相比，如今的運行環(huán)境通常面臨著更大的安全威脅。譬如銀行卡、手持無線設備、汽車遙控鎖、交通卡、門禁卡等密碼載體的持有者不僅可以是正常用戶，也可以是攻擊者。攻擊者借助異常時鐘、微波輻射、激光照射等方式干預密碼變換的正常過程，導致運算過程中發(fā)生錯誤，產(chǎn)生錯誤的輸出結果，這種攻擊方式比傳統(tǒng)密碼分析破譯速度更快，有效地達到密碼算法內關鍵數(shù)據(jù)的復制、篡改或偽造的目的，通常被稱為故障分析[9-12]，由于其良好的攻擊效果和潛在的發(fā)展前景，已成為密碼分析和密碼工程領域發(fā)展廣受關注的方向之一。

故障分析在發(fā)展中逐步衍生出多種攻擊方法，Biham等[13]于 1997年提出的差分故障分析法是目前分析范圍最廣、威脅最大且發(fā)展最迅速的一種攻擊技術，被廣泛應用于密碼芯片的安全性研究中。之后，無效故障分析法、碰撞故障分析法、不可能故障分析法等故障攻擊方法應運而生，這些方法充分結合了傳統(tǒng)密碼分析方法及軟硬件實現(xiàn)技術，在實際運行環(huán)境中具有更加廣闊的應用前景。但是，這些故障攻擊方法的故障導入范圍局限于最后若干輪，攻擊輪數(shù)范圍有限。

積分故障分析法是利用積分關系深入密碼算法內部達到最深輪數(shù)的攻擊方法，易于在物聯(lián)網(wǎng)等應用中實現(xiàn)，攻擊者通過分析內部狀態(tài)的積分關系，便可以較低的計算量和存儲量推導出正確的密鑰。目前，國內外關于ARIA算法抵抗積分故障攻擊的安全性尚未有公開發(fā)表的成果。因此，本文提出了一種針對 ARIA算法的新型積分故障分析方法，可以借助異常時鐘、微波輻射、激光照射等方式使ARIA算法內部發(fā)生錯誤，達到擴大攻擊范圍并破譯原始密鑰的目的。所提方法對提升各類高端智能卡系統(tǒng)的防護與破譯能力，具有重要的理論和實際意義。

2 研究背景

1997年，Boneh等[14-15]利用隨機故障法成功破譯了公鑰密碼算法，此后故障分析法在評測密碼體制安全性的方法中擁有重要地位。隨著故障注入精度及軟硬件逆向技術的不斷提高，對密碼載體成功實施故障攻擊所依賴的前提條件不斷減弱，成本不斷下降，故障分析環(huán)境已經(jīng)可以在一定程度上被控制，這使故障分析法逐步發(fā)展為攻擊主要密碼體制的較為容易實施且最難防御的一種攻擊技術[16-19]。

目前已有的針對ARIA算法的故障分析方法均為差分故障分析法[20-22]。在攻擊過程中，攻擊者首先將故障導入ARIA算法的最后兩輪來恢復最后一輪的子密鑰，然后對正確的密文進行解密，以獲得最后一輪的輸入，即倒數(shù)第2輪的輸出，重復以上步驟來恢復最后4輪的子密鑰，直至破譯原始密鑰為止。國內外的最新研究結果均集中于在ARIA算法的倒數(shù)第2輪導入隨機字節(jié)故障來恢復最后一輪的子密鑰。2008年，Li等[20]首次提出了針對ARIA算法的面向隨機單字節(jié)故障模型的差分故障分析法。后來，Park等[21]在相同故障模型下提出一種改進的差分故障分析法，利用線性層的差異性，實現(xiàn)以較少的故障來恢復最后一輪子密鑰，提升了攻擊效率。Kim等[22]提出了面向多字節(jié)的差分故障方法，達到以較少故障數(shù)破譯最后一輪子密鑰的目的。這些方法充分結合了傳統(tǒng)的差分分析方法以及軟硬件實現(xiàn)技術，提高了故障導入的效率。然而，在物聯(lián)網(wǎng)的應用環(huán)境中，故障可以被導入在密碼算法的任意輪數(shù)，如果故障導入點可以擴展到更大的輪數(shù)范圍，那么故障分析具有更強的威脅能力，因此，研究ARIA算法的新型故障分析方法是非常必要的。

Phan等[23]于 2006年首次提出了針對 AES（advanced encryption standard）算法的積分故障攻擊法。該方法通過選擇明文攻擊實現(xiàn)的前提條件，在AES算法運行的倒數(shù)第4輪中加入隨機故障，使其執(zhí)行某些錯誤的操作，產(chǎn)生錯誤的密文，利用中間數(shù)據(jù)的積分關系即可恢復最后一輪子密鑰；然后解密密文，破譯更多的子密鑰，直到破譯原始密鑰。雖然ARIA算法與AES算法具有相同的算法結構，但是由于ARIA算法中多輪故障路徑的擴散性和混亂性更加復雜, 大大增加了攻擊的難度，所以針對ARIA算法的積分故障分析，國內外還未有文獻發(fā)表。

本文提出了針對ARIA算法的新型積分故障分析，利用故障與子密鑰之間的積分關系，構造了 2個不同的積分區(qū)分器，從而使故障可以導入在倒數(shù)第3輪和第4輪運算中，進一步擴展了積分故障分析的攻擊范圍。由于積分故障路徑包含更多的輪數(shù)，因此攻擊者能將故障導入ARIA算法的更深輪數(shù)?，F(xiàn)有的針對ARIA算法的故障分析方法的對比如表1所示。

表1 針對ARIA算法的故障分析方法的對比

3 ARIA算法簡介

ARIA算法是一種典型的具有代換置換網(wǎng)絡結構的迭代型分組密碼，其密鑰長度為3種，分別是128 bit、192 bit和256 bit；分組長度為128 bit[3]；所對應的輪數(shù)分別為12輪、14輪和16輪，分別表示為ARIA-128、ARIA-192和ARIA-256，如表2所示。

表2 ARIA算法的密鑰長度和輪數(shù)的對應關系

ARIA算法由加密、解密和密鑰編排這3個部分組成，其中，加密部分與解密部分的過程相同，不同之處在于子密鑰的使用順序。

3.1 符號說明

記 SL（substitution layer）和 DL（diffusion layer）分別為置換層運算和擴散層運算，SL-1和 DL-1分別為置換層和擴散層的逆運算。W0、W1、W2和W3是密鑰編排方案中初始化部分產(chǎn)生的4個數(shù)據(jù)塊。

3.2 ARIA算法描述

ARIA算法的結構如圖1所示。

圖1 ARIA算法的結構

1）子密鑰加（RKA, round key addition）：子密鑰與中間狀態(tài)逐字節(jié)進行異或運算。

2）置換層：中間狀態(tài)經(jīng)過16個S盒進行置換，其中S盒有2種類型，分別用于奇輪數(shù)和偶輪數(shù)。

3）擴散層：對中間狀態(tài)進行線性映射變換，通過與一個16×16的二進制矩陣C相乘實現(xiàn)，C如下所示。最后一輪中沒有擴散層，被子密鑰加運算所替代。

3.3 密碼編排方案

密鑰編排由初始化和子密鑰生成這2個部分組成，具體如下。

1）初始化：4個 128 bit的數(shù)據(jù)塊W0、W1、W2和W3通過原始密鑰K基于3輪的Feistel網(wǎng)絡結構而產(chǎn)生。

2）子密鑰生成：通過W0、W1、W2和W3進行一系列異或運算、右移和左移操作，獲得加密變換所需各輪子密鑰。

4 ARIA算法的積分故障分析方法

4.1 故障假設和故障模型

故障假設表明了攻擊者具備的能力，本文采用明文攻擊，即攻擊者可以任意選擇明文進行處理，從而獲得相對應的密文；故障模型表明了故障的狀態(tài)，本文采用隨機單字節(jié)模型，將單字節(jié)故障引入運算過程中某些輪的指定位置，并可以隨機設定故障值。

4.2 主要過程

攻擊者選擇隨機明文并使用同一個密鑰進行加密，在運算過程中的某一輪中導入一組隨機故障，從而獲得一組錯誤的密文。故障導入既可以利用異常時鐘、異常電流、微波輻射、激光照射、渦流磁場等手段通過真實的密碼硬件來實現(xiàn)，也可以通過修改程序等軟件模擬技術的方式來實現(xiàn)。攻擊者通過構造合適的積分故障區(qū)分器，可以恢復最后一輪的子密鑰；然后解密正確的密文，獲得最后一輪的輸入，即倒數(shù)第2輪的輸出。重復上述過程，通過密鑰編排方案直至破譯原始密鑰。

4.3 3輪攻擊方案

針對ARIA算法，本文構造了一個2輪積分區(qū)分器，使得故障位置和子密鑰恢復范圍在3輪之間，從而可以破譯ARIA算法，具體算法如圖2所示。

圖2 故障導入在倒數(shù)第3輪的擴散路徑

在構造積分區(qū)分器時，需要做以下定義。

定義 1如果定義在F2n上的集合對任意0≤u＜v≤2n-1，均有 α（u）≠ α（v），則稱O為F上的活躍集[24]。

定義 2若定義在F2n上的集合對任意0≤u＜v≤ 2n-1，均有則稱P為F上的穩(wěn)定集[24]。

定義3若定義在F2n上的集合

則稱Q為F2n上的平衡集[24]。

攻擊者為了構造ARIA算法的積分區(qū)分器，需要遵循以下性質：穩(wěn)定/活躍字集通過雙射（如可逆S盒，子密鑰加）后，仍然是穩(wěn)定/活躍的；2個活躍字集的和一定是平衡字集；穩(wěn)定字集與活躍字集的和為活躍集；2個平衡字集的和為平衡字集。

結合上述定義和性質，攻擊者可以追蹤2輪運算中活躍字節(jié)的位置變化，如圖2所示。具體路徑為：第1輪中活躍字節(jié)通過擴散層變?yōu)?個活躍字節(jié)，然后這7個活躍字節(jié)經(jīng)由第2輪擴散層變?yōu)?6個活躍字節(jié)，這構成了第2輪擴散層輸出中的一組集合；通過遍歷該集合中所有字節(jié)值，使得第2輪的輸出字節(jié)的積分之和為零。因此，在2輪積分區(qū)分器中，第2輪輸出中的每個字節(jié)都是平衡的，并適用于第1輪中所有可能的活躍字節(jié)位置。

定理 1設多項式其中q是某個素數(shù)的方冪，則

定理 2若多項式是置換多項式，則aq-1=0 。

利用上述2個定理[25]來證明命題1中所構造的ARIA算法的2輪積分區(qū)分器的正確性。

命題1對于ARIA算法，如果第1輪輸入中只有一個活躍字節(jié)而其他都是穩(wěn)定字節(jié)，那么第 2輪輸出中的所有字節(jié)都是平衡字節(jié)。

證明設 γ0, γ1,γ2,…,γ15為第1輪的輸入字節(jié)，其中，只有一個字節(jié)β為變量，其他字節(jié)均為常量。假設 β=γ0，則第1輪的輸入表示為

其中，β是變量，γ1,…,γ15均為常量。根據(jù)圖2和表3中ARIA算法的運算特點，第1輪的輸出可以表示為

第2輪的輸出為

其中，h0（β）,… ,h15（β） 屬于F28域上的置換多項式。第2輪輸出中的每個字節(jié)都可以用F28上7個置換多項式的積分和來表示。

假設第2輪輸出中的第一個字節(jié)為

其中,p0（β）,…,p7（β）是F28上的置換多項式。結合置換多項式的性質，則有

因此

證畢。

根據(jù)2輪積分區(qū)分器，實現(xiàn)3輪攻擊方案的具體步驟如下。

步驟1選擇任意明文X，使用原始密鑰K進行加密，并獲得正確密文Y。

步驟2最后2輪子密鑰ekl+1具有如下關系。

表3 ARIA算法的故障路徑擴散

攻擊者在加密算法的第l-2輪中的Al-2或Bl-2中導入隨機故障，從而獲得錯誤密文，如圖2所示。在故障的導入過程中，均可以導致最后更多輪中發(fā)生變化，例如Cl-2、Al-1、Bl-2、Cl-1、Al、Bl、Cl等的字 節(jié) 變 化 會 導 致 出 現(xiàn) ΔCl-2、 ΔAl-1、 ΔBl-2、 ΔCl-1、ΔAl、 ΔBl、ΔCl，最后生成錯誤密文。攻擊者可以隨機選擇一個字節(jié)位置改變故障值，取值在[0,255]之間。因此，基于Cl-1的積分關系如下。

攻擊者通過窮盡搜索ekl+1候選值的每個字節(jié)，然后結合同一個密鑰和不同明文得到的正確和錯誤密文，進行重復操作，直到ekl+1候選集合中只有一個元素為止，即可求出正確的子密鑰ekl+1。

步驟3假設故障被導入到第l-3輪，攻擊者通過子密鑰ekl+1對正確的密文進行解密最后一輪，得到lA。此時，lA既是最后一輪的輸入，同時也是倒數(shù)第2輪的輸出，因此

攻擊者構建Cl-2的積分關系如下。

攻擊者計算擴散層中Cl-2的總和，窮盡搜索中的每個字節(jié)值。利用即可推導出子密鑰ekl。同理，通過將故障導入在第l-4輪和第l-5輪，攻擊者可以分別恢復其他2個子密鑰

步驟 4 結合密鑰編排方案，攻擊者通過最后4個子密鑰，即可推導出ARIA算法的原始密鑰。

4.4 4輪攻擊方案

在上述3輪攻擊方案中，攻擊者可以對步驟2中的第l-2輪和步驟3中的第l-3輪、第l-4輪和第l-5輪分別導入故障，從而恢復最后4輪子密鑰。然而，在輕量級環(huán)境中，隨機故障可能發(fā)生在算法的其他輪中。如果將故障位置擴展到更多輪，則積分故障分析的實現(xiàn)范圍更大。

結合命題2構建了2.5輪積分區(qū)分器，此時故障導入位置分別推廣到步驟2中的第l-3輪和步驟3中的第l-4輪、第l-5輪和第l-6輪。此時故障位置和子密鑰處于4輪運算范圍內，因此稱為4輪攻擊方案，具體如圖3所示。

圖3 故障導入在倒數(shù)第3.5輪的擴散路徑

命題2對于ARIA算法，如果第1輪輸入中只有一個活躍字節(jié)而其他都是穩(wěn)定字節(jié)，則在第3輪替代層的輸出存在3個平衡字節(jié)[5]。

4輪攻擊方案采用了與3輪攻擊方案相同的步驟1和步驟4，不同之處在于步驟2與步驟3。4輪攻擊方案的步驟2故障導入在第l-3輪的Al-3或Bl-3，可知Bl-1中有3個字節(jié)的集合是平衡集，如表4所示，則有

表4 活躍字節(jié)和相應的3個平衡字節(jié)的位置列

此時，計算Dl-1可以轉化為7個向量的異或，該步運算將數(shù)據(jù)復雜度由 2128降到 7 ×28?；?2.5輪的積分區(qū)分器，Bl-1的第j個字集是平衡字集，因此有

其中，j∈J。

在步驟3中，當故障導入在第l-4輪的Al-4或Bl-4時，可知Bl-2中有3個字節(jié)的集合是平衡集，并且

此時，j∈J，j0到j6的值如表4所示。同理有

其中，0≤j≤1 5。攻擊者可以依靠同一個密鑰和不同明文得到的不同密文，利用窮盡搜索運算求出最后4輪子密鑰。

5 理論時間復雜度

在上述分析過程中，為了計算平衡字節(jié)的積分和，攻擊者至少需要一組密文，包括一個正確的密文和255個錯誤的密文。

設η表示一個錯誤的子密鑰可以通過積分和檢查的概率，θ表示攻擊過程中窮盡搜索的子密鑰空間。當攻擊者誘導ι個密文集合時，子密鑰候選項中剩余的錯誤子密鑰數(shù)為（θ-1）ηι。如果（θ-1）ηι＜1，子密鑰候選值集合中只有唯一值，即為正確的子密鑰。

在3輪攻擊方案中，存在

如果ι＞2，那么攻擊者可以計算出真正的子密鑰。此時窮盡搜索一組密文的時間復雜度是

因而，破譯ARIA算法的最少理論時間復雜度為

在4輪攻擊方案中，存在

如果ι＞2，則攻擊者可以推導出真正的子密鑰。此時窮盡搜索一組密文的時間復雜度是

因而，恢復ARIA算法密鑰的最少理論時間復雜度為

6 實驗結果分析

實驗環(huán)境為Inter Core I7-7700K@4.2GHz、內存為 32 GB的計算機，使用 Java語言編程進行ARIA算法的加解密和攻擊操作。利用軟件模擬故障產(chǎn)生，從而得到錯誤密文，本文共進行了 1 000次實驗，將這些實驗平均分成了 5組，記為G1、G2、G3、G4和G5。在積分故障分析過程中，攻擊者至少需要一組密文，包含一個正確密文和255個錯誤密文。本節(jié)采用準確性、可靠性和耗費時間對實驗結果進行了詳細描述。

準確性是指候選密鑰數(shù)與真實密鑰數(shù)之間接近的程度。數(shù)值越接近，則實驗結果就越準確。采用均方根誤差（RMSE, root mean square error）計算式來進行計算。

其中，m為實驗次數(shù)，e為第e次實驗，φ'（e）為在第e次實驗中已恢復出的候選子密鑰的比特數(shù)，φ為真正子密鑰的比特數(shù)。均方根值越接近于0，則實驗結果就越準確，候選子密鑰的均方根值如表5與表6所示，其中m=200，φ=128、e={ 1 , …, 2 00}。實驗結果表明，在3輪和4輪攻擊方案中，分別最多僅需要3組和16組密文集合即可恢復子密鑰。

可靠性是指成功實驗在所有實驗中的比例。如表5與表6所示，在3輪攻擊方案中，子密鑰恢復的平均比例分別為0、94.8%和100%。在四輪攻擊方案中，子密鑰恢復的平均比例分別為0、0、…、0和100%。

表5 在3輪攻擊方案中恢復子密鑰的準確性和可靠性

表6 在4輪攻擊方案中恢復子密鑰的準確性和可靠性

耗費時間是指從故障導入到恢復子密鑰的時間。圖4顯示了1 000次實驗的耗時。在3輪攻擊方案中，97.7%的耗費時間處于5～10 s之間，而在4輪攻擊方案中，87%的耗費時間處于30～40 s之間。

圖4 在攻擊方案中恢復子密鑰的耗費時間

因此，在3輪攻擊和4輪攻擊方案中，窮盡搜索一組密文的實際時間復雜度分別為

則恢復ARIA原始密鑰的最少實際時間復雜度分別為

7 結束語

本文提出了基于ARIA密碼的積分故障分析方法。理論分析和實驗結果表明，在面向單字節(jié)的故障模型中，分別可以構建2個積分區(qū)分器進行故障導入來破譯ARIA算法。相較于其他故障分析方法，積分故障分析可以進一步深入算法內部更深輪數(shù)進行攻擊，在攻擊范圍上均具有顯著的優(yōu)勢。因此，以ARIA為代表的標準密碼在現(xiàn)實環(huán)境中實現(xiàn)時必須加以軟硬件防護措施進行保護，否則極易受到積分故障分析的威脅。