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

Impossible differential cryptanalysis of the Gimli authenticated encryption scheme

作　　者：谭豪 申兵[1] 苗旭东 张文政[1] TAN Hao;SHEN Bing;MIAO Xudong;ZHANG Wenzheng(Institute of Southwestern Communication,Chengdu 610041,China)

机构地区：[1]保密通信重点实验室,四川成都610041

出　　处：《西安电子科技大学学报》2022年第5期213-220,共8页Journal of Xidian University

基　　金：国家重点研发计划(2017YFB0802000);四川省科技计划(2020JDJQ0076)。

摘　　要：Gimli是美国国家标准与技术研究院发起的轻量级加密算法标准第二轮候选算法。当前,Gimli的安全性分析主要针对Gimli置换、Gimli杂凑函数、Gimli带有关联数据的认证加密方案等。Gimli认证加密方案总体采用sponge结构,适用于受限环境下的数据加密场景。目前对Gimli认证加密方案的状态恢复攻击最好结果是9轮,时间复杂度为2^(190),数据复杂度为2^(192)。为了评估这种方案抵抗不可能差分分析的能力,根据Gimli置换设计了一个差分传播系统,找到了适用于分析sponge结构认证加密方案的7轮不可能差分,此不可能差分仅限制了1 bit输出差分的取值,可显著地降低状态恢复阶段的时间复杂度与数据复杂度。将7轮不可能差分向前扩展4轮,成功实现了对11轮Gimli认证加密方案的状态恢复攻击。在状态恢复阶段,基于Gimli置换前两轮的弱扩散性,将2^(128)的密钥猜测量缩小为2个2^(64)密钥猜测量,此状态恢复攻击的时间复杂度约为2^(110)次加密,数据复杂度约为2^(52.5),优于现有公开文献中对Gimli认证加密方案的状态恢复攻击结果。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^(190) and a data complexity of 2^(192).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^(128) key guesses are reduced to two 2^(64) key guesses.The time complexity of this state recovery attack is about 2^(110) 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.

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

分 类 号：TN918[电子电信—通信与信息系统]