S-boxes and Linear Redundancy
An S-box (substitution box) maps $n$ input bits to $m$ output bits and is the main source of nonlinearity in most block ciphers. A bijective $n \times n$ S-box can be viewed as $n$ Boolean functions $b_0, \ldots, b_{n-1}$, one per output bit, together with all $2^n - 1$ of their XOR combinations $b_\alpha$. These component functions determine the S-box's resistance to linear and differential cryptanalysis.
Linear redundancy
The PhD research proposed a new S-box criterion: an S-box has linear redundancy if two of its component functions are affine equivalent, that is, one output is just another output with its inputs linearly transformed. For random S-boxes this essentially never happens: in 10,000 random bijective S-boxes of size $7 \times 7$ and $8 \times 8$, none had any linear redundancy. Its presence is therefore a clear sign of non-random structure.
The AES S-box
The AES S-box (inversion in $\mathrm{GF}(2^8)$ followed by an affine map) has excellent nonlinearity, degree and autocorrelation. Using the equivalence test built on the Theorem of Connectivity, Fuller and Millan (2002) showed that all 255 component functions of the AES S-box are affine equivalent: the AES S-box has complete linear redundancy. The search for each mapping was cut to about $2^{15}$ candidates, and exactly eight distinct linear transforms relate any pair. For example, output bit 1 is output bit 0 with its inputs transformed by a fixed matrix, $b_1(x) = b_0(D_{01}\,x)$, with
$$D_{01} = \begin{pmatrix} 1&0&1&1&0&0&1&0\\ 0&1&0&1&0&1&1&0\\ 0&0&0&1&0&0&1&0\\ 1&0&0&1&1&0&0&0\\ 0&1&0&1&1&1&0&0\\ 1&0&0&0&1&1&1&0\\ 1&1&0&1&0&0&0&0\\ 1&0&0&0&1&1&0&1 \end{pmatrix}$$
(with $x = (x_1, \ldots, x_8)^T$ and $x_8$ the least significant bit). As the thesis records, following this result Biham, Wagner, and Youssef and Tavares (2002) showed that every S-box based on finite field inversion or power maps has complete linear redundancy, and the surrounding affine maps do not remove it.
Check it yourself. This builds the AES S-box in your browser from its definition, analyses all 255 component functions, and tests the mapping above on every input.
Removing it
Can the redundancy be removed without giving up too much strength? The thesis gave tweaking algorithms that repeatedly swap S-box outputs: a two-step version, and a four-step version that keeps the self-inverse property of inversion S-boxes and creates no fixed points. Applied to finite field S-boxes, they produced bijective $8 \times 8$ S-boxes without linear redundancy with nonlinearity 108, degree 7 and maximum autocorrelation 56. The best such S-box previously in use, from the original Hierocrypt specification, had 106, 6 and 72.
The security impact of linear redundancy is still not fully understood. The thesis suggested avenues for cryptanalysis (reduced-round distinguishers, the algebraic representation of Rijndael, the key schedule's use of the S-box) and recommended S-boxes without linear redundancy until the implications are known.
Survey of cipher S-boxes
An $m \times k$ S-box has $k$ output coordinates, each a Boolean function of $m$ inputs. The table below summarises, for a range of well-known cipher S-boxes, how many distinct affine equivalence classes those coordinate functions fall into and the range of their nonlinearity. It does this both for the individual coordinate functions and for all non-zero XOR combinations of them (for an 8 × 8 S-box, the 255 non-zero linear combinations of the outputs).
When every function falls into a single class, the S-box has linear redundancy: each output can be obtained from any other by an affine transformation. The AES S-box, built by inversion in a finite field, is the standout example. See the papers on linear redundancy on the Publications page.
| cipher | design technique | size | individual functions | XOR combinations | ||||
|---|---|---|---|---|---|---|---|---|
| classes | nl min | nl max | classes | nl min | nl max | |||
| AES (Rijndael), Grand-Cru, Mugi, Q, Scream | Finite field inversion | 8 × 8 | 1 | 112 | 112 | 1 | 112 | 112 |
| Anubis | Pseudo-random | 8 × 8 | 8 | 96 | 108 | 255 | 94 | 110 |
| Noekeon | Bit-sliced algebraic; contains fixed points | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Q (s-box 1) | Bit-sliced algebraic; contains fixed points | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Q (s-box 2) | Bit-sliced algebraic; contains fixed points | 4 × 4 | 1 | 4 | 4 | 2 | 4 | 4 |
| Q (s-box 3) | Bit-sliced algebraic; contains fixed points | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Camellia (s-box 1) | Finite field inversion | 8 × 8 | 1 | 112 | 112 | 1 | 112 | 112 |
| Camellia (s-box 4) | Finite field inversion | 8 × 8 | 1 | 112 | 112 | 1 | 112 | 112 |
| SC2000 | Unknown | 5 × 5 | 1 | 12 | 12 | 1 | 12 | 12 |
| SC2000 | Unknown | 6 × 6 | 1 | 24 | 24 | 1 | 24 | 24 |
| Hierocrypt | Unknown | 8 × 8 | 8 | 106 | 110 | 255 | 106 | 112 |
| Serpent (s-box 1) | Heuristic | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Serpent (s-box 2) | Heuristic | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Serpent (s-box 3) | Heuristic | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Serpent (s-box 4) | Heuristic | 4 × 4 | 1 | 4 | 4 | 2 | 4 | 4 |
| Serpent (s-box 5) | Heuristic | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Serpent (s-box 6) | Heuristic | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Serpent (s-box 7) | Heuristic | 4 × 4 | 2 | 4 | 4 | 2 | 4 | 4 |
| Serpent (s-box 8) | Heuristic | 4 × 4 | 1 | 4 | 4 | 2 | 4 | 4 |
| Khazad | Pseudo-random | 8 × 8 | 8 | 98 | 108 | 255 | 96 | 110 |
| Square | Finite field inversion | 8 × 8 | 1 | 112 | 112 | 1 | 112 | 112 |
| Misty1 | Heuristic; contains fixed points | 7 × 7 | 1 | 56 | 56 | 1 | 56 | 56 |
| Misty1 | Heuristic; contains fixed points | 9 × 9 | 1 | 240 | 240 | 1 | 240 | 240 |
| Sober-t32 | Hybrid of Skipjack S-box and ISRC-designed S-box | 8 × 32 | 32 | 104 | 112 | n/a | n/a | n/a |
| Skipjack | Unknown | 8 × 8 | 8 | 104 | 108 | 255 | 100 | 108 |
| Mars | Heuristic | 9 × 32 | 32 | 207 | 226 | n/a | n/a | n/a |
Notes from the original survey: the Rijndael (AES) S-box functions are also affine-equivalent to those of the Camellia S-boxes (the same primitive polynomial is used to construct each), and to those of the Square S-box. "n/a" marks S-boxes with more outputs than inputs, where the XOR-combination analysis was not carried out.