KNOT认证加密算法的零和区分器分析

doi:10.19665/j.issn1001-2400.2021.01.009

Abstract

Abstract:

As one of the second round candidates of the lightweight crypto standardization process,KNOT has the advantages of fast implementation in software and hardware,low hardware area and software memory.Currently,the security of KNOT has received extensive attention.In this paper,based on the flag technique,a new method to design the model of division property for S-box is proposed.Moreover,by using the structure of KNOT,a new Mixed Integer Linear Programming (MILP) model of division property for KNOT is constructed.The automated search method of zero-sum distinguisher of KNOT-256 is also further presented.It is illustrated that there exists a 30-round zero-sum distinguisher of KNOT-256 permutation.Although the security of the KNOT authenticated encryption algorithm (whose 256-bit block size version has 52 rounds in the initialization process) is not practically threatened via this distinguisher,the result verifies that the method of constructing zero-sum distinguisher is valid.

Key words: block cipher, zero-sum distinguisher, KNOT authenticated encryption algorithm, mixed integer linear programming, block cipher, zero-sum distinguisher, KNOT authenticated encryption algorithm, mixed integer linear programming

CLC Number:

TN918.4

YE Tao,WEI Yongzhuang,LI Lingchen. Analysis of zero-sum distinguisher of the KNOT authenticated encryption algorithm[J].Journal of Xidian University, 2021, 48(1): 76-86.

Figures/Tables 6

符号	定义
f^r(X)	r轮加密函数
$(f - 1) r$ (X)	r轮解密函数
\|X\|	表示集合X中包含的元素的个数
X‖Y	表示比特串X和Y串联
A-B	表示从集合A中移除包含在集合B中的元素
·	点乘运算
$e I n$	表示n比特的0/1串,e[j]=1,j∈I,其余位置为0

输入 $D k 1,4$	输出 $D K 1,4$
(0,0,0,0)	(0,0,0,0)
(1,0,0,0)	(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)
(0,1,0,0)	(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)
(1,1,0,0)	(1,0,0,0),(0,1,1,0),(0,0,0,1)
(0,0,1,0)	(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)
(1,0,1,0)	(1,0,0,0),(0,1,1,0),(0,1,0,1),(0,0,1,1)
(0,1,1,0)	(0,1,0,0),(0,0,1,0),(1,0,0,1)
(1,1,1,0)	(1,1,1,0),(0,1,0,1),(1,0,1,1)
(0,0,0,1)	(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)
(1,0,0,1)	(1,0,0,0),(0,1,0,0),(0,0,1,1)
(0,1,0,1)	(1,0,0,0),(0,1,0,0),(0,0,1,1)
(1,1,0,1)	(1,0,0,0),(0,1,1,0),(0,0,1,1)
(0,0,1,1)	(1,0,0,0),(0,1,0,0),(0,0,1,1)
(1,0,1,1)	(1,1,1,0),(1,0,0,1),(0,1,0,1)
(0,1,1,1)	(0,1,0,0),(1,0,1,0),(0,0,1,1)
(1,1,1,1)	(1,1,1,1)

输入 $D k 1,4$	输出 $D K 1,4$
(0,0,0,0)	(0,0,0,0)
(1,0,0,0)	(1,0,0,0),(0,0,1,0),(0,0,0,1)
(0,1,0,0)	(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)
(1,1,0,0)	(1,0,0,0),(0,1,1,0),(0,0,0,1)

活跃位	区分器轮数	零和位数	数据复杂度	方法	求解时间/s
$w i 10$ ,i∈v₁	20(10+10)	37+27	2⁶⁴	标志位和可分性分析	230
$w i 10$ ,i∈v₁	19(9+10)	243+14	2⁶⁴	可分性分析	1 075
$w i 15$ ,i∈v₂	30(15+15)	39+107	2²⁴⁸	标志位和可分性分析	4 072
$w i 15$ ,i∈v₂	30(15+15)	39+107	2²⁴⁸	可分性分析	16 488
$w i 15$ ,i∈v₃	30(15+15)	71+128	2²⁴⁸	标志位和可分性分析	26 239
$w i 15$ ,i∈v₃	30(15+15)	71+128	2²⁴⁸	可分性分析	大于40 000

References 19

[1]	董新锋, 张文政, 许春香.Feistel结构的8比特轻量化S盒[J/OL][2020-10-30].https://kns.cnki.net/kcms/detail/61.1076.TN.20201014.0919.002.html.
[2]	魏悦川, 潘晓中, 戎宜生, 等. 对PRINCE分组密码的不可能差分攻击[J]. 西安电子科技大学学报, 2017,44(1):119-124.
	WEI Yuechuan, PAN Xiaozhong, RONG Yisheng, et al. Impossible Differential Cryptanalysis on the PRINCE[J]. Journal of Xidian University, 2017,44(1):119-124.
[3]	CSRC.Lightweight Cryptography[EB/OL] .[2020-06-20].https://csrc.nist.gov/Projects/lightweight-cryptography.
[4]	CSRC.Lightweight Cryptography-Round 2 Candidates[EB/OL].[2020-06-20].https://csrc.nist.gov/Projects/lightweight-cryptography/round-2-candidates.
[5]	AUMASSON J P, MEIER W.Zero-sum Distinguishers for Reduced Keccak-f and for the Core Functions of Luffa and Hamsi[C/OL].[ 2020- 06- 20]. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6876033685AFD156727796 DAF826B264?doi=10.1.1.374.6193&rep=rep1&type=pdf.
[6]	KNUDSEN L, WAGNER D. Integral Cryptanalysis [C]//Lecture Notes in Computer Science:2365.Heidelberg:Springer Verlag, 2002: 112-127.
[7]	KNUDSEN L R, RIJMEN V. Known-Key Distinguishers for Some Block Ciphers [C]//Lecture Notes in Computer Science:4833.Heidelberg:Springer Verlag, 2007: 315-324.
[8]	LI Y, WANG M, LIU W, et al. Cryptanalysis of PRIMATEs[J]. Science China Information Sciences, 2020,63(1):112106.
[9]	BOURA C, CANTEAUT A. Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256 [C]// Lecture Notes in Computer Science:6544.Heidelberg:Springer Verlag, 2011: 1-17.
[10]	YAN H, LAI X, WANG L, et al. New Zero-sum Distinguishers on Full 24-round Keccak-f Using the Division Property[J]. IET Information Security, 2019,13(5):469-478.
[11]	TODO Y. Structural Evaluation by Generalized Integral Property [C]//Lecture Notes in Computer Science:9056.Heidelberg:Springer Verlag, 2015: 287-314.
[12]	WANG Q, GRASSI L, RECHBERGER C. Zero-sum Partitions of PHOTON Permutations [C]//Lecture Notes in Computer Science:10808.Heidelberg:Springer Verlag, 2018: 279-299.
[13]	LI R, JIN C, PAN H. Integral Distinguishers for Grøstl-512 and Kupyna-512 Permutation Functions[J]. IET Information Security, 2020,14(1):126-132.
[14]	WANG Q, HAO Y, TODO Y, et al. Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly [C]//Lecture Notes in Computer Science:10991.Heidelberg:Springer Verlag, 2018: 275-305.
[15]	TODO Y, MORII M. Bit-based Division Property and Application to Simon Family [C]//Lecture Notes in Computer Science:9783.Heidelberg:Springer Verlag, 2016: 357-377.
[16]	XIANG Z, ZHANG W, BAO Z, et al. Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers [C]//Lecture Notes in Computer Science:10031.Heidelberg:Springer Verlag, 2016: 648-678.
[17]	GUROBI.Gurobi[EB/OL].[ 2020- 06- 20]. http://www.gurobi.cn/.
[18]	SAGE.SageMath[EB/OL].[2020-06-20].https://www.sagemath.org/.
[19]	SASAKI Y, TODO Y. New Algorithm for Modeling S-box in MILP Based Differential and Division Trail Search [C]//Lecture Notes in Computer Science:10543.Heidelberg:Springer Verlag, 2017: 150-165.

区分器	轮数	数据复杂度	时间复杂度	存储复杂度	文献
积分区分器	17	2²⁵⁵	2²⁵⁵次17轮加密	256比特	[4]
零和区分器	20	2⁶⁴	2⁶⁴次20轮加密	512 比特	本文
零和区分器	30	2²⁴⁸	2²⁴⁸次30轮加密	512 比特	本文

Analysis of zero-sum distinguisher of the KNOT authenticated encryption algorithm

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 19

Related Articles 9

Metrics

Comments

Recommended 10

[1]	LUO Yinuo,TONG Peng,CHEN Jie,DONG Xiaoli. Self-equivalence encodings and improvements of white-box implementations [J]. Journal of Xidian University, 2022, 49(2): 146-154.
[2]	WANG Leilei,WANG Lu. Optimization of the voltage noise induced by the power gating technique [J]. Journal of Xidian University, 2019, 46(5): 48-54.
[3]	LUO Fang;ZHOU Xueguang;OU Qingyu. Cryptanalysis of the LBlock using multiple zero-correlation linear approximations [J]. J4, 2014, 41(5): 173-179.
[4]	WEI Yong-zhuang;HU Yu-pu;CHEN Jie. Differential-nonlinear attack on 33-round SHACAL-2 [J]. J4, 2010, 37(1): 102-106+118.
[5]	LI Xue-yuan;WANG Xin-mei. Generalized tweakable enciphering schemes [J]. J4, 2009, 36(4): 686-690.
[6]	CHEN Jie;HU Yu-pu;ZHANG Yue-yu. Impossible differential attack on the 17-round block cipher SMS4 [J]. J4, 2008, 35(3): 455-458.
[7]	ZHONG Ming-fu;HU Yu-pu;CHEN Jie. Square attack on the 14-round block cipher SMS4 [J]. J4, 2008, 35(1): 105-109.
[8]	LI Zan1;CAI Jue-ping2;JIN Li-jun1;CHANG Yi-lin1. 基于3DES的跳频序列族构造方法的VLSI实现 [J]. J4, 2004, 31(4): 501-504.
[9]	WEI Bao-dian1;2;LIU Jing-wei1;WANG Xin-mei1. The NESSIE block ciphers and their security [J]. J4, 2004, 31(3): 377-382.