侯鋮安,劉美成

(1. 中國科學院信息工程研究所 信息安全國家重點實驗室,北京 100093;2. 中國科學院大學 網絡空間安全學院,北京 100093)

現(xiàn)代密碼學發(fā)展至今，已經衍生出對稱密碼學和非對稱密碼學(公鑰密碼學)兩大方向。它們的主要區(qū)別是在對稱密碼算法中，發(fā)送者和接收者共享同一個秘密密鑰；而在非對稱密碼中，雙方需要分別使用不同而又緊密相關的2個密鑰。對稱密碼算法在效率方面具有顯著的優(yōu)勢，而非對稱密碼算法則可以提供豐富的安全功能。只有將對稱密碼算法與非對稱算法結合起來，才能滿足人們對安全和效率的需求。

傳輸層安全(Transport Layer Security，TLS)協(xié)議綜合應用了對稱密碼和非對稱密碼算法，常用于安全超文本傳輸協(xié)議(Hyper Text Transfer Protocol Secure，HTTPS)，在計算機網絡通信安全中起著至關重要的作用。然而，TLS協(xié)議中使用的密碼算法在設計和實現(xiàn)上存在漏洞，近年來有許多對TLS協(xié)議的攻擊被提出[1-2]。這些攻擊表明現(xiàn)有的密碼算法還遠遠不能滿足人們的安全需求。同時也帶給密碼算法設計者一個重要的設計原則，就是在密碼算法中必須同時考慮數(shù)據(jù)的機密性和完整性，也就是認證加密(Authenticated Encryption，AE)。目前，密碼學界已經在研究和標準化認證加密算法方面做出了許多努力。例如，經過 CAESAR競賽，ASCON算法在安全和效率方面展現(xiàn)出了強大的實力[3]。

在醫(yī)療、分布式控制系統(tǒng)、物聯(lián)網等新興領域，常常需要將一些資源非常有限的設備進行連接，并協(xié)同工作。但目前廣泛應用的密碼算法大都是為個人電腦或服務器環(huán)境而設計，因此，不適用于資源受限的設備。在這樣的背景下，輕量級密碼算法應運而生。美國標準與技術研究所(National Institute of Standards and Technology，NIST)也開始公開征集、評估和標準化輕量級密碼算法(Lightweight Cryptography，LWC)，以用于其他NIST 密碼標準無法工作的資源受限場景。2021年3月，經過3輪篩選，NIST公布了包括 ASCON和Elephant 在內的10個算法進入最終的候選列表，并將在接下來一段時間中對這10個算法進行更全面而深入地評估。

Elephant算法是由Beyne等提交到 NIST 的 LWC 競賽的輕量級認證加密算法[4]，并于 2020年發(fā)表在IACRTransactionsonSymmetricCryptology(ToSC)。Elephant 算法具有狀態(tài)小、并行度高等特性，其底層使用了較為成熟的 Spongent結構和Keccak-f[200]置換，這些優(yōu)點使得Elephant從LWC競賽的候選算法中脫穎而出，進入到最終列表的評估。因此，分析Elephant算法的安全性具有十分重要的理論價值和現(xiàn)實意義。目前，除了設計者在理想置換模型下的安全分析之外，Zhou等[5]使用優(yōu)化插值攻擊以298.3的復雜度實現(xiàn)了對8輪 Elephant-Delirium實例的密鑰恢復攻擊，該結果于2021年4月正式發(fā)表在TheComputerJournal上，也是目前為止唯一的第三方分析。本文利用立方攻擊的思想改進了這一攻擊結果，將時間復雜度降到295.2。除了理論分析，本文還首次實現(xiàn)了對6輪Elephant-Delirium 實例的實際密鑰恢復攻擊。

1 預備知識

1.1 布爾函數(shù)與莫比烏斯變換

(1)

使用莫比烏斯變換可以將一個布爾函數(shù)f從它的真值表形式轉換為ANF，也可以反過來從ANF轉換為真值表。對于一個n元布爾函數(shù)，莫比烏斯變換需要n2n-1次異或運算。

1.2 高階差分攻擊與立方攻擊

對布爾函數(shù)的每一次求導都會降低導數(shù)的代數(shù)次數(shù)[6]。因此，對于任何維數(shù)大于該函數(shù)的代數(shù)次數(shù)的子空間，其對應的導數(shù)為

(2)

對于一個特定輪數(shù)的密碼算法，如果能夠找到某個輸入子空間，使得這個子空間的維數(shù)超過輸出函數(shù)的代數(shù)次數(shù)，那么對這個輸入子空間對應的輸出子空間進行求和將恒等于0，也就是得到了一個零和區(qū)分器，然后可以利用這個零和區(qū)分器來實現(xiàn)密鑰恢復攻擊。不難看出，輸出函數(shù)的代數(shù)次數(shù)對高階差分攻擊至關重要。但一般而言，需要很高的復雜度才能得到輸出函數(shù)的準確次數(shù)。因此，在實際中人們常常只是估計輸出函數(shù)代數(shù)次數(shù)的上界。對于一個輪函數(shù)的代數(shù)次數(shù)為d的密碼算法，由于第二輪輸入的代數(shù)次數(shù)為d，第二輪的輸出函數(shù)關于第二輪輸入的代數(shù)次數(shù)也為d，因此，第二輪輸出函數(shù)關于第一輪輸入的代數(shù)次數(shù)不超過d2，由歸納法可知，經過r輪迭代后的輸出函數(shù)的代數(shù)次數(shù)不會超過dr。例如，Keccak-f[200]的代數(shù)次數(shù)為2，那么經過4輪后輸出函數(shù)的代數(shù)次數(shù)不會超過16。因此，根據(jù)高階差分性質，任意超過16維的子空間都對應一個4輪的零和區(qū)分器。

立方攻擊是高階差分攻擊的一種變體，由Dinur等[7]在2009年的歐密會上提出。立方攻擊作為一種用來分析對稱密碼算法的通用方法，已經成功用于攻擊許多密碼體制。立方攻擊將輸出比特的ANF看作是關于n個秘密變量x=(x1,x2,…,xn)和m個公開變量v=(v1,v2,…,vm)的多項式，記為f(x,v)。對于任何一個集合I={i1,i2,…,i|I|}?{1,…,m}，f(x,v)可以寫作

f(x,v)=tIp(x,v)?q(x,v)，

其中，tI=vi1vi2…vi|I|稱為極大項，極大項中的變量vi1,vi2,…,vi|I|稱為立方變量。p(x,v)不含有立方變量，稱為tI對應的超級多項式，且q(x,v)至少比tI少一個變量。

(3)

恰當?shù)剡x擇立方變量將使得超級多項式在變量和次數(shù)方面都比原多項式簡單得多，因此，更有利于分析函數(shù)的性質。

1.3 優(yōu)化插值攻擊

優(yōu)化插值攻擊[8]是對插值攻擊[9]的改進，利用莫比烏斯變換降低了攻擊的復雜度。

插值攻擊考慮一個目標比特a，其ANF可以用密文C和密鑰K表示，即

2 Elephant 密碼算法

Elephant算法是由Beyne等[4]提交到 NIST 的 LWC 競賽的輕量級認證加密算法，是LWC競賽最終列表中的10個算法之一。Elephant算法的結構是基于nonce的先加密后認證的構造，根據(jù)底層所用置換的不同，Elephant算法共有Dumbo、Jumbo和Delirium 3個實例，分別使用的是Spongent-π[160]、Spongent-π[176]和Keccak-f[200]置換。每一個實例都使用一個置換和一個線性反饋移位寄存器來將密鑰擴展為掩碼。這個過程是可逆的，如果可以恢復出秘密掩碼，那么就可以直接逆推得到密鑰。本文關注的是使用Keccak-f[200]置換的Delirium實例，此后所說的Elephant算法都特指Delirium實例。

Elephant算法的內部狀態(tài)有200比特，初始時用96比特隨機數(shù)和104比特的0進行填充。然后，將密鑰擴展后的200比特掩碼異或到初始狀態(tài)上。經過18輪Keccak-f[200]置換后，再將掩碼異或到所有狀態(tài)上，得到輸出狀態(tài)。對于一個200比特的明文分組，異或輸出狀態(tài)后得到相應的密文。本文只使用一個明文分組進行選擇明文攻擊，所以略去了Elephant算法關于分組的處理和認證階段。

Keccak-f[200]置換有200比特內部狀態(tài)，總共18輪。這200比特的狀態(tài)X∈{0,1}200被表示為一個5×5×8的數(shù)組a∈{0,1}5×5×8。對于數(shù)組a中下標為(x,y,z)∈5×5×8的元素ax,y,z，對應的是X的第8·(5y+x)+z比特，即ax,y,z=X[8·(5y+x)+z]。Keccak-f[200]的每一輪置換都對所有200比特狀態(tài)依次進行5個操作θ,ρ,π,,ι，其中，是唯一的非線性操作，它們的定義如下：

ρ:ax,y,z←ax,y,z+tx,y，

π:ax,y,z←ax+3y,x,z，

ι:ax,y,z←ax,y,z+RCi,x,y,z，

注意到Keccak-f[200]中的非線性操作的代數(shù)次數(shù)只有2次，這一性質被許多攻擊所利用。

3 6輪Elephant算法的實際密鑰恢復攻擊

由于Elephant算法的非線性操作可以看作40個并行的5比特S盒，輸出時異或的秘密掩碼可以看作是輪密鑰，因此，本文采用了分組密碼分析中常見的區(qū)分器-解密的攻擊方式進行密鑰恢復攻擊。具體來說，如果有一個r輪的區(qū)分器，那么首先猜測輪密鑰，然后將r+1輪的輸出進行解密。如果猜測的輪密鑰恰好是正確的輪密鑰，那么解密出來的結果恰好是r輪的輸出，因此，滿足區(qū)分器的性質。另外，如果猜測的輪密鑰是錯誤的，則解密出來的結果近似于均勻分布，因此，不能觀察到區(qū)分器的性質。由于40個S盒是相互獨立的，因此，可以利用分治法來恢復每個S盒對應的輪密鑰，也就是Elephant算法中的秘密掩碼。

3.1 5輪零和區(qū)分器的構造

基于Keccak-f[200]置換的代數(shù)次數(shù)為2的特點，本文利用高階差分性質來構造零和區(qū)分器。Elephant算法加密時的初始狀態(tài)是用96比特的隨機數(shù)(nonce)和104比特的0進行填充的，然后該初始狀態(tài)異或200比特的秘密掩碼。其中，nonce是可以控制的，即可以選擇的子空間的最大維數(shù)是96維。根據(jù)高階差分性質，任何65維的子空間都可以構造一個6輪的零和區(qū)分器，因為65>26。由于這個零和區(qū)分器的復雜度遠遠超過了人們的計算能力，所以只能降低攻擊的輪數(shù)。一個直接的想法就是用33維的子空間構造5輪的零和區(qū)分器，或者用17維的子空間構造4輪的零和區(qū)分器。事實上，可以利用CP-kernel性質(CP-kernel性質是Keccak的設計者提出的θ操作的一個性質),將使用17維子空間的4輪零和區(qū)分器推進到5輪。

要將4 輪的零和區(qū)分器推進1輪，則17 維的子空間必須滿足一定的條件?？梢詮拇鷶?shù)次數(shù)的角度來看這個問題：之所以可以用17維的子空間得到4輪的零和區(qū)分器，是因為4輪輸出函數(shù)的代數(shù)次數(shù)至多為16，而17維的子空間對應的極大項是一個17次項，因此，其系數(shù)必然為0。如果選擇17維子空間對應的立方變量，在經過1輪置換后沒有乘出二次項，則再經過4輪置換，其輸出函數(shù)中不可能出現(xiàn)17 個變量的乘積項，所以子空間的求和仍然是 0。從另一個角度說，在遍歷 17 維輸入子空間的時候，恰好遍歷了1 輪置換的某個17 維輸出子空間。而這個1 輪置換的17維輸出子空間，又可以看作是4 輪零和區(qū)分器的輸入子空間，也就必然滿足零和的性質。綜上所述，本研究的問題轉化為尋找滿足條件的 17 維子空間。

這個問題可以使用混合整數(shù)線性規(guī)劃模型進行建模。首先，用(x0,…,x95),xi∈2來表示可以控制的96比特隨機數(shù)(nonce)。當xi=1時，表示將其選為立方變量，否則表示不選為立方變量。其次，本研究的目標是最大化子空間的維數(shù)，也就是最大化立方變量的個數(shù)，即約束條件是經過1輪置換后，立方變量之間不會相互乘出二次項，這需要借助1輪 Keccak-f[200]的ANF來給出。將所有的隨機數(shù)比特都用一個布爾變量來表示，其他比特賦值為0。然后，使用 SageMath 軟件進行符號計算，得到1輪Keccak-f[200]關于nonce的 ANF。所得的 ANF 中包含一些二次項，每一個二次項，不妨設為xixj，給出一個約束條件xi+xj≤1，即這2個變量不能同時選為立方變量。最后，使用 Gurobi 軟件求解這個 MILP 模型，即可得到滿足條件的子空間的最大維數(shù)，給出所選的立方變量。

在選擇立方變量時，必須考慮Keccak-f[200]的CP-kernel性質，因為不考慮CP-kernel性質時，以上模型給出的子空間的最大維數(shù)只有8維，不能滿足5輪零和區(qū)分器所要求的17維子空間。觀察θ操作的表達式不難發(fā)現(xiàn)，如果將ax,y,z和ax,y′,z,y′≠y同時選為相等的立方變量。則在它們的和中，立方變量將被消掉。這一性質是異或的直接結果，稱為CP-kernel性質。θ操作的目的是提供擴散，而CP-kernel性質阻止了擴散。因為ρ和π操作都只是比特位置的移動而不存在擴散，所以CP-kernel性質使得Keccak-f[200]的θ，ρ，π操作退化為比特置換。這樣一來，就有可能找到更大維數(shù)的子空間。實驗的結果也驗證了這一點，在考慮了CP-kernel性質后，子空間的最大維數(shù)達到28維，因此，可以從中選取17維的子空間來構造零和區(qū)分器。

3.2 攻擊過程

本研究的攻擊是一個選擇明文攻擊，只使用一個明文塊。不妨固定M=0200，則加密得到的密文C=P(N‖0104?maskK)?maskK。其中，P是約簡輪數(shù)的Keccak-f[200]置換，maskK=P(K‖072)是由密鑰導出的秘密掩碼。

因為θ,ρ,π操作都是線性操作，不會破壞零和的性質，所以5輪的零和區(qū)分器可以直接推進到第6輪的操作之前。那么，距離6輪的輸出，還有,ι和異或秘密掩碼3個操作。其中，ι操作只是異或了第6輪的輪常數(shù)，可以等效到異或秘密掩碼的操作中。因此，需要考慮和異或等效掩碼2個操作。

(4)

反之，如果猜測錯誤，則得到的結果近似于均勻分布，那么5個比特同時滿足零和的概率近似于2-5。在實驗中發(fā)現(xiàn)，對于每一個S盒，除了正確的掩碼，還可能有至多3個錯誤的掩碼也滿足零和的性質。為了降低錯誤的概率，使用3個17維的子空間。假設錯誤的結果為均勻分布，則錯誤的掩碼同時在3個子空間都滿足零和的概率為2-15。實驗結果表明，使用3個不同的零和區(qū)分器，只有正確的掩碼才能同時滿足零和的性質。

對所有40個S盒都進行以上過程，就可以恢復出200比特的掩碼，進而恢復出密鑰。

整個攻擊的過程如算法1所示。

算法1：對6輪Elephant算法的密鑰恢復攻擊

輸入:MILP模型給出的任意18個立方變量I={x0,…,x17}

輸出：200比特秘密掩碼maskK

遍歷18個立方變量的取值，任意給定nonce其他比特的取值，構建集合NI

對NI中的每一個nonce，設置明文M=0200，訪問加密函數(shù)得到對應的密文，并異或輪常數(shù)，得到集合CI

fors←0 to 39 do

fori←0 to 25do

ifsum0?sum1=0 andsum0?sum2=0 andsum2?sum3=0 then

end if

end for

end for

3.3 攻擊復雜度分析

總共需要對3個17維子空間，這可以從18維子空間中選取。而且，這3個17維子空間可以共享同一個16維子空間，這樣一來，3個子空間的并集大小為218，而不是3×217。我們需要218的數(shù)據(jù)復雜度，同時存儲這些數(shù)據(jù)需要218的空間復雜度。

然后，對40個S盒分別進行猜測，每個S盒的輸出有5比特，共25種可能性。對于每一種可能的取值，需要在218的數(shù)據(jù)上進行求和，然后根據(jù)是否滿足零和性質來篩選出正確的掩碼。因此，攻擊的時間復雜度為40×25×218≈229。

3.4 攻擊的實現(xiàn)

為了驗證以上理論，使用C++編程實現(xiàn)了攻擊。隨機生成了超過100個密鑰，然后調用Elephant的參考代碼進行加密，最終以100%的成功率恢復出所有的秘密掩碼。實驗在裝有Ubuntu Server 21.04操作系統(tǒng)的臺式機上運行，使用單核CPU(AMD Ryzen7-3700X，3.6 GHz)。本文所實現(xiàn)的串行版本，計算1個17維的子空間對應的密文空間，需要大約1.2 s。在準備好所需的nonce-密文對后，平均一次密鑰恢復攻擊需要大約2.8 s時間。同時，使用并行計算還可以進一步減少運行時間，既可以對40個S盒并行執(zhí)行，也可以在每次判斷零和時并行執(zhí)行。

4 8輪Elephant算法的密鑰恢復攻擊

4.1 攻擊過程

本文同樣考慮第6輪的輸出比特。一方面，可以逆向計算2輪Keccak-f[200]得到關于第8輪輸出的密文表達式;另一方面，可以計算立方和得到關于輸入明文的超級多項式。本文的改進主要針對6輪的零和區(qū)分器。通過立方攻擊放寬了零和的限制，從而可以使用更小維數(shù)的子空間。一個子空間的超級多項式可以給出一個方程：

其中，GK(VP)是VP對應的超級多項式，VC是VP加密后得到的密文空間。

此時，等式左右兩邊都是非線性的多項式，因此，都必須進行線性化。對于等式的左邊，使用與Zhou等[5]相同的方法來進行線性化，即需要引入223.1個新變量來線性化。因此，只需要考慮等式右邊的超級多項式的線性化。

在線階段，攻擊的步驟與Zhou等[5]類似。首先，對67維子空間的所有nonce和固定的明文M=0200加密得到對應的密文,用這些密文計算出Mu，得到一個比特向量；然后對這個比特向量做莫比烏斯變換，從所得的結果中去除子空間對應的系數(shù)，即是一個等效密鑰的系數(shù)。在遍歷了223.11個子空間后，即可求解方程組得到所有等效密鑰的值，進而恢復出密鑰比特。

4.2 攻擊復雜度分析

與Zhou等[5]的攻擊相比，本研究的攻擊使用了維數(shù)更小的子空間和更多的變量。在離線階段，需要恢復223.11個超級多項式，每個超級多項式需要求解213.3個變量的線性方程組。在線階段時，需要遍歷67維子空間，并存儲所得的密文。因此，數(shù)據(jù)復雜度和空間復雜度都是267。計算一次莫比烏斯變換需要266×log267次異或操作，總共需計算223.11次莫比烏斯變換。因此，總的攻擊復雜度約為223.11×266×log267≈295.2。

5 總結與展望

本文對 Elephant-Delirium 算法的安全性進行分析，提出了6輪的實際密鑰恢復攻擊并改進了8輪的密鑰恢復攻擊。

對于6輪的實際密鑰恢復攻擊，采用了區(qū)分器-解密的攻擊方式。首先，利用底層的Keccak-f[200]置換代數(shù)次數(shù)為2的特點，使用17維子空間構造出4輪零和區(qū)分器；然后,利用MILP模型并借助 Keccak-f[200]置換中θ操作的CP-kernel性質阻止立方變量的擴散，使得子空間對應的 17個立方變量在經過1輪Keccak-f[200]置換后仍然是1次，從而得到5輪零和區(qū)分器。利用構造出的5輪零和區(qū)分器對猜測的秘密掩碼的正確性進行區(qū)分，最終恢復出所有的秘密掩碼。

另外，利用立方攻擊的思想改進了 8 輪密鑰恢復攻擊的結果。在優(yōu)化插值攻擊中使用超級多項式來建立方程，擴展了現(xiàn)有的使用零和區(qū)分器的方法。將攻擊的時間復雜度從298.3降低到295.2，空間復雜度和數(shù)據(jù)復雜度也都有降低。值得注意的是，本研究的方法依然可能存在改進空間。例如本文對超級多項式的項數(shù)上界只是粗略的估計，如果可以更加精確地估計這個上界，攻擊的復雜度也會隨之降低。