La expansión de clave y el descifrado de AES

En la lección anterior desmontamos una ronda de AES, y en la última cuenta usamos «la clave de ronda 1» sin decir de dónde sale. Hoy cerramos el diseño de AES: cómo se fabrican las once claves de ronda a partir de los 16 bytes de la clave, cómo se descifra, y qué se sabe de los intentos de romperlo. Seguimos en el punto del relato en que AES ya ha sustituido a DES, y quedan por delante los modos de operación.

La idea

AES-128 hace un AddRoundKey antes de la primera ronda y uno al final de cada una de las diez rondas: necesita 11 claves de ronda de 16 bytes, 176 bytes en total. Alicia y Bernardo comparten solo 16. La expansión de clave estira esos 16 bytes hasta 176 con un procedimiento público y sin secretos: lo único secreto es la clave.

Para que la expansión sirva, debe cumplir dos cosas. Cada byte de la clave debe influir en muchas claves de ronda, y las claves de ronda no deben ser fáciles de relacionar entre sí. Lo primero se consigue encadenando las palabras; lo segundo, metiendo de vez en cuando una caja S y una constante distinta en cada ronda.

Descifrar es la otra mitad: como cada operación de AES es invertible, se deshace una a una en orden inverso, y las claves de ronda se usan al revés. La diferencia con DES es que aquí no hay truco de Feistel: hay que construir de verdad las operaciones inversas.

La expansión de clave

Una palabra es una cadena de 4 bytes. La clave de 16 bytes son las cuatro primeras palabras $w_0, w_1, w_2, w_3$ (los bytes $0$ a $3$ forman $w_0$, y así sucesivamente). Las demás, hasta $w_{43}$, se calculan con la regla

$$w_i = w_{i-4} \oplus \text{temp}, \qquad \text{temp} = \begin{cases} \mathrm{SubWord}(\mathrm{RotWord}(w_{i-1})) \oplus \mathrm{Rcon}_{i/4} & \text{si } i \text{ es múltiplo de } 4,\\ w_{i-1} & \text{en otro caso.} \end{cases}$$

• $\mathrm{RotWord}$ rota la palabra un byte a la izquierda: $(a_0,a_1,a_2,a_3)\mapsto(a_1,a_2,a_3,a_0)$.
• $\mathrm{SubWord}$ aplica la caja S de SubBytes a cada uno de los cuatro bytes.
• $\mathrm{Rcon}_j$ es la palabra $(\texttt{rc}_j, \texttt{00}, \texttt{00}, \texttt{00})$, con $\texttt{rc}_j$ la constante de la ronda $j$.

La clave de ronda $r$ son las palabras $w_{4r}, w_{4r+1}, w_{4r+2}, w_{4r+3}$, colocadas como columnas de una matriz $4\times 4$, igual que el estado.

Las constantes. Los bytes $\texttt{rc}_1,\dots,\texttt{rc}_{10}$ son las potencias $x^0, x^1, \dots, x^9$ en $\mathbb{F}_{2^8}$. Se obtienen multiplicando por $\texttt{02}$ (xtime) cada vez:

$j$	1	2	3	4	5	6	7	8	9	10
$\texttt{rc}_j$	$\texttt{01}$	$\texttt{02}$	$\texttt{04}$	$\texttt{08}$	$\texttt{10}$	$\texttt{20}$	$\texttt{40}$	$\texttt{80}$	$\texttt{1b}$	$\texttt{36}$

Hasta $\texttt{80}$ es solo desplazar. Luego, $x^8 = x^4+x^3+x+1 = \texttt{1b}$ por el polinomio con el que se construye el cuerpo, y $x^9 = \texttt{1b}\cdot\texttt{02} = \texttt{36}$. Para qué sirven: sin ellas, las cuatro palabras de cada bloque se calcularían de la misma forma en todas las rondas, y la expansión tendría simetrías que un atacante podría aprovechar. Con una constante distinta por ronda se rompe esa simetría.

Ejemplo resuelto: de $w_0,\dots,w_3$ a la clave de la ronda 1

Usamos la clave del ejemplo de FIPS 197:

$$\begin{gathered} w_0 = \texttt{2b7e1516},\quad w_1 = \texttt{28aed2a6},\\ w_2 = \texttt{abf71588},\quad w_3 = \texttt{09cf4f3c}. \end{gathered}$$

$w_4$ ($i=4$ es múltiplo de 4). Partimos de $w_3 = \texttt{09cf4f3c}$.

1. $\mathrm{RotWord}$: $\texttt{cf4f3c09}$.
2. $\mathrm{SubWord}$ (con la tabla de la caja S de FIPS 197, §5.1.1): $S(\texttt{cf})=\texttt{8a}$, $S(\texttt{4f})=\texttt{84}$, $S(\texttt{3c})=\texttt{eb}$, $S(\texttt{09})=\texttt{01}$, luego $\texttt{8a84eb01}$.
3. XOR con $\mathrm{Rcon}_1 = \texttt{01000000}$: $\texttt{8b84eb01}$.
4. $w_4 = w_0 \oplus \texttt{8b84eb01} = \texttt{2b7e1516}\oplus\texttt{8b84eb01} = \texttt{a0fafe17}$.

$w_5, w_6, w_7$. Ya no hay caja S, solo XOR con la palabra anterior:

• $w_5 = w_1 \oplus w_4 = \texttt{28aed2a6}\oplus\texttt{a0fafe17} = \texttt{88542cb1}$.
• $w_6 = w_2 \oplus w_5 = \texttt{abf71588}\oplus\texttt{88542cb1} = \texttt{23a33939}$.
• $w_7 = w_3 \oplus w_6 = \texttt{09cf4f3c}\oplus\texttt{23a33939} = \texttt{2a6c7605}$.

La clave de la ronda 1 es $w_4w_5w_6w_7$, la matriz con esas palabras como columnas, que ya usamos en la lección anterior:

$$\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}.$$

Siguiendo igual hasta $w_{43} = \texttt{b6630ca6}$ se llega a la clave de la ronda 10, $w_{40}w_{41}w_{42}w_{43}$:

$$\texttt{d014f9a8}\ \texttt{c9ee2589}\ \texttt{e13f0cc8}\ \texttt{b6630ca6}.$$

Las diez rondas del ejemplo

Con las claves de ronda, cifrar el bloque del ejemplo de FIPS 197,

$$\texttt{3243f6a8}\ \texttt{885a308d}\ \texttt{313198a2}\ \texttt{e0370734},$$

es repetir lo que ya sabes. Esta tabla da el estado al inicio de cada ronda (el de la ronda 1 es el bloque más la clave de la ronda 0). Cada estado se lista como los 16 bytes en el orden del bloque, es decir, columna a columna (cada grupo de 8 dígitos es una columna).

Ronda	Estado al inicio de la ronda
1	$\texttt{193de3be}\ \texttt{a0f4e22b}\ \texttt{9ac68d2a}\ \texttt{e9f84808}$
2	$\texttt{a49c7ff2}\ \texttt{689f352b}\ \texttt{6b5bea43}\ \texttt{026a5049}$
3	$\texttt{aa8f5f03}\ \texttt{61dde3ef}\ \texttt{82d24ad2}\ \texttt{6832469a}$
4	$\texttt{486c4eee}\ \texttt{671d9d0d}\ \texttt{4de3b138}\ \texttt{d65f58e7}$
5	$\texttt{e0927fe8}\ \texttt{c86363c0}\ \texttt{d9b13550}\ \texttt{85b8be01}$
6	$\texttt{f1006f55}\ \texttt{c1924cef}\ \texttt{7cc88b32}\ \texttt{5db5d50c}$
7	$\texttt{260e2e17}\ \texttt{3d41b77d}\ \texttt{e86472a9}\ \texttt{fdd28b25}$
8	$\texttt{5a4142b1}\ \texttt{1949dc1f}\ \texttt{a3e01965}\ \texttt{7a8c040c}$
9	$\texttt{ea835cf0}\ \texttt{0445332d}\ \texttt{655d98ad}\ \texttt{8596b0c5}$
10	$\texttt{eb40f21e}\ \texttt{592e3884}\ \texttt{8ba113e7}\ \texttt{1bc342d2}$

La ronda 10 no tiene MixColumns, y su salida es el criptograma:

$$c = \texttt{3925841d}\ \texttt{02dc09fb}\ \texttt{dc118597}\ \texttt{196a0b32}.$$

Descifrar: deshacer en orden inverso

Cada operación de la ronda tiene inversa.

• AddRoundKey es su propia inversa: el XOR con la misma clave deshace el XOR.
• InvShiftRows rota la fila $r$ del estado $r$ posiciones a la derecha.
• InvSubBytes aplica la tabla inversa de $S$ (que existe porque $S$ es biyectiva): $S^{-1}(\texttt{ed}) = \texttt{53}$. A mano no se calcula: se lee en la tabla 6 de FIPS 197 (§5.3.2), igual que $S$ se lee en su tabla 4.
• InvMixColumns multiplica cada columna por la matriz inversa de $M$ en $\mathbb{F}_{2^8}$:

$$M^{-1} = \begin{pmatrix} \texttt{0e}&\texttt{0b}&\texttt{0d}&\texttt{09}\\ \texttt{09}&\texttt{0e}&\texttt{0b}&\texttt{0d}\\ \texttt{0d}&\texttt{09}&\texttt{0e}&\texttt{0b}\\ \texttt{0b}&\texttt{0d}&\texttt{09}&\texttt{0e} \end{pmatrix}.$$

Hemos comprobado con un programa que $M\,M^{-1}=I$ en $\mathbb{F}_{2^8}$. Los coeficientes son más «pesados» que $\texttt{01},\texttt{02},\texttt{03}$ (cada uno necesita hasta tres xtime), y por eso el descifrado de AES es algo más costoso que el cifrado.

El descifrado hace, en este orden:

1. AddRoundKey con la clave de la ronda 10.
2. Para $r = 9, 8, \dots, 1$: InvShiftRows, InvSubBytes, AddRoundKey con la clave de la ronda $r$ e InvMixColumns.
3. Última ronda: InvShiftRows, InvSubBytes y AddRoundKey con la clave de la ronda 0.

Las claves de ronda se usan de la 10 a la 0. A diferencia de DES, no basta con invertir el orden de las subclaves: hay que invertir también las operaciones.

Ejemplo resuelto: el primer paso del descifrado

Descifremos $c$ con la clave del ejemplo de FIPS 197. Sumamos la clave de la ronda 10:

$$\begin{pmatrix} \texttt{39}&\texttt{02}&\texttt{dc}&\texttt{19}\\ \texttt{25}&\texttt{dc}&\texttt{11}&\texttt{6a}\\ \texttt{84}&\texttt{09}&\texttt{85}&\texttt{0b}\\ \texttt{1d}&\texttt{fb}&\texttt{97}&\texttt{32} \end{pmatrix} \oplus \begin{pmatrix} \texttt{d0}&\texttt{c9}&\texttt{e1}&\texttt{b6}\\ \texttt{14}&\texttt{ee}&\texttt{3f}&\texttt{63}\\ \texttt{f9}&\texttt{25}&\texttt{0c}&\texttt{0c}\\ \texttt{a8}&\texttt{89}&\texttt{c8}&\texttt{a6} \end{pmatrix} = \begin{pmatrix} \texttt{e9}&\texttt{cb}&\texttt{3d}&\texttt{af}\\ \texttt{31}&\texttt{32}&\texttt{2e}&\texttt{09}\\ \texttt{7d}&\texttt{2c}&\texttt{89}&\texttt{07}\\ \texttt{b5}&\texttt{72}&\texttt{5f}&\texttt{94} \end{pmatrix}.$$

Es el estado tras el ShiftRows de la ronda 10. Ahora InvShiftRows (fila 1 una posición a la derecha, fila 2 dos, fila 3 tres):

$$\begin{pmatrix} \texttt{e9}&\texttt{cb}&\texttt{3d}&\texttt{af}\\ \texttt{09}&\texttt{31}&\texttt{32}&\texttt{2e}\\ \texttt{89}&\texttt{07}&\texttt{7d}&\texttt{2c}\\ \texttt{72}&\texttt{5f}&\texttt{94}&\texttt{b5} \end{pmatrix},$$

y InvSubBytes. Estos son los 16 valores de la tabla inversa que hacen falta, columna a columna:

columna 1	columna 2	columna 3	columna 4
$\texttt{e9}\mapsto\texttt{eb}$	$\texttt{cb}\mapsto\texttt{59}$	$\texttt{3d}\mapsto\texttt{8b}$	$\texttt{af}\mapsto\texttt{1b}$
$\texttt{09}\mapsto\texttt{40}$	$\texttt{31}\mapsto\texttt{2e}$	$\texttt{32}\mapsto\texttt{a1}$	$\texttt{2e}\mapsto\texttt{c3}$
$\texttt{89}\mapsto\texttt{f2}$	$\texttt{07}\mapsto\texttt{38}$	$\texttt{7d}\mapsto\texttt{13}$	$\texttt{2c}\mapsto\texttt{42}$
$\texttt{72}\mapsto\texttt{1e}$	$\texttt{5f}\mapsto\texttt{84}$	$\texttt{94}\mapsto\texttt{e7}$	$\texttt{b5}\mapsto\texttt{d2}$

Queda

$$\begin{pmatrix} \texttt{eb}&\texttt{59}&\texttt{8b}&\texttt{1b}\\ \texttt{40}&\texttt{2e}&\texttt{a1}&\texttt{c3}\\ \texttt{f2}&\texttt{38}&\texttt{13}&\texttt{42}\\ \texttt{1e}&\texttt{84}&\texttt{e7}&\texttt{d2} \end{pmatrix}.$$

Es el estado de la fila 10 de la tabla, $\texttt{eb40f21e}\ \texttt{592e3884}\dots$: la entrada de la ronda 10, recuperada. Seguimos: AddRoundKey con la clave de la ronda 9, $w_{36}w_{37}w_{38}w_{39}$,

$$\texttt{ac7766f3}\ \texttt{19fadc21}\ \texttt{28d12941}\ \texttt{575c006e}$$

(en el ejercicio 2 recuperarás dos de esas palabras), da

$$\begin{pmatrix} \texttt{47}&\texttt{40}&\texttt{a3}&\texttt{4c}\\ \texttt{37}&\texttt{d4}&\texttt{70}&\texttt{9f}\\ \texttt{94}&\texttt{e4}&\texttt{3a}&\texttt{42}\\ \texttt{ed}&\texttt{a5}&\texttt{a6}&\texttt{bc} \end{pmatrix},$$

y falta InvMixColumns. La primera columna $(\texttt{47},\texttt{37},\texttt{94},\texttt{ed})$ da, en su primer byte,

$$\begin{aligned} &\texttt{0e}\cdot\texttt{47}\oplus\texttt{0b}\cdot\texttt{37}\oplus\texttt{0d}\cdot\texttt{94}\oplus\texttt{09}\cdot\texttt{ed}\\ &= \texttt{87}\oplus\texttt{fa}\oplus\texttt{3e}\oplus\texttt{c4} = \texttt{87}. \end{aligned}$$

La columna completa es $(\texttt{87},\texttt{6e},\texttt{46},\texttt{a6})$ y el estado resultante,

$$\begin{pmatrix} \texttt{87}&\texttt{f2}&\texttt{4d}&\texttt{97}\\ \texttt{6e}&\texttt{4c}&\texttt{90}&\texttt{ec}\\ \texttt{46}&\texttt{e7}&\texttt{4a}&\texttt{c3}\\ \texttt{a6}&\texttt{8c}&\texttt{d8}&\texttt{95} \end{pmatrix},$$

es exactamente el que salió de ShiftRows en la ronda 9. Repitiendo el proceso otras ocho veces se llega al bloque original, $\texttt{3243f6a8}\dots$ (lo hemos comprobado con un programa).

¿Se puede romper AES?

Ningún ataque práctico se conoce contra AES completo: nadie ha encontrado una forma de recuperar la clave sustancialmente más rápida que probarlas todas con un coste que se pueda ejecutar. En 2011, Bogdanov, Khovratovich y Rechberger publicaron, según el resumen de su artículo, el primer ataque de recuperación de clave contra AES-128 completo: un ataque de biclique con una complejidad de $2^{126{,}1}$ operaciones. La fuerza bruta cuesta $2^{128}$, así que el ataque es unas $2^{128}/2^{126{,}1}\approx 3{,}7$ veces más rápido: menos de cuatro veces. Pero $2^{126{,}1}$ es todavía del orden de $10^{38}$ operaciones: un ahorro de factor pequeño sobre un número inalcanzable. Es un resultado teórico que mide el margen de seguridad de AES, no una amenaza.

Ejercicios

Ejercicio 1

Comprueba que $\texttt{rc}_9 = \texttt{1b}$ y $\texttt{rc}_{10} = \texttt{36}$ partiendo de $\texttt{rc}_8 = \texttt{80}$, y calcula la constante siguiente, $x^{10}$.

Ver la solución

Multiplicar por $\texttt{02}$ es xtime. Con $\texttt{80} = 10000000$, el desplazamiento a la izquierda se sale del byte (queda $\texttt{00}$ con un bit de desbordamiento), y se hace XOR con $\texttt{1b}$: $\texttt{rc}_9 = \texttt{1b}$. Ahora $\texttt{1b} = 00011011$ se desplaza a $00110110 = \texttt{36}$ sin desbordar, así que $\texttt{rc}_{10} = \texttt{36}$. Una vez más, $\texttt{36} = 00110110$ pasa a $01101100 = \texttt{6c}$, sin desbordar. La constante siguiente es $\texttt{6c}$ (AES-128 no la usa).

Ejercicio 2

La expansión de clave se puede recorrer hacia atrás. Sabiendo $w_{42} = \texttt{e13f0cc8}$, $w_{43} = \texttt{b6630ca6}$ y $w_{40} = \texttt{d014f9a8}$, calcula $w_{39}$ y $w_{36}$. Usa $S(\texttt{5c}) = \texttt{4a}$, $S(\texttt{00}) = \texttt{63}$, $S(\texttt{6e}) = \texttt{9f}$, $S(\texttt{57}) = \texttt{5b}$.

Ver la solución

Como $43$ no es múltiplo de 4, $w_{43} = w_{39}\oplus w_{42}$, y despejamos: $w_{39} = w_{43}\oplus w_{42} = \texttt{b6630ca6}\oplus\texttt{e13f0cc8} = \texttt{575c006e}$.

Para $w_{40}$ sí hay caja S: $w_{40} = w_{36}\oplus\mathrm{SubWord}(\mathrm{RotWord}(w_{39}))\oplus\mathrm{Rcon}_{10}$. Calculamos $\mathrm{RotWord}(\texttt{575c006e}) = \texttt{5c006e57}$, $\mathrm{SubWord} = \texttt{4a639f5b}$ y, con $\mathrm{Rcon}_{10} = \texttt{36000000}$, el XOR da $\texttt{7c639f5b}$. Despejamos: $w_{36} = w_{40}\oplus\texttt{7c639f5b} = \texttt{d014f9a8}\oplus\texttt{7c639f5b} = \texttt{ac7766f3}$.

Conclusión: conocida la clave de la ronda 10, se recupera la clave de cifrado entera. La expansión es invertible, así que robar una clave de ronda equivale a robar la clave.

Ejercicio 3

Calcula el primer byte de InvMixColumns de la columna $(\texttt{47},\texttt{37},\texttt{94},\texttt{ed})$ con todas las cuentas.

Ver la solución

Primer byte: $\texttt{0e}\cdot\texttt{47}\oplus\texttt{0b}\cdot\texttt{37}\oplus\texttt{0d}\cdot\texttt{94}\oplus\texttt{09}\cdot\texttt{ed}$. Como $\texttt{0e}=8+4+2$, $\texttt{0b}=8+2+1$, $\texttt{0d}=8+4+1$ y $\texttt{09}=8+1$ (en el sentido de potencias de $x$), calculamos para cada byte $s$ los valores $\texttt{02}s$, $\texttt{04}s$ y $\texttt{08}s$ con xtime:

$s$	$\texttt{02}s$	$\texttt{04}s$	$\texttt{08}s$
$\texttt{47}$	$\texttt{8e}$	$\texttt{07}$	$\texttt{0e}$
$\texttt{37}$	$\texttt{6e}$	$\texttt{dc}$	$\texttt{a3}$
$\texttt{94}$	$\texttt{33}$	$\texttt{66}$	$\texttt{cc}$
$\texttt{ed}$	$\texttt{c1}$	$\texttt{99}$	$\texttt{29}$

Entonces:

• $\texttt{0e}\cdot\texttt{47} = \texttt{0e}\oplus\texttt{07}\oplus\texttt{8e} = \texttt{87}$.
• $\texttt{0b}\cdot\texttt{37} = \texttt{a3}\oplus\texttt{6e}\oplus\texttt{37} = \texttt{fa}$.
• $\texttt{0d}\cdot\texttt{94} = \texttt{cc}\oplus\texttt{66}\oplus\texttt{94} = \texttt{3e}$.
• $\texttt{09}\cdot\texttt{ed} = \texttt{29}\oplus\texttt{ed} = \texttt{c4}$.

Suma: $\texttt{87}\oplus\texttt{fa}\oplus\texttt{3e}\oplus\texttt{c4} = \texttt{87}$.

En resumen

• La expansión de clave produce $w_0,\dots,w_{43}$: cada palabra es $w_{i-4}\oplus w_{i-1}$, salvo cada cuarta, donde $w_{i-1}$ pasa antes por RotWord, SubWord y un XOR con $\mathrm{Rcon}$.
• Las constantes $\mathrm{Rcon}$ son las potencias $x^0,\dots,x^9$ de $\mathbb{F}_{2^8}$ y hacen distinta cada ronda.
• Descifrar es deshacer cada operación en orden inverso con las claves de la 10 a la 0: InvShiftRows, InvSubBytes e InvMixColumns (con $\texttt{0e},\texttt{0b},\texttt{0d},\texttt{09}$).
• Para el ejemplo de FIPS 197, las diez rondas llevan el bloque $\texttt{3243f6a8…}$ al criptograma $\texttt{3925841d…}$, y el descifrado hace el camino inverso.
• No se conoce ataque práctico contra AES; el primer ataque teórico de recuperación de clave contra AES-128 completo, un biclique (2011), cuesta $2^{126{,}1}$ frente a $2^{128}$.

Siguiente lección: Modos de operación