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. If the attacker is allowed to know the intermediate state words in several consecutive rounds as in another recent full-round distinguisher, we could reduce the time complexity of that distinguisher to $2^{52}$ from $2^{64}$ by exploiting a new property of the SP-box and considering a different setting. 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. 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 does not threaten the security of the hash scheme or authenticated encryption scheme built on Gimli.

Note: This is a major revision.1) We added a comparison between our full-round distinguisher with a recent work (Report 2020/744) and try to explain why our distinguisher can be called as a distinguisher.2) If constructing a distinguisher as in Report 2020/744, by proposing a novel property of the SP-box (Property 10) and considering a different setting, we could construct a similar distinguisher for the full Gimli permutation with time complexity of about 2^{52}, thus improving the time complexity of the full-round distinguisher in Report 2020/744 by a factor of 2^{12}.3) Correct some editorial mistakes and list more related results in Table 1.4) The major revised part can be referred to Section 4.4.