The state diagram of χ

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 x as a Boolean map on bi-infinite sequences, F-2(Z) . It is defined by sigma -> v where each v(i) = sigma(i) +(sigma(i)+1 +1)sigma(i+2). A map x(n) is a map that operates on n-bit arrays with periodic boundary conditions. This corresponds with x restricted to periodic infinite sequences with period that divides n. This map xn 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 x on periodic sequences. It turns out that x is surjective on the set of all periodic sequences. We will show what sequences will give collisions after one application of x. We prove that, for odd n , the order of x(n) (in the group of bijective maps on F-2(n)) is 2[lg( n+1/2). A given periodic sequence lies on a cycle in the graph of x , 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 x it will. Furthermore, we can see, for a given sigma , the length of the cycle in its component in the state diagram. Finally, we extend the surjectivity of x to F-2(Z), thus to include non-periodic sequences.