張潤蓮 孫亞平 韋永壯 李迎新

1 (廣西密碼學(xué)與信息安全重點實驗室(桂林電子科技大學(xué)) 廣西桂林 541004)2(廣西高校云計算與復(fù)雜系統(tǒng)重點實驗室(桂林電子科技大學(xué)) 廣西桂林 514004)

密碼S盒是許多對稱密碼算法的核心部件，通常決定算法的安全強度.最優(yōu)密碼S盒通常具有雙射性、高非線性、低差分均勻性等代數(shù)性質(zhì).分組密碼S盒的構(gòu)造，早期主要從數(shù)學(xué)結(jié)構(gòu)方面考慮，比如高級加密標準(advanced encryption standard, AES)與Camellia所使用的S盒均基于冪映射方法.但這種構(gòu)造方法難以同時兼顧S盒的多種密碼安全性質(zhì)，比如透明階指標[1-3]即抵御差分功耗攻擊(diff-erential power attack， DPA)[4]的能力等.如何設(shè)計并確保密碼S盒具有一定能力抵御側(cè)信道攻擊一直是業(yè)界研究的難點.在密碼S盒的設(shè)計中，除了傳統(tǒng)的代數(shù)構(gòu)造外，采用智能化搜索算法進行搜索設(shè)計也是當前的研究熱點之一.這些智能化搜索能夠在更大空間高效搜索最優(yōu)解，提高全局尋優(yōu)效率，并克服了傳統(tǒng)密碼S盒構(gòu)造方法的缺陷.目前，遺傳算法、遺傳規(guī)劃、元胞自動機等相繼被應(yīng)用于S盒構(gòu)造.1999年Millan等人[5]利用啟發(fā)式算法更快地找到密碼性質(zhì)更強的S盒;2004年陳華等人[6]利用基因算法對S盒的密碼特性作局部優(yōu)化，再通過遺傳算法產(chǎn)生性能良好的S盒;2014年P(guān)icek等人使用遺傳算法分別搜索到含有較小透明階值的布爾函數(shù)[7]，4×4 S盒[8]和8×8 S盒[9];2015年Kumar等人[10]提出一種基于可逆CA規(guī)則的AES的S盒設(shè)計方法，降低了實現(xiàn)成本;2017年P(guān)icek等人[11]利用遺傳規(guī)劃演化了大量的CA規(guī)則，產(chǎn)生了具有良好密碼特性的S盒，并在硬件上實現(xiàn)了最優(yōu)S盒的性能測試;2018年Ghoshal等人[12]利用CA規(guī)則構(gòu)造了4×4最優(yōu)S盒，降低了基于門限實現(xiàn)(threshold implementation， TI)占用的芯片面積和功耗；2019年關(guān)杰等人[13]通過實驗找到一類新的基于CA的S盒，其具有代替Keccak雜湊函數(shù)S盒的潛力.注意到，文獻[12]沒有討論所構(gòu)造S盒的透明階大小，并且其搜索到的4×4最優(yōu)S盒數(shù)量偏少.如何設(shè)計低透明階的最優(yōu)密碼S盒是目前有待解決的問題.

本文基于CA規(guī)則，采用變元分量部分固定和分別搜索的策略，提出一種S盒新搜索方法.首先，分析CA規(guī)則下生成的4×4 S盒，對CA規(guī)則下12類S盒數(shù)量進行分類統(tǒng)計，并測試了其透明階值；其次，使用S盒的新自動搜索方法設(shè)計出大量的4×4 S盒，對設(shè)計出的新S盒的密碼學(xué)性質(zhì)進行安全性分析，相對于CA規(guī)則生成的S盒，獲得了數(shù)量更多且透明階值更低的4×4最優(yōu)S盒，這說明這些新的S盒具有更好抵御DPA攻擊的能力.

1 預(yù)備知識

本文考慮具有相同輸入和輸出數(shù)量的S盒，即：n×nS盒.目前，對n×nS盒的安全性評估指標較多，本文主要從傳統(tǒng)安全性指標和抵抗側(cè)信道攻擊的安全性新指標透明階做簡要描述.

1.1 S盒安全性指標

1) 代數(shù)次數(shù)

(1)

其中，βu∈F2，u=(u1,u2,…,un).則稱式(1)為f的代數(shù)正規(guī)型(algebraic normal form， ANF).

布爾函數(shù)f的代數(shù)次數(shù)定義為布爾函數(shù)的ANF中最大乘積項的變量個數(shù)，用degf表示：

(2)

其S盒的代數(shù)次數(shù)是其分量函數(shù)f代數(shù)次數(shù)的最大值，用degF表示；wt(u)表示函數(shù)f的漢明重量，即真值表中“1”的個數(shù).理想情況下，一個密碼學(xué)上有用的S盒具有較高的代數(shù)次數(shù)，以抵御代數(shù)攻擊.

2) 平衡性

3) 非線性度

(3)

其中

(4)

4) 差分均勻性

(5)

其差分均勻度為

(6)

5) 透明階

在2005年FSE會議上，法國學(xué)者Prouff[1]在漢明重量模型下，提出了S盒透明階(transparency order, TO)的定義，這是第1次在多位的條件下，量化S盒抵御DPA攻擊的能力.2017年Chakraborty等人[2]指出TO定義的不足之處，并得到了改進透明階(modified transparency order, MTO)的新定義.

定義4.令F為一個平衡的n×m函數(shù)，改進的透明階TMTO(F)計算為

(7)

2019年Li等人[3]提出了修訂的透明階(revised transparency order, RTO)，以更好地度量密碼S盒抵御DPA攻擊的能力.

定義5.令F為一個平衡的n×m函數(shù)，修訂的透明階TRTO(F)計算為

(8)

由式(3)(7)(8)可知，2個指標都與Walsh譜有關(guān)，當Walsh譜的值越大，透明階越小，S盒的NF也越小.但在理論上，透明階越小越好，NF越大越好，抵抗DPA的能力越強，所以二者存在一種對立的關(guān)系.

1.2 元胞自動機

元胞自動機是用于模擬和分析各種離散復(fù)雜系統(tǒng)的并行計算模型.CA主要由元胞、元胞空間、鄰域和規(guī)則組成，一個CA在每一個時間狀態(tài)中，元胞空間上的每一個元胞都按照局部規(guī)則同步更新其狀態(tài)，其中該局部規(guī)則應(yīng)用于元胞的鄰域.本文只考慮一維布爾周期型邊界元胞自動機(periodic boundary cellular automata, PBCA).其中，CA是一個矢量布爾函數(shù)，每個元胞處于0或1狀態(tài)，即F2={0,1}.

F(x1,x2,…,xn)=(f(x1,…,xd),…,
f(xn-d+2,…,x1),…,f(xn,…,xd-1)),

(9)

其中，xi(i=1,2,…,n)為元胞，d為鄰域半徑，f是變量d(d≤n)上的布爾函數(shù)，稱為局部規(guī)則.

2 基于CA規(guī)則的4×4 S盒

2.1 基于CA規(guī)則的4×4 S盒設(shè)計

CA規(guī)則可作為S盒的設(shè)計策略，該規(guī)則具有良好的密碼學(xué)性質(zhì)和較低的實現(xiàn)成本.根據(jù)PBCA的定義，Ghoshal等人[12]給出了4×4 S盒的如下表示形式：

定義7.選擇CA規(guī)則，給出一個4×1的CA規(guī)則f，則相應(yīng)的4×4的S盒表示為

S(X,Y,Z,W)=(f(X,Y,Z,W),f(Y,Z,W,X),
f(Z,W,X,Y),f(W,X,Y,Z)).

(10)

基于定義7，在S盒構(gòu)造中，先選擇一個局部CA規(guī)則，其本質(zhì)是一個4×1的布爾函數(shù)，將該局部CA規(guī)則的輸入位進行4種不同的循環(huán)置換，得到4×4的S盒映射，使得其能夠在硬件中實現(xiàn)一個低成本的等價迭代.

基于CA規(guī)則的S盒可看作一種特殊類型的向量布爾函數(shù)，其中每個坐標函數(shù)對應(yīng)于局部鄰域的CA規(guī)則.在此規(guī)則下生成的S盒總數(shù)利用德布萊英圖(De Bruijn graph)技術(shù)表示，其首先給定一個德布萊英圖G=(V,E)，其中V表示頂點，E表示邊，E的數(shù)量|E|=2n；其次將圖的每條邊與一個位{0,1}關(guān)聯(lián)，得到局部CA規(guī)則，與此圖相關(guān)聯(lián)的CA規(guī)則總數(shù)為22n.基于上述方法，對于n=4，所產(chǎn)生的CA規(guī)則總數(shù)為224=216，每一個CA規(guī)則產(chǎn)生一個唯一的4×4函數(shù)；對這些函數(shù)進行窮搜索得到1 536個雙射S盒，考慮其非線性度和差分均勻度的密碼性質(zhì)最優(yōu)，最終搜索到512個候選S盒.

2.2 基于CA規(guī)則的4×4 S盒分析

針對基于CA規(guī)則生成的512個4×4候選S盒，文獻[12]根據(jù)S盒的代數(shù)正規(guī)型(ANF)表示的性質(zhì)進行了分類：其首先把S盒用ANF形式表示，由于每一個4×4 S盒的最優(yōu)代數(shù)次數(shù)為3，其劃分每一類的ANF都具有相同數(shù)量的三次項、二次項和線性形式，最終劃分了12類.這些S盒在硬件實現(xiàn)中具有類似的占用面積和功耗，由于每一類都有相同的代數(shù)結(jié)構(gòu)，則有幾乎相同的TI電路表示，減少了硬件面積消耗，提高了運行速度.

在對文獻[12]的分類分析中發(fā)現(xiàn)：每一類的項數(shù)之和為奇數(shù)(記為奇數(shù)類)，則滿足雙射性；若為偶數(shù)(記為偶數(shù)類)，則不滿足雙射性.因此，在進行分類時判斷哪一類存在最優(yōu)S盒不用考慮偶數(shù)類，這將有效減少搜索時間.基于該方法，最終對基于CA規(guī)則生成的S盒劃分為同樣的12類，如表1所示[12].

表1顯示，滿足這12類的雙射S盒有448個，考慮其非線性度、差分均勻度和代數(shù)次數(shù)的密碼性質(zhì)最優(yōu)，得到256個最優(yōu)S盒.

傳統(tǒng)安全性指標可作為衡量經(jīng)典密碼分析的標準，透明階則是評估S盒抵抗DPA攻擊的能力.文獻[12]沒有考慮抵抗DPA攻擊的能力，特別是MTO和RTO指標.

利用式(7)(8)定義的透明階，測試了每一個S盒的透明階值.因篇幅有限，在此僅列出每一類代表元最優(yōu)S盒的MTO,RTO值，具體如表2所示.

Table 1 Statistics Table of 12 Classes of 4×4 S-Boxes表1 12類4×4 S盒數(shù)量統(tǒng)計表

Table 2 Transparent Order Value of 12 Classes of 4×4 S-Boxes Representatives

表2顯示，基于CA規(guī)則生成的12類代表元S盒的MTO值在2.4～2.933之間，未列出的S盒也在這個范圍之內(nèi)；RTO值均為3.200或3.267，其他未列出的S盒的RTO值也均為3.200或3.267.發(fā)現(xiàn)基于CA規(guī)則生成的12類S盒的透明階值普遍不低，抵御DPA攻擊相對較弱，如何構(gòu)造新型最優(yōu)S盒，且在滿足傳統(tǒng)安全性指標的同時還有較低的透明階是目前需要解決的問題.

3 基于改進CA規(guī)則的4×4 S盒

3.1 基于改進CA規(guī)則4×4最優(yōu)S盒

3.1.1 4×4最優(yōu)S盒設(shè)計

基于CA規(guī)則下生成的12類4×4最優(yōu)S盒，本文提出一種新的搜索方法，實現(xiàn)S盒的擴展，以搜索具有更低透明階的最優(yōu)S盒.

注意到基于CA規(guī)則生成的12類4×4最優(yōu)S盒無法直接降低透明階值，則考慮在CA規(guī)則的基礎(chǔ)上實現(xiàn)S盒的擴展，再搜索具有更低透明階的最優(yōu)S盒.首先考慮4×4 S盒的本質(zhì)特征，為此我們通過以下2個性質(zhì)進行改進.

性質(zhì)1.對于4×4 S盒，X∈{0,1,…,15}，fi∈{0,1}(i=0,1,2,3)，F(xiàn)=(f0,f1,f2,f3)，F(xiàn)3=(f0,f1,f2).令4×4 S盒輸入輸出坐標對為(X,F)，參考坐標對為(X,F3)，則輸入輸出坐標對可表示為(X,F3,f3).則任意雙射4×4 S盒可由16對(X,F)均互不相同的輸入輸出坐標對唯一表示.

基于性質(zhì)1和性質(zhì)2，通過變化最后一位f3，S盒的真值表發(fā)生變化，可能對Walsh譜有影響.由定義4和定義5知，透明階與NF存在對立的關(guān)系，且都與Walsh譜有關(guān)，Walsh譜的變化，導(dǎo)致在滿足傳統(tǒng)安全性指標的情況下引起透明階發(fā)生改變.

基于上述性質(zhì)，首先將定義7的CA規(guī)則簡化為F=(f0,f1,f2,f3)；將F3換成CA規(guī)則下的前3個局部規(guī)則，即F3=(f0,f1,f2)，并令最后一個規(guī)則f3未知，則變更后的CA規(guī)則輸入輸出坐標對為(X,F′)，其中F′=(F3,f3)；全遍歷第4個局部規(guī)則f3，實現(xiàn)S盒的自動搜索.

基于改進CA規(guī)則的S盒一種新自動搜索方法具體過程為：

2) 對于變量(x0,x1,x2,x3)按照字典的順序取完所有值，列出該S盒F的真值表(f(0,0,0,0),f(0,0,0,1),…,f(1,1,1,1))；

4) 根據(jù)分量函數(shù)F3的真值表，確定函數(shù)f3的真值.當輸入變量為(x0,x1,x2,x3)時，分量函數(shù)F3從000到111變化，這時F3會出現(xiàn)2個相同的值，則f3的值分別取0或者1，從而得到28個新的函數(shù)F′；

5) 判斷新生成的28個S盒是否滿足平衡性.若某個S盒不滿足平衡性，則剔除，保留所有滿足平衡性的S盒；

6) 隊列前移，若隊列為空則結(jié)束，轉(zhuǎn)7)；否則，轉(zhuǎn)2)；

7) 結(jié)束自動搜索，輸出所有新生成的S盒.

基于CA規(guī)則生成的12類4×4最優(yōu)S盒有256個，基于本文的S盒新搜索方法，一個S盒就可以生成28個新的S盒，則一共生成256×28=216個不同的新S盒，擴展了生成的S盒數(shù)量，在擴展的基礎(chǔ)上找尋透明階較低的最優(yōu)S盒.

以表2中(1,5,3)類代表元4×4最優(yōu)S盒為例，說明新的自動搜索過程如下.

由函數(shù)F3=(f0,f1,f2)來進一步的確定分量函數(shù)f3.首先，根據(jù)(x0,x1,x2,x3)的取值，函數(shù)F3=(f0,f1,f2)的真值表如表3所示：

Table 3 Truth Table for Function F3=(f0,f1,f2)表3 函數(shù)F3=(f0,f1,f2)的真值表

Continued (Table 3)

其次，根據(jù)函數(shù)F3=(f0,f1,f2)的取值情況，分量函數(shù)f3的真值分別變化，如表4所示：

Table 4 Value Form of Component Function f3表4 分量函數(shù)f3取值形式

3.1.2 4×4最優(yōu)S盒分析與對比

對于新生成的4×4 S盒，考慮其雙射性、差分均勻度和非線性度最優(yōu)，利用密碼算法隨機測試平臺，搜索4×4最優(yōu)S盒；根據(jù)定義4和定義5的透明階公式編寫的程序，測試新生成的每一個最優(yōu)S盒的透明階值.

由表1可知，文獻[12]生成的12類最優(yōu)S盒有256個.本文通過改進，對文獻[12]中生成的每一個最優(yōu)S盒，分別生成包含32～72個不同數(shù)量的最優(yōu)S盒.由于采用上述方法生成的S盒數(shù)量較多，因篇幅有限，在此主要以表2所列的12類代表元4×4最優(yōu)S盒為例，統(tǒng)計該代表元下新生成的4×4最優(yōu)S盒數(shù)量及最小的MTO,RTO值，如表5所示：

Table 5 Statistics Table of the Newly Generated 4×4 Optimal S-Boxes Representatives表5 新生成4×4最優(yōu)S盒代表元統(tǒng)計表

表5顯示，對于12類代表元，本文搜索到的4×4最優(yōu)S盒數(shù)量，多于表1中列出的12類所有4×4最優(yōu)S盒的數(shù)量；同時，新生成的最優(yōu)S盒的透明階值也有一定程度的下降，在抵抗差分密碼分析、線性密碼分析等攻擊的同時，可以更好地抵抗DPA攻擊.

進一步地，將基于CA規(guī)則生成的12類最優(yōu)S盒與本文改進CA規(guī)則提出的S盒新搜索方法所生成的最優(yōu)S盒進行比較如下.因采用本文方法生成新的密碼S盒數(shù)量太多，無法一一列出，在此以表2中列出的12類代表元對應(yīng)的S盒進行對比，結(jié)果如表6所示：

Table 6 Results of the Number of 12 Classes of Optimal S-Boxes Representatives and Newly Generated

表6顯示，本文改進CA規(guī)則S盒的自動搜索方法能夠通過遍歷第4個規(guī)則快速地生成更多的最優(yōu)S盒.

基于上述統(tǒng)計結(jié)果，同樣以表2中的某2類代表元，采用本文改進CA規(guī)則生成新的最優(yōu)S盒，對比測試文獻[12]與本文方法所生成S盒的MTO,RTO值，結(jié)果如表7所示.

表7表明，本文方法在滿足傳統(tǒng)安全指標的同時，能夠在新生成的最優(yōu)S盒中找到具有更低透明階值的最優(yōu)S盒.

Table 7 Results of Transparent Order Values of 2 Classes of Optimal S-Boxes and Newly Generated S-Boxes表7 2類最優(yōu)S盒與新生成S盒透明階值對比結(jié)果

3.2 基于改進CA規(guī)則4×4次優(yōu)S盒優(yōu)化

基于CA規(guī)則劃分了12類并生成最優(yōu)S盒，但在這劃分的12類之外，同樣還存在其他的CA規(guī)則.為了能夠充分利用每個規(guī)則，搜索更多的有價值的S盒，對12類規(guī)則外的其他規(guī)則進行搜索.

在2.2節(jié)的分類分析中表明了基于CA規(guī)則劃分的12類均為奇數(shù)類，因偶數(shù)類不滿足雙射性未被考慮.針對其他奇數(shù)類，采用2.2節(jié)中設(shè)計的自動化搜索方法，搜索到除了12類規(guī)則外的3類規(guī)則，即(1,1,1)(3,1,1)(3,1,3)，搜索出每一類的所有局部規(guī)則；進一步地，統(tǒng)計這3類規(guī)則下的S盒數(shù)量，結(jié)果如表8所示:

Table 8 Statistics Table of 3 Classes of 4×4 S-Boxes表8 3類4×4 S盒數(shù)量統(tǒng)計表

表8表明，這3類規(guī)則不存在4×4最優(yōu)S盒，但存在密碼性質(zhì)稍弱的S盒.對表8中的這些S盒，測試其透明階值，發(fā)現(xiàn)最小的MTO值為2.333，RTO值為3.200.

針對表8搜索到的S盒，由于NF=2且δF=6的S盒性質(zhì)較差，本文沒有考慮；但對NF=4且δF=6的S盒，采用本文改進CA規(guī)則自動搜索方法，搜索新的S盒.由于每個S盒可生成28新的S盒，一共生成24×28個不同的新S盒.

對于新生成的4×4 S盒，利用密碼算法隨機測試平臺，從中搜索4×4最優(yōu)S盒，并測試新生成的每一個最優(yōu)S盒的透明階值.

采用上述方法生成的S盒數(shù)量較多，因篇幅有限，在此主要以表8所列的3類代表元NF=4且δF=6的4×4 S盒為例，統(tǒng)計該代表元下新生成的4×4最優(yōu)S盒數(shù)量及最小的MTO,RTO值，如表9所示.

表9顯示，每一類代表元S盒生成了56個新的4×4最優(yōu)S盒.同時，新生成的最優(yōu)S盒的透明階值也有一定程度的下降，具有更好的抵抗DPA攻擊的能力.

Table 9 Statistics Table of the Newly Generated 4×4 Optimal S-Boxes表9 新生成4×4最優(yōu)S盒統(tǒng)計表

進一步地，統(tǒng)計基于CA規(guī)則生成的(1,1,1)(3,1,1)(3,1,3)類S盒與本文改進CA規(guī)則S盒的新搜索方法所生成的最優(yōu)S盒，經(jīng)過驗證，對12類以外的每一個NF=4且δF=6的次優(yōu)S盒，都改進搜索到56個新的4×4最優(yōu)S盒，對比如表10所示.

基于上述統(tǒng)計結(jié)果，同樣以(3,1,1)類代表元，采用本文改進CA規(guī)則生成新的最優(yōu)S盒，對比測試文獻[12]與本文方法所生成S盒的透明階值，結(jié)果如表11所示.

表11表明，本文方法基于CA規(guī)則生成的S盒基礎(chǔ)上，能夠生成新的具有更低透明階值的最優(yōu)S盒.

Table 10 Results of the Number of 3 Classes of S-Boxes and Newly Generated Optimal S-Boxes

Table 11 Results of Transparent Order Values of Sub-Optimal S-Boxes and Newly Generated S-boxes表11 次優(yōu)S盒與新生成最優(yōu)S盒透明階值對比結(jié)果

4 結(jié)束語

基于CA規(guī)則，采用變元分量部分固定和分別搜索的策略，給出了一種設(shè)計密碼S盒的新自動搜索方法.搜索結(jié)果發(fā)現(xiàn)：通過改進CA規(guī)則自動搜索，不僅能夠生成更多的4×4最優(yōu)S盒，也有效降低了最優(yōu)S盒的透明階值；基于CA規(guī)則給出的12類之外的3類規(guī)則，并對基于這3類規(guī)則生成的4×4次優(yōu)S盒進行搜索，同樣獲得了較多的具有較低透明階值的4×4最優(yōu)S盒.在將來的工作中，將重點研究8×8高強度密碼S盒的設(shè)計問題.