SubBytes, ShiftRows y MixColumns: la ronda de AES

En la lección anterior vimos AES desde arriba: un estado de $4\times 4$ bytes, un AddRoundKey inicial y diez rondas. Dentro de la caja negra quedaban tres operaciones sin abrir. Hoy las abrimos. Seguimos en el punto del relato en que AES sustituye a DES, y la matemática que va a hacer el trabajo es la de los cuerpos finitos $\mathbb{F}_{2^8}$ de la lección 9. Más abajo hay una sorpresa para quien conozca los códigos correctores: una de las tres operaciones es, por dentro, un código MDS, la misma propiedad que hace óptimos a los códigos de Reed-Solomon.

La idea

Una ronda de AES reparte el trabajo entre tres operaciones, cada una con un cometido distinto.

• SubBytes cambia cada byte por otro, byte a byte, con una tabla (una caja S, de substitution box). Es la única operación no lineal de AES. Sin ella, todo el cifrado sería un sistema de ecuaciones lineales y se resolvería con álgebra de bachillerato. Es la confusión de Shannon.
• ShiftRows desplaza las filas del estado. No cambia ningún valor: solo lleva cada byte a otra columna.
• MixColumns mezcla los cuatro bytes de cada columna. Es la difusión: un byte que cambia contagia a toda su columna.

La combinación es lo que hace falta. SubBytes sola no mueve nada de sitio. ShiftRows y MixColumns, juntas, hacen que tras dos rondas cada byte de salida dependa de los 16 de entrada.

SubBytes: inverso y transformación afín

SubBytes aplica la misma función $S$ a cada uno de los 16 bytes. Se calcula en dos pasos.

1. Inverso. Se toma el inverso multiplicativo del byte en $\mathbb{F}_{2^8}$, y el $\texttt{00}$, que no tiene inverso, se deja en $\texttt{00}$.
2. Transformación afín. El resultado $b = (b_7\dots b_0)$ se pasa por una transformación lineal sobre $\mathbb{F}_2$ y se le suma la constante $\texttt{63}$.

Repaso Transformación afín

Una transformación lineal sobre $\mathbb{F}_2$ (en el sentido de la lección 3: respeta el XOR) multiplica un vector de bits por una matriz, sumando módulo 2. Una transformación afín hace eso y además suma un vector fijo. Aquí el vector son los bits de $\texttt{63} = 01100011$. Calcular un bit de salida es sumar módulo 2 unos pocos bits de entrada, sin llevadas.

En FIPS 197 la transformación afín es, con los bits en columna $(b_0,\dots,b_7)^T$:

$$\begin{pmatrix} b_0' \\ b_1' \\ b_2' \\ b_3' \\ b_4' \\ b_5' \\ b_6' \\ b_7' \end{pmatrix} = \begin{pmatrix} 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{pmatrix} \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{pmatrix} \oplus \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{pmatrix}.$$

Dicho de otro modo, $b_i' = b_i \oplus b_{i+4} \oplus b_{i+5} \oplus b_{i+6} \oplus b_{i+7} \oplus c_i$, con los índices módulo 8 y $c = \texttt{63}$. (Hemos comprobado con un programa que esta matriz da la misma tabla de 256 valores que la definición.)

Ejemplo: $S(\texttt{53})$. En la lección 9 vimos que $\texttt{53}^{-1} = \texttt{ca} = 11001010$, es decir, $b_7\dots b_0 = 1,1,0,0,1,0,1,0$. Aplicamos la fórmula bit a bit:

$i$	bits que se suman: $b_i,b_{i+4},b_{i+5},b_{i+6},b_{i+7}$	parte lineal	$c_i$	$b_i'$
0	$b_0,b_4,b_5,b_6,b_7 = 0,0,0,1,1$	0	1	1
1	$b_1,b_5,b_6,b_7,b_0 = 1,0,1,1,0$	1	1	0
2	$b_2,b_6,b_7,b_0,b_1 = 0,1,1,0,1$	1	0	1
3	$b_3,b_7,b_0,b_1,b_2 = 1,1,0,1,0$	1	0	1
4	$b_4,b_0,b_1,b_2,b_3 = 0,0,1,0,1$	0	0	0
5	$b_5,b_1,b_2,b_3,b_4 = 0,1,0,1,0$	0	1	1
6	$b_6,b_2,b_3,b_4,b_5 = 1,0,1,0,0$	0	1	1
7	$b_7,b_3,b_4,b_5,b_6 = 1,1,0,0,1$	1	0	1

Leyendo la columna «parte lineal» de abajo arriba ($b_7$ primero) sale $10001110 = \texttt{8e}$. Al sumarle la constante queda $\texttt{8e}\oplus\texttt{63} = 11101101 = \texttt{ed}$. Así que $S(\texttt{53}) = \texttt{ed}$, el mismo valor que da la tabla de FIPS 197.

Nadie calcula la caja S así cada vez: los 256 valores están en una tabla de $16\times 16$, la tabla 4 de FIPS 197 (§5.1.1). Para buscar un byte, su primer dígito hexadecimal da la fila y el segundo la columna: $\texttt{53}$ está en la fila 5, columna 3.

¿Por qué las dos piezas? El inverso es una función muy no lineal, y la afín evita que $S$ tenga puntos fijos ($S(a)=a$) o «anti-fijos» ($S(a)$ igual a $a$ con todos los bits cambiados): se ha comprobado que no hay ninguno. $S$ es una biyección de los 256 bytes, de modo que se puede deshacer (lección 12).

ShiftRows

La fila $r$ del estado (con $r = 0,1,2,3$) se rota $r$ posiciones a la izquierda. La fila 0 no se toca, la 1 se rota una posición, la 2 dos y la 3 tres. Como el estado se rellena por columnas, esto hace que los cuatro bytes de cada columna de salida procedan de cuatro columnas distintas de la entrada.

MixColumns

MixColumns trata cada columna del estado como un vector de cuatro elementos de $\mathbb{F}_{2^8}$ y lo multiplica por una matriz fija $M$, con las operaciones del cuerpo:

$$\begin{pmatrix} s_0' \\ s_1' \\ s_2' \\ s_3' \end{pmatrix} = \begin{pmatrix} \texttt{02}&\texttt{03}&\texttt{01}&\texttt{01}\\ \texttt{01}&\texttt{02}&\texttt{03}&\texttt{01}\\ \texttt{01}&\texttt{01}&\texttt{02}&\texttt{03}\\ \texttt{03}&\texttt{01}&\texttt{01}&\texttt{02} \end{pmatrix} \begin{pmatrix} s_0 \\ s_1 \\ s_2 \\ s_3 \end{pmatrix}.$$

La matriz es circulante: cada fila es la anterior desplazada una posición a la derecha. Recuerda que en $\mathbb{F}_{2^8}$ el byte $\texttt{02}$ es el polinomio $x$, y $\texttt{03} = x+1$. Multiplicar por $\texttt{02}$ es la operación xtime de la lección 9 (desplazar un bit a la izquierda y, si se sale uno, hacer XOR con $\texttt{1b}$). Multiplicar por $\texttt{03}$ es $\texttt{02}\cdot s \oplus s$. Multiplicar por $\texttt{01}$ no hace nada. La suma es el XOR.

Ejemplo resuelto: MixColumns de una columna

Tomamos la columna $(\texttt{db},\texttt{13},\texttt{53},\texttt{45})$. Primero los productos auxiliares, con xtime:

$s$	$\texttt{02}\cdot s$	$\texttt{03}\cdot s = \texttt{02}\cdot s \oplus s$
$\texttt{db}$	$\texttt{ad}$	$\texttt{ad}\oplus\texttt{db} = \texttt{76}$
$\texttt{13}$	$\texttt{26}$	$\texttt{26}\oplus\texttt{13} = \texttt{35}$
$\texttt{53}$	$\texttt{a6}$	$\texttt{a6}\oplus\texttt{53} = \texttt{f5}$
$\texttt{45}$	$\texttt{8a}$	$\texttt{8a}\oplus\texttt{45} = \texttt{cf}$

Por ejemplo, $\texttt{db} = 11011011$; desplazado a la izquierda es $1\,10110110$, se sale un bit, y se hace XOR con $\texttt{1b}$: $\texttt{b6}\oplus\texttt{1b} = \texttt{ad}$. En cambio, $\texttt{13} = 00010011$ se desplaza a $\texttt{26}$ sin salirse, y no hay XOR.

Ahora cada fila de $M$:

• $s_0' = \texttt{02}\cdot\texttt{db} \oplus \texttt{03}\cdot\texttt{13} \oplus \texttt{53} \oplus \texttt{45} = \texttt{ad}\oplus\texttt{35}\oplus\texttt{53}\oplus\texttt{45} = \texttt{8e}$.
• $s_1' = \texttt{db} \oplus \texttt{02}\cdot\texttt{13} \oplus \texttt{03}\cdot\texttt{53} \oplus \texttt{45} = \texttt{db}\oplus\texttt{26}\oplus\texttt{f5}\oplus\texttt{45} = \texttt{4d}$.
• $s_2' = \texttt{db} \oplus \texttt{13} \oplus \texttt{02}\cdot\texttt{53} \oplus \texttt{03}\cdot\texttt{45} = \texttt{db}\oplus\texttt{13}\oplus\texttt{a6}\oplus\texttt{cf} = \texttt{a1}$.
• $s_3' = \texttt{03}\cdot\texttt{db} \oplus \texttt{13} \oplus \texttt{53} \oplus \texttt{02}\cdot\texttt{45} = \texttt{76}\oplus\texttt{13}\oplus\texttt{53}\oplus\texttt{8a} = \texttt{bc}$.

Resultado: $(\texttt{db},\texttt{13},\texttt{53},\texttt{45}) \mapsto (\texttt{8e},\texttt{4d},\texttt{a1},\texttt{bc})$, que es el ejemplo de FIPS 197.

MixColumns es un código MDS

Repaso Si no has hecho el curso de códigos

Un código de longitud 8 y dimensión 4 sobre $\mathbb{F}_{2^8}$ es un conjunto de palabras de 8 bytes que se construyen a partir de 4 bytes libres. Aquí la palabra es $(a, Ma)$. Su distancia mínima es el menor número de bytes no nulos de una palabra no nula. Ningún código así puede tener distancia mayor que $8-4+1 = 5$ (cota de Singleton), y los que la alcanzan se llaman MDS. Un menor de $M$ es el determinante de una submatriz cuadrada que se obtiene quedándose con algunas filas y otras tantas columnas.

Un cambio en un solo byte de la columna ¿a cuántos bytes de salida llega? Con el byte $(\texttt{01},\texttt{00},\texttt{00},\texttt{00})$ la salida es $(\texttt{02},\texttt{01},\texttt{01},\texttt{03})$: llega a los cuatro. Y con dos bytes distintos de cero, por ejemplo $(\texttt{01},\texttt{01},\texttt{00},\texttt{00})$, la salida es $(\texttt{01},\texttt{03},\texttt{00},\texttt{02})$: llega a tres, que sumados a los dos de entrada hacen cinco bytes distintos de cero. Siempre se cumple:

$$\mathrm{wt}(a) + \mathrm{wt}(Ma) \ge 5 \quad \text{para toda columna } a \ne 0,$$

donde $\mathrm{wt}$ es el número de bytes no nulos. Ese mínimo se llama branch number de MixColumns, y vale 5. Es el máximo posible para una matriz $4\times 4$.

La razón está en la lección de códigos de Reed-Solomon. Mira las palabras $(a, Ma)$ de ocho bytes: forman un código sobre $\mathbb{F}_{2^8}$ de longitud $8$ y dimensión $4$. Su distancia mínima es justo el mínimo de $\mathrm{wt}(a)+\mathrm{wt}(Ma)$, es decir, el branch number. Y un código cuyas palabras son $(a, Aa)$ es MDS (alcanza la cota de Singleton $d = n-k+1$ de la lección sobre errores y borrones) si y solo si todos los menores cuadrados de $A$ son distintos de cero. Aquí $n-k+1 = 8-4+1 = 5$.

Lo hemos comprobado con un programa: los $16 + 36 + 16 + 1 = 69$ menores cuadrados de $M$ (de tamaños $1,2,3$ y $4$) son no nulos en $\mathbb{F}_{2^8}$; en particular $\det M = \texttt{01}$. Así que el código de las palabras $(a, Ma)$ es MDS, con longitud 8, dimensión 4 y distancia 5 (un código $[8,4,5]$) sobre $\mathbb{F}_{2^8}$, como los Reed-Solomon, y su branch number es 5. Daemen y Rijmen, los autores de Rijndael, eligieron esta matriz precisamente por eso: en su estrategia de la huella ancha (wide trail strategy) necesitan que la difusión sea la mayor posible, y un código MDS la da. Ojo con el «como»: comparte con los Reed-Solomon la propiedad MDS, pero no es un código de Reed-Solomon, ni siquiera en su versión generalizada. Una forma de verlo: si multiplicas sus palabras coordenada a coordenada, los productos generan un espacio de dimensión 8, y con cualquier Reed-Solomon (generalizado) de longitud 8 y dimensión 4 solo llegan a dimensión $2\cdot 4-1 = 7$ (lo hemos comprobado con un programa). Otra diferencia es el uso: allí la redundancia sirve para recuperar bytes perdidos, y aquí, para que un cambio local se extienda a toda la columna.

Ejemplo resuelto: la ronda 1 entera

Retomamos el ejemplo de FIPS 197 de la lección anterior. El estado al inicio de la ronda 1 (tras el primer AddRoundKey) es

$$\begin{pmatrix} \texttt{19}&\texttt{a0}&\texttt{9a}&\texttt{e9}\\ \texttt{3d}&\texttt{f4}&\texttt{c6}&\texttt{f8}\\ \texttt{e3}&\texttt{e2}&\texttt{8d}&\texttt{48}\\ \texttt{be}&\texttt{2b}&\texttt{2a}&\texttt{08} \end{pmatrix}.$$

SubBytes. Cada byte pasa por $S$. Los valores salen de la tabla 4 de FIPS 197; para este ejemplo te bastan estos 16:

columna	SubBytes
0	$\texttt{19}\mapsto\texttt{d4}$, $\texttt{3d}\mapsto\texttt{27}$, $\texttt{e3}\mapsto\texttt{11}$, $\texttt{be}\mapsto\texttt{ae}$
1	$\texttt{a0}\mapsto\texttt{e0}$, $\texttt{f4}\mapsto\texttt{bf}$, $\texttt{e2}\mapsto\texttt{98}$, $\texttt{2b}\mapsto\texttt{f1}$
2	$\texttt{9a}\mapsto\texttt{b8}$, $\texttt{c6}\mapsto\texttt{b4}$, $\texttt{8d}\mapsto\texttt{5d}$, $\texttt{2a}\mapsto\texttt{e5}$
3	$\texttt{e9}\mapsto\texttt{1e}$, $\texttt{f8}\mapsto\texttt{41}$, $\texttt{48}\mapsto\texttt{52}$, $\texttt{08}\mapsto\texttt{30}$

Sale

$$\begin{pmatrix} \texttt{d4}&\texttt{e0}&\texttt{b8}&\texttt{1e}\\ \texttt{27}&\texttt{bf}&\texttt{b4}&\texttt{41}\\ \texttt{11}&\texttt{98}&\texttt{5d}&\texttt{52}\\ \texttt{ae}&\texttt{f1}&\texttt{e5}&\texttt{30} \end{pmatrix}.$$

ShiftRows. La fila 1 se rota una posición, la 2 dos y la 3 tres:

$$\begin{pmatrix} \texttt{d4}&\texttt{e0}&\texttt{b8}&\texttt{1e}\\ \texttt{bf}&\texttt{b4}&\texttt{41}&\texttt{27}\\ \texttt{5d}&\texttt{52}&\texttt{11}&\texttt{98}\\ \texttt{30}&\texttt{ae}&\texttt{f1}&\texttt{e5} \end{pmatrix}.$$

MixColumns. Cada columna se multiplica por $M$. La primera, $(\texttt{d4},\texttt{bf},\texttt{5d},\texttt{30})$, da $(\texttt{04},\texttt{66},\texttt{81},\texttt{e5})$. Por ejemplo, $\texttt{02}\cdot\texttt{d4} = \texttt{b3}$ y $\texttt{03}\cdot\texttt{bf} = \texttt{da}$. El estado completo es

$$\begin{pmatrix} \texttt{04}&\texttt{e0}&\texttt{48}&\texttt{28}\\ \texttt{66}&\texttt{cb}&\texttt{f8}&\texttt{06}\\ \texttt{81}&\texttt{19}&\texttt{d3}&\texttt{26}\\ \texttt{e5}&\texttt{9a}&\texttt{7a}&\texttt{4c} \end{pmatrix}.$$

AddRoundKey. Se hace XOR con la clave de ronda 1 (la calcularemos en la lección siguiente):

$$\begin{pmatrix} \texttt{04}&\texttt{e0}&\texttt{48}&\texttt{28}\\ \texttt{66}&\texttt{cb}&\texttt{f8}&\texttt{06}\\ \texttt{81}&\texttt{19}&\texttt{d3}&\texttt{26}\\ \texttt{e5}&\texttt{9a}&\texttt{7a}&\texttt{4c} \end{pmatrix} \oplus \begin{pmatrix} \texttt{a0}&\texttt{88}&\texttt{23}&\texttt{2a}\\ \texttt{fa}&\texttt{54}&\texttt{a3}&\texttt{6c}\\ \texttt{fe}&\texttt{2c}&\texttt{39}&\texttt{76}\\ \texttt{17}&\texttt{b1}&\texttt{39}&\texttt{05} \end{pmatrix} = \begin{pmatrix} \texttt{a4}&\texttt{68}&\texttt{6b}&\texttt{02}\\ \texttt{9c}&\texttt{9f}&\texttt{5b}&\texttt{6a}\\ \texttt{7f}&\texttt{35}&\texttt{ea}&\texttt{50}\\ \texttt{f2}&\texttt{2b}&\texttt{43}&\texttt{49} \end{pmatrix}.$$

Esa es la entrada de la ronda 2. En una sola ronda ya se ve la difusión: cada byte de la primera columna del resultado depende de cuatro bytes del estado inicial, que venían de cuatro columnas distintas.

Ejercicios

Ejercicio 1

Calcula $S(\texttt{01})$ con la definición (inverso y transformación afín).

Ver la solución

El inverso de $\texttt{01}$ es $\texttt{01}$ (el uno del cuerpo). Sus bits son $b_0 = 1$ y los demás $0$. En $b_i' = b_i \oplus b_{i+4} \oplus b_{i+5} \oplus b_{i+6} \oplus b_{i+7} \oplus c_i$ el único bit que vale 1 es $b_0$, que aparece en los índices $i$ con $i \in \{0, 4, 3, 2, 1\}$ (porque $i+4$, $i+5$, $i+6$ o $i+7$ valen $0$ módulo 8 cuando $i = 4,3,2,1$). Así que la parte lineal da $b_4'\dots b_0' = 11111$, es decir, $\texttt{1f}$. Sumamos la constante: $\texttt{1f}\oplus\texttt{63} = \texttt{7c}$. Por tanto $S(\texttt{01}) = \texttt{7c}$.

Ejercicio 2

Aplica ShiftRows al estado

$$\begin{pmatrix} \texttt{00}&\texttt{01}&\texttt{02}&\texttt{03}\\ \texttt{10}&\texttt{11}&\texttt{12}&\texttt{13}\\ \texttt{20}&\texttt{21}&\texttt{22}&\texttt{23}\\ \texttt{30}&\texttt{31}&\texttt{32}&\texttt{33} \end{pmatrix}.$$

Ver la solución

La fila 0 se queda igual. La fila 1, $(\texttt{10},\texttt{11},\texttt{12},\texttt{13})$, rota una posición a la izquierda: $(\texttt{11},\texttt{12},\texttt{13},\texttt{10})$. La fila 2 rota dos: $(\texttt{22},\texttt{23},\texttt{20},\texttt{21})$. La fila 3 rota tres: $(\texttt{33},\texttt{30},\texttt{31},\texttt{32})$.

$$\begin{pmatrix} \texttt{00}&\texttt{01}&\texttt{02}&\texttt{03}\\ \texttt{11}&\texttt{12}&\texttt{13}&\texttt{10}\\ \texttt{22}&\texttt{23}&\texttt{20}&\texttt{21}\\ \texttt{33}&\texttt{30}&\texttt{31}&\texttt{32} \end{pmatrix}$$

Los bytes de la primera columna, $\texttt{00},\texttt{11},\texttt{22},\texttt{33}$, proceden de las cuatro columnas de la entrada.

Ejercicio 3

Calcula MixColumns de las columnas $(\texttt{01},\texttt{00},\texttt{01},\texttt{00})$ y $(\texttt{00},\texttt{00},\texttt{01},\texttt{01})$ y halla en cada caso $\mathrm{wt}(a)+\mathrm{wt}(Ma)$. ¿Qué te dice sobre el branch number?

Ver la solución

Con $a = (\texttt{01},\texttt{00},\texttt{01},\texttt{00})$, $Ma$ es la suma de las columnas primera y tercera de $M$: $(\texttt{02}\oplus\texttt{01},\ \texttt{01}\oplus\texttt{03},\ \texttt{01}\oplus\texttt{02},\ \texttt{03}\oplus\texttt{01}) = (\texttt{03},\texttt{02},\texttt{03},\texttt{02})$. Pesos: $2 + 4 = 6$.

Con $a = (\texttt{00},\texttt{00},\texttt{01},\texttt{01})$, $Ma$ es la suma de las columnas tercera y cuarta: $(\texttt{01}\oplus\texttt{01},\ \texttt{03}\oplus\texttt{01},\ \texttt{02}\oplus\texttt{03},\ \texttt{01}\oplus\texttt{02}) = (\texttt{00},\texttt{02},\texttt{01},\texttt{03})$. Pesos: $2 + 3 = 5$.

La suma nunca baja de 5, pero puede ser mayor: aquí sale 6 en un caso y 5 en el otro. El branch number es un mínimo sobre todas las columnas no nulas, no el valor de cada una. Con las dos columnas del texto, $(\texttt{01},\texttt{00},\texttt{00},\texttt{00})$ y $(\texttt{01},\texttt{01},\texttt{00},\texttt{00})$, se alcanza exactamente 5, y por eso el mínimo es 5 y no más.

En resumen

• SubBytes es el inverso en $\mathbb{F}_{2^8}$ seguido de una transformación afín con la constante $\texttt{63}$: es la única parte no lineal de AES.
• ShiftRows rota la fila $r$ del estado $r$ posiciones a la izquierda, y mezcla las columnas entre sí.
• MixColumns multiplica cada columna por una matriz circulante con $\texttt{02},\texttt{03},\texttt{01},\texttt{01}$, operando en $\mathbb{F}_{2^8}$.
• La matriz de MixColumns genera, con $I_4$, un código MDS $[8,4,5]$ sobre $\mathbb{F}_{2^8}$: su branch number es 5, el máximo posible, y de ahí sale la difusión (Daemen y Rijmen).
• Una ronda es SubBytes, ShiftRows, MixColumns y AddRoundKey; solo falta saber de dónde salen las claves de ronda.

Siguiente lección: La expansión de clave y el descifrado de AES