Gimli is a 384-bit cryptographically secure pseudorandom permutation that can be used to construct a hash function or stream cipher by using it in a sponge construction. One stated design goal is the ability to deliver high speeds on many different platforms from 8-bit AVR CPUs to 64-bit desktop CPUs while still maintaining high security. It has been submitted to the second round of the NIST Lightweight Cryptography Standardization Process.
Algorithm Gimli has a 384-bit state represented by a 3×4 matrix of 32-bit words. A column is represented by 3×32 = 96 bits while a row is represented by 4×32 = 128 bits. Each round, each of the 4 columns is separately split into 3 32-bit words x, y and z. Those are then transformed according to the following 3 steps in parallel. Step 1:
x ← x ⋘ 24 {\displaystyle x\gets x\lll 24}
y ← y ⋘ 9 {\displaystyle y\gets y\lll 9}
Step 2:
x ← x ⊕ ( z ≪ 1 ) ⊕ ( ( y ∧ z ) ≪ 2 ) {\displaystyle x\gets x\oplus (z\ll 1)\oplus ((y\land z)\ll 2)}
y ← y ⊕ x ⊕ ( ( x ∨ z ) ≪ 1 ) {\displaystyle y\gets y\oplus x\oplus ((x\lor z)\ll 1)}
z ← z ⊕ y ⊕ ( ( x ∧ y ) ≪ 3 ) {\displaystyle z\gets z\oplus y\oplus ((x\land y)\ll 3)}
Step 3:
x ← z {\displaystyle x\gets z}
z ← x {\displaystyle z\gets x}
After every fourth round starting from the first round, the first and second word and the third and fourth word are swapped. This is called "Small-Swap". After every fourth round starting from the third round, the first and third word and the second and fourth word are swapped. This is called "Big-Swap". The round number decrements starting from 24 and when it reaches 24, 20, 16, 12, 8 or 4, the round number or 0x9e377900 is xored into the first word of the state. The magic constant 0x9e377900 is chosen to be the upper 3 bytes of ⌊232⁄𝜙⌋, which would be 0x9e3779b9, where 𝜙 is the golden ratio (as a nothing-up-my-sleeve number) An implementation of the core permutation in C/C++ appears below.
Implementation and usage The reference implementation provided with the specification libhydrogen: a cryptographic library that constructs all primitives using Gimli and Curve25519 liblithium: like libhydrogen and maintained by Tesla
See also Keccak: another permutation.
References