[Resource Topic] 2017/743: Cryptanalysis of 22 1/2 rounds of Gimli

Welcome to the resource topic for 2017/743

Cryptanalysis of 22 1/2 rounds of Gimli

Authors: Mike Hamburg


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.

ePrint: https://eprint.iacr.org/2017/743

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .