基于分治策略的SAT差分自动化搜索算法及其应用

doi:10.11959/j.issn.1000-436x.2023082

通信学报 ›› 2023, Vol. 44 ›› Issue (4): 137-144.doi: 10.11959/j.issn.1000-436x.2023082

基于分治策略的SAT差分自动化搜索算法及其应用

胡斌¹, 谈潇¹, 王森鹏¹^,²

¹ 信息工程大学密码工程学院，河南郑州 450001
² 密码科学技术国家重点实验室，北京 100878

修回日期:2023-02-03 出版日期:2023-04-25 发布日期:2023-04-01
作者简介:胡斌（1971- ），男，河南信阳人，博士，信息工程大学教授、博士生导师，主要研究方向为密码学与信息安全
谈潇（1998- ），女，湖北鄂州人，信息工程大学硕士生，主要研究方向为分组密码自动化分析
王森鹏（1990- ），男，河南商丘人，博士，信息工程大学讲师，主要研究方向为对称密码算法的设计与分析
基金资助:
国家自然科学基金资助项目(62102448)

SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications

Bin HU¹, Xiao TAN¹, Senpeng WANG¹^,²

¹ Department of Cryptogram Engineering, Information Engineering University, Zhengzhou 450001, China
² State Key Laboratory of Cryptology, Beijing 100878, China

Revised:2023-02-03 Online:2023-04-25 Published:2023-04-01
Supported by:
The National Natural Science Foundation of China(62102448)

摘要/Abstract

摘要：

为了提高自动化搜索效率，结合分治策略提出了一种基于SAT模型的最优差分特征搜索算法。利用任意部分连续轮的Matsui边界条件提供的信息，将搜索空间划分为互不相交的子集。通过分析SAT差分模型间的可满足性关系，提出一种降序分支搜索链模型。进一步地，在模型优化层面，减少了需搜索划分子集数量的方法；在算法实现层面，结合并行技术实现对模型搜索空间的约减。将加速算法应用于ARX类密码算法族SPECK，获得了 20 轮、14 轮、11 轮 SPECK-48、SPECK-96、SPECK-128 的最优差分特征，较现有最好结果分别提高了 1轮、4轮、2轮。

关键词: 差分特征, 分组密码, 自动化搜索, 分治策略

Abstract:

To improve the efficiency of automatic search, an algorithm for searching the optimal differential characteristics based on SAT model was proposed by combining the divide-and-conquer strategy.The search space was divided into disjoint subsets by using the information from Matsui boundary conditions of arbitrary continuous rounds.By analyzing the relationships between satisfiability of differential models based on SAT, a descending branch search chain model was proposed.Furthermore, at the model optimization level, the number of subsets that need to be searched and partitioned was decreased.At the level of algorithm implementation, the search space was reduced by utilizing the parallel technology.Finally, the accelerated algorithm was applied to SPECK family of ARX cryptographic algorithms.The 20, 14, 11-round optimal differential characteristics of SPECK-48, SPECK-96, SPECK-128 are obtained, which increase the previous best results by 1, 4, 2 rounds respectively.

Key words: differential characteristic, block cipher, automatic search, divide-and-conquer strategy

中图分类号:

TP391

胡斌, 谈潇, 王森鹏. 基于分治策略的SAT差分自动化搜索算法及其应用[J]. 通信学报, 2023, 44(4): 137-144.

Bin HU, Xiao TAN, Senpeng WANG. SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications[J]. Journal on Communications, 2023, 44(4): 137-144.

图/表 3

参考文献 21

[1]	National Bureau of Standards. Data encryption standard[S]. 1977.
[2]	DAEMEN J , RIJMEN V . AES proposal:Rijndael[R]. 1999.
[3]	WHEELER D J , NEEDHAM R M . TEA,a tiny encryption algorithm[M]. Berlin: Springer, 1995.
[4]	BERNSTEIN D J . The Salsa20 family of stream ciphers[M]. Berlin: Springer, 2008.
[5]	AUMASSON J P , BERNSTEIN D J . SipHash:a fast short-input PRF[C]// Proceedings of International Conference on Cryptology in India. Berlin:Springer, 2012: 489-508.
[6]	BEAULIEU R , TREATMAN-CLARK S , SHORS D ,et al. The SIMON and SPECK lightweight block ciphers[C]// Proceedings of 2015 52nd ACM/EDAC/IEEE Design Automation Conference (DAC). Piscataway:IEEE Press, 2015: 1-6.
[7]	HONG D , LEE J K , KIM D C ,et al. LEA:a 128-bit block cipher for fast encryption on common processors[C]// Proceedings of International Workshop on Information Security Applications. Berlin:Springer, 2014: 3-27.
[8]	MOUHA N , MENNINK B , HERREWEGE A V ,et al. Chaskey:an efficient MAC algorithm for 32-bit microcontrollers[C]// Proceedings of International Conference on Selected Areas in Cryptography. Berlin:Springer, 2014: 306-323.
[9]	BIHAM E , SHAMIR A . Differential cryptanalysis of DES-like cryptosystems[C]// Advances in Cryptology-CRYPTO’ 90. Berlin:Springer, 1991: 2-21.
[10]	MATSUI M . Linear cryptanalysis method for DES cipher[M]. Berlin: Springer, 1994.
[11]	MOUHA N , WANG Q J , GU D W ,et al. Differential and linear cryptanalysis using mixed-integer linear programming[C]// Proceedings of International Conference on Information Security and Cryptology. Berlin:Springer, 2012: 57-76.
[12]	MASSACCI F , MARRARO L . Logical cryptanalysis as a SAT problem[J]. Journal of Automated Reasoning, 2000,24(1): 165-203.
[13]	BIRYUKOV A , VELICHKOV V . Automatic search for differential trails in ARX ciphers[C]// Proceedings of Cryptographers’ Track at the RSA Conference. Berlin:Springer, 2014: 227-250.
[14]	SONG L , HUANG Z J , YANG Q Q . Automatic differential analysis of ARX block ciphers with application to SPECK and LEA[C]// Proceedings of Australasian Conference on Information Security and Privacy. Berlin:Springer, 2016: 379-394.
[15]	BIRYUKOV A , VELICHKOV V , CORRE Y L . Automatic search for the best trails in ARX:application to block cipher speck[C]// Proceedings of International Conference on Fast Software Encryption. Berlin:Springer, 2016: 289-310.
[16]	FU K , WANG M Q , GUO Y H ,et al. MILP-based automatic search algorithms for differential and linear trails for SPECK[C]// Proceedings of International Conference on Fast Software Encryption. Berlin:Springer, 2016: 268-288.
[17]	LIPMAA H , MORIAI S . Efficient algorithms for computing differential properties of addition[C]// Proceedings of Fast Software Encryption. Berlin:Springer, 2002: 336-350.
[18]	ZHANG Y J , SUN S W , CAI J H ,et al. Speeding up MILP aided differential characteristic search with Matsui’s strategy[C]// Proceedings of International Conference on Information Security. Berlin:Springer, 2018: 101-115.
[19]	SUN L , WANG W , WANG M . Accelerating the search of differential and linear characteristics with the SAT method[J]. IACR Transactions on Symmetric Cryptology, 2021(1): 269-315.
[20]	WANG S P , FENG D , HU B ,et al. The simplest SAT model of combining Matsui’s bounding conditions with sequential encoding method[J]. IACR Cryptol ePrint Arch,2022, 2022:626.
[21]	LIU Y W , WANG Q J , RIJMEN V . Automatic search of linear trails in ARX with applications to SPECK and Chaskey[C]// Proceedings of International Conference on Applied Cryptography and Network Security. Berlin:Springer, 2016: 485-499.

算法	轮数/轮	最优差分概率	时间	文献
SPECK-48	19	2^-89	1 736 050.9 s	文献[20]
			827 299.5 s	本文
	20	2^-96	>10 d	本文
SPECK-96	10	2^-49	1 323 894.2 s	文献[20]
			160 641.0 s	本文
	11	2^-58	998 381.2 s	本文
	12	2^-62	154 312.1 s	本文
	13	2^-66	63 628.4 s	本文
	14	2^-72	170 265.6 s	本文
SPECK-128	9	2^-39	247 510.6 s	文献[20]
			7 043.6 s	本文
	10	2^-49	145 132.6 s	本文
	11	2^-58	1 054 561.7 s	本文

基于分治策略的SAT差分自动化搜索算法及其应用

SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 21

相关文章 15

Metrics

推荐阅读 0

分组规模/组	α	β	轮数/轮	密钥规模/bit
32	7	2	22	64
48	8	3	22	72
			23	96
64	8	3	26	96
			27	128
96	8	3	28	96
			29	144
128	8	3	32	128
			33	192
			34	256

[1]	杜少宇. 积分攻击改进——随机线性区分与密钥恢复攻击[J]. 通信学报, 2023, 44(4): 145-153.
[2]	刘正斌, 李永强, 朱朝熹. 分组密码最小活跃S盒个数快速搜索算法[J]. 通信学报, 2023, 44(1): 118-128.
[3]	李曼曼, 陈少真. 改进的减轮Kiasu-BC算法的中间相遇攻击[J]. 通信学报, 2022, 43(7): 41-48.
[4]	蒋梓龙, 金晨辉. Saturnin算法的不可能差分分析[J]. 通信学报, 2022, 43(3): 53-62.
[5]	谢敏,李嘉琪,田峰. FeW的差分故障攻击[J]. 通信学报, 2020, 41(4): 143-149.
[6]	武小年,李迎新,韦永壮,孙亚平. GRANULE和MANTRA算法的不可能差分区分器分析[J]. 通信学报, 2020, 41(1): 94-101.
[7]	谢敏,田峰,李嘉琪. TWINE算法的相关密钥不可能飞来去器攻击[J]. 通信学报, 2019, 40(9): 184-192.
[8]	沈煜,李玮,谷大武,吴益鑫,曹珊,刘亚,刘志强,周志洪. ARIA密码的积分故障分析[J]. 通信学报, 2019, 40(2): 164-173.
[9]	高杨,王永娟,王磊,王涛. 轻量级分组密码算法TWINE差分故障攻击的改进[J]. 通信学报, 2017, 38(Z2): 178-184.
[10]	谢敏,牟彦利. LBlock算法的相关密钥不可能飞来去器分析[J]. 通信学报, 2017, 38(5): 66-71.
[11]	崔杰,左海风,仲红. 对轻量级分组密码I-PRESENT-80和I-PRESENT-128的biclique攻击[J]. 通信学报, 2017, 38(11): 13-23.
[12]	王敏,吴震,饶金涛,凌杭. 针对SM4算法的约减轮故障攻击[J]. 通信学报, 2016, 37(Z1): 98-103.
[13]	王永娟,任泉宇,张诗怡. 轻量级分组密码Klein的差分故障攻击[J]. 通信学报, 2016, 37(Z1): 111-115.
[14]	黄静,赵新杰,张帆,郭世泽,周平,陈浩,杨建. PRESENT代数故障攻击的改进与评估[J]. 通信学报, 2016, 37(8): 144-156.
[15]	李荣佳,金晨辉. FOX算法的中间相遇攻击[J]. 通信学报, 2016, 37(8): 185-190.