Gim li/Xoodoo密碼算法的不可能差分分析

樊 婷 韋永壯李靈琛

(桂林電子科技大學廣西密碼學與信息安全重點實驗室 桂林 541004)

1 引言

2018年8月，美國國家標準與技術研究院(National Institute of Standards and Technology,NIST)開始征集輕量級密碼算法，接受面向資源受限環境下帶關聯數據的輕量級認證加密(Authentica ted En cryp t ion w ith A ssocia ted D a ta,AEAD)和哈希方案的投稿，在2019年8月、2021年3月分別公布了進入第2、第3輪的候選算法[1–3]。許多方案以大狀態密碼算法作為底層置換，如384 bit的Gimli[4],320 bit ASCON[5],非線性部件采用64 bit A lzette盒的Spark le[6]以及與Keccak-p[7]置換結構類似的Xoodyak[8]等。其中，Gim li置換是由Bernstein等人[4]在CHES 2017(Cryp tographic Hardware and Embedded System s 2017)首次提出，基于Gim li置換的哈希方案(Gim li-Hash)和帶有關聯數據的認證加密方案(Gim li-AEAD)是NIST輕量級加密算法項目第2輪的候選方案[9]。Xoodoo置換是Daemen等人[10]在FSE 2018(Fast Software Encryption 2018)提出的一種新型置換結構，其設計受到Keccak-p置換的啟發。Gim li和Xoodoo置換的規模相同，二者實現性能出色、抵抗側信道攻擊能力強，在嵌入式系統、RFID、傳感器網絡等物聯網環境下，成為同時滿足安全性和性能要求的可選方案。

迄今為止，Gim li和Xoodoo置換安全性問題吸引了很多密碼學者的關注。在差分類分析方面，Liu等人[11]在美密會(CRYPTO 2020)發表的論文中提出了自動化檢測差分路徑有效性的混合整數線性規劃(M ixed Integer Linear Programm ing,M ILP)模型，搜索到6輪Gim li有效差分路徑，同時給出滿足差分路徑的消息對。2022年，譚豪等人[12]針對G im li提出一個差分傳播系統，找到了可應用于Gim li-AEAD的7輪不可能差分路徑，對11輪帶有關聯數據的Gim li-AEAD進行攻擊。在Xoodoo安全性分析方面，歐密會(EUROCRYPT 2021)會議發表的論文對差分-線性分析進一步擴展，確定了Xoodoo置換一個相關性為1的4輪旋轉差分-線性區分器[13]。2022年，一種使用可滿足性模理論(Satisfiability Modulo Theories,SMT)構造有效差分路徑的方法被Bellini等人[14]提出，尋找到多條3輪最優差分路徑。Gim li置換存在弱擴散性的特點，而針對Xoodoo以及基于Xoodoo置換的方案，大多處于低輪次的攻擊。那么，Gim li和Xoodoo置換是否存在更高輪的不可能差分區分器，以及二者是否能抵御不可能差分密碼分析仍亟待進一步研究。

鑒于上述存在的問題，本文基于Gim li/Xoodoo密碼算法的結構特點，研究了這兩個算法非線性操作與S盒之間的關系，給出二者的等價表示；針對非線性操作轉化后的幾類S盒，利用M ILP技術進行建模，提出了用于Gim li/Xoodoo密碼算法的不可能差分分析自動化分析模型。此外，為了驗證區分器的正確性，本文結合“二分法”思想，給出了一種用于檢測不可能差分區分器矛盾點的新方法。該方法能夠快速定位矛盾點，具備高效驗證區分器正確性的優勢。結果表明：Gim li存在10輪不可能差分區分器；Xoodoo存在4輪不可能差分區分器。與已有結果相比，Gim li的新不可能差分區分器輪數提高了3輪。

后續章節組織如下，第2節描述Gim li/Xoodoo算法的具體步驟；第3節介紹基于M ILP面向比特的不可能差分區分器搜索模型；第4節闡述G im li/Xoodoo中非線性操作與S盒之間的等價表示；第5節給出Gim li和Xoodoo置換不可能差分區分器以及檢測矛盾位置的新方法，第6節進行總結。

2 算法介紹

2.1 符號說明

符號表示如表1所示。

表1 符號說明

2.2 Gim li算法

入和輸出。SP盒操作表達式為

進一步，得到(Xout,Yout,Zout)和(Xin,Yin,Zin)之間關系為

2.3 Xoodoo算法

X oodoo算法狀態大小與G im li相同，即 SX=384，分布在4× 3× 32的狀態矩陣中(如圖2所示)，SX=(S x,y)(0≤x≤3,0≤y ≤2)，每個字長度為32 b it，即Sx,y ∈F232×3，共迭代12輪(-11≤r ≤0)，輪函數被定義為FX=ρeast?χ ?τ ?ρwest?θ，其中χ是唯一的非線性部件，5個步驟具體定義為

圖1 Gim li狀態矩陣

圖2 Xoodoo狀態矩陣

3 基于M ILP面向比特的不可能差分模型

M ILP模型用于解決最優化問題，在密碼學分析領域，可將密碼算法安全性分析問題轉化為M ILP問題。總的來說，是用不等式約束條件表示線性、非線性操作，求目標函數的最優解。對于不可能差分搜索模型而言，不需要設定目標函數，只需固定輸入和輸出差分，然后在特定的約束條件下，觀察模型是否有解。若模型無解，則為不可能差分。接下來，主要介紹不可能差分分析模型中線性操作和非線性操作的建模。

(1)I型XOR操作。對于a ⊕b=c(a,b,c都表示單比特)，用式(6)約束條件表示

(2)II型XOR操作。對于a ⊕b ⊕c=d(a,b,c,d都表示單比特)，用式(6)約束條件表示

(3)線性操作。線性操作一般包括循環移位、移位和交換操作等，可用線性等式有效地描述。以G im li中SP盒的循環移位操作“＜＜＜”為例，設Gim li一個字的輸入差分為x=(x31,x30,...,x0)，經過循環左移24 bit后，輸出差分為y=(y31,y30,...,y0)，約束條件為

(4)S盒操作。考慮差分值通過S盒的傳播性質，用Sun等人[15]提出的凸殼H-Representation(通過線性(不)等式切割歐拉空間獲得的多面體)。設x=(x0,x1,...,x p)，p=w+v(其中w和v分別是S盒的輸入和輸出規模)是p維可能的差分模式。則可用以下m個不等式約束條件來表示，其中a i,j(0≤i≤m-1,0≤j ≤p-1)是SageM ath[16]生成的二進制系數

(5)額外條件。限制輸入輸出差分均只有1 bit或1 個S 盒活躍，即添加2 種額外約束條件，(x0,x1,...,x n)=0 和(x0,x1,...,x n)r=0。其 中，(x0,x1,...,x n)r是初始輸入差分(x0,x1,...,x n)經過r輪迭代后的輸出差分，n為分組長度。

4 非線性操作與S盒的等價表示

在本節中，主要介紹如何將Gim li算法的SP盒、Xoodoo算法的χ操作等價表示為幾類常規S盒(即輸入為wbit，輸出規格為vbit)，給出每一種S盒替換表。

4.1 Gim li算法SP盒等價表示

G im li置換的非線性操作SP盒與普通w×v的S盒不同，它包含循環移位、異或、移位、與操作和或操作。觀察式(2)—式(4)，進行分解，SP盒等價表示為3種S盒(S1,S2,S3)和一個線性操作，如圖3所示。

圖3 Gim li置換SP盒等價表示

S1,S2,S3盒和線性運算L表達式分別為

S2盒。當i=2時，S2盒規模為7進3出，(A,B,C,D,E,F,G)為7 bit輸入，(Zout,Yout,Xout)為3 bit輸出。遍歷7 bit輸入(0000000～1111111)，計算對應的3 bit輸出，則得到S2盒置換表。

S3盒。當i=1時，S1盒規模為5進3出，(A,B,C,D,E)為5 bit輸入，(Zout,Yout,Xout)為3 bit輸出。遍歷5 bit輸入(00000～11111)，計算對應的3 bit輸出，則得到S3盒置換表，如表2。

表2 S1,S2和S3盒置換表3 bit輸出

4.2 Xoodoo算法χ 操作等價表示

χ是Xoodoo中唯一的非線性運算，包含AND操作。將χ看作一個3進3出的S盒，遍歷3 bit輸入SX[x][y][z] ,S X[x][y+1][z],S X[x][y+2][z]的值，計算相應的輸出值，形成的3 bit對合S盒如表3所示。

表3 Xoodoo算法操作χ 的S盒表示

5 Gim li和Xoodoo的具體應用

本部分首先構建基于M ILP技術的Gim li/Xoodoo算法不可能差分區分器自動化搜索模型。對非線性操作建模主要是將轉化后的幾類S盒，構建差分分布表(Difference Distribution Table,DDT)。再將DDT表中所有可能的差分傳播模式放入SageM ath軟件，調用sage.geometry.polyhedron中的不等式生成函數，將所有可能的輸入輸出差分模式表示為一個不等式系統。對線性操作建模參考文章第3節列出的不等式約束。最后，本文提出一種檢測矛盾點的新方法，從而驗證不可能差分區分器的正確性。

5.1 Gim li算法不可能差分區分器搜索模型

Gim li輪函數包含4種操作：移位、SP盒、2種Swap、輪常數加，這里不考慮輪常數的影響。以下涉及的所有變量都表示狀態差分，假設ΔSGr[m][n][i] 和ΔSGr-1[m][n][i]分 別是第r輪的輸入差分和輸出差分。本部分若無特殊說明，m,n,i的取值范圍為0≤m≤2, 0≤n≤3, 0≤i≤31。

(1)非線性操作SP盒約束條件。由在4.1節可知，對SP盒建模等價于對S1盒、S2盒、S3盒和線性操作L分別進行建模。注意到，雖然S1盒的規模大，維度高，元素數量多，但僅用12個不等式就可以表示S1的差分傳播過程。S1盒、S2盒、S3盒和線性操作L的約束條件分別為

(2)線性操作約束條件。Gim li算法的線性操作包括移位、SmallSwap和BigSwap。3種操作都可用等式約束條件進行刻畫，細節請參考第3節中“線性操作”的約束條件表示。

(4)模型求解。將所有不等式約束條件放入Gurobi[17]求解器，若M ILP模型無解，得到一條Gim li的10輪不可能差分區分器，以十六進制按狀態矩陣表示為

5.2 Xoodoo算法不可能差分區分器搜索模型

Xoodoo輪函數共包含5個操作：線性層θ、循環移位ρwest、輪常數加τ、非線性層χ和循環移位ρeast。這里不考慮輪常數加操作τ的影響，只需要對線性層θ、循環移位ρwest、非線性層χ和循環移位ρeast4個操作進行建模，下面將分別進行介紹。以下涉及的所有變量都表示狀態差分，ΔSXr[x][y][z]和 ΔSXr+1[x][y][z]分 別是第r輪和r+1輪的輸入差分，M1[x][z],M2[x][j][z],N3[x][j][z]都是生成的中間狀態變量。本部分若無特殊說明，x,y,z的取值范圍為0≤x≤3, 0≤y,j≤2, 0≤z ≤31。

(1)線性層θ約束條件。根據θ操作的定義式，分為3步，首先將輸入差分初始狀態的3個平面進行疊加，然后將疊加后的平面進行循環移位，最后與輸入差分的初始狀態異或，得到經過θ操作后的中間狀態。∑

(2)循環移位ρwest約束條件。循環移位首先以字作為單位進行位置變換，再基于比特進行變換。只改變狀態差分的位置，不產生新的差分變量：M2[x][1][z]=M2[x-1][1][z],M2[x][2][z]=M2[x][2][z-11]。

(3)非線性層χ約束條件。狀態矩陣中的元素以3 bit為一列進行狀態更新，更新時差分值會發生改變，產生新差分變量。在步驟(1)和步驟(2)的基礎上，生成4.2節提出的非線性層χ的等價S盒DDT表，用3 bit S盒的約束條件來描述非線性操作χ，為了方便表示，令M2[x][0][z]=P,M2[x][1][z]=Q,M2[x][2][z]=T,N3[x][0][z]=X,N3[x][1][z]=Y,N3[x][2][z]=Z。

(4)循環移位ρeast約 束條件。Δ SXr+1[x][1][z]=N3[x][1][z-1], Δ SXr+1[x][2][z]=N3[x-2][2][z-8]。

(5)額外條件。添加3個額外約束條件，即輸入差分Δ SX-11[1][0][0]=1 ,Δ SX-11[1][1][0]=1和輸出差分ΔSX-7[1][0][0]=1。

(6)模型求解。將所有不等式約束條件放入Gurobi求解器，若M ILP模型無解，得到一條Xoodoo的4輪不可能差分區分器，以十六進制按狀態矩陣表示為

5.3 矛盾點驗證

對于Gim li/Xoodoo等大狀態密碼算法，由于狀態較大時，矛盾點之間可能具有依賴性，它們不是獨立的，使用Cui等人[18]逐條刪除比特間的聯系無法找到矛盾點。所以，本節給出了一個基于“二分法”思想的新驗證算法。該算法分為2步，第1步劃分區間，判斷矛盾點所在區間；第2步在第1步尋找的區間中確定矛盾點的具體位置，遍歷矛盾點位置的取值，查看解的集合。

假設搜索到分組長度為nbit的密碼算法一條r輪不可能差分區分器Δin→Δout，那么在[r/2]輪和[r/2]+1輪之間一般存在矛盾點。令α=(α0,α1,...,αn-1)表 示[r/2]的 輸出差分，第[r/2]+1的輸入差分表示為β=(β0,β1,...,βn-1)。尋找矛盾點時，直接刪除(α0,α1,...,αn-1)=(β0,β1,...,βn-1)中的某些不等式，若刪除后，該模型由無解變為有解，可判定該中間變量所在的比特位置即為矛盾點。具體驗證算法見算法2。

5.3.1實際應用

(1)Gim li的10輪不可能差分區分器。對于Gim li算法，之前最長的不可能差分路徑是由譚豪等人[12]提出的，利用AND,OR操作的差分傳播性質找到了7 輪不可能差分區分器。在5.1 節構建關于Gim li算法不可能差分區分器新型搜索模型，考慮輸入差分和輸出差分漢明重量均為1的情況，最終搜索到464條10輪Gim li的不可能差分區分器，這里以5.1節列出的路徑為例，使用算法2進行驗證。

算法2 新驗證算法

由圖4可知，在第5輪輸出的{α108,α126}位置找到2個矛盾點。此時，模型有解當且僅當集合T1取{α108=1,α126=1}，集 合T2取{β108=0,β126=0}。這意味著T1與T2不存在交集，不可能差分區分器驗證成功。

(2)Xoodoo的4輪不可能差分區分器。經過驗證，在第2輪輸出(第3輪輸入)位置找到矛盾點{α69,α78,α257,α280,α290,α313}，此時集合T1取{α18=1,α27=1,α295=1,α318=1,α328=1,α351=1}，集合T2取{β18=0,β27=0,β295=0,β318=0,β328=0,β351=0}。T1與T2不存在交集，4輪Xoodoo的不可能差分區分器驗證成功，具體結果對比見表4。

6 結束語

本文給出了G im li/Xoodoo密碼算法非線性操作與S盒之間的等價表示，構建了相應的M ILP模型來描述兩個算法的不可能差分傳播路徑。利用自動化分析工具，對Gim li/Xoodoo密碼算法抵抗不可能差分分析的能力進行了評估，發現了Gim li的10輪不可能差分區分器，相比Tan等人的結果，本文的區分器提高了3輪。Xoodoo密碼算法差分類分析方面，最優差分區分器目前只搜索到3輪，本文發現了4輪Xoodoo的不可能差分區分器。進一步，為了驗證區分器的正確性，利用“二分法”設計了一種新的驗證算法，提高了驗證效率，大大縮短了驗證時間，為以后的分組密碼算法的設計與分析提供了強有力的支撐。