Rijndael S-box

Substitution box used in the Rijndael cipher

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]

Forward S-box

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.

Inverse S-box

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.

Design criteria

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).

Example implementation in C language

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;}

References

1. "The Rijndael Block Cipher" (PDF). Retrieved 2013-11-11.
2. Nyberg K. (1991) Perfect nonlinear S-boxes. In: Davies D.W. (eds) Advances in Cryptology – EUROCRYPT ’91. EUROCRYPT 1991. Lecture Notes in Computer Science, vol 547. Springer, Berlin, Heidelberg
3. "The Advanced Encryption Standard" (PDF). FIPS PUB 197: the official AES standard. Federal Information Processing Standard. 2001-11-26. Retrieved 2010-04-29.
4. Jörg J. Buchholz (2001-12-19). "Matlab implementation of the Advanced Encryption Standard" (PDF).
5. Jie Cui; Liusheng Huang; Hong Zhong; Chinchen Chang; Wei Yang (May 2011). "An Improved AES S-box and Its Performance Analysis" (PDF). Archived from the original (PDF) on 2016-03-04.