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

樊 婷 韋永壯李靈琛

(桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室 桂林 541004)

1 引言

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

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

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

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

2 算法介紹

2.1 符號說明

符號表示如表1所示。

表1 符號說明

2.2 Gim li算法

入和輸出。SP盒操作表達(dá)式為

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

2.3 Xoodoo算法

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

圖1 Gim li狀態(tài)矩陣

圖2 Xoodoo狀態(tài)矩陣

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

M ILP模型用于解決最優(yōu)化問題，在密碼學(xué)分析領(lǐng)域，可將密碼算法安全性分析問題轉(zhuǎn)化為M ILP問題?？偟膩碚f，是用不等式約束條件表示線性、非線性操作，求目標(biāo)函數(shù)的最優(yōu)解。對于不可能差分搜索模型而言，不需要設(shè)定目標(biāo)函數(shù)，只需固定輸入和輸出差分，然后在特定的約束條件下，觀察模型是否有解。若模型無解，則為不可能差分。接下來，主要介紹不可能差分分析模型中線性操作和非線性操作的建模。

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

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

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

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

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

4 非線性操作與S盒的等價(jià)表示

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

4.1 Gim li算法SP盒等價(jià)表示

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

圖3 Gim li置換SP盒等價(jià)表示

S1,S2,S3盒和線性運(yùn)算L表達(dá)式分別為

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

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

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

4.2 Xoodoo算法χ 操作等價(jià)表示

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

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

5 Gim li和Xoodoo的具體應(yīng)用

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

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

Gim li輪函數(shù)包含4種操作：移位、SP盒、2種Swap、輪常數(shù)加，這里不考慮輪常數(shù)的影響。以下涉及的所有變量都表示狀態(tài)差分，假設(shè)Δ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節(jié)可知，對SP盒建模等價(jià)于對S1盒、S2盒、S3盒和線性操作L分別進(jìn)行建模。注意到，雖然S1盒的規(guī)模大，維度高，元素?cái)?shù)量多，但僅用12個(gè)不等式就可以表示S1的差分傳播過程。S1盒、S2盒、S3盒和線性操作L的約束條件分別為

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

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

5.2 Xoodoo算法不可能差分區(qū)分器搜索模型

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

(1)線性層θ約束條件。根據(jù)θ操作的定義式，分為3步，首先將輸入差分初始狀態(tài)的3個(gè)平面進(jìn)行疊加，然后將疊加后的平面進(jìn)行循環(huán)移位，最后與輸入差分的初始狀態(tài)異或，得到經(jīng)過θ操作后的中間狀態(tài)?！?/p>

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

(3)非線性層χ約束條件。狀態(tài)矩陣中的元素以3 bit為一列進(jìn)行狀態(tài)更新，更新時(shí)差分值會發(fā)生改變，產(chǎn)生新差分變量。在步驟(1)和步驟(2)的基礎(chǔ)上，生成4.2節(jié)提出的非線性層χ的等價(jià)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)循環(huán)移位ρeast約 束條件。Δ SXr+1[x][1][z]=N3[x][1][z-1], Δ SXr+1[x][2][z]=N3[x-2][2][z-8]。

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

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

5.3 矛盾點(diǎn)驗(yàn)證

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

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

5.3.1實(shí)際應(yīng)用

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

算法2 新驗(yàn)證算法

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

(2)Xoodoo的4輪不可能差分區(qū)分器。經(jīng)過驗(yàn)證，在第2輪輸出(第3輪輸入)位置找到矛盾點(diǎn){α69,α78,α257,α280,α290,α313}，此時(shí)集合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的不可能差分區(qū)分器驗(yàn)證成功，具體結(jié)果對比見表4。

6 結(jié)束語

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