Boolean Functions for Cryptography

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.

cipherdesign techniquesizeindividual functionsXOR combinations
classesnl minnl maxclassesnl minnl max
AES (Rijndael), Grand-Cru, Mugi, Q, ScreamFinite field inversion8 × 811121121112112
AnubisPseudo-random8 × 889610825594110
NoekeonBit-sliced algebraic; contains fixed points4 × 4244244
Q (s-box 1)Bit-sliced algebraic; contains fixed points4 × 4244244
Q (s-box 2)Bit-sliced algebraic; contains fixed points4 × 4144244
Q (s-box 3)Bit-sliced algebraic; contains fixed points4 × 4244244
Camellia (s-box 1)Finite field inversion8 × 811121121112112
Camellia (s-box 4)Finite field inversion8 × 811121121112112
SC2000Unknown5 × 51121211212
SC2000Unknown6 × 61242412424
HierocryptUnknown8 × 88106110255106112
Serpent (s-box 1)Heuristic4 × 4244244
Serpent (s-box 2)Heuristic4 × 4244244
Serpent (s-box 3)Heuristic4 × 4244244
Serpent (s-box 4)Heuristic4 × 4144244
Serpent (s-box 5)Heuristic4 × 4244244
Serpent (s-box 6)Heuristic4 × 4244244
Serpent (s-box 7)Heuristic4 × 4244244
Serpent (s-box 8)Heuristic4 × 4144244
KhazadPseudo-random8 × 889810825596110
SquareFinite field inversion8 × 811121121112112
Misty1Heuristic; contains fixed points7 × 71565615656
Misty1Heuristic; contains fixed points9 × 912402401240240
Sober-t32Hybrid of Skipjack S-box and ISRC-designed S-box8 × 3232104112n/an/an/a
SkipjackUnknown8 × 88104108255100108
MarsHeuristic9 × 3232207226n/an/an/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.