Feistel結構的8比特輕量化S盒

董新鋒，張文政，許春香

(1.電子科技大學 計算機科學與工程學院，四川 成都 611731；2.保密通信重點實驗室，四川 成都 610041)

國內外現有的對稱密碼算法設計仍然沿用香農1949年提出的“混淆”、“擴散”思想[1]，通過對稱密碼算法的“混淆”和“擴散”部件使得明文、密文和密鑰之間的關系異常復雜，以至于攻擊者無法從密文得到明文的任何信息或者從明文密文對得到密鑰的任何信息。“混淆”部件普遍采用非線性置換S盒(Substitution Box)。S盒首次出現在分組密碼算法LUCIFER中，隨著美國標準化技術研究機構(National Institute of Standard Technology，NIST)在1977年發布的數據加密算法標準(Data Encryption Standard，DES)的使用而廣為流行[2]。S盒是絕大多數密碼算法中唯一的非線性部件，如AES、CAMELLIA、ARIA、CLEFIA等[3-6]。S盒的密碼性質極大影響整個算法的“混淆”效果，也幾乎決定了整個密碼算法的安全強度。

自2004年之后，針對物聯網中RFID類資源受限設備的安全保密需求，密碼算法設計時不僅要考慮密碼算法及部件的安全性，同時要兼顧算法實現的硬件門數等資源指標。目前適用于RFID類資源受限設備的輕量級密碼算法其硬件實現等效門一般不超過2000 GATE[7]，使用傳統查表方式實現的S盒難以滿足輕量級密碼算法的硬件實現資源小等要求，特別是使用8比特S盒的情形。基于代數結構的S盒的輕量化實現、基于簡單邏輯運算的S盒的輕量化設計等是當前國內外密碼領域的研究熱點問題之一，也取得了一些研究進展，如：對具有最優密碼學性質的4比特S盒的16個等價類劃分[8]，這類S盒已成功應用于設計PRINCE、MIDORI、SKINNY等輕量級分組密碼算法[9-11]；NBC、SPRING等分組密碼算法提出了16比特、32比特S盒的輕量化設計思路，但基于該設計思路的S盒需要迭代20輪或32輪，其實現方式具有較大的時延，32比特S盒目前仍難以完全刻畫其差分均勻度和非線性度等密碼性質[12-13]；在SKINNY-128分組密碼算法中，設計者提出一種基于2個4比特S盒并置構成1個新的8比特S盒的設計思路[10]，但基于該設計思路的8比特S盒的差分均勻度和非線性度等密碼性質較弱，會導致密碼算法的整體迭代輪數較大，影響密碼算法實現性能；美國標準化組織NIST先后啟動了認證加密方面的CAESAR競賽、輕量級AEAD和雜湊算法征集等活動，提交的密碼算法方案中也對輕量化密碼部件及其實現性能進行了一些研究[14-19]。

筆者提出一種新的8比特輕量化S盒設計方法，其單輪邏輯運算僅涉及4個單比特與運算和4個單比特異或運算，迭代4輪后差分均勻度為16(差分概率為2-4)、非線性度為96(線性概率為2-4)、分量函數代數次數可以達到6。與已有研究結果相比，設計的8比特輕量化S盒需要較少的硬件實現資源，同時達到了8比特輕量化S盒的已知最優差分均勻度和非線性度等密碼性質，解決了之前8比特輕量化S盒差分均勻度和非線性度等密碼性質較弱的問題。

1 S盒及其主要密碼學性質

1.1 符號與定義

1.1.1S盒

n比特輸入m比特輸出的S盒(簡稱為n×m的S盒)定義如下：

1.1.2 布爾函數的代數正規型、項數和代數次數

每一個n元布爾函數f都可以唯一地表示為F2上關于n個變元x1，x2，…，xn的多項式，即

上式稱為布爾函數f的代數正規型，其中a0，ai，aij，…，a12…n∈F2，⊕為F2上的加法運算。f的代數正規型中非零單項式的個數稱為f的項數，所有非零單項式中變元個數的最大值稱為布爾函數f的代數次數。

1.1.3 漢明重量

n維向量c=(c1，c2，…，cn)的漢明重量定義為此向量中非零元的個數，記為wt(c)，即wt(c)=#{ci|ci≠0}。

1.2 S盒主要密碼學性質

1.2.1S盒平衡性

1.2.2S盒的非線性度、線性概率

1.2.3S盒的差分均勻度、差分概率

1.2.4CCZ等價

S盒一般以表的形式存儲，通過查表實現調用。如果參數n和m過大，將給S盒的設計以及密碼算法的實現帶來困難。目前絕大多數密碼算法采用8×8的S盒，簡稱8比特S盒。

S盒的其他密碼學性質還包括：代數免疫階、分支數、透明階等。針對差分攻擊和線性攻擊這兩類重要的分析方法，密碼算法設計者主要考慮S盒的差分均勻度和非線性度。

2 Feistel結構的8比特S盒

目前已知硬件門數最少的8比特輕量化S盒構造方法，是SKINNY-128算法中直接基于2個4比特S盒并置構成1個新的8比特S盒[11](構造方法的結構圖如圖1所示)。其單輪邏輯運算涉及2個單比特或運算、2個單比特取反運算和2個單比特異或運算，迭代4輪后其差分均勻度為64、非線性度為64(即差分概率為2-2、線性概率為2-2)，與隨機方式產生的8×8的S盒的差分均勻度16和非線性度96(即差分概率為2-4、線性概率為2-4)相比，差距較大。

圖1 SKINNY-128分組密碼算法中的 8×8輕量化S盒的邏輯結構圖

在圖1中，SKINNY-128分組密碼算法中的8比特輕量化S盒的單輪邏輯運算為

(x7，x6，x5，x4，x3，x2，x1，x0)→(x2，x1，x7，x6，x4⊕(～(x7|x6))，x0⊕(～(x3|x2))，x3，x5) ，

其中，邏輯運算符號“～”表示比特取反運算，邏輯運算符號“|”表示比特或運算。

下面介紹文中提出的一種新的8比特輕量化S盒設計方法，其單輪邏輯運算僅涉及4個比特與運算和4個比特異或運算，迭代4輪后差分均勻度為16、非線性度為96(即差分概率為2-4、線性概率為2-4)。

2.1 Feistel結構的8比特S盒設計方法

基于八分支Feistel結構的8比特輕量化S盒設計方法，其運算過程的結構圖如圖2所示。

圖2 基于八分支Feistel結構的8比特輕量化S盒設計方法結構圖

將基于八分支Feistel結構的8比特S盒設計方法記為算法1，具體運算過程如下。

算法1 S盒的8比特輸入數據記為(x0，x1，x2，x3，x4，x5，x6，x7)，S盒的8比特輸出數據記為(y0，y1，y2，y3，y4，y5，y6，y7)，8比特中間變量記為(t0，t1，t2，t3，t4，t5，t6，t7)，2比特中間變量記為(T0，T1)，包括步驟QS1至QS3。

QS2 對S盒的8比特輸入數據(x0，x1，x2，x3，x4，x5，x6，x7)，依次遍歷{0，1，…，255}所有整數值對應的8比特二元向量{(0，0，0，0，0，0，0，0)，(0，0，0，0，0，0，0，1)，…，(1，1，1，1，1，1，1，1)}，對任意整數值i∈{0，1，…，255}對應的8比特二元向量(x0，x1，x2，x3，x4，x5，x6，x7)，依次計算步驟QS21至QS25。

QS21 對輸入的8比特二元向量(x0，x1，x2，x3，x4，x5，x6，x7)計算第1輪8支Feistel結構的輪變換，即t6=x0⊕f1(x2，x3，x4，x5，x6，x7)，t7=x1⊕f2(x2，x3，x4，x5，x6，x7)，t0=x2，t1=x3，t2=x4，t3=x5，t4=x6，t5=x7；

QS22 對QS21的運算結果8比特二元向量(t0，t1，t2，t3，t4，t5，t6，t7)計算第2輪8支Feistel結構的輪變換，即T0=t0⊕f1(t2，t3，t4，t5，t6，t7)，T1=t1⊕f2(t2，t3，t4，t5，t6，t7)，t0=t2，t1=t3，t2=t4，t3=t5，t4=t6，t5=t7，t6=T0，t7=T1；

QS23 對QS22的運算結果8比特二元向量(t0，t1，t2，t3，t4，t5，t6，t7)計算第3輪8支Feistel結構的輪變換，即T0=t0⊕f1(t2，t3，t4，t5，t6，t7)，T1=t1⊕f2(t2，t3，t4，t5，t6，t7)，t0=t2，t1=t3，t2=t4，t3=t5，t4=t6，t5=t7，t6=T0，t7=T1；

QS24 對QS23的運算結果8比特二元向量(t0，t1，t2，t3，t4，t5，t6，t7)計算第4輪非線性變換，即T0=t0⊕f1(t2，t3，t4，t5，t6，t7)，T1=t1⊕f2(t2，t3，t4，t5，t6，t7)；

QS25 對QS24的運算結果8比特二元向量(T0，T1，t2，t3，t4，t5，t6，t7)進行比特組合，得到8比特S盒Sbox在整數i的數值，即：y0=T0，y1=T1，y2=t2，y3=t3，y4=t4，y5=t5，y6=t6，y7=t7，Sbox(i)=y0‖y1‖y2‖y3‖y4‖y5‖y6‖y7。

QS3 輸出8比特S盒Sbox，其真值表為{Sbox(0)，Sbox(1)，…，Sbox(254)，Sbox(255)}。

結論1設8比特S盒SB是由算法1產生的S盒，則SB是平衡的。

由八分支廣義Feistel結構的單輪變換是置換，易知，迭代4輪后得到的SB依然是置換，即SB是平衡的。

結論2設8比特S盒SB是由算法1產生的S盒，則SB分量函數的代數次數大于等于2。

結論3設8比特S盒SB是由算法1產生的S盒，則與SB對應的f1與f2組合形式共有2114-258+1種。

2.2 輕量化8比特S盒設計方法

考慮到適用于RFID類資源受限設備的輕量級密碼算法其硬件實現資源(如等效門等)的輕量化要求，本小節對算法1中使用的f1、f2做如下限定：f1、f2的代數正規型僅包含2個2次項。

在上述限定條件下，f1共包含105種滿足限定條件的可選布爾函數，f2共包含105種滿足限定條件的可選布爾函數，f1與f2按照算法1中的組合情形共有11 025種。具體地，f1與f2經限定后具有如下形式：

f1(x2，x3，x4，x5，x6，x7)=(C0&x2&x3)⊕ (C1&x2&x4)⊕ (C2&x2&x5)⊕ (C3&x2&x6)⊕ (C4&x2&x7)⊕ (C5&x3&x4)⊕ (C6&x3&x5)⊕ (C7&x3&x6)⊕ (C8&x3&x7)⊕ (C9&x4&x5)⊕ (C10&x4&x6)⊕ (C11&x4&x7)⊕ (C12&x5&x6)⊕ (C13&x5&x7)⊕ (C14&x6&x7)；

f2(x2，x3，x4，x5，x6，x7)=(D0&x2&x3)⊕(D1&x2&x4)⊕(D2&x2&x5)⊕(D3&x2&x6)⊕(D4&x2&x7)⊕(D5&x3&x4)⊕(D6&x3&x5)⊕(D7&x3&x6)⊕ (D8&x3&x7)⊕ (D9&x4&x5)⊕ (D10&x4&x6)⊕ (D11&x4&x7)⊕ (D12&x5&x6)⊕ (D13&x5&x7)⊕ (D14&x6&x7)；

通過計算機程序搜索，在f1、f2的代數正規型僅包含2個2次項的限定條件下，根據算法1共找到了52個新的8比特輕量化S盒，其單輪邏輯運算僅涉及4個與運算(單比特)和4個異或運算(單比特)，經過4輪迭代后，這52個新的8比特S盒的差分均勻度為16、非線性度為96(即差分概率為2-4、線性概率為2-4)。f1、f2代數正規型僅包含2個2次項時，密碼性質好的52個8比特S盒對應的向量C、D的具體結果如表1所示。

表1 52個8比特S盒對應的f1、f2代數正規型

定理1設8比特S盒LW_SB是由算法1產生的表1中的52個S盒中的任意一個，則LW_SB具有如下密碼學性質：

(1) LW_SB是平衡的；

(2) LW_SB的分量函數的代數次數至少為2，至多為6；

(3) LW_SB的非線性度大于等于96；

(4) LW_SB的差分均勻度小于等于16。

證明：性質(1)、(2)由結論1、結論2容易得到，性質(2)、性質(3)、性質(4)可通過測試上述52個S盒得到。

8比特S盒LW_SB與目前已知硬件門數最少的8比特輕量化S盒(SKINNY-128算法中基于2個4×4的S盒并置構成的S盒)[11]相比，具有如下顯著優勢：

(1) 其單輪邏輯運算涉及4個單比特與運算和4個單比特異或運算，與SKINNY-128算法中S盒硬件實現資源相當；

(2) 其差分均勻度為16、非線性度為96，即差分概率為2-4、線性概率為2-4、分量函數代數次數達到6，優于SKINNY-128算法中S盒的密碼性質(即差分概率為2-2、線性概率為2-2、分量函數代數次數達到6)。

2.3 輕量化8比特S盒的CCZ等價類分布

利用2.2節輕量化8比特S盒的設計方法，共得到52個新的8比特輕量化S盒，其單輪邏輯運算僅涉及4個單比特與運算和4個單比特異或運算，經過4輪迭代后，這52個新的8比特S盒的差分均勻度為16、非線性度為96。

更進一步，文中研究了表1中52個新的8比特輕量化S盒的CCZ等價類分布。首先將8比特S盒轉化為有限域上線性碼的生成矩陣，再利用數學軟件magma判定不同線性碼之間的等價性，從而判定不同8比特S盒之間的CCZ等價性。

研究結果表明，上述52個輕量化S盒屬于13個不同的CCZ等價類，每個CCZ等價類包含4個S盒。CCZ等價類分布如表2所示。

表2中S盒序號對應的列(第2列、第4列、第6列和第8列)包含的數字i(i=1，2，…，52)分別表示表1中第i行向量C、D對應的f1、f2通過算法1得到的8比特S盒。

2.4 輕量化8比特S盒的應用

筆者設計的8比特輕量化S盒在硬件實現資源小的條件下達到已知最優的差分均勻度和非線性度，同時適用于BitSlice等運算方式，在8位、16位、32位、64位等不同實現平臺上具有良好的兼容性和易移植性，能夠廣泛應用于對稱密碼算法設計中。

如果將文中設計的8比特輕量化S盒用于SKINNY-128算法[11]，即直接替換SKINNY-128算法中8比特輕量化S盒，不會增加SKINNY-128算法的硬件實現資源，同時能大幅降低SKINNY-128算法抵抗差分攻擊、線性攻擊、相關TWEAKEY攻擊的安全界輪數，具體為

(1) 抵抗差分攻擊與線性攻擊的安全界輪數將從15輪降低為8輪；

(2) 對應TWEAKEY比特長度128、256、384三種情況，抵抗相關TWEAKEY攻擊的安全界輪數將分別從19輪降低為11輪、從22輪降低為15輪、從26輪降低為18輪。

3 結束語

筆者提出了一種新的8比特輕量化S盒設計方法，其單輪邏輯運算僅涉及4個比特與運算和4個比特異或運算，迭代4輪后得到的S盒其差分均勻度為16、非線性度為96、分量函數的代數次數能達到6且整體平衡。與目前已有的輕量化S盒設計方法相比，筆者設計的8比特輕量化S盒在硬件實現資源小的條件下達到已知最優的差分均勻度和非線性度，同時具有較高的代數次數，特別適用于設計高安全強度的輕量化密碼算法。