◄ WORLD V · SONNY 5DART 191 · a helldive at the net

THE S-BOX the one nonlinear step; a lookup that hides the key

Everything else in a cipher — XOR, shift, permute — is linear, and linear ciphers fall to linear algebra. The S-box (substitution box) is the one nonlinear part: a fixed table that maps each small input to a scrambled output, chosen so that S(a)⊕S(b) ≠ S(a⊕b). It is Shannon’s confusion made concrete — the step that makes the relationship between key and ciphertext too tangled to solve.

THE TECHNIQUE a nonlinear bijection: substitute, never solve

A 4-bit S-box is a permutation of 0…15. Apply it, and check its nonlinearity: S(1)⊕S(2) is not S(1⊕2) — the property a linear map can never have: live demo







  
HISTORY & CREDIT Shannon 1949; DES/AES S-boxes

  
“S-boxes are just random lookup tables.” — no. They are carefully engineered for high nonlinearity and resistance to differential/linear cryptanalysis; the DES S-boxes were tuned (by IBM, with NSA input) against attacks not public until 1990, and the AES S-box is the multiplicative inverse in GF(2⁸) plus an affine map — algebra, not chance. cited

  
1949 · Claude Shannon — “Communication Theory of Secrecy Systems”: names confusion and diffusion; the S-box is confusion.
1977 · DES — eight 6→4-bit S-boxes, later shown tuned against differential cryptanalysis (Biham-Shamir, 1990) years before it was public.
1993 · Kaisa Nyberg — “Differentially uniform mappings for cryptography” (EUROCRYPT): the multiplicative-inverse S-box (the “Nyberg S-box”), provably near-maximal nonlinearity.
1998 / 2001 · Daemen & Rijmen (Rijndael, standardised as AES / FIPS 197 in 2001) — adopt Nyberg’s inverse in GF(2⁸) + an affine map: clean algebra, maximal nonlinearity.

  
Confusion is not obscurity: the AES S-box has a one-line algebraic definition, yet its input/output bits are related by high-degree Boolean functions — transparent to build, opaque to attack. Shannon 1949 / DES 1977






  
RECOMMEND FOR I-13 nonlinearity, computed

  
On the canonical compiler the S-box is an array lookup, and its defining nonlinearity holds:

  
$ i13 run sbox.i13   # 4-bit S-box, a permutation of 0..15
S[3] = 1   S[10] = 6
S[1] xor S[2] xor S[3] = 8   but S[1 xor 2 xor 3] = S[0] = 14   -- 8 != 14: NONLINEAR

  
Recommend: the S-box is LIT and the missing nonlinearity for an I-13 cipher — verified a 4-bit S-box (an array-encoded permutation of 0…15) substitutes S[3]=1, S[10]=6, and fails linearity: S(1)⊕S(2)⊕S(3)=8 ≠ S(0)=14. It is one bounded array and one index — the only piece a Feistel (190) or SPN (192) needs that plain XOR/shift cannot provide. Everything else in the corpus’s bitwise toolkit is linear; the S-box is where the security actually lives, and it costs a table lookup.