胡建勇，穆道光，周 宇，董新鋒

（1.中國電子科技集團公司第三十研究所，四川 成都 610041；2.保密通信重點實驗室，四川 成都 610041）

0 引 言

隨著密碼學(xué)與計算機、數(shù)學(xué)等交叉領(lǐng)域的不斷發(fā)展，密碼算法的自動化分析程度越來越高。自動化分析手段逐步替代原來手工推導(dǎo)驗證的方式，具有分析能力強、準(zhǔn)確性高、容易驗證等優(yōu)點，備受密碼研究人員的青睞，被廣泛用于密碼算法的安全性分析和評估中，從而“反哺”算法設(shè)計，對提升密碼算法的安全強度具有重要的作用。

密碼自動化分析是指將密碼分析問題轉(zhuǎn)化為數(shù)學(xué)求解問題，根據(jù)專業(yè)數(shù)學(xué)求解軟件的求解情況獲得密碼分析的結(jié)果。常見的數(shù)學(xué)求解問題有混合整數(shù)線性規(guī)劃問題（Mixed Integer Linear Programming，MILP）和布爾可滿足性問題（Boolean Satisfiability Problem，SAT），常用的數(shù)學(xué)求解軟件有Cplex、Gurobi、MIT、SMT 等。根據(jù)求解問題的不同，密碼自動化分析主要分為基于MILP 的自動化分析和基于SAT 的自動化分析兩種類型。它們的區(qū)別在于問題的刻畫不同，基于MILP 的自動化分析使用線性不等式刻畫，而基于SAT 的自動化分析使用布爾邏輯方程刻畫。

目前，實現(xiàn)自動化的分析方法主要有差分分析[1-2]、線性分析[2]、不可能差分分析[3-4]、零相關(guān)線性分析[5-6]和積分分析[7-12]。其中，自動化積分分析根據(jù)可分性質(zhì)在密碼算法中的傳播規(guī)律和可分特征的刻畫，實現(xiàn)了區(qū)分器的搜索。根據(jù)可分性質(zhì)定義的不同，自動化積分分析又分為基于兩子集可分性質(zhì)的自動化積分分析[7-9]和基于三子集可分性質(zhì)的自動化積分分析[10-12]。由于后者僅適用于分組小、算法結(jié)構(gòu)簡單的輕量級分組密碼，因此主流使用基于兩子集可分性質(zhì)的自動化積分分析。但仍然存在一些問題，例如，在多數(shù)分組密碼算法中，使用可分特征的比特級刻畫，其適用性不佳，所建立的數(shù)學(xué)求解問題難以有效求解，而使用可分特征的非比特級刻畫，部分密碼部件和基本運算的線性不等式等價刻畫困難。

基于此，本文對常用密碼部件和基本運算非比特級可分性質(zhì)的傳播規(guī)律及其可分特征的刻畫進行研究，首次提出S 盒和邏輯與運算的線性不等式等價刻畫，給出自動化積分分析的基本思想和基于MILP 的自動化積分分析流程，并應(yīng)用于ISO 標(biāo)準(zhǔn)分組密碼算法CLEFIA[13]，得到其存在積分區(qū)分器的最大輪數(shù)為10 輪，是目前最好的積分分析結(jié)果。

1 符號與定義

記2F 為二元域，域中元素取值為0 或者1， F2上n 比特向量構(gòu)成的全體記為。設(shè)向量，記a 的第 i+ 1個比特為，其中i = 0,1,… , n -1，定義a 中非零比特的個數(shù)稱為a 的漢明重量，記為 w( a )，滿足設(shè)m 維向量，其中， i = 0,1, … , m -1，其漢明重量 W ( b )定義為

2 傳播規(guī)律與刻畫

線性不等式刻畫是一種常用的點集刻畫方法，其滿足所有可行解能夠覆蓋的點集。為了不引入錯誤的點，要求線性不等式刻畫必須是等價刻畫，即所有可行解恰好構(gòu)成整個點集。

在密碼算法設(shè)計中，經(jīng)常使用的密碼部件或基本運算包括異或、分支、級聯(lián)、拆分、S 盒、邏輯與、列混淆等，其可分性質(zhì)的傳播規(guī)律和可分特征的刻畫都不相同。

2.1 異或運算

根據(jù)異或運算可分性質(zhì)的傳播規(guī)律，可以計算其所有可分特征構(gòu)成的點集為：

對應(yīng)的線性不等式刻畫為：

式中：0b 和1b 為異或運算對應(yīng)的輸入變量；a 為對應(yīng)的輸出變量，它們的取值均為整數(shù)。容易驗證式（2）所有的可行解恰好覆蓋異或運算的可分特征，因此式（2）等價刻畫了異或運算的可分特征。

2.2 分支運算

設(shè)X 為 n比特分支運算的一個輸入多重集，對于任意的 ∈x X ，滿足為x 經(jīng)過分支運算后的輸出，則所有的構(gòu)成分支運算的輸出多重集，記為Y 。當(dāng)輸入多重集 X 滿足可分性質(zhì)時，分支運算的輸出多重集Y 滿足可分性質(zhì)

根據(jù)分支運算可分性質(zhì)的傳播規(guī)律，可以計算其所有可分特征構(gòu)成的點集為：

對應(yīng)的線性不等式刻畫為：

式中： a0和 a1為分支運算對應(yīng)的輸入變量；b為對應(yīng)的輸出變量，它們的取值均為正數(shù)。容易驗證式（4）所有的可行解恰好覆蓋分支運算的可分特征，因此式（4）等價刻畫了分支運算的可分特征。

2.3 級聯(lián)運算

設(shè)X 為m 個n 比特數(shù)據(jù)級聯(lián)運算的一個輸入多重集，對于任意的 (x1, x2,…,xm)∈X ， 滿足，其中 i = 1,2,… ,m ，令，則所有的y 構(gòu)成級聯(lián)運算的輸出多重集，記為Y 。當(dāng)輸入多重集X 滿足可分性質(zhì)時，級聯(lián)的輸出多重集 Y滿足可分性質(zhì)

根據(jù)級聯(lián)運算可分性質(zhì)的傳播規(guī)律，可以計算其所有可分特征構(gòu)成的點集為：

對應(yīng)的線性不等式刻畫為：

2.4 拆分運算

根據(jù)拆分運算可分性質(zhì)的傳播規(guī)律，可以計算其所有可分特征構(gòu)成的點集為：

對應(yīng)的線性不等式刻畫為：

式中：a 為拆分運算對應(yīng)的輸入變量；b b b…01, , , bm-1為對應(yīng)的輸出變量，它們的取值均為整數(shù)。容易驗證式（8）所有的可行解恰好覆蓋拆分運算的可分特征，因此式（8）等價刻畫了拆分運算的可分特征。

2.5 S 盒運算

設(shè) X為n 比特S 盒運算的一個輸入多重集，對于任意的 ∈x X ，滿足，假設(shè)S 盒的代數(shù)次數(shù)為 d，令 y =S( x )，則所有的y 構(gòu)成S 盒運算的輸出多重集，記為Y 。當(dāng)輸入多重集X 滿足可分性質(zhì)時，S 盒運算的輸出多重集Y 滿足可分性質(zhì)其中0 ≤ k ＜ n，表示對x 向上取整；當(dāng)輸入多重集X 滿足可分性質(zhì)時，S 盒運算的輸出多重集 Y滿足可分性質(zhì)。

根據(jù)S 盒運算可分性質(zhì)的傳播規(guī)律，可以計算其所有可分特征構(gòu)成的點集為：

不同的n 和d 對應(yīng)的線性不等式等價刻畫不同。當(dāng) 4n= ， 3d = 時，對應(yīng)的線性不等式刻畫為：

式中：a 為4 比特S 盒運算對應(yīng)的輸入變量；b為對應(yīng)的輸出變量；d0為臨時變量，它們的取值均為整數(shù)。容易驗證式（10）所有的可行解恰好覆蓋代數(shù)次數(shù)為3 的4 比特S 盒的可分特征，實現(xiàn)了等價刻畫。

當(dāng) 8n= ， 7d = 時，對應(yīng)的線性不等式刻畫為：

式中：a 為8 比特S 盒運算對應(yīng)的輸入變量；b為對應(yīng)的輸出變量；0d 為臨時變量，它們的取值均為整數(shù)。容易驗證式（11）所有的可行解恰好覆蓋代數(shù)次數(shù)為7 的8 比特S 盒的可分特征，實現(xiàn)了等價刻畫。

2.6 邏輯與運算

設(shè)X 為n 比特邏輯與運算的一個輸入多重集，對于任意的，滿足令，則所有的 y構(gòu)成邏輯與運算的輸出多重集，記為Y 。當(dāng)輸入多重集X 滿足可分性質(zhì)時，邏輯與運算輸出多重集Y 滿足可分性質(zhì)

根據(jù)邏輯與運算可分性質(zhì)的傳播規(guī)律，可以計算其所有可分特征構(gòu)成的點集為：

不同的n 對應(yīng)的線性不等式等價刻畫不同。當(dāng) 4n= 時，對應(yīng)的線性不等式刻畫為：

式中： a0和 a1為4 比特邏輯與運算對應(yīng)的輸入變量；b 為對應(yīng)的輸出變量；d 為臨時變量，它們的取值均為整數(shù)。容易驗證式（13）所有的可行解恰好覆蓋4 比特邏輯與運算的可分特征，實現(xiàn)了等價刻畫。

當(dāng) 8n= 時，對應(yīng)的線性不等式刻畫為：

式中：0a 和1a 為8 比特邏輯與運算對應(yīng)的輸入變量；b 為對應(yīng)的輸出變量；d 為臨時變量，它們的取值均為整數(shù)。容易驗證式（14）所有的可行解恰好覆蓋8 比特邏輯與運算的可分特征，實現(xiàn)了等價刻畫。

2.7 列混淆運算

列混淆運算是指對m 個n 比特數(shù)據(jù)進行線性變換并輸出m 個n 比特數(shù)據(jù)。設(shè)X 為列混淆運算的一個輸入多重集，對于任意的∈X ，滿足，其中 i = 1 , 2 ,… , m ，記列混淆 運算的輸出為,2,… , m ，并且滿足則所有的( y1,y2,……,ym) 構(gòu)成列混淆運算的輸出多重集，記為Y 。 當(dāng)輸入多重集X 滿足可分性質(zhì)時， 輸出多重集Y 滿足可分性質(zhì)其中，并且滿足所有整數(shù)解的個數(shù)。，

根據(jù)列混淆運算可分性質(zhì)的傳播規(guī)律，可以計算其所有可分特征構(gòu)成的點集為：

對應(yīng)的線性不等式刻畫為：

3 自動化積分分析

根據(jù)可分性質(zhì)在密碼部件和基礎(chǔ)運算的傳播規(guī)律以及線性不等式等價刻畫，可實現(xiàn)密碼算法的自動化積分分析。

3.1 基本思想

對于r 輪的分組密碼算法，自動化積分分析的目的是評估算法存在積分區(qū)分器的最大輪數(shù)，即找到 rmax，使得存在一個輸入多重集，經(jīng)過 rmax輪算法后，對應(yīng)的輸出多重集在某一位置是平衡的，而對于任意的輸入多重集，經(jīng)過rmax+1 輪算法后，對應(yīng)的輸出多重集在任意位置都不平衡。

當(dāng)X 中元素的維數(shù)m 較大時，在判定積分區(qū)分器的存在性時，遍歷所有的X 枚舉量過大，實際不可行。值得注意的是，如果兩個不同的，滿 足， Y1不含 所 有的單位向量，2Y 必然也不含所有的單位向量。基于這一性質(zhì)，X 只需遍歷m 次，第 1i+ 次的取值記為其中

3.2 分析流程

基于MILP 的自動化積分分析的中心思想是將積分區(qū)分器的存在性判定問題轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問題，其分析流程如下文所述。

（1）分解輪函數(shù)。根據(jù)輪函數(shù)的設(shè)計，按照計算順序?qū)⑵湟来畏纸獬梢恍┗具\算的組合，比如異或運算、分支運算、級聯(lián)運算、拆分運算、S 盒運算、邏輯與運算等。

（2）分析傳播規(guī)律。給定輸入多重集滿足的可分性質(zhì)，經(jīng)過基本運算后，根據(jù)可分性質(zhì)的定義，分析對應(yīng)輸出多重集滿足的可分性質(zhì)。

（3）確定建模規(guī)格n。建模規(guī)格一般選取S 盒的狀態(tài)大小。當(dāng)某基本運算可分性質(zhì)的傳播規(guī)律分析困難或者無法分析時，可以適當(dāng)擴大建模規(guī)格，從而規(guī)避該基本運算帶來的影響。比如8 比特的數(shù)據(jù)左循環(huán)移位5 比特，如果按照4 比特建模，則不易分析其可分性質(zhì)的傳播規(guī)律，若將建模規(guī)格擴大至8 比特，循環(huán)移位只改變某些位置的比特可分性質(zhì)，并不影響整體可分性質(zhì)的取值大小。

（4）計算可分特征，實現(xiàn)等價刻畫。根據(jù)可分性質(zhì)的傳播規(guī)律，計算所有的可分特征，使用線性不等式實現(xiàn)等價刻畫。

（5）建立MILP 求解模型。與其他自動化密碼分析技術(shù)相同，目前自動化積分分析并沒有實現(xiàn)真正意義上的自動化，其主要原因在于算法識別困難，仍依賴于人工識別，因此模型文件無法全自動化地建立。盡管可以將基本運算和常用部件可分特征的線性不等式等價刻畫寫成基本函數(shù)，制成數(shù)據(jù)庫的形式，但由于每一個算法使用運算和部件的順序及次數(shù)都不相同，因此，需要人工編寫算法模型模塊，按照算法的組合邏輯依次調(diào)用基本函數(shù)，然后結(jié)合自動化積分分析的基本思想，建立完整的求解模型。

（6）求解模型文件，得到分析結(jié)果。使用專業(yè)數(shù)學(xué)軟件求解模型文件，根據(jù)求解情況得到分析結(jié)果。

3.3 應(yīng)用

CLEFIA[13]是一個ISO 輕量級標(biāo)準(zhǔn)分組密碼算法，分組長度為128 比特，如圖1 所示，采用4 支Type-2 型廣義Feistel 結(jié)構(gòu)。0S 和1S 是兩個不同的8 比特S 盒，代數(shù)次數(shù)為7，0M 和 1M是兩個不同的最大距離可分（Maximum Distance Separable，MDS）MDS 變換。

使用基于MILP 的自動化積分分析方法搜索CLEFIA 存在積分器的最大輪數(shù)。輪函數(shù)可分解成分支運算、異或運算、S 盒運算和MDS 變換，其中MDS 變換可看作列混運算。在不考慮輪密鑰 0RK 和 1RK 的情況下，當(dāng)建模規(guī)格 8n= 時，輸入多重集滿足可分性質(zhì)中X 的取值共有16 個，記 為， i= 0,1,… ,15， 其中建立MILP 求解模型，遍歷16 個向量 iin ，自第1 輪開始判定積分區(qū)分器的存在性。分析結(jié)果表明：自第1 輪開始，直至第10 輪，CLEFIA 算法都存在積分區(qū)分器，而自第11 輪起，CLEFIA 算法都不存在積分區(qū)分器。

因此，CLEFIA 算法存在積分區(qū)分器的最大輪數(shù)max10r = ，是目前最好的積分分析結(jié)果。

4 結(jié) 語

基于MILP 的自動化積分分析的關(guān)鍵在于可分特征的刻畫，為了使混合整數(shù)線性規(guī)劃問題能夠有效求解，MILP 模型文件中不宜出現(xiàn)太多變量。因此，除了分組較小的輕量級分組密碼，多數(shù)分組密碼必須采用非比特級建模。本文研究了非比特級可分性質(zhì)在密碼部件和基本運算中的傳播規(guī)律，給出可分特征的線性不等式刻畫，首次實現(xiàn)了S 盒和邏輯與運算的等價刻畫，給出自動化積分分析的基本思想和分析流程，并應(yīng)用于CLEFIA 算法，得到最長為10 輪的積分區(qū)分器。

在自動化積分分析中，建立MILP 求解模型仍然處于半自動化狀態(tài)，無法智能識別算法，需要人工編寫算法模型模塊。隨著計算機技術(shù)的不斷提高，算法智能識別的問題終將得到解決，基于可分性質(zhì)的積分分析將實現(xiàn)全自動化，從一種分析手段逐步開發(fā)成通用的自動化分析工具，最終成為密碼智能化分析模塊。