ACE密碼算法的積分分析

葉 濤 韋永壯* 李靈琛

①(桂林電子科技大學(xué)廣西無線寬帶通信與信號處理重點(diǎn)實(shí)驗(yàn)室 桂林 541004)

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

1 引言

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

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

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

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

2 基礎(chǔ)知識

2.1 ACE置換

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

表1 文中用到的符號

圖1 ACE置換

2.2 利用置換函數(shù)性質(zhì)構(gòu)建積分區(qū)分器

文獻(xiàn)[18]給出了新的積分區(qū)分器的構(gòu)建方法，主要用到了置換函數(shù)的性質(zhì)。

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

文獻(xiàn)[18]構(gòu)建積分區(qū)分器的主要步驟如下：

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

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

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

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

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

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

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

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

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

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

3.2 構(gòu)建分組密碼算法字傳播模型

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

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

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

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

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

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

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

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

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

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

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

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

fr ∈(Fn2 )m R k 輸入：分組密碼輪函數(shù) ，加密輪數(shù) ，活躍字的下標(biāo)rke rke k ωk 輸出： ，以及加密 輪后，當(dāng)?shù)?個字活躍時，輸出狀態(tài)中的平衡字的下標(biāo)集合rh =R rl =0 rke =0r =0 (1) , , , , flag= 0 xik[0]xik[1]···xik[m-1] i (2) , , , 為 輪加密后，輸出狀態(tài)對應(yīng)的MILP模型變量，每一個MILP變量的值范圍是大于等于0的整數(shù)rh-rl ＞1 (3) While do r =?(rh+rl)/2」 (4) r Me (5) 利用性質(zhì)3和性質(zhì)4構(gòu)建出 輪的字傳播模型 (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) 利用求解器對模型 進(jìn)行求解 (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盒，則在不考慮輪常數(shù)和輪密鑰的條件下，可得第 i輪的輸出狀態(tài)與輸入狀態(tài)的關(guān)系為

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

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

fr-1 ∈(Fn2 )m R k 輸入：分組密碼解密輪函數(shù) ，解密輪數(shù) ，活躍字的下標(biāo)rkd rkd k φk 輸出： ，以及解密 輪后，輸出狀態(tài)中的不包含第 個字的下標(biāo)集合rh =R rl =0 rkd =0r =0flag=0 (1) , , , , yik[0] yik[1]···yik[m-1] i (2) , , , 為第 輪解密輸出狀態(tài)對應(yīng)的MILP模型變量，每一個MILP變量的值范圍是大于等于0的整數(shù)rh-rl ＞1 (3) While do r =?(rh+rl)/2」 (4) r Md (5) 利用性質(zhì)3和性質(zhì)4構(gòu)建出 輪的字解密傳播模型 (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) 利用求解器對模型 進(jìn)行求解 (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)先構(gòu)建出密碼算法輪函數(shù)的加密和解密方向的字傳播模型；

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

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

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

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

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

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

rkd φk表 5 ACE置換對應(yīng)的 和k rkd φk 0 4[0]1[4]2 5[0]3[0]4 4[4]3 3

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

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

表7 ACE置換積分分析結(jié)果對比

5 結(jié)束語

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