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

doi:10.11772/j.issn.1001-9081.2022091395

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (9): 2784-2788.DOI: 10.11772/j.issn.1001-9081.2022091395

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP309

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

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.

图/表 9

图1 PFP算法加密流程

Fig. 1 Encryption flow of PFP

图2 轮函数F的加密流程

Fig. 2 Encryption flow of round function F

表1 PFP算法的S盒

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

表2 PFP算法S盒的差分分布表

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

表3 PFP算法的差分传播规律

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$

表3 PFP算法的差分传播规律

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$

图3 两轮轮函数的差分传播

Fig. 3 Differential propagation of 2-round round function

图4 PFP算法的9轮不可能差分分析

Fig. 4 9-round impossible differential cryptanalysis of PFP

图5 PFP算法的10轮不可能差分分析

Fig. 5 10-round impossible differential cryptanalysis of PFP

表4 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$

表4 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$

参考文献 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]	陈侃松, 郑园, 许立君, 王周宇, 张哲, 姚福娟. 基于ThetaMEX全局池化的人脸识别神经网络——ShuffaceNet[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2572-2580.
[2]	林东东, 李曼曼, 陈少真. 基于神经区分器的KATAN48算法条件差分分析方法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2462-2470.
[3]	石一鹏, 刘杰, 祖锦源, 张涛, 张国群. 基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1504-1510.
[4]	文凯, 唐伟伟, 熊俊臣. 基于注意力机制和有效分解卷积的实时分割算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2659-2666.
[5]	李姚舜, 刘黎志. 嵌入注意力机制的轻量级钢筋检测网络[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2900-2908.
[6]	刘炜, 张聪, 佘维, 宋轩, 田钊. 基于Merkle山脉的数据可信溯源方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2765-2771.
[7]	王娟, 袁旭亮, 武明虎, 郭力权, 刘子杉. 基于压缩提炼网络的实时语义分割方法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 1993-2000.
[8]	贺怀清, 闫建青, 惠康华. 基于深度残差网络的轻量级人脸识别方法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2030-2036.
[9]	赖涵光, 李清, 江勇. 基于场景变化的传输控制协议拥塞控制切换方案[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1225-1234.
[10]	贺丹, 何希平, 李悦, 袁锐, 牛园园. 基于区域分块和轻量级网络的人脸反欺骗方法[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3708-3714.
[11]	吴恺凡, 殷新春. 基于随机运算符的轻量级匿名射频识别系统双向认证协议[J]. 计算机应用, 2021, 41(6): 1621-1630.
[12]	史杨潇, 章军, 陈鹏, 王兵. 基于轻量级网络的钢铁表面缺陷分类[J]. 计算机应用, 2021, 41(6): 1836-1841.
[13]	胡嵽, 冯子亮. 基于深度学习的轻量级道路图像语义分割算法[J]. 计算机应用, 2021, 41(5): 1326-1331.
[14]	顾桐, 许国良, 李万林, 李家浩, 王志愿, 雒江涛. 基于集成LightGBM和贝叶斯优化策略的房价智能评估模型[J]. 计算机应用, 2020, 40(9): 2762-2767.
[15]	朱怡, 宁振虎, 周艺华. 基于视觉特征的仿冒域名轻量级检测技术[J]. 计算机应用, 2020, 40(8): 2279-2285.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 20

相关文章 15

编辑推荐

Metrics