Constructing an S-Box: Field Inversion and Differential Uniformity

A substitution box is a small lookup table that maps $m$ input bits to $n$ output bits. In DES it is six bits to four, specified as eight tables of sixty-four entries with no stated derivation; the values were chosen for resistance to differential cryptanalysis, a fact only explained decades after publication. In AES the table is eight bits to eight and has a closed-form description: it is the multiplicative inverse in the field $\mathrm{GF}(2^8)$ followed by a fixed affine transform over $\mathrm{GF}(2)$. The difference between an opaque table and a formula is the difference between hoping a property holds and being able to prove it.

Why inversion

The field $\mathrm{GF}(2^8)$ has 255 nonzero elements, and each has exactly one multiplicative inverse. The map $x \mapsto x^{-1}$ on the nonzero elements, with zero mapped to zero by convention, is a permutation of the 256 byte values — the minimum requirement for a substitution that must be invertible. It is also about as far from linear as a function on eight bits can be, in a sense made precise shortly.

The property that matters for differential cryptanalysis is this. For a fixed nonzero input difference $\alpha$ and any output difference $\beta$, count how many $x$ satisfy

$$S(x) \oplus S(x \oplus \alpha) = \beta$$

The maximum of that count over all $\alpha \neq 0$ and all $\beta$ is the differential uniformity of $S$. For a random function on eight bits the expected count for a given pair of differences is 1, with a Poisson-ish spread. A linear function achieves 256 for some $\beta$, since the output difference is then a fixed linear image of $\alpha$ for every input. For the inversion map in $\mathrm{GF}(2^8)$ the maximum is 4. That is a theorem, not a measurement: for any $\alpha \neq 0$ and $\beta$, the equation $x^{-1} \oplus (x \oplus \alpha)^{-1} = \beta$ reduces to a quadratic in $x$ after clearing denominators, and a quadratic over a field has at most two roots. Doubling for the zero case and the symmetry gives the bound of 4, and it is attained.

The consequence for a differential characteristic is direct. A characteristic that predicts a particular difference at the S-box input and a particular difference at the output holds for a fraction at most $4/256 = 2^{-6}$ of inputs, so each active S-box contributes at most $6 - 2 = 4$ bits of probability deficit against a random function, where the 2 accounts for the expected count of one. AES has at least 25 active S-boxes over four rounds, giving a bound of $2^{-100}$ for any four-round characteristic. Ten rounds then cannot be covered by a single characteristic of usable probability, which is why differential cryptanalysis against full AES is not a practical concern.

The affine step and why it exists

Inversion alone is a poor S-box for one reason: it has simple algebraic structure. Its inputs and outputs satisfy $x \cdot S(x) = 1$ for nonzero $x$, which is a single low-degree equation linking input and output bits. An attack that writes the whole cipher as a system of polynomial equations gets a compact system for free. Interpolation of the inverse map over $\mathrm{GF}(2^8)$ yields a polynomial of degree 254, but expressed in terms of the field’s own multiplication that high degree collapses into a low-complexity relation.

The AES designers’ answer was to compose the inverse with an affine transform over $\mathrm{GF}(2)$: a bit matrix multiplication plus a constant XOR. This does not change differential uniformity or nonlinearity, because affine maps preserve difference structures up to relabelling — if $S$ has uniformity 4 then so does $A \circ S$ for affine $A$, and the sets of active S-boxes are unchanged. What it does change is the algebraic description. The resulting function has no low-degree implicit equation in the input and output bits, and its univariate polynomial representation over $\mathrm{GF}(2^8)$ becomes dense.

The affine map is chosen so that the S-box has no fixed points and no opposite fixed points — $S(x) \neq x$ and $S(x) \neq \bar{x}$ for all $x$ — which removes a trivial self-similarity an attacker could exploit in a fixed-point attack. It is also chosen to simplify the circuit implementation, because the matrix can be evaluated with a small number of XOR and rotate operations rather than 64 AND gates.

# Constructing the AES S-box from first principles, without the published table.
def gmul(a, b):
    r = 0
    for _ in range(8):
        if b & 1:
            r ^= a
        hi = a & 0x80
        a = (a << 1) & 0xFF
        if hi:
            a ^= 0x1B          # reduction by x^8+x^4+x^3+x+1
        b >>= 1
    return r

def ginv(x):
    if x == 0:
        return 0
    for y in range(1, 256):    # exhaustive; a real build uses exponentiation
        if gmul(x, y) == 1:
            return y

def affine(x):
    # y_i = x_i ^ x_{(i+4)%8} ^ x_{(i+5)%8} ^ x_{(i+6)%8} ^ x_{(i+7)%8} ^ c_i
    y = 0
    for i in range(8):
        bit = ((x >> i) ^ (x >> ((i + 4) % 8)) ^ (x >> ((i + 5) % 8))
               ^ (x >> ((i + 6) % 8)) ^ (x >> ((i + 7) % 8))) & 1
        y |= bit << i
    return y ^ 0x63

sbox = [affine(ginv(x)) for x in range(256)]
assert sbox[0x00] == 0x63 and sbox[0x53] == 0xED

The cost of a table

The formula is compact; the implementation is not. Computing an inverse in $\mathrm{GF}(2^8)$ by exponentiation costs a chain of multiplications, each of which is a loop over eight bits in the straightforward version, and the affine step adds a dozen XORs. That is why every practical AES implementation ships a 256-byte table instead. The table is small enough to fit in a few cache lines and its access is a single load.

The load is also the cipher’s main side-channel liability. A table indexed by a secret byte produces a memory access whose address depends on the key and the plaintext. On a processor with a data cache, the timing of the load and the cache lines it evicts leak information about the index. The classic attack on AES implementations — Bernstein’s cache-timing analysis, and the later cache-collision and prime-and-probe variants — recovers key bytes from these effects. Any implementation that indexes a table with secret data has this exposure; the mitigations are covered in constant-time AES implementations.

Bit-sliced implementations avoid the table entirely. The state is held as 128 bits spread across eight 16-bit registers, one register per bit position, and the S-box is evaluated as a Boolean circuit over those bit-planes. The circuit is a fixed sequence of AND, OR, XOR, and NOT operations, roughly a hundred of them for the inverse-plus-affine construction, with no data-dependent memory access. The cost is that the cipher processes one block at a time in a form that is awkward to parallelise across blocks; the gain is that the timing is independent of the data. In a vectorised setting the same circuit applied to 128 parallel blocks in SIMD registers gives a throughput advantage as well.

Smaller S-boxes and the 4-bit case

Not every cipher can afford an eight-bit table. Lightweight designs use four-bit S-boxes, 16-entry tables that fit in a register and can be evaluated by a few arithmetic operations. The PRESENT S-box is specified as a 16-entry table with differential uniformity 4 out of 16 possible inputs — the same bound relative to the domain size as AES achieves, but with a much smaller diffusion reach per active S-box.

The trade is stark. A four-bit S-box with uniformity 4 contributes a probability deficit of only $4/16 = 2^{-2}$ per active S-box against the $2^{-6}$ of AES, so a cipher needs many more active S-boxes or many more rounds to reach the same bound. PRESENT compensates with a bit permutation that spreads each nibble across the state and 31 rounds. The relevant comparison is not table size but the product of active S-boxes per round and rounds, and lightweight designs generally accept a worse ratio in exchange for a gate count that fits a constrained device.

There is a further structural option: use the inversion map on a smaller field. The field $\mathrm{GF}(2^4)$ has 15 nonzero elements, and inversion there gives a four-bit S-box with the same uniformity argument — at most two roots for a quadratic. Designs that use this are structurally similar to AES with a narrower field, and their round counts rise accordingly. The uniformity bound scales with the field size, so the security margin has to be bought back with rounds.

Reading the table

Given the table, several properties are checkable directly. Every entry appears exactly once, since the map is a permutation. The S-box has no fixed point: S(0x00) = 0x63, S(0x63) = 0x63 would be a fixed point and does not occur. The inverse S-box, used in decryption, is the table with its entries reversed — inv_sbox[sbox[x]] == x for all $x$ — and implementations frequently store both, at a cost of 512 bytes.

The table’s resistance properties are not visible by inspection, which is the point of having a derivation. Differential uniformity is computed by enumerating all $255 \times 256$ difference pairs, and linearity by computing the Walsh transform of each output-bit/input-mask pair. Both are exhaustive over a space of 65,536 evaluations and take negligible time. What the derivation gives is not the ability to check the numbers but the ability to predict them: a designer choosing a new field or a new affine map knows in advance that the uniformity will be 4, and can spend effort on the other properties instead. The interaction between these S-box properties and the linear layer around them is what diffusion and branch numbers quantifies.