# A 10-bit S-box generated by Feistel construction from cellular automata

Thomas Prévost, Bruno Martin

► To cite this version:

Thomas Prévost, Bruno Martin. A 10-bit S-box generated by Feistel construction from cellular automata. AUTOMATA 2025, Jun 2025, Lille, France. hal-05141041

HAL Id: hal-05141041

https://univ-cotedazur.hal.science/hal-05141041v1

Submitted on 2 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A 10-bit S-box generated by Feistel construction
from cellular automata*

Thomas Prévost¹[0009-0000-2224-8574] and Bruno Martin¹[0000-0002-0048-5197]

Université Côte d'Azur, CNRS, I3S, France
{thomas.prevost, bruno.martin}@univ-cotedazur.fr

**Abstract.** We propose a new 10-bit S-box generated from a Feistel construction. The subpermutations are generated by a 5-cell cellular automaton based on a unique well-chosen rule and bijective affine transformations. In particular, the cellular automaton rule is chosen based on empirical tests of its ability to generate good pseudorandom output on a ring cellular automaton. Similarly, Feistel's network layout is based on empirical data regarding the quality of the output S-box.

We perform cryptanalysis of the generated 10-bit S-box, and we find security properties comparable to or sometimes even better than those of the standard AES S-box. We believe that our S-box could be used to replace the 5-bit substitution of ciphers like ASCON.

**Keywords:** S-box · Block cipher · Cellular automata · Feistel permutation · Boolean functions.

## 1 Introduction

Cryptography plays a central role in telecommunications, with symmetric encryption enabling secure communication between parties sharing a secret key. The ciphertext must appear random to outsiders lacking the key.

Symmetric ciphers fall into two categories: stream ciphers, which encrypt data on the fly, and block ciphers, which operate on fixed-size blocks. Block ciphers, such as AES, are more widely used. The core component of block ciphers is the substitution box (S-box), which introduces nonlinearity and must be carefully designed to resist cryptanalytic attacks such as linear [3], differential [2], and boomerang [23]. As S-boxes are permutations over $[0, 2^n - 1]$, the number of possible n-bit S-boxes grows factorially, making exhaustive analysis infeasible (e.g., $2^8! \approx 8.58 \cdot 10^{506}$).

While many constructions use algebraic techniques over finite fields, we propose a combinatorial method based on a Feistel network of depth 11. Our design combines three affine layers with eight layers of permutations generated by a 1-dimensional uniform binary cellular automaton, using a Boolean function as a pseudo-random permutation.

<footnote>* This work has been supported by a government grant managed by the Agence Nationale de la Recherche under the Investissement d'avenir program, reference ANR-17-EURE-004</footnote>
We begin with background on binary uniform cellular automata (CA), Boolean functions (Section 2), then review Feistel constructions and the Luby-Rackoff theorem (Section 3). Section 4 details our 10-bit S-box generation method, followed by its cryptanalysis (Section 5). We conclude with applications and potential extensions.

**Related work** Many research papers propose new methods for generating S-boxes. Most focus on 8-bit S-boxes, although some offer smaller S-boxes.

The generation of 2n-bit S-boxes from n-bit subpermutations has already been considered in the literature, either by Feistel or MISTY constructions [13,4].

[18] proposed a method to generate S-Boxes of arbitrary size allowing to maximize their degree, their nonlinearity and to minimize their differential uniformity.

The use of CAs for cryptography is not recent [7]. Gutowitz proposed to use CAs for a block cipher [11]. Several papers have already been proposed to construct S-boxes or hash-functions from CA [15]. However, to our knowledge, no one has yet designed an S-box from a CA based Luby-Rackoff construction.

# 2 Definitions and notation

## 2.1 Uniform binary 1-dimensional cellular automaton

Let us recall the definition of a uniform binary 1-dimensional cellular automaton.

**Definition 1 (Cellular automaton).** *A cellular automaton is a triple (F₂, δ, N) where:*

- F₂ is the set of states.

- δ is the local transition function (or rule) $F_2^n \to F_2$ with arity n.

- N ⊆ Z is the finite neighborhood, $card(N) = a$ being the size of the CA.

## 2.2 Boolean functions

A Boolean function with $n$ variables takes $n$ Boolean values as input and returns a single Boolean value as output. The local transition functions of CAs can be viewed as Boolean functions. There are $2^{2^n}$ $n$-variable Boolean functions.

Boolean functions are characterized by their truth table, which lists the outputs corresponding to the inputs, unique in the set of functions with a given number of variables. A convenient way to represent Boolean functions is given by their Algebraic Normal Form:

**Definition 2 (Algebraic Normal Form).** *Any $n$-variable Boolean function $f$ can be expressed by a unique binary polynomial, called Algebraic Normal Form (ANF):* $f(x) = \bigoplus_{u \in F_2^n} a_u (\prod_{i=1}^n x_i^{u_i})$, $a_u \in F_2$, $u_i$ $i$-th projection of $u$, $x_i$ being the $i$-th bit of input $x$.
**Definition 3 (Algebraic degree).** The algebraic degree of a function $f$ counts the number of variable in the largest monomial $x_1^{u_1}...x_n^{u_n}$ of its ANF.

A function $f$ is nonlinear if and only if its degree is at least 2.

**Definition 4 (Hamming weight).** The Hamming weight of a Boolean function $f$, written $w_h(f)$, is the number of $x \in \mathbb{F}_2^n$ such that $f(x) = 1$.

**Definition 5 (Balancedness).** A $n$-variable Boolean function $f$ is balanced if and only if $w_h(f) = 2^{n-1}$ (it returns as many ones as zeroes).

**Definition 6 (Correlation-immunity).** An $n$-variable Boolean function $f$ is $k$-correlation immune, $1 \le k \le n$, if and only if for any binary random input $x = x_1, ..., x_n$, $f(x)$ is statistically independent from any subset of size $k$ of $x$.

The Walsh-Hadamard transform [6] of a Boolean function $f$ is an essential tool for analyzing the statistical properties of a Boolean function. It is defined by: $\hat{f}(\omega) = \sum_{x=0}^{2^n-1} (-1)^{f(x)\oplus x\cdot\omega}$, where $x \cdot \omega$ denotes the dot product of the two binary vectors.

**Theorem 1.** A $n$-variable Boolean function $f$ is $k$-order correlation immune, $1 \le k \le n$ if and only if for every $\omega \in \mathbb{F}_2^n$ such that $1 \le w_h(\omega) \le k$, $\hat{f}(\omega) = 0$.

Xiao and Massey proved theorem 1 in [26]. A Boolean function that is both balanced and correlation immune at order $k$ is said to be *resilient at order k*.

**Definition 7 (Strict avalanche criterion).** A $n$-variable Boolean function $f$ satisfies the Strict Avalanche Criterion (SAC) iff $\forall i \in [1, n]$, flipping the $i$-th bit of the input $x$ results in the output $f(x)$ being changed for exactly half of the inputs $x$.

The strict avalanche criterion is particularly interesting in the cryptographic context since it makes it difficult to infer input from output.

## 3 Feistel constructions

The Feistel construction [9] is a method for constructing secure pseudo-random bijective permutations from pseudo-random functions. The Feistel network, from a certain depth, guarantees the computational indistinguishability of its pseudo-random permutation from a random permutation.

**Definition 8.** A function $f: \mathbb{F}_2^n \to \mathbb{F}_2^n$ is said to be pseudo-random (PRF) if its output is computationally difficult to distinguish from a random output.

**Definition 9.** A pseudo-random function $f: \mathbb{F}_2^n \to \mathbb{F}_2^n$ is called pseudo-random permutation (PRP) if and only if it is bijective.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Example of Feistel construction of depth 1. $f_1$ is a pseudo-random permutation</figcaption></figure>

As shown in Fig. 1, the Feistel construction creates a block permutation function of size $n$. It is made up of a stack of layers, each composed of PRP $f_i$ of input and output size $\frac{n}{2}$. We call *depth* the number of sub-permutations $f_i$.

Luby and Rackoff [14] proved that the output of the LR function is computationally indistinguishable from a random output as long as the depth of the network is at least 4, even for an adversary who knows the input. As shown by [19], a Feistel construction with a depth of at least 7 returns an output that is computationally indistinguishable from a random output for an adversary able to choose the input value (Chosen-Plaintext-Attack, CPA), that is to say, no probabilistic algorithm is capable of making the distinction in polynomial time.

# 4 Our 10-bit S-box from a CA based Feistel construction

## 4.1 Architecture of the Feistel construction

The permutation function generated by the Feistel construction allows to construct an S-box. We pass the $2^{10} = 1024$ possible inputs to the function, the output of which gives us the S-box. The latter must validate several security requirements, explained in section 5. Another important property to respect is bijectivity, which allows to invert the S-box and permits decryption.

In our network, we use a 5-cell CA as a PRP $f_i$, its output is evaluated after a single time step on the input. The automaton has only one local transition function with 5 variables, which we detail in section 4.2.

However, a uniform CA will fail to return chaotic output for some particular inputs that are regular. If we used only this type of CA for intermediate permutation functions $f_i$, some inputs would still return a predictable result, for example $S(0)$ or $S(1023)$ which would return 0 or 1023 (0b1111111111).

Fortunately, [16] tells us that it is possible to replace certain pseudo-random permutations by pair-wise independent permutations, i.e. permutations whose
output is “almost” uniformly distributed for any two given inputs. An affine function $f_{a,b}(x) = a \cdot x + b$ satisfies these requirements. So that the permutation is bijective, we chose a and b prime.

The Luby-Rackoff construction we chose to generate our 10 bits S-box consists of the following eleven layers:

1. A first layer uses the affine function $f_{5,3}(x) = 5 \cdot x + 3 \bmod 2^{10}$.

2. Next comes 4 layers using the 5-bit CA of section 4.2 as PRP.

3. The next layer uses the affine function $f_{7,11}(x) = 7 \cdot x + 11 \bmod 2^{10}$.

4. Next we have 3 layers of CA.

5. We have another affine layer, $f_{13,17}(x) = 13 \cdot x + 17 \bmod 2^{10}$.

6. Finally a last layer reuses the 5-bit-cellular automaton.

## 4.2 Construction of the local PRP with a CA

**Construction of the cellular automaton** We are looking for a CA which permutes its input value. For this, we build a CA in a ring of 5 cells. To perform the permutation, we assign to the cells of the ring the value to be permuted, then we return the value of the CA after a single time step. We chose this construction because there are no 4-variable Boolean functions with convenient cryptographic properties and which allows to create a bijective CA.

**Basic properties of local transition rule** There are $2^{2^5} = 4.294.967.296$ 5-bit local transition functions. The papers [25,10] fortunately give us some ideas for selecting the Boolean functions most likely to introduce “chaos” into the output of the cellular automaton.

Let us start by keeping only balanced Boolean functions (see def. 5). There are then $\binom{32}{16} = 601.080.390$ functions left. We then eliminate the functions which are not first-order correlation immune (see def. 6), to keep only 807.980 rules. We next eliminate linear functions, to keep 807.928 functions. We are satisfied with the nonlinearity property here: [20] proves that there cannot exist bent functions (maximally non-linear) with an odd number of variables. Finally we eliminate all functions that do not respect the Strict Avalanche Criterion (SAC) (see def. 7), to keep 7.080 local rules.

**Selection over NIST FIPS 140-2 randomness test** We try to create a pseudo-random generator from a uniform CA, then we only keep rules which allows to create “good” pseudo-random bit generators. We start by creating a ring CA, of size 1024 bits. Indeed, [21] informs us that the ring must have more than 1000 cells to produce a secure pseudo-random generator.

For the seed value, we fill the ring with 1024 truly random bits. The seed and CA random generator are available at: https://github.com/thomasarmel/cellular_automata_prng.

Next, we test each of the 7.080 local rules as follows: at each time step, we update all cells in the ring with the rule under test. We then extract bit 512
from the ring. We iterate the CA and repeat the operation for as many bits as we wish to extract.

For each of the 7.080 rules, we evaluate the pseudo-random bit generator with the NIST FIPS 140-2 test [22]. The generator must pass all tests ("Monobit", "Poker", "Runs", "Long run" and "Continuous run") out of 100.000 bits generated, which is equivalent to passing each test 39 times. There then remain 53 rules which allow the ring cellular automaton to validate the NIST FIPS 140-2 pseudo-random generation test.

Finally, we must ensure that the 5-bit ring cellular automaton of the Luby-Rackoff construction is bijective. To do this, we eliminate all the local rules which do not allow us to create a bijective CA.

Finally, only one rule remains, whose truth table numbering is 1.438.886.595 (in decimal), or $x_0 \cdot x_3 + x_1 \cdot x_3 + x_2 \cdot x_3 + x_3 \cdot x_4 + x_1 + x_2 + x_3 + 1$.

The source code to generate the S-box can be found at the following address: https://github.com/thomasarmel/luby_rackoff_sbox.finder.

# 5 Cryptanalysis

Here we propose the cryptanalysis of the specific S-box that we generated from the construction described above. In order to have a more systemic analysis of the security of S-boxes generated from Feistel networks, refer to [4].

Our S-box has a minimum algebraic degree of 8 and a maximum degree of 9. In comparison, the minimum and maximum degree of the AES S-box is 7 (having a larger S-box gives us an advantage). Our S-box's algebraic complexity is 1023, which is the maximum possible. The algebraic complexity of the AES S-box is 255, which is also the highest possible value. (The algebraic complexity of an S-box defines its ability to resist interpolation attacks [12]).

A strong nonlinearity [5] allows the S-box to resist linear cryptanalysis. It is defined as the minimum nonlinearity of each of the component functions. The nonlinearity of our S-box is 434. For both AES S-box and ours, it is not possible to express the value of one of the output bits as a function of a linear combination of the input bits with a probability ≥ 60% (56.25% for AES S-box and 57.62% for our S-box).

The notion of *Strict avalanche criterion (SAC)* (see def. 7) for the design of S-boxes was first introduced in 1985 by [24]. To satisfy the SAC, half of the output bits must be modified when a single input bit is modified. For an S-box, the bits of the SAC dependency matrix must be close to the ideal value of 0.5. Our S-Box has an average SAC of **0.50**, with a minimum of **0.44** and a maximum of **0.57**. For comparison, AES's S-Box has an average SAC of 0.50, with a minimum of 0.45 and a maximum of 0.56. So our average value is good, and the extreme values are almost as good as those of the AES S-box.

The *Bit Independence Criterion Parameter* measures how inverting an input bit changes the output bits independently. The BIC parameter of our S-box is **0.124**. For comparison, the one of the AES S-box is 0.134. Our BIC parameter is therefore better than the one of the AES S-box.
The *Linear Approximation Probability* (LAP) gives us an indication of how resistant our S-box is to linear cryptanalysis [3]. The Linear Approximation Probability of our S-box is **9.28%**, which is comparable or even better than other S-boxes proposed in the scientific literature [1]. However, the LAP is a little bit worse than that of the AES S-box, which is 6.25%.

The *Differential Approximation Probability* is determined by the XOR distribution between the input and output of an S-box. The lowest possible value guarantees the security of the S-box against differential cryptanalysis [2]. The DAP of our S-box is **1.37%**, in comparison the AES S-box DAP is 1.56%.

The *Differential Uniformity* of an S-box defines its proximity to perfect non-linearity [17]. The Differential Uniformity of our 10-bit S-box is **14**. Let us divide this value by $\frac{2^{10}}{2^8} = 4$ in order to compare with 8-bit S-box, we obtain 3.5. This is a better value than the Differential Uniformity of the AES S-box which is 4.

The *Boomerang Uniformity* $BU$ defines the resistance of an S-box to the boomerang attack [23], which is an improvement of differential cryptanalysis. Our 10-bit S-box has a $BU$ of **24**. Let's divide this value by 4 to compare it with 8-bit S-boxes. We find a value of 6, which equals the $BU$ of the AES S-box.

## Discussion

Our 10-bit S-box demonstrates security properties comparable to the AES standard. Its quality may be further enhanced by increasing the Feistel network depth or adjusting affine function parameters, although we expect similar security behavior across such variations.

Larger S-boxes (e.g., 14- or 18-bit) could be constructed if $n$ is even and $\frac{n}{2}$ is odd, but selecting suitable Boolean functions with many variables (e.g., 7 or 9) becomes computationally intensive, as the number of $n$-bit Boolean functions grows exponentially (e.g., $1.34 \cdot 10^{154}$ for $n = 9$).

Our S-box could be integrated into sponge-based ciphers like ASCON [8], potentially improving security at the cost of performance. For instance, our Rust implementation (https://github.com/thomasarmel/sponges/blob/sbox_10/ascon/src/lib.rs#L100) shows a 10–15× slowdown on an Intel Core i7-13700H CPU, with added complexity in achieving constant-time execution.

## Conclusion

We have proposed a new 10-bit S-box from a Feistel construction based on uniform CA permutations, and carried out its cryptanalysis. In particular, we evaluated its robustness against linear, differential or boomerang attacks. We shown that our S-box has comparable, or even better security than those of the AES S-box. Our method can be extended for the construction of $n$-bit S-box, given that $n$ is even and $\frac{n}{2}$ is odd.
References

1. Arshad, B., Siddiqui, N., Hussain, Z., Ehatisham-Ul-Haq, M.: A novel scheme for designing secure substitution boxes (S-boxes) based on Möbius group and finite field. Wireless Personal Communications (2022)

2. Biham, E., Shamir, A.: Differential cryptanalysis of the data encryption standard. Springer Science & Business Media (2012)

3. Biryukov, A., De Canniere, C.: Linear cryptanalysis for block ciphers. Encyclopedia of cryptography and security (2011)

4. Canteaut, A., Duval, S., Leurent, G.: Construction of lightweight S-boxes using Feistel and MISTY structures. In: Selected areas in crypto. Springer (2015)

5. Carlet, C., Ding, C.: Nonlinearities of S-boxes. Finite fields and their applications (2007)

6. Carlet, C., Mesnager, S.: On the supports of the Walsh transforms of Boolean functions. BFCA'05 (2005)

7. Daemen, J., Govaerts, R., Vandewalle, J.: A framework for the design of one-way hash functions including cryptanalysis of Damgård's one-way function based on a cellular automaton. In: ASIACRYPT. Springer (1993)

8. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1. 2: Lightweight authenticated encryption and hashing. Journal of Cryptology (2021)

9. Feistel, H.: Cryptography and computer privacy. Scientific american (1973)

10. Formenti, E., Imai, K., Martin, B., Yunès, J.: Advances on random sequence generation by uniform cellular automata. Computing with new resources (2014)

11. Gutowitz, H.: Cryptography with dynamical systems. In: Cellular Automata and Cooperative Systems. Springer (1993)

12. Jakobsen, T., Knudsen, L.R.: Attacks on block ciphers of low algebraic degree. Journal of Cryptology (2001)

13. Li, Y., Wang, M.: Constructing S-boxes for lightweight cryptography with Feistel structure. In: Int. Workshop on Crypto. Hardware and Embedded Systems. Springer (2014)

14. Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing (1988)

15. Mariot, L., Picek, S., Leporati, A., Jakobovic, D.: Cellular automata based S-boxes. Cryptography and Communications (2019)

16. Naor, M., Reingold, O.: On the construction of pseudo-random permutations: Luby-Rackoff revisited. In: ACM symposium on Theory of computing (1997)

17. Nyberg, K., Knudsen, L.R.: Provable security against differential cryptanalysis. In: Annual international cryptology conference. Springer (1992)

18. Nyberg, K.: Differentially uniform mappings for cryptography. In: Workshop on the Theory and Application of Cryptographic Techniques. Springer (1993)

19. Patarin, J.: Luby-Rackoff: 7 rounds are enough for $2^n(1-\varepsilon)$ security. In: CRYPTO. Springer (2003)

20. Poinsot, L.: Boolean bent functions in impossible cases: odd and plane dimensions. International Journal of Computer Science and Network Security (2006)

21. Preneel, B.: Analysis and design of crypto. hash functions. Ph.D. thesis (1993)

22. Pub, F.: Security requirements for cryptographic modules. FIPS PUB (1994)

23. Wagner, D.: The boomerang attack. In: FSE. Springer (1999)

24. Webster, A.F., Tavares, S.E.: On the design of S-Boxes. In: Conference on the theory and application of cryptographic techniques. Springer (1985)

25. Wolfram, S.: Statistical mechanics of ca. Reviews of modern physics (1983)

26. Xiao, G.Z., Massey, J.L.: A spectral characterization of correlation-immune combining functions. IEEE Transactions on information theory (1988)