Rijndael S-box explained

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

AES S-box!! 00 !! 01 !! 02 !! 03 !! 04 !! 05 !! 06 !! 07 !! 08 !! 09 !! 0a !! 0b !! 0c !! 0d !! 0e !! 0f

00	63	7c	77	7b	f2	6b	6f	c5	30	01	67	2b	fe	d7	ab	76
10	ca	82	c9	7d	fa	59	47	f0	ad	d4	a2	af	9c	a4	72	c0
20	b7	fd	93	26	36	3f	f7	cc	34	a5	e5	f1	71	d8	31	15
30	04	c7	23	c3	18	96	05	9a	07	12	80	e2	eb	27	b2	75
40	09	83	2c	1a	1b	6e	5a	a0	52	3b	d6	b3	29	e3	2f	84
50	53	d1	00	ed	20	fc	b1	5b	6a	cb	be	39	4a	4c	58	cf
60	d0	ef	aa	fb	43	4d	33	85	45	f9	02	7f	50	3c	9f	a8
70	51	a3	40	8f	92	9d	38	f5	bc	b6	da	21	10	ff	f3	d2
80	cd	0c	13	ec	5f	97	44	17	c4	a7	7e	3d	64	5d	19	73
90	60	81	4f	dc	22	2a	90	88	46	ee	b8	14	de	5e	0b	db
a0	e0	32	3a	0a	49	06	24	5c	c2	d3	ac	62	91	95	e4	79
b0	e7	c8	37	6d	8d	d5	4e	a9	6c	56	f4	ea	65	7a	ae	08
c0	ba	78	25	2e	1c	a6	b4	c6	e8	dd	74	1f	4b	bd	8b	8a
d0	70	3e	b5	66	48	03	f6	0e	61	35	57	b9	86	c1	1d	9e
e0	e1	f8	98	11	69	d9	8e	94	9b	1e	87	e9	ce	55	28	df
f0	8c	a1	89	0d	bf	e6	42	68	41	99	2d	0f	b0	54	bb	16
The column is determined by the least significant nibble, and the row by the most significant nibble. For example, the value 9a is converted into b8.

The S-box maps an 8-bit input,, to an 8-bit output, . Both the input and output are interpreted as polynomials over GF(2). First, the input is mapped to its multiplicative inverse in, 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:\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 is the S-box output and 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:

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

where represents the multiplicative inverse,

⊕ is the bitwise XOR operator, \lll is a left bitwise circular shift, and the constant is given in hexadecimal.

An equivalent formulation of the affine transformation is

s _{i} = b _{i} ⊕ b _{(i} 8 } ⊕ b _{(i} 8 } ⊕ b _{(i} 8 } ⊕ b _{(i} 8 } ⊕ c _{i}

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

Another equivalent is:

s = \left(b x 31 _{10} \mod{ 257 _{10} }\right) \oplus 99_^{[4] [5]} where x is polynomial multiplication of b and 31 _{10} taken as bit arrays.

Inverse S-box

01	02	03	04	05	06	07	08	09	0a	0b	0c	0d	0e	0f
00	52	09	6a	d5	30	36	a5	38	bf	40	a3	9e	81	f3	d7	fb
10	7c	e3	39	82	9b	2f	ff	87	34	8e	43	44	c4	de	e9	cb
20	54	7b	94	32	a6	c2	23	3d	ee	4c	95	0b	42	fa	c3	4e
30	08	2e	a1	66	28	d9	24	b2	76	5b	a2	49	6d	8b	d1	25
40	72	f8	f6	64	86	68	98	16	d4	a4	5c	cc	5d	65	b6	92
50	6c	70	48	50	fd	ed	b9	da	5e	15	46	57	a7	8d	9d	84
60	90	d8	ab	00	8c	bc	d3	0a	f7	e4	58	05	b8	b3	45	06
70	d0	2c	1e	8f	ca	3f	0f	02	c1	af	bd	03	01	13	8a	6b
80	3a	91	11	41	4f	67	dc	ea	97	f2	cf	ce	f0	b4	e6	73
90	96	ac	74	22	e7	ad	35	85	e2	f9	37	e8	1c	75	df	6e
a0	47	f1	1a	71	1d	29	c5	89	6f	b7	62	0e	aa	18	be	1b
b0	fc	56	3e	4b	c6	d2	79	20	9a	db	c0	fe	78	cd	5a	f4
c0	1f	dd	a8	33	88	07	c7	31	b1	12	10	59	27	80	ec	5f
d0	60	51	7f	a9	19	b5	4a	0d	2d	e5	7a	9f	93	c9	9c	ef
e0	a0	e0	3b	4d	ae	2a	f5	b0	c8	eb	bb	3c	83	53	99	61
f0	17	2b	04	7e	ba	77	d6	26	e1	69	14	63	55	21	0c	7d

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:\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:

b = (s \lll 1 ) ⊕ (s \lll 3 ) ⊕ (s \lll 6 ) ⊕ 5 _{16}

where

⊕ is the bitwise XOR operator, \lll is a left bitwise circular shift, and the constant 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, 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:

1. include
2. define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))

void initialize_aes_sbox(uint8_t sbox[256])

Notes and References

1. Web site: The Rijndael Block Cipher . 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. Web site: The Advanced Encryption Standard . FIPS PUB 197: the official AES standard . 2001-11-26 . . 2010-04-29.
4. Web site: Matlab implementation of the Advanced Encryption Standard . 2001-12-19 . Jörg J. Buchholz.
5. Web site: An Improved AES S-box and Its Performance Analysis . May 2011 . Jie Cui . Liusheng Huang . Hong Zhong . Chinchen Chang . Wei Yang.