Gimli认证加密方案的不可能差分分析

doi:10.19665/j.issn1001-2400.2022.05.024

西安电子科技大学学报 ›› 2022, Vol. 49 ›› Issue (5): 213-220.doi: 10.19665/j.issn1001-2400.2022.05.024

• 计算机科学与技术 & 人工智能 • 上一篇

Gimli认证加密方案的不可能差分分析

谭豪(),申兵(),苗旭东(),张文政()

保密通信重点实验室,四川成都 610041

收稿日期:2021-09-07 出版日期:2022-10-20 发布日期:2022-11-17
作者简介:谭豪(1997—),男,硕士,E-mail:tan_hao1@163.com；|申兵(1971—),男,高级工程师,E-mail:shenbing1115@qq.com；|苗旭东(1989—),男,工程师,E-mail:miaoxudong_sx@163.com；|张文政(1966—),男,研究员,E-mail:zwz85169038@sina.com
基金资助:
国家重点研发计划(2017YFB0802000);四川省科技计划(2020JDJQ0076)

Impossible differential cryptanalysis of the Gimli authenticated encryption scheme

TAN Hao(),SHEN Bing(),MIAO Xudong(),ZHANG Wenzheng()

Institute of Southwestern Communication,Chengdu 610041,China

Received:2021-09-07 Online:2022-10-20 Published:2022-11-17

摘要/Abstract

摘要：

Gimli是美国国家标准与技术研究院发起的轻量级加密算法标准第二轮候选算法。当前,Gimli的安全性分析主要针对Gimli置换、Gimli杂凑函数、Gimli带有关联数据的认证加密方案等。Gimli认证加密方案总体采用sponge结构,适用于受限环境下的数据加密场景。目前对Gimli认证加密方案的状态恢复攻击最好结果是9轮,时间复杂度为2¹⁹⁰,数据复杂度为2¹⁹²。为了评估这种方案抵抗不可能差分分析的能力,根据Gimli置换设计了一个差分传播系统,找到了适用于分析sponge结构认证加密方案的7轮不可能差分,此不可能差分仅限制了1 bit输出差分的取值,可显著地降低状态恢复阶段的时间复杂度与数据复杂度。将7轮不可能差分向前扩展4轮,成功实现了对11轮Gimli认证加密方案的状态恢复攻击。在状态恢复阶段,基于Gimli置换前两轮的弱扩散性,将2¹²⁸的密钥猜测量缩小为2个2⁶⁴密钥猜测量,此状态恢复攻击的时间复杂度约为2¹¹⁰次加密,数据复杂度约为2^52.5,优于现有公开文献中对Gimli认证加密方案的状态恢复攻击结果。

关键词: Gimli, 轻量级密码, 认证加密方案, 差分传播系统, 不可能差分

Abstract:

Gimli is a candidate for the second round of lightweight encryption algorithm standards initiated by the National Institute of Standards and Technology of the United States.The current security analysis of Gimli focuses mainly on the Gimli permutation,Gimli hash function,and Gimli authenticated encryption with associated data.The Gimli authenticated encryption scheme generally adopts a sponge structure,which is suitable for data encryption scenarios in restricted environments.At present,the best result of the state recovery attack on the Gimli authenticated encryption scheme is 9 rounds,with a time complexity of 2¹⁹⁰ and a data complexity of 2¹⁹².This paper designs a differential propagation system based on Gimli permutation,and finds a 7-round impossible differential suitable for analyzing the sponge structure authenticated encryption scheme.This impossible differential only limits the value of the 1-bit output difference,which significantly reduces the time complexity and data complexity of the state recovery phase.In this paper,7 rounds of the impossible differential are extended forward for 4 rounds,and the state recovery attack on 11 rounds of the Gimli authenticated encryption scheme is successfully realized.In the state recovery phase,based on the weak diffusion of the first two rounds of Gimli replacement,the 2¹²⁸ key guesses are reduced to two 2⁶⁴ key guesses.The time complexity of this state recovery attack is about 2¹¹⁰ times encryption,and the data complexity is about 2^52.5,which is better than the state restoration attack result of the Gimli authenticated encryption scheme in the existing public literature.

Key words: gimli, lightweight cipher, authenticated encryption scheme, difference propagation system, impossible differential

中图分类号:

TN918

谭豪,申兵,苗旭东,张文政. Gimli认证加密方案的不可能差分分析[J]. 西安电子科技大学学报, 2022, 49(5): 213-220.

TAN Hao,SHEN Bing,MIAO Xudong,ZHANG Wenzheng. Impossible differential cryptanalysis of the Gimli authenticated encryption scheme[J]. Journal of Xidian University, 2022, 49(5): 213-220.

图/表 10

表1

表2

符号说明"

符号	说明	符号	说明
N	128 bit nonce	Δ $g i k$	经过k轮加密的状态中第i个比特的差分
T	128 bit标签	⊕	按位异或运算符
K	256 bit密钥	∧	按位逻辑与运算符
M	待加密消息	∨	按位逻辑或运算符
A	关联数据AD(Associated Data)	<<<	循环左移运算符
s_i_,_j	状态中第i行第j列的字	<<	左移运算符
$s i, j k$	经过k轮加密的状态中第i行第j列的字	‖	级联运算符
Δ $s i, j k$	经过k轮加密的状态中第i行第j列字的差分	tounit32()	将4 B转换成32 bit无符号整数
$g i k$	经过k轮加密的状态中第i个比特	tobytes()	将32 bit无符号整数转换成4 B

表2

图1

图2

表3

图3

图4

图5

图6

图7

参考文献 12

[1]	BERNSTEIN D J, KOELBL S, LUCKS S, et al. Gimli: A Cross-Platform Permutation[C]//Lecture Notes in Computer Science:10529. Heidelberg: Springer Verlag, 2017:299-320.
[2]	BERNSTEIN D J, KOELBL S, LUCKS S, et al. Gimli[R/OL].[2021-09-20]. https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/submissions-rnd2/gimli.zip .
[3]	HAMBURG M. Cryptanalysis of 22 1/2 Rounds of Gimli[R/OL].[2021-09-20]. http://eprint.iacr.org/2017/743 .
[4]	LIU F, ISOBE T, MEIER W. Automatic Verification of Differential Characteristics: Application to Reduced Gimli[C]//Lecture Notes in Computer Science:12172. Heidelberg: Springer Verlag, 2020:219-248.
[5]	LIU F, ISOBE T, MEIER W. Exploiting Weak Diffusion of Gimli:Improved Distinguishers and Preimage Attacks[J]. IACR Transactions on Symmetric Cryptology, 2021(1):185-216.
[6]	GUTIERREZ A F, LEURENT G, NAYA-PLASENCIA M, et al. New Results on Gimli: Full-Permutation Distinguishers and Improved Collisions[C] //Lecture Notes in Computer Science:12491. Heidelberg: Springer Verlag, 2020:33-63.
[7]	BIHAM E, BIRYUKOV A, SHAMIR A. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials[C]//Lecture Notes in Computer Science:1592. Heidelberg: Springer Verlag, 1999:12-23.
[8]	魏悦川, 潘晓中, 戎宜生, 等. 对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.
[9]	KIM J, HONG S, Lee S, et al. Impossible Differential Cryptanalysis for Block Cipher Structures[C]//Lecture Notes in Computer Science:2904. Heidelberg: Springer Verlag, 2003:82-96.
[10]	WU S, WANG M. Automatic Search of Truncated Impossible Differentials for Word-Oriented Block Ciphers[C]//Lecture Notes in Computer Science:7668. Heidelberg: Springer Verlag, 2012:283-302.
[11]	CUI T, CHEN S, FU K, et al. New Automatic Tool for Finding Impossible Differentials and Zero-Correlation Linear Approximations[J/OL].[2021-02-01].DOI:10.1007/s11432-018-1506-4. doi: 10.1007/s11432-018-1506-4
[12]	SUN S, HU L, WANG P, et al. Automatic Security Evaluation and(Related-key) Differential Characteristic Search:Application to SIMON,PRESENT,LBlock,DES(L) and Other Bit-Oriented Block Ciphers[C]//Lecture Notes in Computer Science:8873. Heidelberg: Springer Verlag, 2014:158-178.

Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂	Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂
		0	0	0	0	0			0	0	0	0	1
0	0	0	1	1	0	0	0	1	0	0	0	1	0
		0	0	0	1	1			1	1	1	0	1
		0	1	1	1	1			1	1	1	1	0
		1	0	1	1	1			0	0	1	1	0
1	0	0	0	1	0	0	1	1	1	0	1	0	1
		0	1	0	0	0			1	1	0	1	0
		1	1	0	1	1			0	1	0	0	1

Gimli认证加密方案的不可能差分分析

Impossible differential cryptanalysis of the Gimli authenticated encryption scheme

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 12

相关文章 4

Metrics

本文评价

推荐阅读 0

方案	攻击类型	轮数	数据复杂度	时间复杂度	文献
Gimli AE方案	状态恢复	9	2¹⁹²	2¹⁹⁰	[4]
Gimli AE方案	状态恢复	11	2^52.5	2¹¹⁰	文中
Gimli置换	区分器	24	可忽略	2⁶⁴	[6]
Gimli置换	区分器	24	可忽略	2⁵²	[5]
Gimli杂凑函数	碰撞	6	2⁶⁴	2⁶⁴	[4]
Gimli杂凑函数	碰撞	12^a	可忽略	2⁹⁶	[6]

Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂	Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂
		0	0	0	0	0			0	0	0	0	1
0	0	0	1	1	0	0	0	1	0	0	0	1	0
		0	0	0	1	1			1	1	1	0	1
		0	1	1	1	1			1	1	1	1	0
		1	0	1	1	1			0	0	1	1	0
1	0	0	0	1	0	0	1	1	1	0	1	0	1
		0	1	0	0	0			1	1	0	1	0
		1	1	0	1	1			0	1	0	0	1

[1]	刘亚,宫佳欣,赵逢禹. 加密算法Simpira v2的不可能差分攻击[J]. 西安电子科技大学学报, 2022, 49(5): 201-212.
[2]	魏悦川;潘晓中;戎宜生;王绪安. 对PRINCE分组密码的不可能差分攻击[J]. 西安电子科技大学学报, 2017, 44(1): 119-124.
[3]	陈杰;胡予濮;张跃宇. 用不可能差分法分析17轮SMS4算法 [J]. J4, 2008, 35(3): 455-458.
[4]	陈杰;张跃宇;胡予濮. 一种新的6轮AES不可能差分密码分析方法[J]. J4, 2006, 33(4): 598-601.

Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂	Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂
		0	0	0	0	0			0	0	0	0	1
0	0	0	1	1	0	0	0	1	0	0	0	1	0
		0	0	0	1	1			1	1	1	0	1
		0	1	1	1	1			1	1	1	1	0
		1	0	1	1	1			0	0	1	1	0
1	0	0	0	1	0	0	1	1	1	0	1	0	1
		0	1	0	0	0			1	1	0	1	0
		1	1	0	1	1			0	1	0	0	1

Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂	Δa	Δb	η(Δa,Δb,∧)	a₁	a₂	b₁	b₂
		0	0	0	0	0			0	0	0	0	1
0	0	0	1	1	0	0	0	1	0	0	0	1	0
		0	0	0	1	1			1	1	1	0	1
		0	1	1	1	1			1	1	1	1	0
		1	0	1	1	1			0	0	1	1	0
1	0	0	0	1	0	0	1	1	1	0	1	0	1
		0	1	0	0	0			1	1	0	1	0
		1	1	0	1	1			0	1	0	0	1