ARX結構分組密碼積分區分器的自動化搜索

韓亞，王明生

（1. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；2. 中國科學院大學網絡空間安全學院，北京 100049）

1 引言

2015年，Todo[1]在歐密會首次提出積分可分性質，并利用該性質搜索分組密碼積分區分器。同年，Todo[2]在美密會提出了分組密碼算法MISTY1的6輪積分區分器，并對全輪MISTY1實施了理論的積分分析。根據可分性質積分傳播規則，Todo給出10輪SIMON32的積分區分器，比實際搜索結果少了5輪。Wang等[3]提出了SIMON在原積分區分器的基礎上增加一輪而不增加數據復雜度的方法。隨后，Todo等[4]根據類 SIMON簇分組密碼的結構特征，提出基于比特的可分性質，并搜索得到14輪SIMON32積分區分器。同時，他們通過改進基于比特的可分性質，提出利用三子集描述積分傳播過程。利用三子集積分傳播特征，他們搜索得到15輪SIMON32積分區分器。針對其他 SIMON簇分組密碼算法[5]SIMON48/64/96/128，Todo等僅給出理論的積分區分器上界。

2016年，Xiang等[6]在亞密會上通過學習基于比特的可分性質，提出了一種基于混合線性規劃（MILP, mixed integer linear programming）方法的積分區分器自動化搜索算法。該算法可用于搜索類SIMON簇及基于S盒的分組密碼算法的積分區分器。針對 SIMON簇分組密碼算法 SIMON32/48/64/96/128，他們分別給出了14、16、18、22和26輪積分區分器。但是他們無法給出與實際相符的15輪SIMON32積分區分器。隨后，Sun等[7]通過改進Xiang等[6]的方法，提出搜索ARX結構分組密碼積分區分器算法。基于比特可分性質，Sun等[7]通過建立積分傳播模型并利用混合線性規劃求解得到18輪HIGHT[8]積分區分器以及7輪LEA[9]積分區分器。同時，Sun等[7]還第一次給出了TEA[10]、XTEA、KATAN和KTANTAN等ARX結構分組密碼算法的積分區分器。

針對一些小狀態ARX結構分組密碼，混合線性規劃方法能有效地搜索積分區分器。但是對于大狀態ARX結構分組密碼算法如SPECK128，混合線性規劃方法并不能給出有效的解決方案。通過學習基于比特的可分性質，利用三子集傳播方程，本文提出一種基于SAT/SMT求解器自動化搜索ARX結構分組密碼積分區分器的方法。SAT/SMT求解器可通過刻畫比特向量可分性質，等價描述比特可分性質傳播過程，并簡化積分模型建立，加速模型求解過程。

2 比特可分性質傳播模型

2.1 可分性質

積分可分性質由 Todo[1]首次提出并用于搜索分組密碼積分區分器。集合空間的可分性質可通過點積運算描述。取輸入變量，點積運算滿足

任意輸入變量x= (x0,x1,… ,xm?1)，點積運算滿足

對于集合X，任意x∈X屬于有限域空間，如果集合X滿足可分性質，其中，k∈K為m維向量且第i個元素滿足 0 ≤ki≤ni?1，對所有x∈X滿足

其中，U表示不確定取值，Wt(a)表示向量a的向量漢明重量，且Wt(a)=(wt(a0),wt(a1),… ,wt(am?1))。向量a、b的所有分量ai、bi均滿足bi≤ai，則b≤a。

2.2 比特三子集積分可分性質

Todo等[4]將基于字的積分可分性質轉換為比特狀態，給出比特狀態下的可分性質傳播規則，并利用三子集更精確地描述積分可分性質的傳播過程。

對于任意集合X，其元素屬于(2)mF，如果集合X滿足三子集積分可分性質，其中，k∈K為m維比特向量且第i個元素取值為 0或1，所有x∈X滿足

三子集積分可分性質比傳統積分可分性質在傳播過程中多了L集傳播，能更加精確地描述積分可分性質的傳播過程。

2.3 比特三子集傳播規則

基于比特的積分可分性質，K集和L集在經過ARX結構分組密碼輪函數中“分支”“異或”“與”操作時相互獨立。

定義1F為分支操作，其輸入 (x0,x1,… ,xm?1)∈(F2)m。任意比特xi,0 ≤i≤m?1經過分支操作F的K集傳播kxi→(kyi,kzi)滿足

L集傳播滿足

定義2F為異或操作，其輸入 (x0,x1,…,xm?1)∈(F2)m。任意比特xi,xj,0 ≤i≠j≤m?1經過異或操作F的K集傳播(kxi,kxj)→kyi滿足

L集傳播滿足

定義3F為與操作，其輸入。任意比特經過與操作F的K集傳播滿足

L集傳播滿足

定義 4F為異或輪密鑰操作，其輸入(x0,任意L集向量經過異或輪密鑰操作F后，如果滿足lxi=0，需向K集中添加向量

例如，取m=4，異或輪密鑰操作輸入L集向量集合為((0,0,0,1),(1,0,0,0),(1,1,0,0))。其中，向量(0,0,0,1)經過異或輪密鑰操作后K集增加3個額外向量((1,0,0,1),(0,1,0,1),(0,0,1,1))；(1,0,0,0)經過異或輪密鑰操作后K集增加 3個額外向量((1,1,0,0),(1,0,1,0),(1,0,0,1))；(1,1,0,0)經過異或輪密鑰操作后K集增加 2個額外向量((1,1,1,0),(1,1,0,1))，其中，(1,1,1,0)≥ (1,1,0,0)，(1,1,0,1)≥(1,1,0,0)被篩除。K集共增加 5個向量((1,0,0,1),(0,1,0,1),(0,0,1,1),(1,1,0,0),(1,0,1,0))。

定義5Fr為分組密碼輪函數，假設初始三子集積分可分性質為。經過第i輪函數的輸出，三子集積分可分性質滿足，則r輪三子集積分可分性質傳播路徑表示為

2.4 向量三子集傳播規則

基于向量的積分可分性質，K集和L集在經過ARX結構分組密碼輪函數“分支”“異或”“與”操作時相互獨立。

定義 6 二分支操作輸入。經過二分支操作的K集傳播滿足L集傳播滿足

定義7 三分支操作，輸入x=(x0,經過三分支操作的K集傳播滿足L集傳播滿足

定義 8 二異或操作x⊕y=z，輸入x=(x0,x1,… ,xm?1),y =(y0,y1,… ,ym?1)∈ (F2)m。經過二異或操作的K集傳播 kp2xor((kx, ky) →kz)滿足

L集傳播lp2xor((lx,ly) →lz)滿足

定義 9 三異或操作x⊕y⊕z=t，輸入x,y,z∈(F2)m。經過三異或操作的K集傳播kp3xor((kx,ky,kz) →kt)滿足

L集傳播lp3xor((lx,ly,lz) →lt)滿足

定義10 與操作x∧y=z，輸入x=(x0,x1,… ,xm?1),y=(y0,y1,… ,ym?1)∈ (F2)m。經過與操作的K集傳播kpand((kx,ky) →kz)滿足

L集傳播lpand((lx,ly) →lz)滿足

3 ARX結構可分性質模型

模加運算是ARX結構分組密碼算法中唯一的非線性部件。常規模加運算輸入x,y∈ (F2)m，模加運算輸出z∈(F2)m，滿足z=(x+y) mod2m。在某些ARX結構分組密碼算法（HIGHT、TEA、XTEA等）中，存在一種常數模加運算，其輸入變量y為常數（輪密鑰），滿足z= (x+rk)mod2m。

3.1 常規模加運算模型

常規模加運算輸入x,y∈(F2)m，輸出z∈(F2)m滿足

其中，是模加運算的進位。常規模加運算K集傳播過程如表1所示。

增加 12個變量輔助表示模加運算K集傳播，滿足

其中，8個比特為0的分支狀態。因此，在K集傳播過程中該8 bit限制為0。常規模加運算K集傳播系統Sk+((kx,ky)→kz滿足

根據K集傳播過程，可得到常規模加運算L集傳播系滿足

表1 常規模加運算K集傳播

3.2 常數模加運算模型

常數模加運算輸入x,rk∈ (F2)m，輸出z∈(F2)m滿足

其中，c=(c0,c1,… ,cm?1)∈ (F2)m是模加運算的進位。由于輪密鑰為常數，則輪密鑰的三子集積分可分性質滿足= (0,0)。常數模加運算K集傳播過程如表2所示。

表2 常數模加運算K集傳播

增加7個變輔助表示常數模加運算K集傳播，滿足

其中，5個比特為0的分支狀態。因此，在K集傳播過程中該5 bit限制為0。常數模加運算K集傳播系統Sk+c((kx,krk)→kz滿足

根據K集傳播過程，可得到常數模加運算L集傳播系統Sl+c((lx,lrk)→lz滿足

3.3 搜索算法

根據三子集可分性質經過“分支”“異或”“與”及“模加”操作的傳播規則，SAT/SMT求解器可以建立 ARX結構分組密碼輪函數的積分傳播模型。由三子集可分性質經過ARX結構輪函數傳播路徑，可建立r輪積分傳播系統。K集和L集傳播過程中滿足一定傳播條件，可通過L集過濾算法減少L集中的冗余向量從而降低搜索時間復雜度。給定輸入集合X滿足三子集積分 (k,l) =(K0,L0)，對于r輪輸出集合Y滿足三子集可分性質，如果Kr集中包含m個相異的單位向量，則不存在以(k,l)積分特征為輸入的r輪積分區分器。如果Kr集中不存在某單位向量ei，對任意k∈Kr滿足 ⊕y∈Yπei(y)=0，則r輪輸出的第ibit為平衡比特。積分自動化搜索算法的具體描述如下。

1) 初始化參數。給定三子集輸入積分，初始化平衡集合Bset為空集，不確定集合Uset為空集。

2) 建立模型。根據三子集可分性質，通過 ARX結構分組密碼輪函數Fr傳播規則，利用SAT/SMT求解器建立滿足積分傳播路徑的r輪積分傳播系統。

3) 求解。利用SAT/SMT求解器求解r輪積分傳播系統。如果存在一組解滿足步驟2)的傳播條件，添加集合{i|i∈ [0,m? 1]}到Uset，并判定不存在以(k,l)積分特征為輸入的r輪積分區分器。否則對所有i∈ [0,m? 1]測試ei是否滿足ei∈Kr，如果滿足則添加i到Uset中并繼續測試，否則，添加i到Bset中并繼續測試。最后添加到積分區分器集合ID中。

4) 搜索所有可能的積分區分器。遍歷所有可能的 三 子 集 輸 入積分(k,l)， 滿 足wt(l) =m?1,wt(k)=m，執行步驟1)～步驟3)，最終輸出積分區分器集合ID。

在建立模型的過程中，會有大量的冗余L集向量產生，但冗余L集向量并不會影響K集向量傳播，因此，冗余的L集向量可通過篩除算法篩除或不做任何處理。經過模加輪密鑰操作時，L集所有向量均影響K集的向量傳播，利用L集擴展算法擴展L集向量并添加到K集中。該算法的時間復雜度為O(m2)，數據復雜度O(1)，空間復雜度為O(1)。其中，L集向量篩除算法SieveL的具體描述如下。

1) 初始化參數：三子集積分變量(K,L)，積分向量元素長度m。

2)L集向量篩除。SAT/SMT限制語言描述如下。

①初始化空命令字串

②向空字串添加否定斷言

③foriin (0,m)

④ ifi==m?1

⑤ 向命令字串添加命令“BVGE(L[i∶i],L[i∶i])”

⑥ 返回

⑦ else

⑧ 向命令字串添加命令“BVGE(L[i∶i],L[i∶i]) AND”

L集擴展算法ExtendL的具體描述如下。

1) 初始化參數：L集積分變量，臨時變量k，積分向量元素長度m。

2)L集擴展。SAT/SMT限制語言描述如下。①初始化空命令字串

②向空字串添加賦值斷言

③foriin (0,m?1)

④向命令字串添加命令“(ifL[i∶i] == 0b1 then 0 else BVXOR(L,1＜＜i) end if) ork=”

⑤向命令字串添加命令“(ifL[m?1∶m?1] == 0b1 then 0 else BVXOR(L,1＜＜(m?1)) end if) )”

4 應用

本文基于 STP[11]求解器實現積分區分器自動化搜索，平臺搭載 Intel(R) Core(TM) CPU i5-4210M (2.6 GHz, 1 GB RAM, Ubuntu14.04.1)。

4.1 SIMON

SIMON簇分組密碼算法是由NSA提出的一種輕量級分組密碼算法。SIMON采用類Feistel結構，分組長度為2n，表示為 SIMON-2n，字節長度n∈ {16,24,32,48,64}。SIMON分組密碼輪函數表示為

其中，循環移位常數α=8、β=1、γ=2。SIMON簇分組密碼算法輪函數如圖1所示。

圖1 SIMON簇分組密碼算法輪函數

SIMON輪函數，輸入集合X滿足三子集可分性質。根據三子集傳播規則，K集傳播滿足

L集傳播滿足

經過異或輪密鑰操作時，對L集變量lxi擴展為輔助變量ktempi，并將變量和賦值給。輪函數輸出三字集滿足利用該搜索算法，SIMON分組密碼積分區分器如表3所示。

表3 SIMON分組密碼積分區分器

4.2 HIGHT

HIGHT分組密碼算法是由 Deukio等[8]在CHES2006中提出的一種輕量級分組密碼算法。HIGHT分組密碼長度為64 bit，密鑰長度為128 bit。HIGHT分組密碼算法輪函數如圖2所示。

圖2中的Ft,t∈ [0,1]函數定義為

HIGHT輪函數K集傳播變量mi,j,j∈ [0,3]傳播經 過 函 數Ft到ni,j,j∈ [0,3]， 當t=0時 滿 足(α,β,γ) = (1,2,7)，當t=1時滿足(α,β,γ) = (3,4,6)。需要增加額外的 6個變量

來描述K集傳播，滿足傳播系統SFt(km→kn)

由于模加運算輸入變量ni,j,j∈ [0,3]需要額外增加3個變量描述模加積分傳播，且滿足則K集傳播時可以省略3個額外變量以降低搜索時間復雜度，HIGHT輪函數K集傳播滿足傳播方程

L集傳播過程中3xor與3copy操作時不等價，經過Ft函數后3個額外變量不能省略。HIGHT輪函數L集傳播同K集傳播方程。經過異或輪密鑰操作時，對L集變量lni,1、lni,3擴展為輔助變量ktempi,1、ktempi,3，并將輔助變量ktempi,1、ktempi,3分別賦值給kni,1、kni,3。輪函數輸出三字集滿足L集向量篩除規則。利用該搜索算法，HIGHT積分區分器如表4所示。

表4 HIGHT積分區分器

4.3 其他算法

利用該算法搜索得到，SIMECK簇分組密碼算法[12]SIMECK32/48/64分別存在14、17和20輪積分區分器；SPECK簇分組密碼算法SPECK32/48/64/96/128存在6輪積分區分器；LEA分組密碼算法存在8輪積分區分器。

圖2 HIGHT分組密碼算法輪函數

5 結束語

本文提出一種基于 SAT/SMT求解器自動化搜索 ARX結構分組密碼積分區分器的方法。利用三子集積分可分技術，通過建立縮減輪數的ARX結構分組密碼算法積分傳播系統，求解得到縮減輪數的積分區分器，并對所有版本的 SIMON32/48/64/96/128算法進行三子集積分區分器搜索，分別得到14、15、17、21和25輪積分區分器，進一步精確了Todo提出的SIMON積分界。利用該算法，搜索得到8條18輪HIGHT積分區分器。

SAT/SMT求解器同樣能夠應用到SPN結構及Feistel結構分組密碼算法中，但不能有效完整地描述大狀態S盒積分傳播規則。如何自動化搜索大狀態S盒積分傳播，是未來需要研究的工作。

[1] TODO Y. Structural evaluation by generalized integral property[C]//EUROCRYPT. 2015∶ 287-314.

[2] TODO Y. Integral cryptanalysis on full MISTY1[C]//CRYPTO. 2015∶413-432.

[3] WANG Q J, LIU Z Q, KEREM V, et al. Cryptanalysis of reduced-round SIMON32 and SIMON48[C]//INDOCRYPT. 2014∶143-160.

[4] TODO Y, MORII M. Bit-based division property and application to simon family[C]//Fast Software Encryption. 2016∶ 357-377.

[5] ALEX B, ARNAB R, VESSELIN V. Differential analysis of block ciphers SIMON and SPECK[C]//Fast Software Encryption. 2014∶546-570.

[6] XIANG Z J, ZHANG W T, BAO Z Z, et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]// ASIACRYPT. 2016∶ 648-678.

[7] SUN L, WANG W, LIU R, et al. Milp-aided bit-based division property for arx-based block cipher[M]. IACR Cryptology ePrint Archive,2016.

[8] DEUKIO H, JAECHUL S, SEOKHIE H, et al. HIGHT∶ a new block cipher suitablefor low-resource device[C]//Cryptographic Hardware and Embedded Systems. 2006∶ 46-59.

[9] DEUKIO H, JUNG K L, DONG C K, et al. LEA∶ a 128-bit block cipher for fast encryption on common processors[C]//WISA. 2013∶ 3-27.

[10] DAVID J, WHEELER, ROGER M. Tea, a tiny encryption algorithm[C]//Fast Software Encryption. 1994∶ 363-366.

[11] YAO J T, LIU W N. The STP model for solving imprecise problems[C]//GrC. 2006∶ 683-687.

[12] YANG G Q, ZHU B, VALENTIN S, et al. The simeck family of lightweight block ciphers[C]//Cryptographic Hardware and Embedded Systems. 2015∶ 307-329.