Rijndael S-box

The Rijndael S-box is a substitution box (lookup table) used in the Rijndael cipher, on which the Advanced Encryption Standard (AES) cryptographic algorithm is based.^[1]

The S-box maps an 8-bit input, c, to an 8-bit output, s = S(c). Both the input and output are interpreted as polynomials over GF(2). First, the input is mapped to its multiplicative inverse in GF(2⁸) = GF(2) [x]/(x⁸ + x⁴ + x³ + x + 1), Rijndael's finite field. Zero, as the identity, is mapped to itself. This transformation is known as the Nyberg S-box after its inventor Kaisa Nyberg.^[2] The multiplicative inverse is then transformed using the following affine transformation:

${\displaystyle {\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&1\\1&1&1&1&1&0&0&0\\0&1&1&1&1&1&0&0\\0&0&1&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{bmatrix}}{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}+{\begin{bmatrix}1\\1\\0\\0\\0\\1\\1\\0\end{bmatrix}}}$

where [s₇, ..., s₀] is the S-box output and [b₇, ..., b₀] is the multiplicative inverse as a vector.

This affine transformation is the sum of multiple rotations of the byte as a vector, where addition is the XOR operation:

${\displaystyle s=b\oplus (b\lll 1)\oplus (b\lll 2)\oplus (b\lll 3)\oplus (b\lll 4)\oplus 63_{16}}$

where b represents the multiplicative inverse, ${\displaystyle \oplus }$ is the bitwise XOR operator, ${\displaystyle \lll }$ is a left bitwise circular shift, and the constant 63₁₆ = 01100011₂ is given in hexadecimal.

An equivalent formulation of the affine transformation is

${\displaystyle s_{i}=b_{i}\oplus b_{(i+4)\operatorname {mod} 8}\oplus b_{(i+5)\operatorname {mod} 8}\oplus b_{(i+6)\operatorname {mod} 8}\oplus b_{(i+7)\operatorname {mod} 8}\oplus c_{i}}$

where s, b, and c are 8 bit arrays, c is 01100011₂, and subscripts indicate a reference to the indexed bit.^[3]

Another equivalent is:

${\displaystyle s=\left(b\times 31_{10}\mod {257_{10}}\right)\oplus 99_{10}}$^[4][5]

where ${\displaystyle \times }$ is polynomial multiplication of ${\displaystyle b}$ and ${\displaystyle 31_{10}}$ taken as bit arrays.

The inverse S-box is simply the S-box run in reverse. For example, the inverse S-box of b8₁₆ is 9a₁₆. It is calculated by first calculating the inverse affine transformation of the input value, followed by the multiplicative inverse. The inverse affine transformation is as follows:

${\displaystyle {\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}={\begin{bmatrix}0&0&1&0&0&1&0&1\\1&0&0&1&0&0&1&0\\0&1&0&0&1&0&0&1\\1&0&1&0&0&1&0&0\\0&1&0&1&0&0&1&0\\0&0&1&0&1&0&0&1\\1&0&0&1&0&1&0&0\\0&1&0&0&1&0&1&0\end{bmatrix}}{\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}+{\begin{bmatrix}1\\0\\1\\0\\0\\0\\0\\0\end{bmatrix}}}$

The inverse affine transformation also represents the sum of multiple rotations of the byte as a vector, where addition is the XOR operation:

${\displaystyle b=(s\lll 1)\oplus (s\lll 3)\oplus (s\lll 6)\oplus 5_{16}}$

where ${\displaystyle \oplus }$ is the bitwise XOR operator, ${\displaystyle \lll }$ is a left bitwise circular shift, and the constant 5₁₆ = 00000101₂ is given in hexadecimal.

The Rijndael S-box was specifically designed to be resistant to linear and differential cryptanalysis. This was done by minimizing the correlation between linear transformations of input/output bits, and at the same time minimizing the difference propagation probability.

The Rijndael S-box can be replaced in the Rijndael cipher,^[1] which defeats the suspicion of a backdoor built into the cipher that exploits a static S-box. The authors claim that the Rijndael cipher structure is likely to provide enough resistance against differential and linear cryptanalysis even if an S-box with "average" correlation / difference propagation properties is used (cf. the "optimal" properties of the Rijndael S-box).

The following C code calculates the S-box:

#include <stdint.h>  #define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))  void initialize_aes_sbox(uint8_t sbox[256]) { 	uint8_t p = 1, q = 1; 	 	/* loop invariant: p * q == 1 in the Galois field */ 	do { 		/* multiply p by 3 */ 		p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);  		/* divide q by 3 (equals multiplication by 0xf6) */ 		q ^= q << 1; 		q ^= q << 2; 		q ^= q << 4; 		q ^= q & 0x80 ? 0x09 : 0;  		/* compute the affine transformation */ 		uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);  		sbox[p] = xformed ^ 0x63; 	} while (p != 1);  	/* 0 is a special case since it has no inverse */ 	sbox[0] = 0x63; }