Saturnin算法的不可能差分分析

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

摘要/Abstract

摘要：

轻量级分组密码算法Saturnin是类AES算法，在资源受限的环境下，仍具有良好的安全性。对Saturnin算法进行了不可能差分分析。首先，基于Saturnin算法的结构特性，提出并证明了Saturnin算法3.5轮不可能差分区分器的充分条件，利用此充分条件可以快速构造2^70.1个截断式不可能差分区分器。其次，从构造的2^70.1个区分器中，有针对性地挑选了64个区分器并分成了四类。将这四类区分器向前扩展2轮可得四条攻击路径。这四条攻击路径不仅具有相同的明文结构，而且具有大量的公共密钥比特，利用这2个特性，可以改善攻击方案的复杂度。结合明文早夭等分析技术，提出Saturnin算法的5.5轮不可能差分攻击方案，其数据、存储和时间复杂度分别为2^176.88个选择明文、2^143.88算法规模和2^176.91次5.5轮加密，这是目前可见的对Saturnin算法的一种不可能差分攻击方案。

关键词: 轻量级分组密码, 不可能差分, SPN结构, NIST竞赛

Abstract:

A lightweight block cipher, Saturnin, is an AES-like algorithm.In a resource-constrained environment, Saturnin can also provide high security.The impossible differential analysis on Saturnin was proposed.First, based on the structure of Saturnin, the sufficient condition of 3.5-round impossible differential distinguisher of Saturnin was presented and proved, and 2^70.1truncated impossible differential distinguishers could be quickly constructed by utilizing the sufficient condition.Then, from the constructed 2^70.1distinguishers, the 64 distinguishers could be picked out pointedly and classified into four types.Four attack trails could be obtained by appending two rounds before the four types of distinguishers.These four attack trails had the same plaintext structure and a number of common subkey bits.With the help of these two properties, the complexity of the attack scheme could be reduced.Combined with the analysis technologies such as early abort, present the 5.5-round impossible differential attack scheme with 2^176.88chosen plaintexts, 2^143.88 256-bit blocks, and 2^176.915.5-round encryption.As so far, this is the known attack scheme for Saturnin against impossible differential attack.

Key words: lightweight block cipher, impossible differential, SPN structure, NIST competition

中图分类号:

TN918.1

蒋梓龙, 金晨辉. Saturnin算法的不可能差分分析[J]. 通信学报, 2022, 43(3): 53-62.

Zilong JIANG, Chenhui JIN. Impossible differential cryptanalysis of Saturnin algorithm[J]. Journal on Communications, 2022, 43(3): 53-62.

图/表 11

表1

图1

表2

图2

图3

表3

图4

图5

表4

图6

图7

参考文献 19

[1]	CANTEAUT A , DUVAL S , LEURENT G ,et al. Saturnin:a suite of lightweight symmetric algorithms for post-quantum security[J]. IACR Transactions on Symmetric Cryptology, 2020(S1): 160-207.
[2]	BIHAM E , BIRYUKOV A , SHAMIR A . Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[C]// International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 1999: 12-23.
[3]	KIM J , HONG S , SUNG J ,et al. Impossible differential cryptanalysis for block cipher structures[C]// International Conference on Cryptology in India. Berlin:Springer, 2003: 82-96.
[4]	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.
[5]	WU S B , WANG M S . Automatic search of truncated impossible differentials for word-oriented block ciphers[C]// Progress in Cryptology - INDOCRYPT 2012. Berlin:Springer, 2012: 283-302.
[6]	MOUHA N , WANG Q J , GU D W ,et al. Differential and linear cryptanalysis using mixed-integer linear programming[C]// International Conference on Information Security and Cryptology. Berlin:Springer, 2011: 57-76.
[7]	XIANG Z J , ZHANG W T , BAO Z Z ,et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2016: 648-678.
[8]	SHI D P , SUN S W , DERBEZ P ,et al. Programming the demircisel?uk meet-in-the-middle attack with constraints[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2018: 3-34.
[9]	LIU Y , SUN S , LI C . Rotational cryptanalysis from a differential-linear perspective[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2021: 741-770.
[10]	CUI T T , CHEN S Y , FU K ,et al. New automatic tool for finding impossible differentials and zero-correlation linear approximations[J]. Science China Information Sciences, 2020,64(2): 1-3.
[11]	SASAKI Y , TODO Y . New impossible differential search tool from design and cryptanalysis aspects[C]// Advances in Cryptology – EUROCRYPT 2017. Berlin:Springer, 2017: 185-215.
[12]	HU X C , LI Y Q , JIAO L ,et al. Mind the propagation of states:new automatic search tool for impossible differentials and impossible polytopic transitions[C]// Advances in Cryptology - ASIACRYPT 2020. Berlin:Springer, 2020: 415-445.
[13]	张仕伟, 陈少真 . SIMON不可能差分及0相关路径自动化搜索算法[J]. 软件学报, 2018,29(11): 3544-3553.
	ZHANG S W , CHEN S Z . Automatic search algorithm for impossible differential trials and zero-correlation linear trials in SIMON[J]. Journal of Software, 2018,29(11): 3544-3553.
[14]	ZHANG K , GUAN J , HU B . Automatic search of impossible differentials and zero-correlation linear hulls for ARX ciphers[J]. China Communications, 2018,15(2): 54-66.
[15]	武小年, 李迎新, 韦永壮 ,等. GRANULE和MANTRA算法的不可能差分区分器分析[J]. 通信学报, 2020,41(1): 94-101.
	WU X N , LI Y X , WEI Y Z ,et al. Impossible differential distinguisher analysis of GRANULE and MANTRA algorithm[J]. Journal on Communications, 2020,41(1): 94-101.
[16]	王旭姿, 吴保峰, 侯林 ,等. SIMON算法相关密钥不可能差分特征搜索[J]. 密码学报, 2021,8(5): 881-893.
	WANG X Z , WU B F , HOU L ,et al. Searching for related-key impossible differentials for SIMON[J]. Journal of Cryptologic Research, 2021,8(5): 881-893.
[17]	DAEMEN J , RIJMEN V . Reijndael:the advanced encryption standard[J]. Dr.Dobb’s Journal:Software Tools for the Professional Programmer, 2001,26(3): 137-139.
[18]	HOU T , CUI T , ZHANG J Y . Practical attacks on reduced-round 3D and Saturnin[J]. The Computer Journal， 2021,doi:10.1093/comjnl/bxab174.
[19]	张庆贵 . 不可能差分攻击中的明文对筛选方法[J]. 计算机工程, 2010,36(2): 127-129.
	ZHANG Q G . Plaintext pair sieve methods in impossible differential attack[J]. Computer Engineering, 2010,36(2): 127-129.

分析方法	轮数	时间复杂度	数据复杂度	存储复杂度	文献
中间相遇	7.5	2²⁴⁴	2²⁴⁴	2²⁴⁴	文献[1]
Yoyo	5	2⁴⁶	2^39.1	—	文献[8]
不可能差分	5.5	2^176.91	2^176.88	2^143.88	本文

非0页数		非0片数
非0页数	1	2	3
1	A₁A₁=2³⁶	A₁A₂=2^52.6	A₁A₃=2⁶⁸
2	A₂A₁=2^52.6	A₂A₂=2^69.2	0
3	A₃A₁=2⁶⁸	0	0

类别	序号	截断式输入差分	截断式输出差分
	1	(0,4,8)	(0,1,2,3)
	2	(0,4,12)	(4,5,6,7)
一	3	(0,8,12)	(8,9,10,11)
	4	(4,8,12)	(12,13,14,15)
	5	(1,5,9)	(0,1,2,3)
	6	(1,5,13)	(4,5,6,7)
二	7	(1,9,13)	(8,9,10,11)
	8	(5,9,13)	(12,13,14,15)
	9	(2,6,10)	(0,1,2,3)
	10	(2,6,14)	(4,5,6,7)
三	11	(2,10,14)	(8,9,10,11)
	12	(6,10,14)	(12,13,14,15)
	13	(3,7,11)	(0,1,2,3)
	14	(3,7,15)	(4,5,6,7)
四	15	(3,11,15)	(8,9,10,11)
	16	(7,11,15)	(12,13,14,15)