# What is the inverse of this variant of the Gimli SP-box?

Consider a slightly modified variant of the Gimli SP-box:

function spbox(s) {
x = s[0];
y = s[1];
z = s[2];
X = x ^ (z << 1) ^ ((x ^ (y | ~z)) << 1);
Y = y ^ x ^ ((y ^ (x | z)) << 1);
Z = z ^ y ^ ((z ^ (x & y)) << 1);
return [Z, Y, X]
}


Here s is an array of three $$32$$-bit words, ^ is the bitwise XOR, | is the bitwise OR, & is the bitwise AND, ~ is the bitwise NOT, << is the left non-cyclic shift modulo $$2^{32}$$:

~11000000000000000000000000000000 = 00111111111111111111111111111111,
11000000000000000000000000000000 << 1 = 10000000000000000000000000000000.


What is the inverse function of spbox (in the C-like pseudocode)?

• You can start with unmodified inverse Gimli spbox you can find in project.inria.fr/quasymodo/files/2020/05/… (invspbox in datatypes.cpp). Oct 17, 2023 at 6:23
• @LightBit: yes, I have seen that invspbox function. Based on this information, I tried to write the inverse for the modified spbox, but my algorithm did not output the correct results. Oct 17, 2023 at 6:39
• @kelalaka: Proving that this SP-box is invertible is maybe even a bit harder than doing this for the original SP-box, which is already non-trivial. But I computed the spbox for all possible triples of 4-bit and 6-bit words (instead of 32-bit words), and it seems that the function is bijective (which implies that it is invertible). Oct 17, 2023 at 6:48
• No, it can't Z = z ^ y ^ ((z ^ (x & y)) << 1) the $&$ make is non-bijective. Consider that when $y=[0,\ldots,0]$ then for any value of $x$ the $(x \& y)$ Is zero. The other values are x-or and shifts that cannot make it bijective. Oct 17, 2023 at 7:11
• godbolt.org/z/rMjWfGosK Oct 17, 2023 at 15:36

First, note that (z << 1) ^ ((x ^ (y | ~z)) << 1) can be simplified to the shorter ~(x ^ (y & z)) << 1.

The trick is to start from the least significant bit. When considering only the least significant bit, we have \begin{align} x_0 &= X_0 \\ y_0 &= Y_0 \oplus x_0 \\ z_0 &= Z_0 \oplus y_0 \end{align} The next bits are also obtainable similarly by using the newly recovered least significant bits: \begin{align} x_i &= X_i \oplus 1 \oplus x_{i-1} \oplus (y_{i-1} \land z_{i-1}) \\ y_i &= Y_i \oplus x_i \oplus y_{i-1} \oplus (x_{i-1} \lor z_{i-1}) \\ z_i &= Z_i \oplus y_i \oplus z_{i-1} \oplus (x_{i-1} \oplus y_{i-1}) \end{align} Putting this together into pseudocode, we get

function ispbox(s) {
X = s[2];
Y = s[1];
Z = s[0];
x = X & 1;
y = (Y ^ x) & 1;
z = (Z ^ y) & 1;
for(i = 1; i < 32; ++i) {
x |= (1 << i) & (X ^ ~(x ^ (y & z)) << 1);
y |= (1 << i) & (Y ^ x ^ (y ^ (x | z)) << 1);
z |= (1 << i) & (Z ^ y ^ (z ^ (x & y)) << 1);
}
return [x,y,z];
}