Paper 2020/744

Internal Symmetries and Linear Properties: Full-permutation Distinguishers and Improved Collisions on Gimli

Antonio Flórez Gutiérrez, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, André Schrottenloher, and Ferdinand Sibleyras

Abstract

Gimli is a family of cryptographic primitives (both a hash function and an AEAD scheme) that has been selected for the second round of the NIST competition for standardizing new lightweight designs. The candidate Gimli is based on the permutation Gimli, which was presented at CHES 2017. In this paper, we study the security of both the permutation and the constructions that are based on it. We exploit the slow diffusion in Gimli and its internal symmetries to build, for the first time, a distinguisher on the full permutation of complexity $2^{64}$. We also provide a practical distinguisher on 23 out of the full 24 rounds of Gimli that has been implemented. Next, we give (full state) collision and semi-free-start collision attacks on Gimli-Hash, reaching respectively up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round Gimli-Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in Gimli, and we find a linear distinguisher on the full permutation.

Note: Extended version of the ASIACRYPT 2020 paper entitled "New Results on Gimli: Full-Permutation Distinguishers and Improved Collisions."

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in JOC 2021
Keywords
Gimlisymmetriessymmetric cryptanalysisfull-round distinguishercollision attackslinear approximations
Contact author(s)
antonio florez-gutierrez @ inria fr
gaetan leurent @ inria fr
maria naya_plasencia @ inria fr
leo perrin @ inria fr
andre schrottenloher @ m4x org
ferdinand sibleyras @ inria fr
History
2021-09-16: last of 2 revisions
2020-06-21: received
See all versions
Short URL
https://ia.cr/2020/744
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/744,
      author = {Antonio Flórez Gutiérrez and Gaëtan Leurent and María Naya-Plasencia and Léo Perrin and André Schrottenloher and Ferdinand Sibleyras},
      title = {Internal Symmetries and Linear Properties: Full-permutation Distinguishers and Improved Collisions on Gimli},
      howpublished = {Cryptology ePrint Archive, Paper 2020/744},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/744}},
      url = {https://eprint.iacr.org/2020/744}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.