AES visto desde arriba: bloques, rondas y estado

En la lección anterior aprendimos a sumar, multiplicar y dividir bytes como elementos de un cuerpo de 256 elementos. Ahora toca ver para qué sirve. El relato sigue así: DES cayó por su clave de 56 bits, y hacía falta un sustituto. En esta lección ves cómo se eligió, qué forma tiene y cómo se organiza por dentro, sin entrar todavía en el detalle de cada operación (eso será en las lecciones 11 y 12). Y al final hacemos la primera cuenta real del ejemplo que usaremos hasta el final del curso.

La idea

AES, el Advanced Encryption Standard, es un cifrado de bloque. Coge un bloque de 16 bytes (128 bits) y una clave, y devuelve otro bloque de 16 bytes. Es una red de sustitución-permutación (SPN, como la que ya esbozamos en la lección 3), y no una red de Feistel como DES. Eso tiene una consecuencia: en cada ronda se transforman todos los bytes del bloque, no solo una mitad. Como no hay mitades, cada paso tiene que poder invertirse por sí mismo (no vale la trampa de Feistel de la lección 4).

El cifrado trabaja con un estado de $4\times 4$ bytes y repite unas pocas operaciones sencillas, todas basadas en la aritmética del cuerpo de 256 elementos y en XOR.

Cómo se eligió

Los datos siguientes son los de la página de NIST sobre el desarrollo de AES y los de FIPS 197.

• El 2 de enero de 1997 NIST anunció que empezaba el proceso para elegir un nuevo estándar, abierto al público.
• El 20 de agosto de 1998 anunció quince algoritmos candidatos.
• Cinco pasaron a la final: MARS, RC6, Rijndael, Serpent y Twofish.
• El 2 de octubre de 2000 NIST anunció que había elegido Rijndael para proponerlo como AES. FIPS 197 cita como autores del algoritmo a Joan Daemen y Vincent Rijmen.
• AES se publicó como FIPS 197 el 26 de noviembre de 2001. El estándar se actualizó el 9 de mayo de 2023.

Lo notable es el método: cualquiera podía proponer un cifrado y cualquiera podía atacar los propuestos, durante años y a la vista de todos. Con DES no fue así del todo: también salió de una convocatoria pública, pero su diseño se hizo en IBM con la participación de la NSA, y los criterios de las cajas S no se publicaron hasta 1994 (lección 5). Lo de AES fue una aplicación a gran escala del principio de Kerckhoffs de la lección 1.

Parámetros

FIPS 197 define tres variantes, que comparten el tamaño de bloque y se diferencian en la clave:

Variante	Clave	Bloque	Rondas $N_r$
AES-128	128 bits	128 bits	10
AES-192	192 bits	128 bits	12
AES-256	256 bits	128 bits	14

El bloque es siempre de 128 bits: $2^{128} \approx 3{,}4\cdot 10^{38}$ valores posibles, frente a los $2^{64}$ de DES. Hay $2^{128}$, $2^{192}$ y $2^{256}$ claves, es decir, unas $3{,}4\cdot 10^{38}$, $6{,}3\cdot 10^{57}$ y $1{,}2\cdot 10^{77}$. En esta lección y las siguientes usamos AES-128, con 10 rondas.

El estado

Los 16 bytes del bloque, $b_0, b_1, \dots, b_{15}$, se colocan en una matriz $4\times 4$ llamada estado, rellenándola por columnas: los bytes $b_0,b_1,b_2,b_3$ forman la primera columna, $b_4,\dots,b_7$ la segunda, y así. El byte $b_i$ queda en la fila $i \bmod 4$ y la columna $\lfloor i/4 \rfloor$ (contando desde 0). Es la costumbre contraria a la de leer un texto por filas, y conviene fijarse bien: casi todos los errores al hacer AES a mano vienen de aquí.

Por ejemplo, el byte 6 va a la fila 2 y la columna 1. Y los bytes $\texttt{00}, \texttt{01}, \dots, \texttt{0f}$ quedan así:

$$\begin{pmatrix}\texttt{00} & \texttt{04} & \texttt{08} & \texttt{0c}\\ \texttt{01} & \texttt{05} & \texttt{09} & \texttt{0d}\\ \texttt{02} & \texttt{06} & \texttt{0a} & \texttt{0e}\\ \texttt{03} & \texttt{07} & \texttt{0b} & \texttt{0f}\end{pmatrix}$$

Cada columna es una «palabra» de 4 bytes (32 bits). La clave se organiza igual: una clave de 128 bits son 4 palabras.

Las cuatro operaciones

Cada ronda combina cuatro operaciones sobre el estado. En una frase:

• SubBytes: sustituye cada byte por otro mediante una tabla fija de 256 entradas (la caja S de AES), que se construye con el inverso en el cuerpo de la lección 9. Aporta la confusión y la no linealidad.
• ShiftRows: rota cada fila del estado hacia la izquierda un número fijo de posiciones (la fila 0 no se mueve, la 1 una posición, la 2 dos y la 3 tres), para que los bytes de una columna pasen a columnas distintas.
• MixColumns: multiplica cada columna por una matriz fija con elementos del cuerpo, de modo que cada byte de salida depende de los cuatro bytes de la columna. Junto con ShiftRows aporta la difusión.
• AddRoundKey: suma (XOR) al estado la clave de ronda, una por ronda, derivada de la clave principal. Es la única operación que usa la clave.

Las tres primeras son públicas y no dependen de la clave. La seguridad viene de alternarlas con AddRoundKey ronda tras ronda. Las veremos con cuentas en la lección 11 (las tres primeras) y 12 (cómo se obtienen las claves de ronda).

La estructura completa

Con $N_r$ rondas (10 en AES-128), el cifrado hace esto:

1. AddRoundKey con la clave de ronda 0 (la propia clave).
2. Rondas 1 a $N_r - 1$ (9 rondas en AES-128): SubBytes, ShiftRows, MixColumns, AddRoundKey.
3. Ronda final ($N_r$): SubBytes, ShiftRows, AddRoundKey. Sin MixColumns.

Es decir, $N_r + 1 = 11$ claves de ronda (una por cada AddRoundKey), 10 SubBytes, 10 ShiftRows y solo 9 MixColumns. En AES-128 esas 11 claves de ronda ocupan $11 \cdot 16 = 176$ bytes, y salen de la clave de 16 bytes con la expansión de clave de la lección 12.

¿Por qué empieza y termina con una suma de clave? Porque las otras tres operaciones no usan la clave: si el cifrado empezara por SubBytes y acabara con MixColumns, Eva podría deshacer esas capas sin conocer nada secreto. Por una razón parecida sobra un MixColumns en la última ronda. Como es lineal, $\mathrm{MC}(s)\oplus k = \mathrm{MC}(s\oplus k')$ con $k' = \mathrm{MC}^{-1}(k)$: se puede «sacar» por fuera de la última suma de clave, y Eva lo desharía sin saber nada. No aportaría seguridad, y por eso se omite.

Descifrar es aplicar las operaciones inversas, en orden inverso. Cada operación es invertible por sí misma (AddRoundKey es su propia inversa, por la propiedad $a \oplus k \oplus k = a$ de la lección 2). Lo vemos en la lección 12.

Ejemplo resuelto

Usamos el ejemplo del apéndice B de FIPS 197. La clave es

$$k = \texttt{2b7e151628aed2a6abf7158809cf4f3c}$$

y el bloque de entrada, también de 16 bytes, es

$$m = \texttt{3243f6a8885a308d313198a2e0370734}.$$

(Veremos que el criptograma es $c = \texttt{3925841d02dc09fbdc118597196a0b32}$.)

Paso 1: colocar la entrada en el estado, por columnas. Los bytes son, en orden, $\texttt{32}, \texttt{43}, \texttt{f6}, \texttt{a8}$ (primera columna), $\texttt{88}, \texttt{5a}, \texttt{30}, \texttt{8d}$ (segunda), $\texttt{31}, \texttt{31}, \texttt{98}, \texttt{a2}$ (tercera) y $\texttt{e0}, \texttt{37}, \texttt{07}, \texttt{34}$ (cuarta):

$$\begin{pmatrix}\texttt{32} & \texttt{88} & \texttt{31} & \texttt{e0}\\ \texttt{43} & \texttt{5a} & \texttt{31} & \texttt{37}\\ \texttt{f6} & \texttt{30} & \texttt{98} & \texttt{07}\\ \texttt{a8} & \texttt{8d} & \texttt{a2} & \texttt{34}\end{pmatrix}$$

Paso 2: la clave de ronda 0, también por columnas. La clave es la clave de ronda 0, con el mismo reparto: columnas $\texttt{2b7e1516}$, $\texttt{28aed2a6}$, $\texttt{abf71588}$ y $\texttt{09cf4f3c}$.

$$\begin{pmatrix}\texttt{2b} & \texttt{28} & \texttt{ab} & \texttt{09}\\ \texttt{7e} & \texttt{ae} & \texttt{f7} & \texttt{cf}\\ \texttt{15} & \texttt{d2} & \texttt{15} & \texttt{4f}\\ \texttt{16} & \texttt{a6} & \texttt{88} & \texttt{3c}\end{pmatrix}$$

Paso 3: XOR byte a byte. Primero el byte de la esquina: $\texttt{32} \oplus \texttt{2b}$ es, en binario, $00110010 \oplus 00101011 = 00011001$, que es $\texttt{19}$. Hacemos igual con cada columna:

columna	entrada	clave	XOR
0	$\texttt{3243f6a8}$	$\texttt{2b7e1516}$	$\texttt{193de3be}$
1	$\texttt{885a308d}$	$\texttt{28aed2a6}$	$\texttt{a0f4e22b}$
2	$\texttt{313198a2}$	$\texttt{abf71588}$	$\texttt{9ac68d2a}$
3	$\texttt{e0370734}$	$\texttt{09cf4f3c}$	$\texttt{e9f84808}$

El estado tras el AddRoundKey inicial 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}$$

Este es el estado con el que empieza la ronda 1. Para anticipar la lección siguiente: SubBytes sustituirá cada byte por otro; en la primera columna, $\texttt{19}, \texttt{3d}, \texttt{e3}, \texttt{be}$ se convierten en $\texttt{d4}, \texttt{27}, \texttt{11}, \texttt{ae}$.

Ejercicios

Ejercicio 1

¿Cuántos AddRoundKey, SubBytes y MixColumns hace AES-256 al cifrar un bloque? ¿Cuántos bytes ocupan en total sus claves de ronda?

Ver la solución

AES-256 tiene $N_r = 14$ rondas. Hay un AddRoundKey inicial y uno por ronda: $14 + 1 = 15$. SubBytes se hace en cada ronda, incluida la última: 14. MixColumns se hace en todas menos la última: $14 - 1 = 13$. Las 15 claves de ronda de 16 bytes ocupan $15 \cdot 16 = 240$ bytes.

Ejercicio 2

Un bloque tiene los bytes $\texttt{00}, \texttt{11}, \texttt{22}, \texttt{33}, \dots, \texttt{ee}, \texttt{ff}$ (cada byte repite un dígito hexadecimal, del 0 a la f) y la clave son los bytes $\texttt{00}, \texttt{01}, \texttt{02}, \dots, \texttt{0f}$. ¿En qué fila y columna del estado queda el byte $\texttt{66}$? Escribe el estado de entrada, el de la clave y el resultado del primer AddRoundKey.

Ver la solución

El byte $\texttt{66}$ es el séptimo del bloque (el índice empieza en 0), así que es el byte 6: fila $6 \bmod 4 = 2$, columna $\lfloor 6/4\rfloor = 1$, contando desde 0.

Estado de entrada, por columnas:

$$\begin{pmatrix}\texttt{00} & \texttt{44} & \texttt{88} & \texttt{cc}\\ \texttt{11} & \texttt{55} & \texttt{99} & \texttt{dd}\\ \texttt{22} & \texttt{66} & \texttt{aa} & \texttt{ee}\\ \texttt{33} & \texttt{77} & \texttt{bb} & \texttt{ff}\end{pmatrix}$$

Clave:

$$\begin{pmatrix}\texttt{00} & \texttt{04} & \texttt{08} & \texttt{0c}\\ \texttt{01} & \texttt{05} & \texttt{09} & \texttt{0d}\\ \texttt{02} & \texttt{06} & \texttt{0a} & \texttt{0e}\\ \texttt{03} & \texttt{07} & \texttt{0b} & \texttt{0f}\end{pmatrix}$$

XOR byte a byte (por ejemplo, $\texttt{44} \oplus \texttt{04} = \texttt{40}$ y $\texttt{11} \oplus \texttt{01} = \texttt{10}$):

$$\begin{pmatrix}\texttt{00} & \texttt{40} & \texttt{80} & \texttt{c0}\\ \texttt{10} & \texttt{50} & \texttt{90} & \texttt{d0}\\ \texttt{20} & \texttt{60} & \texttt{a0} & \texttt{e0}\\ \texttt{30} & \texttt{70} & \texttt{b0} & \texttt{f0}\end{pmatrix}$$

Leído por columnas, el bloque resultante es

$$\texttt{00102030\,40506070\,8090a0b0\,c0d0e0f0}.$$

Ejercicio 3

Explica por qué AddRoundKey es su propia inversa, y por qué una cadena de «SubBytes, ShiftRows, MixColumns» sin AddRoundKey no daría un cifrado seguro aunque se repitiera mil veces.

Ver la solución

Si $s' = s \oplus k$, entonces $s' \oplus k = s \oplus k \oplus k = s$, porque $k \oplus k$ es cero. Aplicar AddRoundKey con la misma clave de ronda deshace la operación.

Las otras tres operaciones no dependen de la clave, son públicas (principio de Kerckhoffs) y cualquiera puede calcularlas y deshacerlas. Repetirlas mil veces da una transformación del bloque que también es pública. Eva la invertiría sin saber nada secreto. El secreto solo entra con AddRoundKey.

En resumen

• AES se eligió en un concurso público de NIST (1997-2000): 15 candidatos, 5 finalistas (MARS, RC6, Rijndael, Serpent, Twofish) y Rijndael, de Daemen y Rijmen. Se publicó como FIPS 197 en 2001 y se actualizó en 2023.
• Bloque de 128 bits; claves de 128, 192 o 256 bits con 10, 12 o 14 rondas.
• El estado es una matriz $4\times 4$ de bytes que se rellena por columnas.
• Una ronda es SubBytes, ShiftRows, MixColumns y AddRoundKey; el cifrado empieza con un AddRoundKey y la última ronda omite MixColumns.
• Es una red de sustitución-permutación, no de Feistel. Con la clave y la entrada de FIPS 197, el AddRoundKey inicial da el estado que empieza por $\texttt{19}\ \texttt{a0}\ \texttt{9a}\ \texttt{e9}$.

Siguiente lección: SubBytes, ShiftRows y MixColumns