密碼S盒的一種新自動搜索方法

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

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

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

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

1 預備知識

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

1.1 S盒安全性指標

1) 代數次數

(1)

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

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

(2)

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

2) 平衡性

3) 非線性度

(3)

其中

(4)

4) 差分均勻性

(5)

其差分均勻度為

(6)

5) 透明階

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

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

(7)

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

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

(8)

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

1.2 元胞自動機

元胞自動機是用于模擬和分析各種離散復雜系統的并行計算模型.CA主要由元胞、元胞空間、鄰域和規則組成，一個CA在每一個時間狀態中，元胞空間上的每一個元胞都按照局部規則同步更新其狀態，其中該局部規則應用于元胞的鄰域.本文只考慮一維布爾周期型邊界元胞自動機(periodic boundary cellular automata, PBCA).其中，CA是一個矢量布爾函數，每個元胞處于0或1狀態，即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)上的布爾函數，稱為局部規則.

2 基于CA規則的4×4 S盒

2.1 基于CA規則的4×4 S盒設計

CA規則可作為S盒的設計策略，該規則具有良好的密碼學性質和較低的實現成本.根據PBCA的定義，Ghoshal等人[12]給出了4×4 S盒的如下表示形式：

定義7.選擇CA規則，給出一個4×1的CA規則f，則相應的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盒構造中，先選擇一個局部CA規則，其本質是一個4×1的布爾函數，將該局部CA規則的輸入位進行4種不同的循環置換，得到4×4的S盒映射，使得其能夠在硬件中實現一個低成本的等價迭代.

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

2.2 基于CA規則的4×4 S盒分析

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

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

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

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

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

Table 1 Statistics Table of 12 Classes of 4×4 S-Boxes表1 12類4×4 S盒數量統計表

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

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

3 基于改進CA規則的4×4 S盒

3.1 基于改進CA規則4×4最優S盒

3.1.1 4×4最優S盒設計

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

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

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

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

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

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

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

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

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

6) 隊列前移，若隊列為空則結束，轉7)；否則，轉2)；

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

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

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

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

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

Continued (Table 3)

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

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

3.1.2 4×4最優S盒分析與對比

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

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

Table 5 Statistics Table of the Newly Generated 4×4 Optimal S-Boxes Representatives表5 新生成4×4最優S盒代表元統計表

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

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

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

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

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

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

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

3.2 基于改進CA規則4×4次優S盒優化

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

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

Table 8 Statistics Table of 3 Classes of 4×4 S-Boxes表8 3類4×4 S盒數量統計表

表8表明，這3類規則不存在4×4最優S盒，但存在密碼性質稍弱的S盒.對表8中的這些S盒，測試其透明階值，發現最小的MTO值為2.333，RTO值為3.200.

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

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

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

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

Table 9 Statistics Table of the Newly Generated 4×4 Optimal S-Boxes表9 新生成4×4最優S盒統計表

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

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

表11表明，本文方法基于CA規則生成的S盒基礎上，能夠生成新的具有更低透明階值的最優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 次優S盒與新生成最優S盒透明階值對比結果

4 結束語

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