0
$\begingroup$

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)?

$\endgroup$
14
  • $\begingroup$ You can start with unmodified inverse Gimli spbox you can find in project.inria.fr/quasymodo/files/2020/05/… (invspbox in datatypes.cpp). $\endgroup$
    – LightBit
    Oct 17, 2023 at 6:23
  • $\begingroup$ @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. $\endgroup$ Oct 17, 2023 at 6:39
  • $\begingroup$ @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). $\endgroup$ Oct 17, 2023 at 6:48
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Oct 17, 2023 at 7:11
  • 3
    $\begingroup$ godbolt.org/z/rMjWfGosK $\endgroup$ Oct 17, 2023 at 15:36

1 Answer 1

3
$\begingroup$

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];
}
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.