Impossible differential cryptanalysis of reduced-round ultra-lightweight block cipher PFP

doi:10.11772/j.issn.1001-9081.2022091395

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (9): 2784-2788.DOI: 10.11772/j.issn.1001-9081.2022091395

• Cyber security • Previous Articles Next Articles

Impossible differential cryptanalysis of reduced-round ultra-lightweight block cipher PFP

Guangyao ZHAO¹, Xuan SHEN²(), Bo YU¹, Chenhui YI¹, Zhen LI²

^1.School of Electronic Science and Engineering，Hunan University of Information Technology，Changsha Hunan 410151，China
^2.College of Information and Communication，National University of Defense Technology，Wuhan Hubei 430010，China

Received:2022-09-20 Revised:2022-12-05 Accepted:2022-12-15 Online:2023-02-28 Published:2023-09-10
Contact: Xuan SHEN
About author:ZHAO Guangyao， born in 1982， Ph. D.， senior engineer. His research interests include cryptanalysis， machine learning.
YU Bo， born in 1969， Ph. D.， professor. His research interests include intelligent algorithm.
YI Chenhui， born in 1980， M. S.， senior experimentalist. Her research interests include intelligent algorithm.
LI Zhen， born in 1991， Ph. D.， associate professor. His research interests include simulation of intelligent and unmanned system.
Supported by:
National Natural Science Foundation of China(62002370);Research Program of National University of Defense Technology(ZK21-36)

缩减轮的超轻量级分组密码算法PFP的不可能差分分析

赵光耀¹, 沈璇²(), 余波¹, 易晨晖¹, 李祯²

^1.湖南信息学院电子科学与工程学院，长沙 410151
^2.国防科技大学信息通信学院，武汉 430010

通讯作者: 沈璇
作者简介:赵光耀（1982—），男，湖南湘潭人，高级工程师，博士，CCF会员，主要研究方向：密码分析、机器学习
余波（1969—），男，湖南常德人，教授，硕士，CCF会员，主要研究方向：智能算法
易晨晖（1980—），女，湖南娄底人，高级实验师，硕士，主要研究方向：智能算法
李祯（1991—），男，江西赣州人，副教授，博士，主要研究方向：智能与无人系统仿真。
基金资助:
国家自然科学基金资助项目(62002370);国防科技大学学校科研计划项目(ZK21-36)

Abstract

Abstract:

The ultra-lightweight block cipher PFP based on Feistel structure is suitable for extremely resource-constrained environments such as internet of things terminal devices. Up to now， the best impossible differential cryptanalysis of PFP is to use 7-round impossible differential distinguishers to attack the 9-round PFP， which can recover 36-bit master key. The structure of PFP was studied in order to evaluate the ability for resisting impossible differential cryptanalysis more accurately. Firstly， by analyzing the differential distribution characteristics of S-box in the round function， two groups of differences with probability 1 were found. Secondly， combined with the characteristics of the permutation layer， a set of 7-round impossible differential distinguishers containing 16 impossible differences was constructed. Finally， based on the constructed 7-round impossible differential distinguishers， 40-bit master key was recovered by performing impossible differential cryptanalysis on the 9-round PFP， and an impossible differential cryptanalysis method for 10-round PFP was proposed to recover 52-bit master key. The results show that the proposed method has great improvement in terms of the number of distinguishers， the number of cryptanalysis rounds， and the number of bits of the recovered key.

Key words: lightweight, block cipher, PFP, impossible differential, cryptanalysis

摘要：

基于Feistel结构的轻量级分组密码算法PFP适用于物联网终端设备等资源极端受限环境。目前对PFP算法不可能差分分析的最好结果是利用7轮不可能差分区分器攻击9轮PFP算法，这样可恢复36 b的种子密钥。为了更准确地评估PFP算法抵抗不可能差分分析的能力，对PFP算法结构进行研究。首先，通过分析轮函数中S盒的差分分布特性，找到了概率为1的两组差分；其次，结合置换层特点，构造出一组包含16条不可能差分的7轮不可能差分区分器；最后，基于构建的7轮不可能差分区分器，对9轮PFP算法进行不可能差分分析以恢复40 b种子密钥，并提出对10轮PFP算法的不可能差分分析方法来恢复52 b种子密钥。结果表明，所提方法在区分器数量、分析轮数、恢复密钥比特数等方面均有较大改善。

关键词: 轻量级, 分组密码, PFP, 不可能差分, 密码分析

CLC Number:

TP309

Guangyao ZHAO, Xuan SHEN, Bo YU, Chenhui YI, Zhen LI. Impossible differential cryptanalysis of reduced-round ultra-lightweight block cipher PFP[J]. Journal of Computer Applications, 2023, 43(9): 2784-2788.

赵光耀, 沈璇, 余波, 易晨晖, 李祯. 缩减轮的超轻量级分组密码算法PFP的不可能差分分析[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2784-2788.

Figures/Tables 9

Fig. 1 Encryption flow of PFP

Fig. 2 Encryption flow of round function F

Tab. 1 S-box of PFP

x	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
S	C	5	6	B	9	0	A	D	3	E	F	8	4	7	1	2

Tab. 2 Differential distribution table of S-box of PFP

输入差分	输出差分
输入差分	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	H	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	4	0	0	0	4	0	4	0	0	0	4	0	0
2	0	0	0	2	0	4	2	0	0	0	2	0	2	2	2	0
3	0	2	0	2	2	0	4	2	0	0	2	2	0	0	0	0
4	0	0	0	0	0	4	2	2	0	2	2	0	2	0	2	0
5	0	2	0	0	2	0	0	0	0	2	2	2	4	2	0	0
6	0	0	2	0	0	0	2	0	2	0	0	4	2	0	0	4
7	0	4	2	0	0	0	2	0	2	0	0	0	2	0	0	4
8	0	0	0	2	0	0	0	2	0	2	0	4	0	2	0	4
9	0	0	2	0	4	0	2	0	2	0	0	0	2	0	4	0
A	0	0	2	2	0	4	0	0	2	0	2	0	0	2	2	0
B	0	2	0	0	2	0	0	0	4	2	2	2	0	2	0	0
C	0	0	2	0	0	4	0	2	2	2	2	0	0	0	2	0
D	0	2	4	2	2	0	0	2	0	0	2	2	0	0	0	0
E	0	0	2	2	0	0	2	2	2	2	0	0	2	2	0	0
F	0	4	0	0	4	0	0	0	0	0	0	0	0	0	4	4

Tab. 3 Differential propagation rules of PFP

类型	方向	轮数	左支	右支	备注
加密	↓	0	$α 0$	$032$
		1	$032$	$α 0$
		2	$α 0$	$α 1$	$α 1 = Δ F (α 0)$
		3	$α 1$	$α 2$	$α 2 = Δ F 2 (α 0) ⊕ α 0$
		4	$α 2$	$α 3$	$α 3 = Δ F (α 2) ⊕ α 1$
解密	↑	3	$β 2$	$β 1$	$β 2 = Δ F 2 (β 0) ⊕ β 0$
		2	$β 1$	$β 0$	$β 1 = Δ F (β 0)$
		1	$β 0$	$032$
		0	$032$	$β 0$

Tab. 3 Differential propagation rules of PFP

类型	方向	轮数	左支	右支	备注
加密	↓	0	$α 0$	$032$
		1	$032$	$α 0$
		2	$α 0$	$α 1$	$α 1 = Δ F (α 0)$
		3	$α 1$	$α 2$	$α 2 = Δ F 2 (α 0) ⊕ α 0$
		4	$α 2$	$α 3$	$α 3 = Δ F (α 2) ⊕ α 1$
解密	↑	3	$β 2$	$β 1$	$β 2 = Δ F 2 (β 0) ⊕ β 0$
		2	$β 1$	$β 0$	$β 1 = Δ F (β 0)$
		1	$β 0$	$032$
		0	$032$	$β 0$

Fig. 3 Differential propagation of 2-round round function

Fig. 4 9-round impossible differential cryptanalysis of PFP

Fig. 5 10-round impossible differential cryptanalysis of PFP

Tab. 4 Comparison of impossible differential cryptanalysis of PFP

算法	区分器		分析轮数	恢复密钥比特数	数据复杂度	时间复杂度
算法	轮数	个数	分析轮数	恢复密钥比特数	数据复杂度	时间复杂度
文献［8］算法	5	1	6	32	$237$	$265$
文献［20］算法	7	1	9	36	$236$	$258$
本文算法	7	16	9	40	$237$	$266$
本文算法	7	16	10	52	$246$	$275$

Tab. 4 Comparison of impossible differential cryptanalysis of PFP

算法	区分器		分析轮数	恢复密钥比特数	数据复杂度	时间复杂度
算法	轮数	个数	分析轮数	恢复密钥比特数	数据复杂度	时间复杂度
文献［8］算法	5	1	6	32	$237$	$265$
文献［20］算法	7	1	9	36	$236$	$258$
本文算法	7	16	9	40	$237$	$266$
本文算法	7	16	10	52	$246$	$275$

References 20

1	DAEMEN J， RIJMEN V. The Design of Rijndael： The Advanced Encryption Standard （AES）， ISC［M］. 2nd ed. Berlin： Springer， 2002： 31-148.
2	BOGDANOV A， KNUDSEN L， LEANDER G， et al. PRESENT： an ultra-lightweight block cipher［C］// Proceedings of the 2007 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 4727. Berlin： Springer， 2007： 450-466.
3	IZADI M， SADEGHIYAN B， SADEGHIAN S S， et al. MIBS： a new lightweight block cipher［C］// Proceedings of the 2009 International Conference on Cryptology and Network Security， LNCS 5888. Berlin： Springer， 2009： 334-348.
4	GUO J， PEYRIN T， POSCHMANN A， et al. The LED block cipher［C］// Proceedings of the 2011 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 6917. Berlin： Springer， 2011： 326-341.
5	WU W L， ZHANG L. LBlock： a lightweight block cipher［C］// Proceedings of the 2011 International Conference on Applied Cryptography and Network Security. Berlin： Springer， 2011： 327-344. 10.1007/978-3-642-21554-4_19
6	GONG Z， NIKOVA S， LAW Y W. KLEIN： a new family of lightweight block ciphers［C］// Proceedings of the 2011 International Workshop on Radio Frequency Identification： Security and Privacy Issues， LNCS 7055. Berlin： Springer， 2012： 1-18.
7	YANG G Q， ZHU B， SUDER V， et al. The Simeck family of lightweight block ciphers［C］// Proceedings of the 2015 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 9293. Berlin： Springer， 2015： 307-329.
8	黄玉划，代学俊，时阳阳，等. 基于Feistel结构的超轻量级分组密码算法（PFP）［J］. 计算机科学， 2017， 44（3）： 163-167. 10.11896/j.issn.1002-137X.2017.03.036
	HUANG Y H， DAI X J， SHI Y Y， et al. Ultra-lightweight block cipher algorithm （PFP） based on Feistel structure［J］. Computer Science， 2017， 44（3）：163-167. 10.11896/j.issn.1002-137X.2017.03.036
9	BIHAM E， SHAMIR A. Differential cryptanalysis of DES-like cryptosystems［J］. Journal of Cryptology， 1991， 4（1）： 3-72. 10.1007/bf00630563
10	KNUDSEN L R. Truncated and higher order differentials［C］// Proceedings of the 1994 International Workshop on Fast Software Encryption， LNCS 1008. Berlin： Springer， 1995： 196-211.
11	BLONDEAU C， GÉRARD B. Multiple differential cryptanalysis： theory and practice［C］// Proceeding of the 2011 International Workshop on Fast Software Encryption. Cham： Springer， 2011： 35-54. 10.1007/978-3-642-21702-9_3
12	BIHAM E， BIRYUKOV A， SHAMIR A. Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials［C］// Proceeding of the 1999 International Conference on the Theory and Applications of Cryptographic Techniques LNCS 1592. Berlin： Springer， 1999： 12-23. 10.1007/3-540-48910-x_2
13	KNUDSEN L. DEAL - a 128-bit block cipher［EB/OL］. ［2022-07-18］. . 10.25148/etd.fi14051800
14	SHEN X， HE J. Improved impossible differential attack on 7-round reduced ARIA-256［J］. KSII Transactions on Internet and Information Systems， 2019， 13（11）： 5773-5784. 10.3837/tiis.2019.11.027
15	武小年，李迎新，韦永壮，等. 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 Communications， 2020， 41（1）： 94-101. 10.11959/j.issn.1000-436x.2020025
16	刘亚，唐伟明，沈致远，等. 轻量级分组密码Pyjamask的不可能差分分析［J］. 计算机应用研究， 2021， 38（11）：3428-3432.
	LIU Y， TANG W M， SHEN Z Y， et al. Impossible differential cryptanalysis of lightweight block cipher Pyjamask［J］. Application Research of Computers， 2021， 38（11）：3428-3432.
17	杨云霄，沈璇，孙兵. Mysterion算法的不可能差分分析［J］. 信息网络安全， 2021， 21（8）： 43-51. 10.3969/j.issn.1671-1122.2021.08.006
	YANG Y X， SHEN X， SUN B. Impossible differential cryptanalysis of Mysterion［J］. Netinfo Security， 2021， 21（8）： 43-51. 10.3969/j.issn.1671-1122.2021.08.006
18	沈璇，王欣玫，何俊，等. 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.
19	蒋梓龙，金晨辉. Saturnin算法的不可能差分分析［J］. 通信学报， 2022， 43（3）：53-62. 10.11959/j.issn.1000-436x.2022045
	JIANG Z L， JIN C H. Impossible differential cryptanalysis of Saturnin algorithm［J］. Journal on Communications， 2022， 43（3）：53-62. 10.11959/j.issn.1000-436x.2022045
20	沈璇，王欣玫，何俊，等. PFP算法改进的不可能差分分析［J］. 计算机科学， 2020， 47（7）： 263-267.
	SHEN X， WANG X M， HE J， et al. Revised impossible differential cryptanalysis of PFP block cipher［J］. Computer Science， 2020， 47（7）： 263-267.

[1]	Runlian ZHANG, Mi ZHANG, Xiaonian WU, Rui SHU. Differential property evaluation method based on GPU for large-state cryptographic S-boxes [J]. Journal of Computer Applications, 2024, 44(9): 2785-2790.
[2]	Yanjun LI, Yaodong GE, Qi WANG, Weiguo ZHANG, Chen LIU. Improved KLEIN algorithm and its quantum analysis [J]. Journal of Computer Applications, 2024, 44(9): 2810-2817.
[3]	Yongjin ZHANG, Jian XU, Mingxing ZHANG. Lightweight algorithm for impurity detection in raw cotton based on improved YOLOv7 [J]. Journal of Computer Applications, 2024, 44(7): 2271-2278.
[4]	Xiaohui CHENG, Yuntian HUANG, Ruifang ZHANG. Lightweight infrared road scene detection model based on multiscale and weighted coordinate attention [J]. Journal of Computer Applications, 2024, 44(6): 1927-1934.
[5]	Xiaogang SONG, Dongdong ZHANG, Pengfei ZHANG, Li LIANG, Xinhong HEI. Real-time object detection algorithm for complex construction environments [J]. Journal of Computer Applications, 2024, 44(5): 1605-1612.
[6]	Huantong GENG, Zhenyu LIU, Jun JIANG, Zichen FAN, Jiaxing LI. Embedded road crack detection algorithm based on improved YOLOv8 [J]. Journal of Computer Applications, 2024, 44(5): 1613-1618.
[7]	Jun FENG, Jiankang BI, Yiru HUO, Jiakuan LI. PIPNet： lightweight asphalt pavement crack image segmentation network [J]. Journal of Computer Applications, 2024, 44(5): 1520-1526.
[8]	Yanjun LI, Xiaoyu JING, Huiqin XIE, Yong XIANG. Security analysis of PFP algorithm under quantum computing model [J]. Journal of Computer Applications, 2024, 44(4): 1166-1171.
[9]	Bin XIAO, Yun GAN, Min WANG, Xingpeng ZHANG, Zhaoxing WANG. Network abnormal traffic detection based on port attention and convolutional block attention module [J]. Journal of Computer Applications, 2024, 44(4): 1027-1034.
[10]	Zijie HUANG, Yang OU, Degang JIANG, Cailing GUO, Bailin LI. Lightweight deep learning algorithm for weld seam surface quality detection of traction seat [J]. Journal of Computer Applications, 2024, 44(3): 983-988.
[11]	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]	Chenghanyu ZHANG, Yuzhe LIN, Chengke TAN, Junfan WANG, Yeting GU, Zhekang DONG, Mingyu GAO. New dish recognition network based on lightweight YOLOv5 [J]. Journal of Computer Applications, 2024, 44(2): 638-644.
[13]	Yong XIANG, Yanjun LI, Dingyun HUANG, Yu CHEN, Huiqin XIE. Differential and linear characteristic analysis of full-round Shadow algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3839-3843.
[14]	Ziqian CHEN, Kedi NIU, Zhongyuan YAO, Xueming SI. Review of blockchain lightweight technology applied to internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3688-3698.
[15]	Xin ZHAO, Xinjie LI, Jian XU, Buyun LIU, Xiang BI. Parallel medical image registration model based on convolutional neural network and Transformer [J]. Journal of Computer Applications, 2024, 44(12): 3915-3921.

Impossible differential cryptanalysis of reduced-round ultra-lightweight block cipher PFP

缩减轮的超轻量级分组密码算法PFP的不可能差分分析

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 20

Related Articles 15

Recommended Articles

Metrics