全轮Shadow算法的差分和线性特征分析

doi:10.11772/j.issn.1001-9081.2023121762

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (12): 3839-3843.DOI: 10.11772/j.issn.1001-9081.2023121762

全轮Shadow算法的差分和线性特征分析

项勇¹, 李艳俊¹^,²(), 黄丁韫², 陈愚¹, 谢惠琴²

^1.中国电子科技集团公司第十五研究所信息产业信息安全测评中心，北京 100083
^2.北京电子科技学院密码科学与技术系，北京 100070

收稿日期:2023-12-22 修回日期:2024-03-27 接受日期:2024-04-01 发布日期:2024-04-15 出版日期:2024-12-10
通讯作者: 李艳俊
作者简介:项勇（1978—），男，江苏镇江人，高级工程师，硕士，主要研究方向：信息安全系统测评
黄丁韫（2000—），男，江西宜春人，硕士研究生，主要研究方向：分组密码的实现、人工智能
陈愚（1982—），男，山东莒县人，工程师，硕士，主要研究方向：信息安全系统管理
谢惠琴（1992—），女，福建宁德人，讲师，博士，主要研究方向：量子密码、分组密码的设计与分析。
基金资助:
北京市自然科学基金资助项目(4234084)

Differential and linear characteristic analysis of full-round Shadow algorithm

Yong XIANG¹, Yanjun LI¹^,²(), Dingyun HUANG², Yu CHEN¹, Huiqin XIE²

^1.Information Industry Information Security Evaluation Center，The 15th Research Institute of China Electronics Technology Group Corporation，Beijing 100083，China
^2.Department of Cryptographic Science and Technology，Beijing Electronic Science and Technology Institute，Beijing 100070，China

Received:2023-12-22 Revised:2024-03-27 Accepted:2024-04-01 Online:2024-04-15 Published:2024-12-10
Contact: Yanjun LI
About author:XIANG Yong， born in 1978， M. S.， senior engineer. His research interests include information security system evaluation.
HUANG Dingyun， born in 2000， M. S. candidate. His research interests include implementation of block cipher， artificial intelligence.
CHEN Yu， born in 1982， M. S.， engineer. His research interests include network security system management.
XIE Huiqin， born in 1992， Ph. D.， lecturer. Her research interests include quantum cryptography， design and analysis of block cipher.
Supported by:
Beijing Natural Science Foundation(4234084)

摘要/Abstract

摘要：

随着射频识别（RFID）技术、无线传感器的应用越来越广泛，为了保护这类资源受限设备存储和传输的数据，轻量级密码应运而生。轻量级密码的密钥长度较短、轮数较少，因此在正式投入使用前，有必要对轻量级密码进行精确的安全性分析。针对轻量级密码安全需求，分析全轮Shadow算法的差分和线性特征。首先，提出一种二次差分的概念，从而更清楚地刻画差分特征，证明该算法存在概率为1的全轮差分特征，并通过实验验证差分特征的正确性；其次，给出全轮线性特征，即证明给定一组Shadow-32（或Shadow-64）的明密文，可以获取8（或16）比特的密钥信息，并通过实验验证以上说法的正确性；再次，基于明文、密文和轮密钥之间的线性等式关系估计2次布尔函数的方程数和自变量数，再得到求解初始密钥的计算复杂度为 $2 63.4$ ；最后，总结Shadow算法的结构特点，并提出下一步的研究重点。此外，全轮Shadow算法的差分和线性特征的分析工作对其他轻量级密码的差分和线性分析具有一定的借鉴作用。

关键词: Shadow 算法, 轻量级分组密码, 差分特征, 线性特征, 密钥恢复

Abstract:

As Radio Frequency IDentification （RFID） technology and wireless sensors become increasingly common， the need of secure data transmitted and processed by such devices with limited resources leads to the emergence and growth of lightweight ciphers. Characterized by their small key sizes and limited number of encryption rounds， precise security evaluation of lightweight ciphers is needed before putting into service. The differential and linear characteristics of full-round Shadow algorithm were analyzed for lightweight ciphers’ security requirements. Firstly， a concept of second difference was proposed to describe the differential characteristic more clearly， the existence of a full-round differential characteristic with probability 1 in the algorithm was proved， and the correctness of differential characteristic was verified through experiments. Secondly， a full-round linear characteristic was provided. It was proved that with giving a set of Shadow-32 （or Shadow-64） plain ciphertexts， it is possible to obtain 8 （or 16） bits of key information， and its correctness was experimentally verified. Thirdly， based on the linear equation relationship between plaintexts， ciphertexts and round keys， the number of equations and independent variables of the quadratic Boolean function were estimated. After that， the computational complexity of solving the initial key was calculated to be $2 63.4$ . Finally， the structural features of Shadow algorithm were summarized， and the focus of future research was provided. Besides， differential and linear characteristic analysis of full-round Shadow algorithm provides preference for the differential and linear analysis of other lightweight ciphers.

Key words: Shadow algorithm, lightweight block cipher, differential characteristic, linear characteristic, key recovery

中图分类号:

TP309.7

项勇, 李艳俊, 黄丁韫, 陈愚, 谢惠琴. 全轮Shadow算法的差分和线性特征分析[J]. 计算机应用, 2024, 44(12): 3839-3843.

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.

图/表 4

图1 Shadow算法的轮函数

Fig. 1 Round function of Shadow algorithm

图2 密钥比特换位

Fig. 2 Exchange of key bit

表1 两组测试参数及结果

Tab. 1 Test parameters and results of two groups

轮数 $i$	第1组明文（ $p 0 : 0 x a d 75 e a b 3; p 1 : 0 x 1 c 18127 c$ ）					第2组明文（ $p 0 : 0 x a d 75 e a b 3; p 1 : 0 x 49 d b 4 a 79$ ）
轮数 $i$	$Δ X i, 0$	$Δ X i, 1$	$Δ X i, 2$	$Δ X i, 3$	$Δ X i, 0 ⊕ Δ X i, 2$	$Δ X i, 0$	$Δ X i, 1$	$Δ X i, 2$	$Δ X i, 3$	$Δ X i, 0 ⊕ Δ X i, 2$
1	0x79	0xfd	0xf1	0x23	0x88	0x19	0xe2	0xef	0xca	0xf6
2	0x6f	0xf5	0x26	0xdc	0x49	0xcc	0x6e	0x88	0xd9	0x44
3	0x50	0xf4	0xd8	0xc7	0x88	0xae	0x15	0x58	0x29	0xf6
4	0x5c	0x0c	0x15	0x23	0x49	0xf0	0x66	0xb4	0x1b	0x44
5	0x7f	0x89	0xf7	0xa7	0x88	0xd3	0xe6	0x25	0xb1	0xf6
6	0x72	0x66	0x3b	0x3e	0x49	0xa7	0x29	0xe3	0x39	0x44
7	0x27	0xce	0xaf	0x70	0x88	0xc3	0x21	0x35	0xa9	0xf6
8	0xcc	0x39	0x85	0x4b	0x49	0x2f	0x5a	0x6b	0x5e	0x44
9	0x55	0x14	0xdd	0xd0	0x88	0xc7	0xfb	0x31	0x1c	0xf6
10	0x08	0x70	0x41	0xfd	0x49	0xc8	0xaf	0x8c	0x92	0x44
11	0xd8	0x49	0x50	0x02	0x88	0xfa	0xec	0x0c	0x06	0xf6
12	0x43	0xe0	0x0a	0xfc	0x49	0x22	0xdd	0x66	0xc5	0x44
13	0xc4	0x4a	0x4c	0x59	0x88	0xe2	0x7a	0x14	0xad	0xf6
14	0x50	0xbe	0x19	0x0d	0x49	0xf5	0x6f	0xb1	0x01	0x44
15	0x77	0xd8	0xff	0x58	0x88	0x8c	0xa0	0x7a	0x81	0xf6
16	0xd0	0x41	0x99	0x7c	0x49	0xd4	0x8e	0x90	0xeb	0x44

表1 两组测试参数及结果

Tab. 1 Test parameters and results of two groups

轮数 $i$	第1组明文（ $p 0 : 0 x a d 75 e a b 3; p 1 : 0 x 1 c 18127 c$ ）					第2组明文（ $p 0 : 0 x a d 75 e a b 3; p 1 : 0 x 49 d b 4 a 79$ ）
轮数 $i$	$Δ X i, 0$	$Δ X i, 1$	$Δ X i, 2$	$Δ X i, 3$	$Δ X i, 0 ⊕ Δ X i, 2$	$Δ X i, 0$	$Δ X i, 1$	$Δ X i, 2$	$Δ X i, 3$	$Δ X i, 0 ⊕ Δ X i, 2$
1	0x79	0xfd	0xf1	0x23	0x88	0x19	0xe2	0xef	0xca	0xf6
2	0x6f	0xf5	0x26	0xdc	0x49	0xcc	0x6e	0x88	0xd9	0x44
3	0x50	0xf4	0xd8	0xc7	0x88	0xae	0x15	0x58	0x29	0xf6
4	0x5c	0x0c	0x15	0x23	0x49	0xf0	0x66	0xb4	0x1b	0x44
5	0x7f	0x89	0xf7	0xa7	0x88	0xd3	0xe6	0x25	0xb1	0xf6
6	0x72	0x66	0x3b	0x3e	0x49	0xa7	0x29	0xe3	0x39	0x44
7	0x27	0xce	0xaf	0x70	0x88	0xc3	0x21	0x35	0xa9	0xf6
8	0xcc	0x39	0x85	0x4b	0x49	0x2f	0x5a	0x6b	0x5e	0x44
9	0x55	0x14	0xdd	0xd0	0x88	0xc7	0xfb	0x31	0x1c	0xf6
10	0x08	0x70	0x41	0xfd	0x49	0xc8	0xaf	0x8c	0x92	0x44
11	0xd8	0x49	0x50	0x02	0x88	0xfa	0xec	0x0c	0x06	0xf6
12	0x43	0xe0	0x0a	0xfc	0x49	0x22	0xdd	0x66	0xc5	0x44
13	0xc4	0x4a	0x4c	0x59	0x88	0xe2	0x7a	0x14	0xad	0xf6
14	0x50	0xbe	0x19	0x0d	0x49	0xf5	0x6f	0xb1	0x01	0x44
15	0x77	0xd8	0xff	0x58	0x88	0x8c	0xa0	0x7a	0x81	0xf6
16	0xd0	0x41	0x99	0x7c	0x49	0xd4	0x8e	0x90	0xeb	0x44

图3 线性等式验证结果

Fig. 3 Validation results of linear equations

参考文献 21

1	SINGH P， ACHARYA B， CHAURASIYA R K. Lightweight cryptographic algorithms for resource-constrained IoT devices and sensor networks ［M］// SHARMA S K， BHUSHAN B， DEBNATH N C. Security and privacy issues in IoT devices and sensor networks： a volume in advances in ubiquitous sensing applications for healthcare. New York： Academic Press， 2021： 153-185.
2	WU W， ZHANG L. LBlock： a lightweight block cipher［C］// Proceedings of the 2011 International Conference on Applied Cryptography and Network Security， LNCS 6715. Berlin： Springer， 2011： 327-344.
3	BOGDANOV A， KNUDSEN L R， 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.
4	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. Berlin： Springer， 2012： 1-18.
5	BANIK S， BOGDANOV A， ISOBE T， et al. Midori： a block cipher for low energy［C］// Proceedings of the 2015 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 9453. Berlin： Springer， 2015： 411-436.
6	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.
7	OJHA S K， KUMAR N， JAIN K， et al. TWIS — a lightweight block cipher ［C］// Proceedings of the 2009 International Conference on Information Systems Security， LNCS 5905. Berlin： Springer， 2009：280-291.
8	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 the 2013 International Workshop on Information Security Applications， LNCS 8267. Cham： Springer， 2014： 3-27.
9	BANSOD G， PISHAROTY N， PATIL A. PICO： an ultra lightweight and low power encryption design for ubiquitous computing ［J］. Defence Science Journal， 2016， 66（3）： 259-265.
10	GUO Y， LI L， LIU B. Shadow： a lightweight block cipher for IoT nodes ［J］. IEEE Internet of Things Journal， 2021， 8（16）： 13014-13023.
11	SU B， WU W， ZHANG L， et al. Full-round differential attack on TWIS block cipher［C］// Proceedings of the 2010 International Workshop on Information Security Applications， LNCS 6513. Berlin： Springer， 2011： 234-242.
12	BLONDEAU C， PEYRIN T， WANG L. Known-key distinguisher on full PRESENT［C］// Proceedings of the 2015 Annual International Cryptology Conference， LNCS 9215. Berlin： Springer， 2015： 455-474.
13	TODO Y. Integral cryptanalysis on full MISTY1［J］. Journal of Cryptology， 2017， 30（3）： 920-959.
14	LALLEMAND V， NAYA-PLASENCIA M. Cryptanalysis of KLEIN［C］// Proceedings of the 2014 International Workshop on Fast Software Encryption， LNCS 8540. Berlin： Springer， 2015： 451-470.
15	王彩冰，张志宇，胡磊. 对轻量级分组密码 PICO 算法的差分攻击［J］.密码学报， 2023， 10（4）：685-701.
	WANG C B， ZHANG Z Y， HU L. Differential cryptanalysis on ultra lightweight block cipher PICO ［J］. Journal of Cryptologic Research， 2023， 10（4）： 685-701.
16	GUO J， JEAN J， NIKOLIC I， et al. Invariant subspace attack against Midori 64 and the resistance criteria for S-box designs ［J］. IACR Transactions on Symmetric Cryptology， 2016， 2016（1）： 33-56.
17	KIM S， SHIN M， KIM S， et al. Shining light on the Shadow： full-round practical distinguisher for lightweight block cipher Shadow［EB/OL］. ［2023-08-08］..
18	LI Y， LIN H， BI X， et al. MILP-based differential cryptanalysis on full-round Shadow［J］. Journal of Information Security and Applications， 2024， 81： No.103696.
19	BIHAM E， SHAMIR A. Differential cryptanalysis of DES-like cryptosystems ［J］. Journal of Cryptology， 1991， 4： 3-72.
20	MATSUI M. The first experimental cryptanalysis of the Data Encryption Standard［C］// Proceedings of the 1994 Annual International Cryptology Conference， LNCS 839. Berlin： Springer， 1994： 1-11.
21	BARDET M， FAUGÈRE J C， SALVY B， et al. On the complexity of solving quadratic Boolean systems［J］. Journal of Complex， 2013， 29（1）： 53-75.

[1]	李艳俊, 葛耀东, 王琦, 张伟国, 刘琛. 改进的KLEIN算法及其量子分析[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2810-2817.
[2]	李艳俊, 景小宇, 谢惠琴, 项勇. 量子计算模型下PFP算法的安全性分析[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1166-1171.
[3]	孙晓玲, 李姗姗, 杨光, 杨秋格. 基于差分表的Blow-CAST-Fish算法的密钥恢复攻击[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2742-2749.
[4]	巫光福, 戴子恒. 应对反应攻击的级联中密度准循环奇偶校验码公钥方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3274-3280.
[5]	刘宗甫, 袁征, 赵晨曦, 朱亮. 对PICO算法基于可分性的积分攻击[J]. 计算机应用, 2020, 40(10): 2967-2972.
[6]	丁建立, 穆涛, 王怀超. 基于谱回归核判别分析的候机楼室内快速定位算法[J]. 计算机应用, 2019, 39(1): 256-261.
[7]	马云飞, 王韬, 陈浩, 黄长阳. 轻量级分组密码SIMON代数故障攻击[J]. 计算机应用, 2017, 37(7): 1953-1959.
[8]	付荣. 基于智能卡实现的分组加密算法的功耗分析[J]. 计算机应用, 2015, 35(9): 2546-2552.
[9]	杨敏刘光远温万惠. 两类情感状态下心电与心率变异性信号的非线性分析[J]. 计算机应用, 2012, 32(10): 2963-2965.
[10]	周拥军尹忠海高大化. 一种抗缩放攻击的盲检测数字水印方案[J]. 计算机应用, 2010, 30(05): 1233-1235.

全轮Shadow算法的差分和线性特征分析

Differential and linear characteristic analysis of full-round Shadow algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 21

相关文章 10

编辑推荐

Metrics