基于SAT的GRANULE算法不可能差分分析

doi:10.11772/j.issn.1001-9081.2023040435

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (3): 797-804.DOI: 10.11772/j.issn.1001-9081.2023040435

基于SAT的GRANULE算法不可能差分分析

武小年(), 匡晶, 张润莲, 李灵琛

广西密码学与信息安全重点实验室（桂林电子科技大学），广西桂林 541004

收稿日期:2023-04-17 修回日期:2023-06-21 接受日期:2023-06-30 发布日期:2023-12-04 出版日期:2024-03-10
通讯作者: 武小年
作者简介:匡晶（1998—），女，湖南邵阳人，硕士研究生，主要研究方向：网络安全
张润莲（1974—），女，山西介休人，副教授，博士，主要研究方向：信息安全、分布式计算
李灵琛（1988—），女，广西桂林人，讲师，博士，主要研究方向：分组密码设计与分析。
基金资助:
国家自然科学基金资助项目(62062026);广西创新研究团队项目(2019GXNSFGA245004);广西重点研发计划项目(桂科AB23026131);广西自然科学基金资助项目(2020GXNSFBA297076)

SAT-based impossible differential cryptanalysis of GRANULE cipher

Xiaonian WU(), Jing KUANG, Runlian ZHANG, Lingchen LI

Guangxi Key Laboratory of Cryptography and Information Security （Guilin University of Electronic Technology），Guilin Guangxi 541004，China

Received:2023-04-17 Revised:2023-06-21 Accepted:2023-06-30 Online:2023-12-04 Published:2024-03-10
Contact: Xiaonian WU
About author:KUANG Jing， born in 1998， M. S. candidate. Her research interests include network security.
ZHANG Runlian， born in 1974， Ph. D.， associate professor. Her research interests include information security， distributed computing.
LI Lingchen， born in 1988， Ph. D.， lecturer. Her research interests include desgin and analysis of block ciphers.
Supported by:
National Natural Science Foundation of China(62062026);Innovation Research Team Project of Guangxi(2019GXNSFGA245004);Key Research and Development Program of Guangxi(GuikeAB23026131);Natural Science Foundation of Guangxi(2020GXNSFBA297076)

摘要/Abstract

摘要：

基于布尔可满足性问题（SAT）的自动化搜索方法可以直接刻画与、或、非、异或等逻辑运算，从而建立更高效的搜索模型。为更高效地评估GRANULE算法抵抗不可能差分攻击的能力，首先，基于S盒差分分布表性质优化S盒差分性质刻画的SAT模型；其次，对GRANULE算法建立基于比特的不可能差分区分器的SAT模型，通过求解模型得到多条10轮GRANULE算法的不可能差分区分器；再次，针对不可能差分区分器，给出改进的SAT自动化验证方法并验证；最后，将得到的区分器往前和往后各扩展3轮，对GRANULE-64/80算法发起16轮的不可能差分攻击，通过该攻击可以恢复80比特主密钥，时间复杂度为2^51.8次16轮加密，数据复杂度为2^41.8个选择明文。与表现次优的对GRANULE算法不可能差分分析的方法相比，所得到的区分器轮数和密钥恢复攻击轮数都提高了3轮，且时间复杂度、数据复杂度都进一步下降。

关键词: GRANULE算法, 布尔可满足性问题, 不可能差分区分器, 差分分布表, 自动化验证

Abstract:

The Boolean SATisfiability problem （SAT）-based automated search methods can directly describe logical operations such as AND， OR， NOT， XOR， and establish more efficient search models. In order to efficiently evaluate the ability of GRANULE cipher to resist impossible differential attacks， firstly， the SAT model described by the S-box differential property was optimized based on the S-box differential distribution table property. Then， the SAT model of bit-oriented impossible differential distinguisher was established for GRANULE cipher， and multiple 10-round impossible differential distinguishers of GRANULE cipher were obtained by solving the SAT model. Furthermore， an improved SAT automated verification method was given， by which the impossible differential distinguishers were verified. Finally， 16-round impossible differential attack was performed on GRANULE-64/80 cipher， where the impossible differential distinguisher was further extended forward 3-round and backward 3-round respectively. As a result， 80-bit master key was recovered with the time complexity of 2^51.8 16-round encryptions and the data complexity of 2^41.8 chosen-plaintexts. Compared with the suboptimal results for impossible differential cryptanalysis of the GRANULE cipher， the number of distinguisher rounds and key recovery attack rounds obtained are improved by 3 rounds， and the time complexity and data complexity are further reduced.

Key words: GRANULE cipher, Boolean SATisfiability problem (SAT), impossible differential distinguisher, differential distribution table, automation verification

中图分类号:

TN918.4

武小年, 匡晶, 张润莲, 李灵琛. 基于SAT的GRANULE算法不可能差分分析[J]. 计算机应用, 2024, 44(3): 797-804.

Xiaonian WU, Jing KUANG, Runlian ZHANG, Lingchen LI. SAT-based impossible differential cryptanalysis of GRANULE cipher[J]. Journal of Computer Applications, 2024, 44(3): 797-804.

图/表 12

图1 GRANULE算法结构

Fig. 1 Structure of GRANULE cipher

表1 GRANULE算法的P置换

Tab. 1 P-permutation of GRANULE cipher

x	0	1	2	3	4	5	6	7
P（x）	4	0	3	1	6	2	7	5

表2 GRANULE算法的S盒

Tab. 2 S-box of GRANULE cipher

x	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
S（x）	e	7	8	4	1	9	2	f	5	a	b	0	6	c	d	3

表3 GRANULE算法S盒差分分布表

Tab. 3 Differential distribution table of S-box in GRANULE cipher

输入差分	输出差分
输入差分	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	2	2	2	2	2	2	2	2
2	0	0	0	4	0	0	4	0	0	0	2	2	0	0	2	2
3	0	4	0	0	0	4	0	0	0	0	2	2	0	0	2	2
4	0	0	0	4	0	0	4	0	0	0	2	2	0	0	2	2
5	0	0	0	0	0	0	4	4	2	2	0	0	2	2	0	0
6	0	0	0	0	0	0	0	0	4	4	0	0	4	4	0	0
7	0	4	0	0	0	4	4	4	0	0	0	0	0	0	0	0
8	0	0	0	2	2	2	0	2	0	0	0	2	2	2	0	2
9	0	2	4	0	2	0	0	0	2	0	0	0	0	2	0	4
a	0	0	0	2	2	2	0	2	0	0	2	0	2	2	2	0
b	0	2	4	0	2	0	0	0	0	2	0	0	2	0	4	0
c	0	0	0	2	2	2	0	2	2	2	0	2	0	0	0	2
d	0	2	4	0	2	0	0	0	0	2	0	4	2	0	0	0
e	0	0	0	2	2	2	0	2	2	2	2	0	0	0	2	0
f	0	2	4	0	2	0	0	0	2	0	4	0	0	2	0	0

表4 GRANULE算法的部分不可能差分区分器

Tab. 4 Some impossible differential distinguishers of GRANULE cipher

不可能差分输入 $Δ L 0 Δ R 0$	不可能差分输出 $Δ L 10 Δ R 10$
0000000002000000	0001000000000000
0000000004000000	0000000200000000
0000000010000000	0001000000000000
0000000010000000	0000100000000000
0000000000010000	0000200000000000
0000000000000002	0002000000000000

表4 GRANULE算法的部分不可能差分区分器

Tab. 4 Some impossible differential distinguishers of GRANULE cipher

不可能差分输入 $Δ L 0 Δ R 0$	不可能差分输出 $Δ L 10 Δ R 10$
0000000002000000	0001000000000000
0000000004000000	0000000200000000
0000000010000000	0001000000000000
0000000010000000	0000100000000000
0000000000010000	0000200000000000
0000000000000002	0002000000000000

表5 矛盾位置可能的取值

Tab. 5 Possible values of contradictory positions

可能的取值	（u₄，u₃₃）	（w₄，w₃₃）
0，0	×	√
0，1	×	√
1，0	√	×
1，1	√	×

表6 GRANULE算法S盒输入/输出差分特征概率

Tab. 6 S-box input/output differential feature probability of GRANULE cipher

输入差分	输出差分	概率
0001	1***	1/8
0010	*1	1/8
0100	*1	1/8
0110	10	1/4
0111	0***	1/8

图2 GRANULE算法的16轮攻击路线

Fig. 2 GRANULE cipher attack route of 16 rounds

表7 GRANULE 算法16轮不可能差分分析时间复杂度

Tab. 7 Time complexity of 16 round impossible differential cryptanalysis of GRANULE cipher

步骤	猜测的密钥比特	时间复杂度
1）	RK₁₅［31-16］	$2 h + 31 × 216 × 1 8 × 16 = 2 h + 40 = 2 49.8$
2）	RK₁₄［19-16］	$2 h + 16 × 216 × 24 × 2 × 1 8 × 16 = 2 h + 30 = 2 39.8$
3）	RK₀［27-12］	$2 h + 13 × 216 × 24 × 216 × 1 8 × 16 = 2 h + 42 = 2 51.8$
4）	RK₁［31-27］	$2 h - 2 × 236 × 24 × 2 × 1 8 × 16 + 240 = 2 h + 32 + 240 = 2 41.8 + 240$

表7 GRANULE 算法16轮不可能差分分析时间复杂度

Tab. 7 Time complexity of 16 round impossible differential cryptanalysis of GRANULE cipher

步骤	猜测的密钥比特	时间复杂度
1）	RK₁₅［31-16］	$2 h + 31 × 216 × 1 8 × 16 = 2 h + 40 = 2 49.8$
2）	RK₁₄［19-16］	$2 h + 16 × 216 × 24 × 2 × 1 8 × 16 = 2 h + 30 = 2 39.8$
3）	RK₀［27-12］	$2 h + 13 × 216 × 24 × 216 × 1 8 × 16 = 2 h + 42 = 2 51.8$
4）	RK₁［31-27］	$2 h - 2 × 236 × 24 × 2 × 1 8 × 16 + 240 = 2 h + 32 + 240 = 2 41.8 + 240$

表8 S盒刻画方法优化时间对比

Tab. 8 Optimization time comparison of S-box description methods

方法	区分器轮数	搜索次数	时间/s
本文方法	10	4 096	4 752
文献［9］方法	10	4 096	14 012

表9 不同搜索方法对GRANULE算法不可能差分区分器结果比较

Tab. 9 Results comparison of impossible differential distinguishers for GRANULE cipher by different search methods

方法	轮数	方法	轮数
本文方法	10	文献［19］方法	7
文献［18］方法	5	文献［20］方法	7
文献［21］方法	7

表10 GRANULE算法不可能差分攻击结果对比

Tab. 10 Comparison of impossible differential attack results of GRANULE cipher

方法	攻击轮数	数据复杂度	时间复杂度	存储复杂度
本文方法	16	2^41.8	2^51.8	2^40.8
文献［18］方法	11	2^64.0	2^73.3	—
文献［21］方法	13	2^62.1	2^62.2	2^46.1
文献［20］方法	13	2^50.7	2^52.3	—

参考文献 23

1	BIHAM E， SHAMIR A. Differential cryptanalysis of DES-like cryptosystems ［J］. Journal of Cryptology， 1991， 4： 3-72. 10.1007/bf00630563
2	KNUDSEN L. DEAL — a 128-bit block cipher ［J］. Complexity， 1998， 258（2）： 216.
3	BIHAM E， BIRYUKOV A， SHAMIR A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials ［C］// Proceedings of the Conference on 1999 Advances in Cryptology — EUROCRYPT’99. Cham： Springer， 1999： 12-23. 10.1007/3-540-48910-x_2
4	MOUHA N， PRENEEL B. Towards finding optimal differential characteristics for ARX： application to Salsa20 ［EB/OL］. （2013-11-13）［2022-12-12］. .
5	KÖLBL S， LEANDER G， TIESSEN T. Observations on the Simon block cipher family ［C］// Proceedings of the 2015 Annual Cryptology Conference. Cham： Springer， 2015： 161-185. 10.1007/978-3-662-47989-6_8
6	LIU Y， DE WITTE G， RANEA A， et al. Rotational-XOR cryptanalysis of reduced-round SPECK ［J］. IACR Transactions on Symmetric Cryptology， 2017， 2017 （3）： 24-36. 10.46586/tosc.v2017.i3.24-36
7	SUN L， WANG W， WANG M. More accurate differential properties of LED64 and Midori64 ［J］. IACR Transactions on Symmetric Cryptology， 2018， 2018（3）： 93-123. 10.46586/tosc.v2018.i3.93-123
8	HU X， LI Y， JIAO L， et al. Mind the propagation of states ［C］// Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security. Cham： Springer， 2020： 415-445. 10.1007/978-3-030-64837-4_14
9	LIU Y， LIANG H， LI Met al. STP models of optimal differential and linear trail for linear trail for S-box based ciphers ［J］. SCIENCE CHINA Information Sciences， 2021， 64（5）： 159103. 10.1007/s11432-018-9772-0
10	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， 2021（1）： 269-315. 10.46586/tosc.v2021.i1.269-315
11	MATSUI M. On correlation between the order of S-boxes and the strength of DES ［C］// Proceedings of the 1994 Workshop on the Theory and Application of Cryptographic Techniques. Cham： Springer， 1994： 366-375. 10.1007/bfb0053451
12	NIU C， LI M， WANG M， et al. Related-tweak impossible differential cryptanalysis of reduced-round TweAES ［C］// Proceedings of the 28th International Conference on the Selected Areas in Cryptography. Cham： Springer， 2022： 223-245. 10.1007/978-3-030-99277-4_11
13	BANSOD B， PATIL A， PISHAROTY N. GRANULE： an ultra lightweight cipher design for embedded security ［EB/OL］. （2018-06-18）［2022-12-12］. . 10.1002/sec.1692
14	MATSUI M. Linear cryptanalysis method for DES cipher ［C］// Proceedings of the 1993 Workshop on the Theory and Application of Cryptographic Techniques. Cham： Springer， 1993： 386-397. 10.1007/3-540-48285-7_33
15	BOGDANOV A， KHOVRATOVICH D， RECHBERGER C. Biclique cryptanalysis of the full AES ［C］// Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security. Cham： Springer， 2011： 344-371. 10.1007/978-3-642-25385-0_19
16	BOGDANOV A， RIJMEN V. Linear hulls with correlation zero and linear cryptanalysis of block ciphers ［J］. Designs， Codes and Cryptography， 2014， 70： 369-383. 10.1007/s10623-012-9697-z
17	DEMIRCI H， TAŞKIN İ， ÇOBAN M， et al. Improved meet-in-the -middle attacks on AES ［C］// Proceedings of the 10th International Conference on Cryptology in India. Cham： Springer， 2009： 144-156. 10.1007/978-3-642-10628-6_10
18	石淑英，何骏. GRANULE算法的不可能差分分析［J］. 计算机工程，2019，45（10）：134-138.
	SHI S Y， HE J. Impossible differential cryptanalysis of GRANULE algorithm ［J］. Computer Engineering， 2019， 45（10）： 134-138.
19	武小年，李迎新，韦永壮，等. GRANULE和MANTRA算法的不可能差分区分器分析［J］. 通信学报，2020，41（1）：94-101. 10.11959/j.issn.1000-436x.2020025
	WU X N， LI Y X， WEI Y Z， et al. Impossible differential distinguisher analysis of GRANULE and MANTRA algorithm ［J］. Journal on Communication， 2020， 41（1）： 94-101. 10.11959/j.issn.1000-436x.2020025
20	赵晨曦.轻量级分组密码的不可能差分分析［D］. 西安：西安电子科技大学，2021： 41-51.
	ZHAO C X. Impossible differential cryptanalysis of lightweigh block ciphers［D］. Xi’an：Xidian University， 2021： 41-51.
21	刘先蓓，刘亚. GRANULE算法的截断不可能差分分析［J］. 山西师范大学学报（自然科学版），2023，37（1）：41-51.
	LIU X B， LIU Y. Truncated impossible differential cryptanalysis of GRANULE ［J］. Journal of Shanxi Normal University （Natural Science Edition）， 2023， 37（1）： 41-51.
22	CUI T， CHEN S， JIA K， et al. New automatic search tool for impossible differentials and zero-correlation linear approximations［EB/OL］. ［2023-04-01］. . 10.1007/s11432-018-1506-4
23	韦永壮，史佳利，李灵琛. LiCi分组密码算法的不可能差分分析［J］.电子与信息学报，2019，41（7）：1610-1617. 10.11999/JEIT180729
	WEI Y Z， SHI J L， LI L C. Impossible differential cryptanalysis of LiCi block cipher ［J］. Journal of Electronics & Information Technology， 2019， 41（7）： 1610-1617. 10.11999/JEIT180729

[1]	刘家芬. 基于串空间理论的安全协议自动验证[J]. 计算机应用, 2015, 35(7): 1870-1876.
[2]	杨建书吴尽昭周瑾. 基于CSP的OWL-S语义分析与建模[J]. 计算机应用, 2010, 30(8): 2173-2176.

基于SAT的GRANULE算法不可能差分分析

SAT-based impossible differential cryptanalysis of GRANULE cipher

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 23

相关文章 2

编辑推荐

Metrics