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