ARX結(jié)構(gòu)分組密碼積分區(qū)分器的自動(dòng)化搜索

韓亞，王明生

（1. 中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室，北京 100093；2. 中國科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，北京 100049）

1 引言

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

2016年，Xiang等[6]在亞密會(huì)上通過學(xué)習(xí)基于比特的可分性質(zhì)，提出了一種基于混合線性規(guī)劃（MILP, mixed integer linear programming）方法的積分區(qū)分器自動(dòng)化搜索算法。該算法可用于搜索類SIMON簇及基于S盒的分組密碼算法的積分區(qū)分器。針對(duì) SIMON簇分組密碼算法 SIMON32/48/64/96/128，他們分別給出了14、16、18、22和26輪積分區(qū)分器。但是他們無法給出與實(shí)際相符的15輪SIMON32積分區(qū)分器。隨后，Sun等[7]通過改進(jìn)Xiang等[6]的方法，提出搜索ARX結(jié)構(gòu)分組密碼積分區(qū)分器算法?；诒忍乜煞中再|(zhì)，Sun等[7]通過建立積分傳播模型并利用混合線性規(guī)劃求解得到18輪HIGHT[8]積分區(qū)分器以及7輪LEA[9]積分區(qū)分器。同時(shí)，Sun等[7]還第一次給出了TEA[10]、XTEA、KATAN和KTANTAN等ARX結(jié)構(gòu)分組密碼算法的積分區(qū)分器。

針對(duì)一些小狀態(tài)ARX結(jié)構(gòu)分組密碼，混合線性規(guī)劃方法能有效地搜索積分區(qū)分器。但是對(duì)于大狀態(tài)ARX結(jié)構(gòu)分組密碼算法如SPECK128，混合線性規(guī)劃方法并不能給出有效的解決方案。通過學(xué)習(xí)基于比特的可分性質(zhì)，利用三子集傳播方程，本文提出一種基于SAT/SMT求解器自動(dòng)化搜索ARX結(jié)構(gòu)分組密碼積分區(qū)分器的方法。SAT/SMT求解器可通過刻畫比特向量可分性質(zhì)，等價(jià)描述比特可分性質(zhì)傳播過程，并簡(jiǎn)化積分模型建立，加速模型求解過程。

2 比特可分性質(zhì)傳播模型

2.1 可分性質(zhì)

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

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

對(duì)于集合X，任意x∈X屬于有限域空間，如果集合X滿足可分性質(zhì)，其中，k∈K為m維向量且第i個(gè)元素滿足 0 ≤ki≤ni?1，對(duì)所有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 比特三子集積分可分性質(zhì)

Todo等[4]將基于字的積分可分性質(zhì)轉(zhuǎn)換為比特狀態(tài)，給出比特狀態(tài)下的可分性質(zhì)傳播規(guī)則，并利用三子集更精確地描述積分可分性質(zhì)的傳播過程。

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

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

2.3 比特三子集傳播規(guī)則

基于比特的積分可分性質(zhì)，K集和L集在經(jīng)過ARX結(jié)構(gòu)分組密碼輪函數(shù)中“分支”“異或”“與”操作時(shí)相互獨(dú)立。

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

L集傳播滿足

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

L集傳播滿足

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

L集傳播滿足

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

例如，取m=4，異或輪密鑰操作輸入L集向量集合為((0,0,0,1),(1,0,0,0),(1,1,0,0))。其中，向量(0,0,0,1)經(jīng)過異或輪密鑰操作后K集增加3個(gè)額外向量((1,0,0,1),(0,1,0,1),(0,0,1,1))；(1,0,0,0)經(jīng)過異或輪密鑰操作后K集增加 3個(gè)額外向量((1,1,0,0),(1,0,1,0),(1,0,0,1))；(1,1,0,0)經(jīng)過異或輪密鑰操作后K集增加 2個(gè)額外向量((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個(gè)向量((1,0,0,1),(0,1,0,1),(0,0,1,1),(1,1,0,0),(1,0,1,0))。

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

2.4 向量三子集傳播規(guī)則

基于向量的積分可分性質(zhì)，K集和L集在經(jīng)過ARX結(jié)構(gòu)分組密碼輪函數(shù)“分支”“異或”“與”操作時(shí)相互獨(dú)立。

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

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

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

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

定義 9 三異或操作x⊕y⊕z=t，輸入x,y,z∈(F2)m。經(jīng)過三異或操作的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。經(jīng)過與操作的K集傳播kpand((kx,ky) →kz)滿足

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

3 ARX結(jié)構(gòu)可分性質(zhì)模型

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

3.1 常規(guī)模加運(yùn)算模型

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

其中，是模加運(yùn)算的進(jìn)位。常規(guī)模加運(yùn)算K集傳播過程如表1所示。

增加 12個(gè)變量輔助表示模加運(yùn)算K集傳播，滿足

其中，8個(gè)比特為0的分支狀態(tài)。因此，在K集傳播過程中該8 bit限制為0。常規(guī)模加運(yùn)算K集傳播系統(tǒng)Sk+((kx,ky)→kz滿足

根據(jù)K集傳播過程，可得到常規(guī)模加運(yùn)算L集傳播系滿足

表1 常規(guī)模加運(yùn)算K集傳播

3.2 常數(shù)模加運(yùn)算模型

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

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

表2 常數(shù)模加運(yùn)算K集傳播

增加7個(gè)變輔助表示常數(shù)模加運(yùn)算K集傳播，滿足

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

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

3.3 搜索算法

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

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

2) 建立模型。根據(jù)三子集可分性質(zhì)，通過 ARX結(jié)構(gòu)分組密碼輪函數(shù)Fr傳播規(guī)則，利用SAT/SMT求解器建立滿足積分傳播路徑的r輪積分傳播系統(tǒng)。

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

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

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

1) 初始化參數(shù)：三子集積分變量(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集擴(kuò)展算法ExtendL的具體描述如下。

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

2)L集擴(kuò)展。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 應(yīng)用

本文基于 STP[11]求解器實(shí)現(xiàn)積分區(qū)分器自動(dòng)化搜索，平臺(tái)搭載 Intel(R) Core(TM) CPU i5-4210M (2.6 GHz, 1 GB RAM, Ubuntu14.04.1)。

4.1 SIMON

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

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

圖1 SIMON簇分組密碼算法輪函數(shù)

SIMON輪函數(shù)，輸入集合X滿足三子集可分性質(zhì)。根據(jù)三子集傳播規(guī)則，K集傳播滿足

L集傳播滿足

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

表3 SIMON分組密碼積分區(qū)分器

4.2 HIGHT

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

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

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

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

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

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

表4 HIGHT積分區(qū)分器

4.3 其他算法

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

圖2 HIGHT分組密碼算法輪函數(shù)

5 結(jié)束語

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

SAT/SMT求解器同樣能夠應(yīng)用到SPN結(jié)構(gòu)及Feistel結(jié)構(gòu)分組密碼算法中，但不能有效完整地描述大狀態(tài)S盒積分傳播規(guī)則。如何自動(dòng)化搜索大狀態(tài)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.