Paper 2020/561

Exploiting Weak Diffusion of Gimli: A Full-Round Distinguisher and Reduced-Round Preimage Attacks

Fukang Liu and Takanori Isobe and Willi Meier

Abstract

The Gimli permutation was proposed in CHES 2017, which is distinguished from other well-known permutation-based primitives for its cross-platform performance. One main strategy to achieve such a goal is to utilize a sparse linear layer (Small-Swap and Big-Swap), which occurs every two rounds. In addition, the round constant addition occurs every four rounds and only one 32-bit word is affected by it. By exploiting the above two facts, We demonstrate that it is feasible to construct a distinguisher for the full Gimli permutation with time complexity $2^{129}$. The corresponding technique is named as hybrid zero internal differential since the internal difference and XOR difference are simultaneously traced. Our distinguisher can be interpreted as a variant of the common differential distinguisher and \mbox{zero-sum} distinguisher. Apart from the permutation itself, combined with some new properties of the SP-box, the weak diffusion can also be utilized to accelerate the preimage attacks on reduced \mbox{Gimli-Hash} and Gimli-XOF-128 with a divide-and-conquer method. As a consequence, the preimage attack on 2-round Gimli-Hash is practical and it can reach up to 5 rounds. For Gimli-XOF-128, our preimage attack can reach up to 9 rounds. To the best of our knowledge, this is the first attack on the full Gimli permutation and our preimage attacks on reduced Gimli-Hash and Gimli-XOF-128 are the best so far. Since Gimli is included in the second round candidates in NIST's Lightweight Cryptography Standardization process, we expect that our analysis can advance the understanding of Gimli. It should be emphasized that this work can not threaten the security of the hash scheme or authenticated encryption scheme built on Gimli.

Note: We noticed that there is an independent work on the distinguishing atttack on Gimli announced at the rump session of Eurocrypt 2020, where a full-round distinguisher is claimed to be found. According to our understanding, it shares a very similar idea with our distinguisher. However, the details on their full-round distinguisher are not clear yet.