类MARS动态密码结构不可能差分区分器的自动化分析研究

doi:10.3778/j.issn.1002-8331.2408-0278

摘要/Abstract

摘要： 动态分组密码结构设计与安全性分析已成为当前密码学领域研究的热点，王念平等人提出了类MARS动态密码结构，其线性变换层可从[0,1]4上多个线性双射中选取，并从抵抗线性分析角度得出控制参数取值为1111时，是该结构线性变换层的一种优化设计。为进一步研究该设计在抵抗不可能差分分析的安全性能，将控制参数取值扩展成[0,1]4上线性双射集合中的一个子集，同时为提高分析效率，利用轮函数双射性质、中间相错技术和矩阵表示方法，设计了基于矩阵刻画的不可能差分自动化搜索算法，逐一对子集中16种情形的不可能差分区分器潜在轮数分析对比，当控制参数取值为0011、0101、0110、1001、1010和1100时，此6种情形存在任意轮不可能差分区分器，其他10种情形区分器为有限轮，其中控制参数1101对应结构的不可能差分区分器轮数最短。研究得出，类MARS动态密码结构同一参数设置抵抗不同密码分析强度各不相同，抗线性分析优化设计从不可能差分分析的角度看并不是最优选择，在设计密码结构时不能选择存在任意长区分器的参数，应选取抗各类密码攻击综合性能较强的设计，且提出的自动化搜索算法有助于动态密码结构的分析研究。

关键词: 分组密码, 类MARS动态密码结构, 不可能差分分析, 中间相错技术, 矩阵表示, 自动化搜索

Abstract: The design and security analysis of dynamic block cipher structure has become a research hotspot in the field of cryptography. Wang Nianping et al have proposed a MARS-like dynamic cipher structure, whose linear transformation layer can be selected from multiple linear double targets on [0,1]4, and obtained from the perspective of resistance linear analysis that the control parameter value is 1111, which is an optimal design of the linear transformation layer of the structure. In order to further study the safety performance of the design against impossible difference analysis, the control parameter values are extended to a subset of the linear bijection set on [0,1]4, At the same time, in order to improve the analysis efficiency, an automatic search algorithm for impossible difference based on matrix characterization is designed by using the bijection property of wheel function, miss-in-the-middle technique and matrix representation method. The number of potential rounds of the impossible difference divider for 16 cases in the subset are analyzed and compared one by one. When the control parameter is 0011, 0101, 0110, 1001, 1010 and 1100, there are arbitrary rounds of impossible difference divider in these 6 cases, and the discriminators in the other 10 cases are finite rounds. The control parameter 1101 corresponds to the structure with the shortest number of impossible difference divider rounds. The results show that the same parameter setting of the MARS-like dynamic cipher structure has different resistance to different cryptanalysis strengths, and the optimal design of anti-linear analysis is not the optimal choice from the perspective of impossible difference analysis. When designing the cipher structure, the parameter with arbitrary long discriminator should not be selected, and the design with strong comprehensive performance against all kinds of cipher attacks should be selected. The proposed automatic search algorithm is helpful to the analysis and research of dynamic cipher structure.

Key words: block cipher, MARS-like dynamic cipher structure, impossible differential cryptanalysis , miss-in-the-middle technique, matrix representation, automated search

沈霞民, 沈璇, 卜予彤. 类MARS动态密码结构不可能差分区分器的自动化分析研究[J]. 计算机工程与应用, 2025, 61(21): 297-308.

SHEN Xiamin, SHEN Xuan, BU Yutong. Research on Automated Analysis of Impossible Difference Discriminator for MARS-Like Dynamic Cryptographic Structures[J]. Computer Engineering and Applications, 2025, 61(21): 297-308.

参考文献

[1] BEIERLE C, JEAN J, K?LBL S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C]//Advances in Cryptology. Berlin: Springer, 2016: 123-153.
[2] BEIERLE C, LEANDER G, MORADI A, et al. CRAFT: lightweight tweakable block cipher with efficient protection against DFA attacks[J]. IACR Transactions on Symmetric Cryptology, 2019(1): 5-45.
[3] BOSSERT J, LIST E, LUCKS S, et al. Pholkos-efficient large-state tweakable block ciphers from the AES round function[C]//Proceedings of Topics in Cryptology—CT-RSA 2022. Cham: Springer International Publishing, 2022: 511-536.
[4] LISKOV M, RIVEST R L, WAGNER D. Tweakable block ciphers[J]. Journal of Cryptology, 2011, 24(3): 588-613.
[5] 王念平, 郭祉成. 动态密码结构抵抗差分密码分析能力评估[J]. 通信学报, 2021, 42(8): 70-79.
WANG N P, GUO Z C. Security evaluation against differential cryptanalysis for dynamic cryptographic structure[J]. Journal on Communications, 2021, 42(8): 70-79.
[6] 杨继林, 王念平. 类CLEFIA动态密码结构抵抗差分密码分析能力评估[J]. 电子学报, 2021, 49(11): 2279-2283.
YANG J L, WANG N P. Security evaluation against differential cryptanalysis for CLEFIA-like dynamic cryptographic structure[J]. Acta Electronica Sinica, 2021, 49(11): 2279-2283.
[7] 李艳俊, 王琦, 项勇, 等. 动态密码组件对合MDS矩阵的设计与实现[J]. 微电子学与计算机, 2024, 41(7): 37-45.
LI Y J, WANG Q, XIANG Y, et al. Design and implementation of dynamic cipher component involutory MDS matrix[J]. Microelectronics & Computer, 2024, 41(7): 37-45.
[8] 郑建华, 任盛, 靖青, 等. Z密码算法设计方案[J]. 密码学报, 2018, 5(6): 579-590.
ZHENG J H, REN S, JING Q, et al. Z cipher scheme[J]. Journal of Cryptologic Research, 2018, 5(6): 579-590.
[9] ZHAO G S, WANG J. Security analysis and enhanced design of a dynamic block cipher[J]. China Communications, 2016, 13(1): 150-160.
[10] IBRAHIM S, ABBAS A M. Efficient key-dependent dynamic S-boxes based on permutated elliptic curves[J]. Information Sciences, 2021, 558: 246-264.
[11] PEYRAVIAN O M, BURWICK C, GENNARO R, et al.MARS-a candidate cipher for AES[C]//NIST AES Proposal, 1999.
[12] MORIAI S, VAUDENAY S. On the pseudorandomness of top-level schemes of block ciphers[C]//Advances in Cryptology—ASIACRYPT 2000. Berlin: Springer, 2000: 289-302.
[13] KIM J, HONG S, SUNG J, et al. Impossible differential cryptanalysis for block cipher structures[C]//Proceedings of the 4th International Conference on Progress in Cryptology—INDOCRYPT 2003. Berlin: Springer, 2003: 82-96.
[14] LUO Y Y, LAI X J, WU Z M, et al. A unified method for finding impossible differentials of block cipher structures[J]. Information Sciences, 2014, 263: 211-220.
[15] XUE W J, LAI X J. Impossible differential cryptanalysis of MARS-like structures[J]. IET Information Security, 2015, 9(4): 219-222.
[16] 王念平, 洪礼荣. 类MARS密码结构的线性特性及其优化设计[J]. 通信学报, 2021, 42(4): 169-176.
WANG N P, HONG L R. Linear property and optimal design of MARS-like cryptographic structure[J]. Journal on Communications, 2021, 42(4): 169-176.
[17] 吴文玲, 冯登国, 张文涛. 分组密码的设计与分析[M]. 2版. 北京: 清华大学出版社, 2009: 220-224.
WU W L, FENG D G, ZHANG W T. Design and analysis of block cipher[M]. 2nd ed. Beijing: Tsinghua University Press, 2009: 220-224.
[18] MATSUI M. Linear cryptanalysis method for DES cipher[C]//Advances in Cryptology—EUROCRYPT’93. Berlin: Springer, 1994: 386-397.
[19] BIHAM E, SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3-72.
[20] BIHAM E, BIRYUKOV A, SHAMIR A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[C]//Advances in Cryptology—EUROCRYPT’99. Berlin: Springer, 1999: 12-23.
[21] 李艳俊, 李寅霜, 杨明华, 等. 轻量级PFP算法的差分攻击[J]. 计算机工程与应用, 2023, 59(21): 296-302.
LI Y J, LI Y S, YANG M H, et al. Differential attack on lightweight PFP algorithm[J]. Computer Engineering and Applications, 2023, 59(21): 296-302.
[22] 沈璇, 王欣玫, 何俊, 等. Robin算法改进的6轮不可能差分攻击[J]. 计算机工程与应用, 2021, 57(5): 95-99.
SHEN X, WANG X M, HE J, et al. Revised impossible differential attack on reduced 6-round robin[J]. Computer Engineering and Applications, 2021, 57(5): 95-99.