GIMLI is a cross-platform method which produces a 384-bit permutation state with high levels of security. and has excellent performance across a range of 8-bit, 16-bit, 32-bit and 64-bit platforms [paper]. It has 24 rounds and uses simple EX-OR, AND, OR, and Cyclic shift operations. In the following we will generate a seed value, and which is used to create an initial state for GIMLI. After this we will create three permutations based on GIMLI:
GIMLI permutation generator |
Theory
GIMLI is focused on producing a relatively large state size (384 bits) and is efficient for energy consumption and processor requirements. It is free from side channel attacks and has protection against short messages. A few other methods for permuations includes:
- Keccak provides a 1600-bit permutation and is energy-efficient and has 24 rounds.
- Chaskey provides a 128-bit permutation for a 128-bit key and runs well on microcontrollers [link].
- Salsa20 and ChaCha20 provide a 512-bit permutation and is efficient on embedded systems.
A state in GIMLI is defined as 3×4 matrix of 32-bit words. A column \(j\) is defined with 96 bits, and row \(i\) by 128 bits. The algorithm used is:
Sample
For this we generate a seed of 0x9e3779b9 and generate our 3x4 matrix:
Seed: 0x9e3779b9 2654435769 00000000 9e3779ba 3c6ef37a daa66d46 78dde724 1715611a b54cdb2e 53845566 f1bbcfc8 8ff34a5a 2e2ac522 cc624026 ---------------------- ba11c85a 91bad119 380ce880 d24c2c68 3eceffea 277a921c 4f73a0bd da5a9cd8 84b673f0 34e52ff7 9e2bef49 f41bb8d6 ---------------------- ea223492 3fbb2166 68314a61 9165986e 67fca6e0 bd9c5b3b 71d12d9c c13c4a87 b4683e05 8298cbfb a5b64fa5 717d83e1 ---------------------- bf11569b acff7155 3b5c36bd f9e06baa f51bd351 bf8a897e 877cfcea 39a4c248 e17db921 17650092 05c7b1b6 abb9a379 ----------------------
If we change the seed value to 0x9e3779b8, we see the permuation changes creately:
Seed: 0x9e3779b8 2654435768 00000000 9e3779b9 3c6ef378 daa66d43 78dde720 17156115 b54cdb28 5384555f f1bbcfc0 8ff34a51 2e2ac518 cc62401b ---------------------- bfaf61f2 6c896d82 cf9682ef 345a2120 397498c8 df6136e3 60234065 66960283 caa12626 da2b16e9 f8a01954 23bbec34 ---------------------- 2844a96a 8662d9bf f98322a5 5281d29d 1c8e0d68 98588f1f b49848ba 481af1b7 1a1874ba 141b5d14 48cf2713 75bb932c ---------------------- 3df8e05d eef36199 ae4769de 19263580 e51a6793 0acd040d e5f3053b 5f4ab0bd 15a432e2 8832ddd8 98944796 001445a2 ----------------------
Coding
from typing import List import sys R = 24 S = 9 Sheet = List[int] State = List[Sheet] """State are seen as a 3 x 4 x 32 array """ shift_x = 2 # a shift_y = 1 # b shift_z = 3 # c rot_x = R # d rot_y = S # e rot_z = 0 # f def rot(x: int, n: int) -> int: """Bitwise rotation (to the left) of n bits considering the \ string of bits is 32 bits long""" x %= 1 << 32 n %= 32 # if n == 0: # print(hex(x), "=>", hex((x >> (32 - n)) | (x << n) % (1 << 32))) return (x >> (32 - n)) | (x << n) % (1 << 32) def non_lin_perm_96(sheet: Sheet, a: int, b: int, c: int, d: int, e: int, f: int) -> Sheet: """Apply the non linear permutation on the 96 sheet of the state""" x,y,z = sheet x,y,z = rot(x,d),rot(y,e),rot(z,f) x,y,z = ( x ^ (z << 1) ^ ((y & z) << a), y ^ x ^ ((x | z) << b), z ^ y ^ ((x & y) << c) ) sheet[0] = z % (1 << 32) sheet[1] = y % (1 << 32) sheet[2] = x % (1 << 32) return sheet def small_swap(state: State) -> State: for j in range(1): state[0][j], state[1][j], state[2][j], state[3][j] \ = state[1][j], state[0][j], state[3][j], state[2][j] return state def big_swap(state: State) -> State: for j in range(1): state[0][j], state[1][j], state[2][j], state[3][j] \ = state[2][j], state[3][j], state[0][j], state[1][j] return state def print_to_hex(x): for i in range(3): print(hex(x[0][i])[2:].zfill(8), hex(x[1][i])[2:].zfill(8), hex(x[2][i])[2:].zfill(8), hex(x[3][i])[2:].zfill(8), "") print("----------------------") def gimli(state: State) -> State: """ Number of rounds has still to be determined """ for outer_rounds in range(6): """ Apply the inner diffusion (96 bits) on the sheet """ for inner_rounds in range(4): """ Apply the 96 Non linear permutation on each sheet """ for i_sheet in range(4): state[i_sheet] = non_lin_perm_96(state[i_sheet], shift_x, shift_y, shift_z, rot_x, rot_y, rot_z) if inner_rounds == 0: state = small_swap(state) if inner_rounds == 2: state = big_swap(state) if inner_rounds == 0: state[0][0] ^= 0x9e377900 state[0][0] ^= 24 - (outer_rounds * 4 + inner_rounds) return state seed = 0x9e3779b9 if (len(sys.argv)>1): seed=int(sys.argv[1],16) print ("Seed:\t",hex(seed), seed) x = [(i * i * i + i *seed ) % (2 ** 32) for i in range(12)] x = [[x[4 * i + j] for i in range(3)] for j in range(4)] print_to_hex(x) x = gimli(x) print_to_hex(x) x = gimli(x) print_to_hex(x) x = gimli(x) print_to_hex(x)