Paper 2017/743

Cryptanalysis of 22 1/2 rounds of Gimli

Mike Hamburg

Abstract

Bernstein et al. have proposed a new permutation, Gimli, which aims to provide simple and performant implementations on a wide variety of platforms. One of the tricks used to make Gimli performant is that it processes data mostly in 96-bit columns, only occasionally swapping 32-bit words between them. Here we show that this trick is dangerous by presenting a distinguisher for reduced-round Gimli. Our distinguisher takes the form of an attack on a simple and practical PRF that should be nearly 192-bit secure. Gimli has 24 rounds. Against 15.5 of those rounds, our distinguisher uses two known plaintexts, takes about $2^{64}$ time and uses enough memory for a set with $2^{64}$ elements. Against 19$\frac12$ rounds, the same attack uses three non-adaptively chosen plaintexts, and uses twice as much memory and about $2^{128}$ time. Against $22\frac12$ rounds, it requires about $2^{138.5}$ work, $2^{129}$ bits of memory and $2^{10.5}$ non-adaptively chosen plaintexts. The same attack would apply to 23$\frac12$ rounds if Gimli had more rounds. Our attack does not use the structure of the SP-box at all, other than that it is invertible, so there may be room for improvement. On the bright side, our toy PRF puts keys and data in different positions than a typical sponge mode would do, so the attack might not work against sponge constructions.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
cryptanalysispermutation-based cryptographymeet-in-the-middle attack
Contact author(s)
mike @ shiftleft org
History
2017-08-07: received
Short URL
https://ia.cr/2017/743
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/743,
      author = {Mike Hamburg},
      title = {Cryptanalysis of 22 1/2 rounds of Gimli},
      howpublished = {Cryptology ePrint Archive, Paper 2017/743},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/743}},
      url = {https://eprint.iacr.org/2017/743}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.