Paper 2020/561

Exploiting Weak Diffusion of Gimli: Improved Distinguishers and Preimage Attacks

Fukang Liu, Takanori Isobe, and Willi Meier

Abstract

The Gimli permutation proposed in CHES 2017 was designed for 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. The above two facts have been recently exploited to construct a distinguisher for the full Gimli permutation with time complexity $2^{64}$. By utilizing a new property of the SP-box, we demonstrate that the time complexity of the full-round distinguisher can be further reduced to $2^{52}$ while a significant bias still remains. Moreover, for the 18-round Gimli permutation, we could construct a distinguisher even with only 2 queries. Apart from the permutation itself, the weak diffusion can also be utilized to accelerate the preimage attacks on reduced Gimli-Hash and Gimli-XOF-128 with a divide-and-conquer method. As a consequence, the preimage attacks on reduced Gimli-Hash and Gimli-XOF-128 can reach up to 5 rounds and 9 rounds, respectively. Since Gimli is included in the second round candidates in NIST's Lightweight Cryptography Standardization process, we expect that our analysis can further advance the understanding of Gimli. To the best of our knowledge, the distinguishing attacks and preimage attacks are the best so far.

Note: This is a major revision. We removed the 21-round and 24-round distinguisher and will focus on the 18-round distinguisher as well as the improved full-round distinguisher based on a new property of the SP-box.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. ToSC 2021 (Issue 1)
Keywords
hash functionGimliGimli-HashGimli-XOFpreimage attackdistinguisher
Contact author(s)
liufukangs @ 163 com
takanori isobe @ ai u-hyogo ac jp
willimeier48 @ gmail com
History
2021-02-08: last of 5 revisions
2020-05-15: received
See all versions
Short URL
https://ia.cr/2020/561
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/561,
      author = {Fukang Liu and Takanori Isobe and Willi Meier},
      title = {Exploiting Weak Diffusion of Gimli: Improved Distinguishers and Preimage Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2020/561},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/561}},
      url = {https://eprint.iacr.org/2020/561}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.