密码组件安全指标测试工具设计与实现

霍珊珊，李艳俊*，刘健，李寅霜

密码组件安全指标测试工具设计与实现

霍珊珊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）；北京高校“高精尖”学科建设项目（20210101Z0401）。

霍珊珊（1981—），女，北京人，高级工程师，主要研究方向：信息安全、信息系统评估； 李艳俊（1979—），女，山西晋城人，副教授，博士，主要研究方向：分组密码的设计与分析、密码协议设计与分析； 刘健（1983—），男，浙江文成人，高级工程师，硕士，主要研究方向：网络与信息安全、商用密码应用安全性评估； 李寅霜（1999—），女，四川成都人，硕士研究生，主要研究方向：分组密码分析方法。

TP393.08

A

2022⁃12⁃28。