葉 濤 韋永壯* 李靈琛

①(桂林電子科技大學廣西無線寬帶通信與信號處理重點實驗室 桂林 541004)

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

1 引言

隨著物聯(lián)網技術和5G技術的快速發(fā)展，信息安全問題日趨突出，分組密碼算法作為一種主流的加密體制，由于其安全性高、加密速度快、安全性易于評估等特點，具有非常重要的應用。對于一個安全的分組密碼算法，其需要抵抗已知的各種攻擊方法，比如線性密碼分析[1]、差分密碼分析[2]、不可能差分分析[3,4]、立方分析[5]、積分分析[6]等。目前除屬性[7]以及自動化分析工具在密碼分析中的廣泛應用，使得積分分析成為近些年來國內外密碼學者的研究熱點之一。

積分分析最初是由Knudsen等人[6]為了分析Square的安全性而提出的分析方法，其基本思想是選取某些輸入的明文字節(jié)為任意的固定值，其余的明文字節(jié)活躍，如果這個明文集合通過密碼算法后，某些輸出位的和恒為0，則攻擊者構建了一個積分區(qū)分器。搜索積分區(qū)分器的典型方法一般可以分為如下3種：第1種方案是通過觀察積分性質的傳播軌跡來構建積分區(qū)分器[8,9]。第2種方案是通過評估密碼算法輸出表達式的代數次數來構建積分區(qū)分器[10,11]。第3種方法是利用除屬性[7,12]構建出相應的模型，然后，利用優(yōu)化工具來搜索積分區(qū)分器[13-17]。但是，這些構建積分區(qū)分器的方法受到密碼結構或計算能力的限制。在2020年的國際快速軟件加密會議(FSE2020)上，Zhang等人[18]給出了一種新的搜索算法。其主要思想是將內部狀態(tài)的表達式用明文或密文字來表示，通過統(tǒng)計這些明文或密文字在內部狀態(tài)中出現(xiàn)的次數，評估密碼算法抵抗積分分析的能力。但是該方法需要手動推導出內部狀態(tài)關于明文字或密文字的具體表達式形式，不能做到自動化分析。如何給出一種自動分析方法是目前的研究難點。

本文引入字傳播軌跡新概念，基于混合整數線性規(guī)劃技術(Mixed Integer Linear Programming, MILP)，構建了一個傳播軌跡的描述模型，并給出一個新的積分區(qū)分器自動化搜索方法。利用這個自動化搜索算法，不需手動推導復雜的表達式，只需要判斷模型是否有解就可以快速地得到明文(密文)字在內部狀態(tài)的表達式中出現(xiàn)的次數，降低了密碼分析者的工作量。利用這個新的自動化搜索工具，本文對國際輕量級密碼算法標準化過程的第2輪候選算法之一ACE[19]的安全性進行了分析。結果表明：ACE密碼算法存在12步的積分區(qū)分器，需要的數據復雜度為 2256，需要的時間復雜度為 2256次12步的ACE置換操作，存儲復雜度為8 Byte。

本文后續(xù)章節(jié)的安排如下，第2節(jié)主要介紹一些基礎知識；第3節(jié)主要介紹如何利用MILP結合文獻[18]中的思想搜索積分區(qū)分器；第4節(jié)利用新的自動化分析方法對ACE置換的安全性進行分析；第5節(jié)是對全文的總結。文中用到的符號定義如表1所 示。

2 基礎知識

2.1 ACE置換

ACE認證加密算法是由加拿大滑鐵盧大學Aagaard等人[19]設計的，它是國際輕量級密碼算法標準化[20]過程的第2輪候選算法之一。其中，ACE的置換包含16步，每一步都對320 bit的數據進行操作，其基本結構基于廣義Feistel結構[21]，并且每一步都使用不帶密鑰的減輪Simeck密碼算法[22]作為非線性部件。由于ACE算法每一步的操作僅包含與、異或、循環(huán)移位運算等基本操作，其具有很好的軟硬件實現(xiàn)性能。在設計ACE的原文檔中，算法的設計者給出了ACE置換的8步的積分區(qū)分器，但是，是否存在步數更高的積分區(qū)分器還有待于進一步探究。

表1 文中用到的符號

圖1 ACE置換

2.2 利用置換函數性質構建積分區(qū)分器

文獻[18]給出了新的積分區(qū)分器的構建方法，主要用到了置換函數的性質。

性質1如果函數 F(X):→是關于 X的置換函數，f (Y):→為任意布爾函數，則對于X,Y ∈，存在

文獻[18]構建積分區(qū)分器的主要步驟如下：

(1) 利用輪函數的結構，對明文進行加密運算，并觀察輸出狀態(tài)的表達式，直到第j 個明文字達到了全擴散，并且至少存在1個輸出狀態(tài)的表達式中第j 個明文字只出現(xiàn)1次，此時記錄加密的輪數為。

(2) 利用輪函數的結構，對密文進行解密運算，觀察輸出狀態(tài)的表達式，直到第j 個密文字達到了全擴散，記錄此時對應的解密輪數為，并且，當解密-1輪后，至少存在1個輸出狀態(tài)的表達式中不出現(xiàn)第j 個密文字，記錄下此時對應的。

則利用性質2，可以評估密碼算法抵抗積分分析的能力。

性質2對于一個SPN結構的分組密碼算法，令renc和 rdec分別為加密和解密方向達到全擴散的最小輪數，則這個密碼算法存在renc+rdec輪的積分區(qū)分 器[18]。

3 新的積分區(qū)分器自動化搜索算法

3.1 分組密碼算法字傳播軌跡

為了觀察每一個輸入字在內部狀態(tài)中出現(xiàn)的次數，攻擊者需要利用輪函數的具體形式來推導出多輪后輸出狀態(tài)關于輸入字的表達式形式，然后再觀察每一個輸入字在輸出狀態(tài)中出現(xiàn)的次數。以ACE密碼算法的第0個字 A0為例，本文定義數組[4]] 為第i步的輸出狀態(tài)的表達式 Ai,Bi,Ci,Di,Ei中包含第0個字 A0的次數。首先，在不考慮步常數的條件下，可以得到ACE置換第i步的輸入與輸出之間的關系為

利用式(2)，當只有 A0為活躍塊時，在加密方向上，可以得到 A0的傳播軌跡為

由于x90[j]＞1(0 ≤j ＜5) ，則A9,B9,C9,D9,E9都不是關于輸入字 A0的置換；由于x80[1]=1，所以， B8是 輸入塊 A0的置換，則=8( A為步函數輸入的第0個字)。

由上面的實例可以發(fā)現(xiàn)，對于一個字，經過輪函數后，在每一輪的輸出狀態(tài)中出現(xiàn)的次數是固定的。根據這個特點，本文定義字傳播軌跡如下。

3.2 構建分組密碼算法字傳播模型

如果直接手動推導字傳播軌跡，需要的時間較長，并且容易發(fā)生錯誤。為了提高密碼分析者的效率，本文給出了字傳播軌跡的混合整數規(guī)劃模型(MILP)，利用這個模型結合優(yōu)化工具(Gurobi8.0)給出了一個自動化搜索積分區(qū)分器的方法。

本文的方法主要是在不考慮S盒內部結構的前提下，根據密碼算法線性部件的特點來構建字傳播模型。在密碼算法的線性部件中，基本的操作包括置換運算、異或運算，下面分別討論如何構建這兩個運算的字傳播軌跡。

性質3置換運算的字傳播軌跡模型：由于置換運算只是對某些字進行位置上的置換，不影響輸入字在輸出狀態(tài)中出現(xiàn)的次數。如果輪函數中存在置換操作 si[k]→si[k1]，則可以構建出如下的模型來描述第j 個字的傳播軌跡

性質4異或運算的字傳播軌跡模型：由于在分組密碼算法的輪函數中，線性操作之前一般都會經過非線性層，所以，進行異或操作的變量都是非線性部件的輸出，則經過異或操作后的輸出中某一個字出現(xiàn)的次數為異或操作前這個變量在對應的字中出現(xiàn)的次數之和。如果輪函數的線性層中包含異或操作 si[k1]⊕si[k2]⊕si[k3]⊕···⊕si[kl]=si+1[k]，則可以構建如式(5)的模型來描述第 j個字的傳播軌跡

通過將密碼算法的線性層拆分為異或和置換操作，可以構建出這個密碼算法每一輪的字傳播模型 ，將其迭代r 輪后可以得到r 輪字傳播模型M 。

3.3 新積分區(qū)分器自動化搜索算法

基于文獻[18]中的積分區(qū)分器構建方法，結合本文構建的MILP模型，同時利用優(yōu)化求解工具，本文設計了積分區(qū)分器自動化搜索算法。

首先，給出如何設置模型的初始的輸入。如果想得到輸入的第 k個字的傳播軌跡，由于s0[k]只在s0[k]中出現(xiàn)1次，在其余的位置沒有出現(xiàn)，則初始輸入對應的模型變量為

所以，利用字傳播軌跡，如果向量 Xkr中至少存在1個元素等于1，則存在r 輪的關于第k 個字的積分區(qū)分器。則有如下的性質。

為了向解密方向繼續(xù)擴展積分區(qū)分器的輪數，需要判斷出第 k個字解密方向上沒有達到全擴散的最大輪數，即解密+1 輪后第k 個輸入字第1次達到了全擴散，但是解密輪后第k 個字沒有達到全擴散。根據這個關系，有如下的性質。

表2 算法1：利用字傳播模型確定

表2 算法1：利用字傳播模型確定

fr ∈(Fn2 )m R k 輸入：分組密碼輪函數 ，加密輪數 ，活躍字的下標rke rke k ωk 輸出： ，以及加密 輪后，當第 個字活躍時，輸出狀態(tài)中的平衡字的下標集合rh =R rl =0 rke =0r =0 (1) , , , , flag= 0 xik[0]xik[1]···xik[m-1] i (2) , , , 為 輪加密后，輸出狀態(tài)對應的MILP模型變量，每一個MILP變量的值范圍是大于等于0的整數rh-rl ＞1 (3) While do r =?(rh+rl)/2」 (4) r Me (5) 利用性質3和性質4構建出 輪的字傳播模型 (6) Me.con ←x0k[k]=1,M.con ←x0k[j]=0,j ∈[0,m),j /=k Me.con ←min′{(xrk[0],xrk[1],··· ,xrk[m-1])}=1 (7) Me (8) 利用求解器對模型 進行求解 (9) If Me 有解rl =r,flag=1 (10) (11) else rh =r,flag=0 (12) (13) End If (14) End While flag==1 (15) If rke =r (16) (17) else rke =r-1 (18) (19)End If(1,ωk)=min{(xrke k [0],xrkek [1],··· ,xrkek [m-1])} (20)rke ωk (21) return 和

定義密碼算法的線性層可以使用矩陣A=(ai,j)?來表示，非線性層使用S表 示第i輪中的第j 個密碼S盒，則在不考慮輪常數和輪密鑰的條件下，可得第 i輪的輸出狀態(tài)與輸入狀態(tài)的關系為

表3 算法2：利用字傳播模型確定

表3 算法2：利用字傳播模型確定

fr-1 ∈(Fn2 )m R k 輸入：分組密碼解密輪函數 ，解密輪數 ，活躍字的下標rkd rkd k φk 輸出： ，以及解密 輪后，輸出狀態(tài)中的不包含第 個字的下標集合rh =R rl =0 rkd =0r =0flag=0 (1) , , , , yik[0] yik[1]···yik[m-1] i (2) , , , 為第 輪解密輸出狀態(tài)對應的MILP模型變量，每一個MILP變量的值范圍是大于等于0的整數rh-rl ＞1 (3) While do r =?(rh+rl)/2」 (4) r Md (5) 利用性質3和性質4構建出 輪的字解密傳播模型 (6) Md.con ←y0k[k]=1,M.con ←y0k[j]=0,j ∈[0,m),j /=k Md.con ←min′{(yrk[0],yrk[1],···,yrk[m-1])}=0 (7) Md (8) 利用求解器對模型 進行求解 (9) If Md 有解rl =r,flag=1 (10) (11) else rh =r,flag=0 (12) (13) End If (14) End While flag==1 (15) If rkd =r (16) (17) else rkd =r-1 (18) (19) End If(0,φk)=min{(yrkd (20) rkd φk (21) return 和k [0],yrkdk [1],···,yrkdk [m-1])}

4 ACE密碼算法新積分分析

對于一個給定的迭代分組密碼算法，本文給出了如下的積分區(qū)分器搜索步驟：

(1)先構建出密碼算法輪函數的加密和解密方向的字傳播模型；

(4)根據算法結構，觀察 red輪的積分區(qū)分器能否繼續(xù)向加密方向擴展1輪。

利用上面的步驟對ACE置換進行積分分析。首先，在加密方向上，定義初始輸入(A0,B0,C0,D0,E0) 對應的模型變量為k ∈[0,5)， 其中，k 表示在初始輸入中第k 個字是活躍的，ACE置換加密方向第i步的輸出對應的模型變量為， 例如，x30[0]表示加密3步后，字 A0在字 A3的表達式中出現(xiàn)的次數，其他的變量代表的含義同理。則根據ACE置換的步函數的結構，可以得到加密方向第i步的步函數對應的字傳播模型為

定義ACE置換解密方向第 i 步的輸出對應的模型變量為 ([0],[1],··· ,[4])， 則第i步解密方向的步函數對應的字傳播模型為

利用式(9)和式(10)， r 次迭代后就可以得到r 步的字傳播模型。然后，將模型輸入到算法1和算法2中，使用求解器對模型進行求解(求解器：Gur o b i 8.0，編程語言：P y t h o n 2.7)，并遍歷k ∈[0,5)，得到的結果如表4和表5所示。

由 表4 和 表5 可 得 red=12 , φ =[0,2,3]，則ACE置換存在1個12步的積分區(qū)分器，對應的區(qū)分器的具體形式如表6所示。

images/BZ_38_811_2277_845_2322.pngωk表 4 ACE置換對應的 和k rke ωk 0 8[1][3]2 7[1]1 8 3[1]4 7[3]9

rkd φk表 5 ACE置換對應的 和k rkd φk 0 4[0]1[4]2 5[0]3[0]4 4[4]3 3

表6 ACE置換12步的積分區(qū)分器

由于13步加密后，僅有字 E13的表達式中包含了字 B12， 同時E13中還包含了C12，則12步的積分區(qū)分器不能繼續(xù)向下擴展1步，所以，本文得到的ACE置換的積分區(qū)分器的步數為12步。相比于ACE設計文檔中給出的結果[19]，本文給出的積分區(qū)分器步數更高，需要的數據量更少。結果對比如表7。

表7 ACE置換積分分析結果對比

5 結束語

本文給出了字傳播軌跡的概念，構建了相應的MILP模型來描述字傳播軌跡，并在此基礎上設計了一種新的積分區(qū)分器自動化搜索方法，同時利用二分法減少了需要求解模型的次數。利用這個自動化分析工具，對ACE置換抵抗積分分析的能力進行了評估，發(fā)現(xiàn)了12步的積分區(qū)分器，在ACE的設計文檔中，設計者利用可分性搜索到了8步的積分區(qū)分器，所以，相比ACE設計文檔中的區(qū)分器，本文的區(qū)分器提高了4步。雖然，本文的區(qū)分器沒有對ACE認證加密算法的安全性造成威脅(ACE認證加密算法中ACE置換的總步數為16步)，但是本文給出了一種自動化搜索分組密碼算法積分區(qū)分器的新方法，提高了密碼分析的效率，為以后的分組密碼算法的設計與分析提供了強有力的工具。