密碼組件安全指標測試工具設計與實現

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

密碼組件安全指標測試工具設計與實現

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

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

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

非線性組件；S盒；安全指標；非線性度；代數免疫度

0 引言

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

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

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

1 基礎知識

1.1　差分均勻度

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

1.2　非線性度

S盒的非線性度本質上就是它的分量布爾函數的最小非線性度。

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

1.3　不動點數

不動點數的具體定義如下。

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

1.4　代數次數與項數

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

由于S盒由若干個布爾函數表示，所以關于S盒的代數次數作如下定義。

定義6 S盒代數次數與項數。S盒代數次數定義為：

取項數最小的分量函數的項數為S盒的項數，即

1.5　代數免疫度

定義8 S盒的代數免疫度。S盒代數免疫度為：

1.6　雪崩特性

雪崩特性主要測試S盒對輸入數據的混淆是否充分。通過改變輸入的1比特，統計得到輸出改變的比特數，由此衡量S盒的混淆強度。雪崩特性達到最優時，即滿足嚴格雪崩準則（Strict Avalanche Criterion， SAC），具體定義如下。

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

1.7　擴散特性

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

2 安全性指標測試實現

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

2.1　整體框架設計

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

圖1　S盒密碼指標測試工具模塊

2.2　差分均勻度子模塊設計

2.3　非線性度子模塊設計

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

2.4　不動點數子模塊設計

該子模塊設計原理簡單，對應彈窗直接輸出不動點即可。

2.5　代數次數與項數子模塊設計

2.6　代數免疫度子模塊優化設計

表1　的真值表

2.7　雪崩特性和擴散特性子模塊設計

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

3 案例演示

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

表2　4×4的S盒示例

圖2　S盒安全指標顯示界面

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

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

圖4　代數項數和代數免疫度細節描述

圖5　雪崩特性和擴散特性細節描述

4 實驗測試

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

表3　測試結果

表4　S盒測試工具對比

5 結語

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

[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盒硬件優化［J］. 電子與信息學報， 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] 中國科學院軟件研究所. 一種快速的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] 中國科學院軟件研究所. 一種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] 桂林電子科技大學. 密碼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盒代數性質評估方法［J］. 計算機應用， 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] 嚴迎建，鄭震，郭朋飛，等. 一種檢測S盒能量信息泄漏的t檢驗方法［J］. 北京理工大學學報， 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] 關杰，盧健偉，劉帥. 一類新的基于元胞自動機的S盒的線性性質研究［J］. 密碼學報， 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] 中國電子科技集團公司第十五研究所，中電科（北京）信息測評認證有限公司. 一種用于測試對稱密碼組件安全性的系統及方法：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] 吳文玲，馮登國，張文濤. 分組密碼的設計與分析［M］. 2版. 北京：清華大學出版社， 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；

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

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

TP393.08

A

2022?12?28。