Paper 2023/328

The state diagram of $\chi$

Abstract

In symmetric cryptography, block ciphers, stream ciphers and permutations often make use of a round function and many round functions consist of a linear and a non-linear layer. One that is often used is based on the cellular automaton that is denoted by $\chi$ as a Boolean map on bi-infinite sequences, ${\mathbb{F}}^{\mathbb{Z}}$. It is defined by $$ where each $$. A map $$ is a map that operatos on $$-bit arrays with periodic boundary conditions. This corresponds with $$ restricted to periodic infinite sequences with period that divides $$. This map $$ is used in various permutations, e.g., Keccak-f (the permutation in SHA-3), ASCON (the NIST standard for lightweight cryptography), Xoodoo, Rasta and Subterranean (2.0). In this paper, we characterize the graph of $$ on periodic sequences. It turns out that $$ is surjective on the set of \emph{all} periodic sequences. We will show what sequences will give collisions after one application of $$. We prove that, for odd $$, the order of $$ (in the group of bijective maps on $$) is $$. A given periodic sequence lies on a cycle in the graph of $$, or it can be represented as a polynomial. By regarding the divisors of such a polynomial one can see whether it lies in a cycle, or after how many iterations of $$ it will. Furthermore, we can see, for a given $$, the length of the cycle in its component in the state diagram. Finally, we extend the surjectivity of $$ to $$, thus to include non-periodic sequences.