Score:2

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

cn flag

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.

poncho avatar
my flag
"All the other suboperations are using xor and rotations which can be reversed"; actually, the invertability of the $\theta$ step is rather more subtle; if Keccak had a width of 60 (rather than 64), $\theta$ would not be invertible.
Score:2
vu flag

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.

glurks avatar
cn flag
Ola, this explains the invertibility in terms of landscapes, seeds and leaps. All perhaps given earlier in the text. All I want is an argument how to get around the irreversibility of and. And with algebraic degree they mean higher than quadratic? What have polynomials to do with logical operations?
fgrieu avatar
ng flag
Found that [\[20\], Section 6.6.2](https://cs.ru.nl/~joan/papers/JDA_Thesis_1995.pdf#page=118) on the author's website.
Score:1
cx flag

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)]));
        }
    }
}
kelalaka avatar
in flag
This is a link only answer that we don't want in this community. Could you write some details about it in your words?
Score:1
de flag

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.

Score:1
sa flag

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.$

enter image description here

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.

enter image description here

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

enter image description here

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.