Gimli: a cross-platform permutation

Statement regarding "Cryptanalysis of 22 1/2 rounds of Gimli"

To achieve high security with the best possible efficiency on a broad range of platforms, Gimli works locally with portions of its internal state for a few rounds before the portions communicate. As an analogy, a Feistel cipher achieves high security with just 4 communication steps between halves of the state when the computations on half-states are strong enough.

In a paper titled "Cryptanalysis of 22 1/2 rounds of Gimli", Hamburg claims to "show" that this is "dangerous", that Gimli's "slow diffusion is a serious weakness", etc.

However, Hamburg's specific claim is that his "attack" takes "2138.5 work" and "2129 bits of memory". This is more hardware and more time than a naive brute-force attack against Hamburg's 192-bit key.

Specifically, a cluster of 280 brute-force key-search units would cost billions of times less than Hamburg's "attack" and would find the key millions of times faster. Replacing the cipher with another 192-bit cipher, such as AES-192, would not stop this brute-force attack.

Applying the "golden collision" techniques of 1996 van Oorschot–Wiener would allow memory to be reduced in Hamburg's "attack", but at a huge cost in time, again making the attack more expensive than a naive brute-force attack against the 192-bit key.

Furthermore, there are actually many users with many keys. Brute force gains far more from this than Hamburg's "attack" does, making the actual gap even larger than the above analysis indicates.

Furthermore, Hamburg's "attack" is against an artificial, ad-hoc mode that we would not recommend, that we did not recommend, and that, as far as we know, has never appeared before. Most importantly, the standard practice established by Salsa20 and ChaCha20 is for stream-cipher ("PRF") users to add key words to positions selected to maximize diffusion for the underlying permutation, whereas Hamburg adds key words to positions selected to minimize diffusion.

Finally, Hamburg's "attack" will not be feasible in the foreseeable future, even with quantum computers. Even if the "attack" were extended to the full 24 rounds, it would not contradict any security claims made in the Gimli paper.


Version: This is version 2017.09.26 of the Statement web page.