How is the $\chi$ step of the Keccak permutation invertible?

Question

I would like to understand how Keccak's permutation function is reversible. The difficulty I have is with the $\chi$ step that uses the and operator which is not revertible. All the other suboperations are using xor and rotations which can be reversed.

Answer 1

This is more a demonstration than a proof.

From the pseudocode below [taken from the Keccak specification] it is clear that the mapping is invertible if it is invertible for each fixed $y$ and operates on states with fixed $y.$

Assume $y$ is fixed and omit it, and let $x=i,$ and write the mapping as $$ A_i=a_i\oplus(1\oplus a_{i+1})a_{i+2}=a_i \oplus a_{i+2}\oplus a_{i+1}a_{i+2}\quad (1) $$ where the subscripts are taken modulo the worldlength (cyclically). The invertibility is proven in Daemen's PhD section 6.6.2 (available here thanks @DannyNiu) by a relatively complicated leap and shift argument. This map is only invertible if the wordlength is odd (in the example above it is equal to five) since otherwise you get non unique pre-images.

Note that if any input bit $a_i$ is zero then the AND output is zero and that makes the input to $A_{i+1}$ and $A_{i-1}$ linear, thus locally invertible. I don't think there is a short intuitive explanation for why this mapping is invertible for all odd wordlength other than the one given in the thesis. Here is a table that demonstrates invertibility of the map in equation $(1)$ for wordlength 3.

For wordlength 3 this map is self-inverse (an involution) which is not true in general. Here is a table of inputs and outputs only which demonstrates that it is not an involution for wordlength 5. In particular we have the cycle $$ (10000)\rightarrow(10010)\rightarrow (11000) \rightarrow (11010)\rightarrow (10000) $$

Answer 2

In Keccak Reference, the authors said this:

$\chi$ is invertible but its inverse is of a different nature than χ itself. For example, it does not have algebraic degree 2. We refer to [20, Section 6.6.2] for an algorithm for computing the inverse of $\chi$.

Where [20] was:

[20] J. Daemen, Cipher and hash function design strategies based on linear and differential cryptanalysis, PhD thesis, K.U.Leuven, 1995.

It's quite hard to find it online, here's a link but I'm not sure if it'd suffer from link rot.

UPDATE

I know it's hard to understand it, and I myself had gave up. $\chi$ is the XOR of AND function on bits, and I tried to enumerate output of the AND operation to see if it's unique.

But that's expectable. $\chi$ is the "SBox" of the Keccak permutation (being non-linear). So it's totally normal for its mechanism to be arcane.

Answer 3

There is a paper titled “The Inverse of $\chi$ and Its Applications to Rasta-like Ciphers” [F. Liu, S. Sarkar, W. Meier, T. Isobe]:

https://eprint.iacr.org/2022/399

In this work, we give a very simple formula of $\chi^{-1}_{n}$ that can be written down in only one line and we prove its correctness in a rigorous way.

Answer 4

According to KeccakTools, the inverse of χ is given by the inverseChi function, i.e.:

template<class Lane>
void KeccakF::inverseChi(vector<Lane>& A) const
{
    for(unsigned int y=0; y<5; y++) {
        unsigned int length = 5;
        vector<Lane> C(length);
        for(unsigned int x=0; x<length; x++) C[index(x)] = A[index(x,y)];
        for(unsigned int x=0; x<(3*(length-1)/2); x++) {
            unsigned int X = (length-2)*x;
            A[index(X,y)] = C[index(X)] ^ (A[index(X+2,y)] & (~C[index(X+1)]));
        }
    }
}