// Workers AI · dad joke modeWhat did Gimli cipher say? "I've got a code to crack, it's a dwarf-ed task

Gimli

General
Designers	Daniel J. Bernstein, Stefan Kölbl, Stefan Lucks, Pedro Maat Costa Massolino, Florian Mendel, Kashif Nawaz, Tobias Schneider, Peter Schwabe, François-Xavier Standaert, Yosuke Todo, Benoît Viguier
First published	27 June 2017 (2017-06-27)
Detail
Rounds	24
Best public cryptanalysis
Distinguisher against full-round Gimli with 264 work

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\gets x\lll 24$
• $y\gets y\lll 9$

Step 2:

• $x\gets x\oplus (z\ll 1)\oplus ((y\land z)\ll 2)$
• $y\gets y\oplus x\oplus ((x\lor z)\ll 1)$
• $z\gets z\oplus y\oplus ((x\land y)\ll 3)$

Step 3:

• $x\gets z$
• $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 ⌊2³²⁄𝜙⌋, 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.

#include <stdint.h>
#define ROTL(x, b) (b == 0 ? x : ((x << b) | (x >> (32 - b))))

void gimli(uint32_t *state) {
  uint32_t x, y, z;

  for (int round = 24; round > 0; --round) {
    for (int column = 0; column < 4; ++column) {
      x = ROTL(state[column], 24);
      y = ROTL(state[column + 4], 9);
      z = state[column + 8];

      state[column + 8] = x ^ (z << 1) ^ ((y & z) << 2);
      state[column + 4] = y ^ x ^ ((x | z) << 1);
      state[column] = z ^ y ^ ((x & y) << 3);
    }

    if ((round & 3) == 0) {
      x = state[0];
      state[0] = state[1];
      state[1] = x;
      x = state[2];
      state[2] = state[3];
      state[3] = x;
    }
   
    if ((round & 3) == 2) {
      x = state[0];
      state[0] = state[2];
      state[2] = x;
      x = state[1];
      state[1] = state[3];
      state[3] = x;
    }

    if ((round & 3) == 0) {
      state[0] ^= (round | 0x9e377900);
    }
  }
}

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.