Also known as: substitution box, S-box
An S-box (substitution box) is a fixed lookup table that replaces an input bit pattern with an output bit pattern.1 It is the nonlinear heart of most modern ciphers: where the surrounding XOR and permutation steps are linear, the S-box deliberately is not, supplying the confusion that makes the key-to-ciphertext relationship hard to unravel.
How it works
An S-box takes m input bits and produces n output bits by table lookup — for example,
AES uses a single 8-bit-to-8-bit S-box, a 256-entry table applied to every byte, while
DES uses eight 6-bit-to-4-bit S-boxes inside its
round function. The table is a fixed part of the cipher, the same for every key; secrecy
lives in the key, not in the table (Kerckhoffs’s principle).
Because a lookup is a single memory access or a small circuit, an S-box is cheap to evaluate
in both hardware and software.
Design criteria
A good S-box is engineered against the two workhorse attacks on block ciphers, and its resistance can be read straight off two tables:
- Nonlinearity (vs linear cryptanalysis). If any output bit could be approximated by a linear (XOR) combination of input bits, an attacker could stack those approximations across rounds. A strong S-box maximizes distance from every affine function, so the best linear approximation holds only slightly more often than chance. This is summarized by the Linear Approximation Table.
- Low differential uniformity (vs differential cryptanalysis). For every fixed input difference, the resulting output differences should be spread as evenly as possible so no difference propagates with high probability. This is captured by the Difference Distribution Table (DDT); a small maximum DDT entry means high resistance.
- Completeness / avalanche. Each output bit should depend on all input bits, and flipping one input bit should change output bits unpredictably — the local seed of the whole cipher’s avalanche effect.
The AES S-box is built algebraically (the multiplicative inverse in GF(2⁸) followed by an affine map) precisely to hit near-optimal values on all of these. History also underlines why the criteria matter: the DES S-boxes were quietly tuned by IBM and the NSA in the 1970s, and years later it emerged they had been strengthened against differential cryptanalysis — an attack the public did not know until 1990.
In practice
S-boxes appear in both Feistel networks (inside the round function) and substitution-permutation networks (as the substitution layer). They can be fixed and public (AES, DES) or, in a few designs, key-dependent (Blowfish generates its S-boxes from the key). A subtle implementation concern is timing: a naive table lookup can leak key-correlated cache-timing information, so hardened AES implementations compute the S-box with bit-sliced logic instead of a memory table.
Relevance to SDR
S-boxes sit inside the ciphers that protect digital radio traffic — AES (P25 AES-256, DMR) and DES (P25) both rely on S-box substitution — so the construction is part of what makes encrypted voice GopherTrunk monitors infeasible to recover without the key.
The term is also relevant to weaker, non-encryption schemes. The clean-room analysis of the Motorola P25 talker-alias obfuscation in issue #773 recovered a 256-entry substitution table purely from public on-air data, with no third-party source: a fixed lookup like this is exactly an S-box in form, even though, used alone for reversible hiding rather than keyed encryption, it provides obfuscation and not secrecy.