Feistel結(jié)構(gòu)的8比特輕量化S盒

董新鋒，張文政，許春香

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

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

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

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

1 S盒及其主要密碼學(xué)性質(zhì)

1.1 符號與定義

1.1.1S盒

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

1.1.2 布爾函數(shù)的代數(shù)正規(guī)型、項數(shù)和代數(shù)次數(shù)

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

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

1.1.3 漢明重量

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

1.2 S盒主要密碼學(xué)性質(zhì)

1.2.1S盒平衡性

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

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

1.2.4CCZ等價

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

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

2 Feistel結(jié)構(gòu)的8比特S盒

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

圖1 SKINNY-128分組密碼算法中的 8×8輕量化S盒的邏輯結(jié)構(gòu)圖

在圖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盒設(shè)計方法，其單輪邏輯運算僅涉及4個比特與運算和4個比特異或運算，迭代4輪后差分均勻度為16、非線性度為96(即差分概率為2-4、線性概率為2-4)。

2.1 Feistel結(jié)構(gòu)的8比特S盒設(shè)計方法

基于八分支Feistel結(jié)構(gòu)的8比特輕量化S盒設(shè)計方法，其運算過程的結(jié)構(gòu)圖如圖2所示。

圖2 基于八分支Feistel結(jié)構(gòu)的8比特輕量化S盒設(shè)計方法結(jié)構(gòu)圖

將基于八分支Feistel結(jié)構(gòu)的8比特S盒設(shè)計方法記為算法1，具體運算過程如下。

算法1 S盒的8比特輸入數(shù)據(jù)記為(x0，x1，x2，x3，x4，x5，x6，x7)，S盒的8比特輸出數(shù)據(jù)記為(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比特輸入數(shù)據(jù)(x0，x1，x2，x3，x4，x5，x6，x7)，依次遍歷{0，1，…，255}所有整數(shù)值對應(yīng)的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)}，對任意整數(shù)值i∈{0，1，…，255}對應(yīng)的8比特二元向量(x0，x1，x2，x3，x4，x5，x6，x7)，依次計算步驟QS21至QS25。

QS21 對輸入的8比特二元向量(x0，x1，x2，x3，x4，x5，x6，x7)計算第1輪8支Feistel結(jié)構(gòu)的輪變換，即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的運算結(jié)果8比特二元向量(t0，t1，t2，t3，t4，t5，t6，t7)計算第2輪8支Feistel結(jié)構(gòu)的輪變換，即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的運算結(jié)果8比特二元向量(t0，t1，t2，t3，t4，t5，t6，t7)計算第3輪8支Feistel結(jié)構(gòu)的輪變換，即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的運算結(jié)果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的運算結(jié)果8比特二元向量(T0，T1，t2，t3，t4，t5，t6，t7)進行比特組合，得到8比特S盒Sbox在整數(shù)i的數(shù)值，即：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)}。

結(jié)論1設(shè)8比特S盒SB是由算法1產(chǎn)生的S盒，則SB是平衡的。

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

結(jié)論2設(shè)8比特S盒SB是由算法1產(chǎn)生的S盒，則SB分量函數(shù)的代數(shù)次數(shù)大于等于2。

結(jié)論3設(shè)8比特S盒SB是由算法1產(chǎn)生的S盒，則與SB對應(yīng)的f1與f2組合形式共有2114-258+1種。

2.2 輕量化8比特S盒設(shè)計方法

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

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

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的代數(shù)正規(guī)型僅包含2個2次項的限定條件下，根據(jù)算法1共找到了52個新的8比特輕量化S盒，其單輪邏輯運算僅涉及4個與運算(單比特)和4個異或運算(單比特)，經(jīng)過4輪迭代后，這52個新的8比特S盒的差分均勻度為16、非線性度為96(即差分概率為2-4、線性概率為2-4)。f1、f2代數(shù)正規(guī)型僅包含2個2次項時，密碼性質(zhì)好的52個8比特S盒對應(yīng)的向量C、D的具體結(jié)果如表1所示。

表1 52個8比特S盒對應(yīng)的f1、f2代數(shù)正規(guī)型

定理1設(shè)8比特S盒LW_SB是由算法1產(chǎn)生的表1中的52個S盒中的任意一個，則LW_SB具有如下密碼學(xué)性質(zhì)：

(1) LW_SB是平衡的；

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

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

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

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

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

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

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

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

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

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

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

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

2.4 輕量化8比特S盒的應(yīng)用

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

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

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

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

3 結(jié)束語

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