霍珊珊，李艷俊*，劉健，李寅霜

密碼組件安全指標(biāo)測試工具設(shè)計與實現(xiàn)

霍珊珊1，2，李艷俊1，2*，劉健1，李寅霜3

（1.中國電子科技集團(tuán)公司第十五研究所 信息產(chǎn)業(yè)信息安全測評中心，北京 100083； 2.廣西密碼學(xué)與信息安全重點實驗室（桂林電子科技大學(xué)），廣西 桂林 541004； 3.北京電子科技學(xué)院 密碼科學(xué)與技術(shù)系，北京 100070）（ ? 通信作者電子郵箱liyjwuyh@163.com）

對稱密碼是信息系統(tǒng)中數(shù)據(jù)保密的核心技術(shù)，而非線性S盒通常是其中的關(guān)鍵密碼組件，廣泛用于分組密碼、序列密碼和MAC（Message Authentication Code）算法等設(shè)計。為了保障密碼算法設(shè)計的安全性，首先，研究了差分均勻度、非線性度、不動點數(shù)、代數(shù)次數(shù)與項數(shù)、代數(shù)免疫度、雪崩特性、擴(kuò)散特性的指標(biāo)測試方法；其次，通過可視化窗口設(shè)計輸出S盒的各個安全指標(biāo)結(jié)果，并以彈窗形式給出對應(yīng)安全指標(biāo)的細(xì)節(jié)描述；再次，重點設(shè)計了S盒非線性度和代數(shù)免疫度的子模塊，并對應(yīng)非線性度簡化了線性分布表，且基于定理對代數(shù)免疫度計算過程進(jìn)行了優(yōu)化和舉例說明；最后，實現(xiàn)了S盒的測試工具，并給出了7種安全指標(biāo)測試和案例演示。所提測試工具主要應(yīng)用于對稱密碼算法的非線性組件S盒安全指標(biāo)的測試，進(jìn)而為算法整體提供安全保障。

非線性組件；S盒；安全指標(biāo)；非線性度；代數(shù)免疫度

0 引言

密碼技術(shù)是信息安全領(lǐng)域的核心技術(shù)，它可以有效解決信息的真實性、完整性、保密性和不可否認(rèn)性等問題，在網(wǎng)絡(luò)空間安全防護(hù)中發(fā)揮著重要的支撐作用。密碼技術(shù)測評比密碼系統(tǒng)測評、密碼產(chǎn)品測評難度更大，自主設(shè)計的密碼算法和密碼協(xié)議需要使用專業(yè)的密碼分析工具測試，并經(jīng)過密碼專家反復(fù)研究和分析。隨著密碼設(shè)備的升級換代，密碼算法的更新日益頻繁，急需密碼算法安全性測試工具輔助密碼算法的設(shè)計和測試工作。研究密碼算法及部件的安全性測試工具，是推動密碼國產(chǎn)化、自主化的必經(jīng)之路，對保障我國自主研制密碼算法的安全性、先進(jìn)性具有重要的現(xiàn)實意義。

對稱密碼具有運(yùn)行速度快、存儲量小和易于軟硬件實現(xiàn)等優(yōu)點，被廣泛用于數(shù)據(jù)加密認(rèn)證等領(lǐng)域，如文件傳輸、網(wǎng)絡(luò)通信和數(shù)據(jù)庫系統(tǒng)安全等。對稱密碼包括分組密碼、序列密碼、MAC（Message Authentication Code）算法等。為了研制安全強(qiáng)度高的對稱密碼算法，目前普遍采用基于數(shù)理邏輯的方法構(gòu)造密碼組件，最常見的是非線性變換組件S盒和線性變換組件P置換。S盒作為密碼算法的非線性部件，它的安全性影響著密碼算法的整體安全，因此S盒的安全性研究和測試被廣泛關(guān)注［1-6］。隨著S盒的密碼指標(biāo)研究不斷成熟，更多的學(xué)者開始關(guān)注S盒輕量化設(shè)計和量子電路設(shè)計［7-10］；同時隨著密碼算法標(biāo)準(zhǔn)化、本土化的發(fā)展趨勢，對自主設(shè)計的S盒進(jìn)行安全性檢測成為必須。文獻(xiàn)［11］中采用閾值過濾方法給出了S盒透明階檢測工具。文獻(xiàn)［12］中通過增加存儲模塊，并記錄針對當(dāng)前檢測向量值得到中間差分結(jié)果值，提出一種差分均勻性快速檢測方法。文獻(xiàn)［13］中在給出S盒的差分均勻度、非線性度基礎(chǔ)上添加了差分功耗指標(biāo)評估方法。文獻(xiàn)［14-16］中進(jìn)一步引入S盒局部線性關(guān)系的分解和局部二次關(guān)系分解概念，研究了S盒的透明階，改進(jìn)了差分功耗指標(biāo)評估技術(shù)。在關(guān)注S盒安全性測試的同時，密碼學(xué)者們進(jìn)一步將這些指標(biāo)集成為測試工具，主要包括SET（S-box Evaluation Tool）架構(gòu)［17］和BSAT（Boolean function and S-box Analysis Tool）［18］，此外還有一些因保密原因未公開的類似工具。通過使用已公開的測試工具，發(fā)現(xiàn)它們主要存在兩點不足：一方面，給出的安全指標(biāo)較少，如國內(nèi)的S盒測試工具只給出了差分均勻度、非線性度和透明階指標(biāo)測試；另一方面，雖然SET和BSAT較為完善，但是都沒有包含代數(shù)免疫度測試模塊，而且每種安全指標(biāo)也只是輸出一個最終值，并未詳細(xì)描述細(xì)節(jié)部分，對整體算法的安全性保障作用有限。文獻(xiàn)［19］中提出一種用于測試對稱密碼組件安全性的系統(tǒng)及方法，該工具包含了S盒最常用的7個安全指標(biāo)，但是輸出的兩個S盒線性分布表較累贅，而且代數(shù)免疫度的測試僅基于定義完成，測試效率不高。本文優(yōu)化和改進(jìn)非線性度和代數(shù)免疫度兩個子模塊，降低了計算復(fù)雜度，提升了測試效率。

本文首先給出了S盒7個安全指標(biāo)的定義；其次描述了各個子模塊的設(shè)計原理，重點給出S盒非線性度和代數(shù)免疫度兩個子模塊的設(shè)計，詳細(xì)介紹了代數(shù)免疫度測試方法及優(yōu)化；最后設(shè)計了S盒的安全性測試工具，并以案例演示了S盒的差分均勻度、非線性度、不動點數(shù)、代數(shù)次數(shù)與項數(shù)、代數(shù)免疫度、雪崩特性、擴(kuò)散特性等子模塊的測試結(jié)果。

1 基礎(chǔ)知識

1.1　差分均勻度

對基于S盒設(shè)計的對稱密碼進(jìn)行差分分析時， S盒差分分布表中的部分非零元素會被考慮。如果個別元素值明顯大于其他元素值，則它對應(yīng)的輸入輸出差分概率較大，這是影響差分分析效果的主要因素之一，為此引入差分均勻度的概念。

1.2　非線性度

S盒的非線性度本質(zhì)上就是它的分量布爾函數(shù)的最小非線性度。

定義3 S盒的非線性度。S盒的非線性度表示為：

1.3　不動點數(shù)

不動點數(shù)的具體定義如下。

若不動點數(shù)過多，則該S盒無法充分混淆和擴(kuò)散輸入數(shù)據(jù)，進(jìn)而影響對稱密碼算法整體的混淆和擴(kuò)散性能。

1.4　代數(shù)次數(shù)與項數(shù)

S盒的代數(shù)次數(shù)一定程度上反映了S盒的線性復(fù)雜度，S盒線性復(fù)雜度越高，越難用線性表達(dá)式逼近。S盒的代數(shù)次數(shù)和項數(shù)都可以通過分量布爾函數(shù)的代數(shù)正規(guī)型獲得。

由于S盒由若干個布爾函數(shù)表示，所以關(guān)于S盒的代數(shù)次數(shù)作如下定義。

定義6 S盒代數(shù)次數(shù)與項數(shù)。S盒代數(shù)次數(shù)定義為：

取項數(shù)最小的分量函數(shù)的項數(shù)為S盒的項數(shù)，即

1.5　代數(shù)免疫度

定義8 S盒的代數(shù)免疫度。S盒代數(shù)免疫度為：

1.6　雪崩特性

雪崩特性主要測試S盒對輸入數(shù)據(jù)的混淆是否充分。通過改變輸入的1比特，統(tǒng)計得到輸出改變的比特數(shù)，由此衡量S盒的混淆強(qiáng)度。雪崩特性達(dá)到最優(yōu)時，即滿足嚴(yán)格雪崩準(zhǔn)則（Strict Avalanche Criterion， SAC），具體定義如下。

一般情況下，S盒都不能滿足嚴(yán)格雪崩準(zhǔn)則，但是可以通過輸出比特改變量評估它的雪崩特性。

1.7　擴(kuò)散特性

擴(kuò)散特性主要測試S盒對輸入數(shù)據(jù)的擴(kuò)散是否充分，具體定義如下。

2 安全性指標(biāo)測試實現(xiàn)

本文設(shè)計的測試工具用于測試對稱密碼組件S盒的密碼性能，測試模塊包括差分均勻度子模塊、非線性度子模塊、不動點數(shù)子模塊、代數(shù)次數(shù)與項數(shù)子模塊、代數(shù)免疫度子模塊、雪崩特性子模塊和擴(kuò)散特性子模塊，如圖1所示。其中，差分均勻度子模塊基于文獻(xiàn)［21］方法設(shè)計，本文以彈窗形式給出差分分布表；不動點數(shù)子模塊、雪崩子模塊和擴(kuò)散子模塊根據(jù)第1章定義直接設(shè)計。本章重點給出非線性度子模塊、代數(shù)次數(shù)與項數(shù)子模塊和代數(shù)免疫度子模塊的具體實現(xiàn)方法。

2.1　整體框架設(shè)計

S盒安全指標(biāo)測試工具的整體框架設(shè)計如圖1所示，當(dāng)輸入一個具體的S盒時，一共輸出7個安全指標(biāo)，每個指標(biāo)對應(yīng)一個彈窗按鈕，彈窗顯示該指標(biāo)的細(xì)節(jié)描述。如差分均勻度對應(yīng)的彈窗中顯示差分分布表；非線性度對應(yīng)的彈窗中顯示線性分布表；不動點數(shù)對應(yīng)的彈窗直接輸出對應(yīng)的不動點；代數(shù)次數(shù)與項數(shù)分開顯示，對應(yīng)的彈窗顯示代數(shù)正規(guī)型；代數(shù)免疫度對應(yīng)的彈窗顯示S盒輸出的每個分量函數(shù)對應(yīng)的零算子表示；雪崩特性對應(yīng)的彈窗顯示改變每一個輸入比特后不同輸出位置改變的比特數(shù)；擴(kuò)散特性對應(yīng)的彈窗顯示改變不同階數(shù)的輸入比特后，不同輸出位置改變的比特數(shù)。

圖1　S盒密碼指標(biāo)測試工具模塊

2.2　差分均勻度子模塊設(shè)計

2.3　非線性度子模塊設(shè)計

在設(shè)計非線性度子模塊部分，本文不僅輸出非線性度，還進(jìn)一步設(shè)計了線性分布表的彈出演示窗口。這種工具既能給算法設(shè)計者提供具體S盒的密碼指標(biāo)，又可以給出詳細(xì)的線性分布表，有助于準(zhǔn)確評估密碼算法抗線性分析的能力，具體設(shè)計過程如下。

2.4　不動點數(shù)子模塊設(shè)計

該子模塊設(shè)計原理簡單，對應(yīng)彈窗直接輸出不動點即可。

2.5　代數(shù)次數(shù)與項數(shù)子模塊設(shè)計

2.6　代數(shù)免疫度子模塊優(yōu)化設(shè)計

表1　的真值表

2.7　雪崩特性和擴(kuò)散特性子模塊設(shè)計

雪崩特性子模塊是擴(kuò)散特性子模塊的一個子集，通常情況下S盒不滿足完全雪崩準(zhǔn)則，即不能保證每個輸出分量函數(shù)都改變1/2的比特。設(shè)計這兩個子模塊時，對應(yīng)彈窗顯示了S盒每個輸出位改變的比特數(shù)，具體參照第3章案例演示。

3 案例演示

假設(shè)測試案例是一個4×4的S盒，即4比特輸入、4比特輸出，如表2所示。打開S盒的安全指標(biāo)測試顯示界面，如圖2所示，選擇10進(jìn)制，輸入輸出尺寸都為4，輸入“S盒的內(nèi)容”為：2，1，6，11，13，4，8，7，10，14，0，15，3，9，12，5。點擊開始評估，則對應(yīng)的7個子模塊（代數(shù)項數(shù)和代數(shù)次數(shù)分開顯示）方框內(nèi)皆有輸出結(jié)果，如差分均勻度為6，非線性度為2，不動點數(shù)為2，代數(shù)項數(shù)為6、9、8、5，代數(shù)免疫度為3、3、3、2，雪崩特性為和擴(kuò)散特性為“詳情點擊細(xì)節(jié)描述”。

表2　4×4的S盒示例

圖2　S盒安全指標(biāo)顯示界面

點擊“差分分布表”后，彈出差分分布表的窗口，除去第一行第一列，最大整數(shù)值為6，所以差分均勻度為6，細(xì)節(jié)見圖3（a）。點擊“線性分布表”后，彈出線性分布表的窗口，最小正整數(shù)為2，所以非線性度為2，細(xì)節(jié)如圖3（b）所示。

圖3　差分分布表和線性分布表

圖4　代數(shù)項數(shù)和代數(shù)免疫度細(xì)節(jié)描述

圖5　雪崩特性和擴(kuò)散特性細(xì)節(jié)描述

4 實驗測試

本文提出的S盒安全指標(biāo)測試工具基于C++編寫，在主頻為3.8 GHz、32 GB內(nèi)存主機(jī)上測試Present、AES、SM4等算法的S盒。為了方便與SET和BSAT的效率對比，只選擇了4項安全性指標(biāo)，測試結(jié)果如表3所示。雖然本文工具對Present的S盒測試時間比SET長，但是對AES的S盒測試本文工具效果更佳，與SET、BSAT相比，本文工具測試時間分別減少了256 ms和10 ms，并且本文工具還輸出了細(xì)節(jié)描述，總體性能更優(yōu)。與已有的S盒指標(biāo)測試工具相比，本文提出的測試工具可視化界面更加友好，能夠為自主設(shè)計的S盒提供更全面的安全指標(biāo)測試服務(wù)，如表4所示。

表3　測試結(jié)果

表4　S盒測試工具對比

5 結(jié)語

本文研究了組件S盒的密碼安全性指標(biāo)，實現(xiàn)了S盒的差分均勻度、非線性度、不動點數(shù)、代數(shù)次數(shù)與項數(shù)、代數(shù)免疫度、雪崩特性和擴(kuò)散特性等模塊，主要給出了S盒非線性度子模塊、代數(shù)次數(shù)與項數(shù)子模塊以及代數(shù)免疫度子模塊的設(shè)計過程，添加了細(xì)節(jié)描述彈窗，最后設(shè)計了S盒安全指標(biāo)測試工具，并給出案例演示，同時與已公開S盒測試工具進(jìn)行對比，本文工具效果優(yōu)于對比工具。在測試的過程中仍然存在一些不足之處，當(dāng)輸入的S盒規(guī)模超過16×16時，速度明顯降低。下一步考慮基于中央處理器（Central Processing Unit， GPU）改進(jìn)測試工具實現(xiàn)過程，提升測試效率。

[1] WEBSTER A F， TAVARES S E. On the design of S-boxes［C］// Proceedings of the 1985 Conference on the Theory and Application of Cryptographic Techniques， LNCS 218. Berlin： Springer， 1986： 523-534.

[2] ADAMS C， TAVARES S. The structured design of cryptographically good S-boxes［J］. Journal of Cryptology， 1990， 3（1）： 27-41.

[3] DETOMBE J， TAVARES S. Constructing large cryptographically strong S-boxes［C］// Proceedings of the 1992 International Workshop on the Theory and Application of Cryptographic Techniques， LNCS 718. Berlin： Springer， 1993： 165-181.

[4] MILLAN W. How to improve the nonlinearity of bijective S-boxes［C］// Proceedings of the 1998 Australasian Conference on Information Security and Privacy， LNCS 1438. Berlin： Springer， 1998： 181-192.

[5] MATSUI M. New block encryption algorithm MISTY［C］// Proceedings of the 1997 International Workshop on Fast Software Encryption， LNCS 1267. Berlin： Springer， 1997： 54-68.

[6] CARLET C， DALAI D K， GUPTA K C， et al. Algebraic immunity for cryptographically significant Boolean functions： analysis and construction［J］. IEEE Transactions on Information Theory， 2006， 52（7）： 3105-3121.

[7] STOFFELEN K. Optimizing S-box implementations for several criteria using SAT solvers［C］// Proceedings of the 2016 International Conference on Fast Software Encryption， LNCS 9783. Berlin： Springer， 2016： 140-160.

[8] LU Z， WANG W， HU K， et al. Pushing the limits： searching for implementations with the smallest area for lightweight S-boxes［C］// Proceedings of the 2021 International Conference on Cryptology in India， LNCS 13143. Cham： Springer， 2021： 159-178.

[9] KELLY M， KAMINSKY A， KURDZIEL M， et al. Customizable sponge-based authenticated encryption using 16-bit S-boxes［C］// Proceedings of the 2015 IEEE Military Communications Conference. Piscataway： IEEE， 2015： 43-48.

[10] 李艷俊，張偉國，葛耀東，等. 基于多項式基的Camellia算法S盒硬件優(yōu)化［J］. 電子與信息學(xué)報， 2023， 45（3）：921-928.（LI Y J， ZHANG W G， GE Y D， et al. Hardware optimization of S-box of Camellia algorithm based on polynomial basis［J］. Journal of Electronics and Information Technology， 2023， 45（3）：921-928.）

[11] 中國科學(xué)院軟件研究所. 一種快速的S盒透明階檢測方法： 200810102906.9［P］. 2008-09-03.（Institute of Software of Chinese Academy of Sciences. A fast detection method of S-box transparency order： 200810102906.9［P］. 2008-09-03.）

[12] 中國科學(xué)院軟件研究所. 一種S盒差分均勻性快速檢測方法： 201010533858.6［P］. 2011-03-30.（Institute of Software of Chinese Academy of Sciences. A fast detection method for S-box differential uniformity： 201010533858.6［P］. 2011-03-30.）

[13] 桂林電子科技大學(xué). 密碼S盒評估方法： 201611265264.5［P］. 2017-05-31.（Guilin University of Electronic Technology. Evaluation method of cryptographic S-box： 201611265264.5［P］. 2017-05-31.）

[14] 蔡婧雯，韋永壯，劉爭紅. 基于GPU的密碼S盒代數(shù)性質(zhì)評估方法［J］. 計算機(jī)應(yīng)用， 2022， 42（9）： 2750-2756.（CAI J W， WEI Y Z， LIU Z H. GPU-based method for evaluating the algebraic properties of cryptographic S-boxes［J］. Journal of Computer Applications， 2022， 42（9）： 2750-2756.）

[15] 嚴(yán)迎建，鄭震，郭朋飛，等. 一種檢測S盒能量信息泄漏的t檢驗方法［J］. 北京理工大學(xué)學(xué)報， 2021， 41（5）：542-547.（YAN Y J， ZHENG Z， GUO P F， et al. A t-test method for detecting power information leakage of S-box［J］. Transactions of Beijing Institute of Technology， 2021， 41（5）： 542-547.）

[16] 關(guān)杰，盧健偉，劉帥. 一類新的基于元胞自動機(jī)的S盒的線性性質(zhì)研究［J］. 密碼學(xué)報， 2021， 8（4）： 650-659.（GUAN J， LU J W， LIU S. Research on linear properties of a new S-box based on cellular automata［J］. Journal of Cryptologic Research， 2021， 8（4）： 650-659.）

[17] PICEK S， BATINA L， JAKOBOVI? D， et al. S-box， SET， match： a toolbox for S-box analysis［C］// Proceedings of the 2014 IFIP International Workshop on Information Security Theory and Practice， LNCS 8501. Berlin： Springer， 2014： 140-149.

[18] BEHERA P K， GANGOPADHYAY S. BSAT： a new tool for analyzing cryptographic strength of Boolean function and S-Box of symmetric cryptosystem［M］// PANIGRAHI C R， PATI B， PATTANAYAK B K， et al. Progress in Advanced Computing and Intelligent Engineering： Proceedings of ICACIE 2020， AISC 1299. Singapore： Springer， 2021： 557-569.

[19] 中國電子科技集團(tuán)公司第十五研究所，中電科（北京）信息測評認(rèn)證有限公司. 一種用于測試對稱密碼組件安全性的系統(tǒng)及方法：202210785240.1［P］. 2022-10-14.（The 15th Research Institute of China Electronics Technology Group Corporation， CETC （Beijing） Information Evaluation and Certification Co.， Ltd. A system and method for testing the security of symmetric cryptographic components：202210785240.1［P］. 2022-10-14.）

[20] MATSUI M. Linear cryptanalysis method for DES cipher［C］// Proceedings of the 1993 Workshop on the Theory and Application of Cryptographic Techniques， LNCS 765. Berlin： Springer， 1994： 386-397.

[21] 吳文玲，馮登國，張文濤. 分組密碼的設(shè)計與分析［M］. 2版. 北京：清華大學(xué)出版社， 2009： 225-234.（WU W L， FENG D G， ZHANG W T. Design and Analysis of Block Cipher［M］. 2nd ed. Beijing： Tsinghua University Press， 2009： 225-234.）

Design and implementation of cipher component security criteria testing tool

HUO Shanshan1，2， LI Yanjun1，2*， LIU Jian1， LI Yinshuang3

（1，15，100083，；2（），541004，；3，，100070，）

Symmetric cryptography is the core technology of data confidentiality in information systems. At the same time， nonlinear S-box is usually the key cryptographic component， and is widely used in the design of block cipher， stream cipher， MAC （Message Authentication Code） algorithm， etc. In order to ensure the security of the cryptographic algorithm design， firstly， the criteria testing methods for differential uniformity， nonlinearity， fixed point number， algebraic degree and item number， algebraic immunity， avalanche characteristic and diffusion characteristic were researched. Secondly， the results of each security criterion of the S-box were designed and output in the visual window， and the detailed descriptions of the corresponding security criterion were given in a pop-up window way. Thirdly， the design of the sub-components of nonlinearity and algebraic immunity was focused， and the linear distribution table was simplified according to the nonlinearity. At the same time， based on the theorem， the calculation process of algebraic immunity was optimized and illustrated with an example. Finally， the S-box testing tool was implemented with seven security criteria， and the test cases were demonstrated. The proposed tool is mainly used to test the security criteria of the nonlinear component S-box in the symmetric cryptographic algorithm， and then provides a guarantee for the security of the overall algorithm.

nonlinear component; S-box; security criterion; nonlinearity; algebraic immunity

This work is partially supported by Open Project of Guangxi Key Laboratory of Cryptography and Information Security （GCIS201912）， Open Project of Henan Key Laboratory of Network Cryptography Technology （LNCT2020-A09）， Advanced Discipline Construction Project of Beijing Universities （20210101Z0401）.

HUO Shanshan， born in 1981， senior engineer. Her research interests include information security， information system evaluation.

LI Yanjun， born in 1979， Ph. D.， associate professor. Her research interests include design and analysis of block ciphers， design and analysis of cryptographic protocol.

LIU Jian， born in 1983， M. S.， senior engineer. His research interests include network and information security， security assessment of commercial cryptographic applications.

LI Yinshuang， born in 1999， M. S. candidate. Her research interests include block cryptanalysis methods.

1001-9081（2023）10-3156-06

10.11772/j.issn.1001-9081.2022091443

2022?09?29；

2022?12?16；

廣西密碼學(xué)與信息安全重點實驗室開放課題（GCIS201912）；河南省網(wǎng)絡(luò)密碼技術(shù)重點實驗室開放課題（LNCT2020?A09）；北京高?！案呔狻睂W(xué)科建設(shè)項目（20210101Z0401）。

霍珊珊（1981—），女，北京人，高級工程師，主要研究方向：信息安全、信息系統(tǒng)評估； 李艷?。?979—），女，山西晉城人，副教授，博士，主要研究方向：分組密碼的設(shè)計與分析、密碼協(xié)議設(shè)計與分析； 劉?。?983—），男，浙江文成人，高級工程師，碩士，主要研究方向：網(wǎng)絡(luò)與信息安全、商用密碼應(yīng)用安全性評估； 李寅霜（1999—），女，四川成都人，碩士研究生，主要研究方向：分組密碼分析方法。

TP393.08

A

2022?12?28。