Modos de operación: de un bloque de 16 bytes a un mensaje entero

En la lección anterior terminamos AES por dentro: sabes cifrar y descifrar un bloque de 16 bytes. Pero casi nada de lo que se cifra en la vida mide 16 bytes: un correo, una foto, una conversación en vivo. Este es el último paso del relato. Partimos de la libreta de un solo uso, perfecta pero con una clave tan larga como el mensaje, y llegamos a un cifrado de bloque con clave corta. Falta la pieza que lo convierte en algo útil: los modos de operación. Y, al final, el modo CTR nos devolverá, de un modo curioso, a la libreta.

La idea

Un cifrado de bloque $E_k$ es una permutación de $\{0,1\}^{128}$ por cada clave $k$. No dice qué hacer con un mensaje de 40 bytes ni con uno de 3. Un modo de operación es una receta que usa $E_k$ como pieza para cifrar mensajes de cualquier longitud. NIST describe cinco en su SP 800-38A (ECB, CBC, CFB, OFB y CTR); aquí veremos tres, más un cuarto que añade autenticación.

Todos los ejemplos usan AES-128 con la clave del hilo, $k$, y el primer bloque de mensaje será $A$, el primer bloque del texto de los ejemplos de SP 800-38A con esta clave:

$$\begin{aligned} k &= \texttt{2b7e1516}\ \texttt{28aed2a6}\ \texttt{abf71588}\ \texttt{09cf4f3c},\\ A &= \texttt{6bc1bee2}\ \texttt{2e409f96}\ \texttt{e93d7e11}\ \texttt{7393172a}. \end{aligned}$$

Relleno: que el mensaje encaje en bloques

Si la longitud del mensaje no es múltiplo de 16 bytes, hay que rellenar. Un esquema muy extendido es el relleno PKCS#7: se añaden $16 - (\text{longitud} \bmod 16)$ bytes, y cada uno vale justo ese número. Así el receptor mira el último byte, sabe cuántos quitar y no hay ambigüedad.

mensaje	bytes	relleno añadido
«HOLA»	4	doce bytes $\texttt{0c}$
20 bytes	20	doce bytes $\texttt{0c}$ (queda en 32)
16 bytes	16	un bloque entero de dieciséis $\texttt{10}$

La última fila sorprende: un mensaje que ya encaja también se rellena. Si no, el receptor no podría distinguir un mensaje que acaba en $\texttt{01}$ de uno rellenado con un byte. El modo CTR, que veremos, no necesita relleno.

ECB: cada bloque por separado

El modo más ingenuo es ECB (electronic codebook): se corta el mensaje en bloques $m_1, m_2, \dots$ y se cifra cada uno con la misma clave:

$$c_i = E_k(m_i).$$

Es simple y descifra bien, pero tiene un fallo de fondo: bloques iguales dan criptogramas iguales. Eva no sabe qué dicen, pero ve dónde se repiten. Con AES y nuestra clave, el mensaje $A\,A$ (dos bloques iguales) se cifra como

$$\texttt{3ad77bb4…ef97}\quad\texttt{3ad77bb4…ef97}.$$

Se ve la repetición a simple vista. En una imagen con zonas de un solo color, o en un fichero con cabeceras repetidas, el patrón del mensaje queda dibujado en el criptograma. Por eso ECB no debe usarse para mensajes de más de un bloque.

CBC: encadenar los bloques

En CBC (cipher block chaining) cada bloque se mezcla con el criptograma anterior antes de cifrar. Para el primero se necesita un bloque inicial, el vector de inicialización (IV), que no es secreto pero debe ser impredecible: por ejemplo, un bloque elegido al azar para cada mensaje (SP 800-38A, apéndice C). En fórmulas:

$$c_0 = \text{IV}, \qquad c_i = E_k(m_i \oplus c_{i-1}).$$

Para descifrar se deshace cada paso: $m_i = D_k(c_i) \oplus c_{i-1}$. Ahora dos bloques iguales del mensaje dan criptogramas distintos, porque el XOR con el bloque anterior cambia la entrada de $E_k$. Y el mismo mensaje cifrado dos veces da criptogramas distintos solo si cambia el IV: con la misma clave y el mismo IV, CBC repite exactamente el mismo criptograma. La contrapartida es que cifrar es secuencial: para el bloque $i$ necesitas el $i-1$. Descifrar, en cambio, sí se puede hacer en paralelo.

Por qué importa el tamaño del bloque. Si en CBC dos bloques de criptograma coinciden, $c_i = c_j$, es que AES recibió dos veces la misma entrada: $m_i\oplus c_{i-1} = m_j\oplus c_{j-1}$. Entonces Eva obtiene $m_i\oplus m_j = c_{i-1}\oplus c_{j-1}$, otra vez el XOR de dos trozos de mensaje sin necesidad de la clave. Los bloques de criptograma se comportan como bloques al azar, y por la paradoja del cumpleaños, con bloques de $n$ bits las coincidencias empiezan a ser probables hacia los $2^{n/2}$ bloques. Con los 64 bits de DES y del Triple DES eso son $2^{32}$ bloques, es decir, 32 GiB: tras cifrarlos con una misma clave, la probabilidad de alguna coincidencia ronda ya el 40 %. De ahí el interés del límite de $2^{20}$ bloques por juego de claves que el NIST fija para el Triple DES (lección 8): son solo 8 MiB, y esa probabilidad baja a unas 3 entre cien millones. Con los 128 bits de AES el umbral sube a $2^{64}$ bloques, muy lejos de cualquier uso real.

CTR: la libreta vuelve

En CTR (counter) no se cifra el mensaje con $E_k$: se cifra un contador, y el resultado se usa como clave de una libreta. Se parte de un bloque inicial $T_1$ y se suman unidades: $T_i = T_1 + (i-1)$, como número de 128 bits. Entonces

$$s_i = E_k(T_i), \qquad c_i = m_i \oplus s_i.$$

Los bloques $s_1, s_2, \dots$ forman una secuencia de clave que se genera con la clave corta $k$. Y cifrar es hacer XOR con ella, igual que en la lección 2 con «HOLA». Descifrar es exactamente la misma operación. Ventajas: no hace falta $D_k$, no hace falta relleno (el último bloque puede ser corto: se usan solo los bytes que haga falta de $s_i$) y todos los bloques se pueden calcular a la vez.

Hay una regla de oro, la misma que en la libreta: nunca repetir un contador con la misma clave. Si dos mensajes usan la misma secuencia $s_i$, entonces $c_i \oplus c'_i = m_i \oplus m'_i$ y la clave desaparece, justo el fallo de «CHAO» en la lección 2. Lo veremos con números en el ejercicio 2.

GCM: cifrar y comprobar que nadie ha tocado nada

A todo lo anterior le falta algo: ninguno de estos modos detecta que alguien haya modificado el criptograma. Hasta ahora Eva solo escuchaba (lección 1). Pero un atacante activo, que además de escuchar puede cambiar bits por el camino, es igual de real: no puede leer el criptograma, pero a veces puede alterarlo con provecho (el ejercicio 3 lo muestra). GCM (Galois/counter mode, NIST SP 800-38D) es un modo de cifrado autenticado: cifra en modo contador y además calcula una etiqueta de autenticación sobre los datos. Si el criptograma o los datos asociados cambian, la etiqueta ya no cuadra y el receptor rechaza el mensaje. El cálculo de la etiqueta usa una multiplicación en un cuerpo finito, $\mathbb{F}_{2^{128}}$: otra vez cuerpos finitos. No entramos en los detalles, que son el tema de otro curso.

Ejemplo resuelto

Ciframos el mensaje de dos bloques iguales $A\,A$ con los tres modos y la clave del hilo (IV y contador elegidos como en SP 800-38A: IV $=\texttt{000102…0f}$ y primer contador $T_1 = \texttt{f0f1f2…ff}$). Mostramos los bytes abreviados.

ECB. $E_k(A) = \texttt{3ad77bb4…ef97}$, dos veces:

bloque	criptograma
$c_1$	$\texttt{3ad77bb4}\ \texttt{0d7a3660}\ \texttt{a89ecaf3}\ \texttt{2466ef97}$
$c_2$	$\texttt{3ad77bb4}\ \texttt{0d7a3660}\ \texttt{a89ecaf3}\ \texttt{2466ef97}$

CBC. El primer bloque entra en AES como $A \oplus \text{IV} = \texttt{6bc0bce1…1925}$, y el segundo como $A \oplus c_1 = \texttt{1d88154e…0e57}$. Salen

$$\begin{aligned} c_1 &= \texttt{7649abac}\ \texttt{8119b246}\ \texttt{cee98e9b}\ \texttt{12e9197d},\\ c_2 &= \texttt{4cbbc858}\ \texttt{756b3581}\ \texttt{25529e96}\ \texttt{98a38f44}. \end{aligned}$$

Los dos criptogramas ya son distintos.

CTR. Cifras dos contadores consecutivos, $T_1 = \texttt{f0f1…feff}$ y $T_2 = \texttt{f0f1…ff00}$ (la unidad se suma como número de 128 bits y hay acarreo):

$$\begin{aligned} s_1 &= E_k(T_1) = \texttt{ec8cdf73}\ \texttt{98607cb0}\ \texttt{f2d21675}\ \texttt{ea9ea1e4},\\ s_2 &= E_k(T_2) = \texttt{362b7c3c}\ \texttt{67735163}\ \texttt{18a077d7}\ \texttt{fc5073ae}. \end{aligned}$$

Después

$$\begin{aligned} c_1 &= A \oplus s_1 = \texttt{874d6191}\ \texttt{b620e326}\ \texttt{1bef6864}\ \texttt{990db6ce},\\ c_2 &= A \oplus s_2 = \texttt{5deac2de}\ \texttt{4933cef5}\ \texttt{f19d09c6}\ \texttt{8fc36484}. \end{aligned}$$

Distintos otra vez, y sin haber usado más que el cifrado.

Todos estos números se han contrastado con una implementación independiente de AES.

Con relleno. El mensaje de 20 bytes «Reunion a las ocho!!» (sin tilde, para que cada carácter sea un byte ASCII: $\texttt{5265756e…6f2121}$) se rellena con doce $\texttt{0c}$ hasta 32 bytes. En CBC con el mismo IV sale

$$\begin{gathered} \texttt{8600dd4a}\ \texttt{38da3ac5}\ \texttt{043980ac}\ \texttt{dbcdfb05}\\ \texttt{8671340d}\ \texttt{a6cd91ee}\ \texttt{efe87b43}\ \texttt{b6042c7b}. \end{gathered}$$

Ejercicios

Ejercicio 1

Rellena con PKCS#7 un mensaje de exactamente 16 bytes. ¿Qué bytes se añaden? ¿Y si el mensaje tiene 31 bytes?

Ver la solución

Con 16 bytes, $16 - (16 \bmod 16) = 16$: se añade un bloque entero de dieciséis bytes $\texttt{10}$ (en decimal, 16). Con 31 bytes, $31 \bmod 16 = 15$, así que se añade $16 - 15 = 1$ byte, de valor $\texttt{01}$, y el mensaje queda en 32 bytes.

Ejercicio 2

Alicia cifra en CTR, por error con el mismo contador $T_1$, dos mensajes de un bloque: $m = A = \texttt{6bc1bee2…172a}$ y

$$m' = \texttt{ae2d8a57}\ \texttt{1e03ac9c}\ \texttt{9eb76fac}\ \texttt{45af8e51}.$$

Eva ve ambos criptogramas: $c = \texttt{874d6191…b6ce}$ (el del ejemplo) y

$$c' = \texttt{42a15524}\ \texttt{8663d02c}\ \texttt{6c6579d9}\ \texttt{af312fb5}.$$

¿Qué obtiene si hace su XOR?

Ver la solución

Los dos usan $s_1$, así que $c \oplus c' = (m \oplus s_1) \oplus (m' \oplus s_1) = m \oplus m'$. Haciendo el XOR dígito a dígito de los valores dados,

$$c \oplus c' = \texttt{c5ec34b5}\ \texttt{3043330a}\ \texttt{778a11bd}\ \texttt{363c997b},$$

que es justo $m \oplus m'$. La clave ha desaparecido. Si Eva conoce $m$ (por ejemplo, una cabecera estándar), recupera $m' = (c \oplus c') \oplus m$ sin tocar AES.

Ejercicio 3

En el CBC del ejemplo (mensaje $A\,A$), un atacante cambia el último bit del primer byte de $c_1$ y el receptor descifra. ¿Qué pasa con $m_1$ y con $m_2$?

Ver la solución

El bloque $m_2 = D_k(c_2) \oplus c_1$ usa $c_1$ solo en el XOR, así que el bit cambiado pasa tal cual a $m_2$: el primer byte pasa de $\texttt{6b}$ a $\texttt{6a}$ y el resto no cambia. En cambio $m_1 = D_k(c_1) \oplus \text{IV}$ descifra un bloque alterado, y la difusión de AES lo deja irreconocible: sale $\texttt{155b8fb7…a1c6}$, que difiere de $A$ en 68 de los 128 bits. Moraleja: CBC no avisa de que algo ha cambiado, y el atacante controla un bit del bloque siguiente. Por eso se usa un modo autenticado como GCM.

Cierre del curso: AES hoy y lo que viene

Dónde se usa. AES va dentro de casi todo lo que cifras sin darte cuenta. En TLS 1.3 (RFC 8446, §9.1), el protocolo de las conexiones web seguras, toda implementación debe soportar la suite TLS_AES_128_GCM_SHA256 y debería soportar TLS_AES_256_GCM_SHA384: AES en modo GCM. Y se reparte el trabajo como dijimos en la lección 1: un método de clave pública acuerda la clave, y AES cifra los datos. Para el primero, mira por qué funciona RSA y juega con RSA paso a paso.

El ordenador cuántico. El algoritmo de Shor rompe RSA, como cuenta este artículo. A AES le afecta otro algoritmo, el de Grover, que según el NIST permite buscar la clave por fuerza bruta con cuadráticamente menos pasos: entre $N$ claves, del orden de $\sqrt N$ pasos en lugar de $N$; para 128 bits, unos $2^{64}$ en lugar de $2^{128}$. Pero, como subraya el NIST, esos pasos tienen que hacerse uno tras otro (no se reparten entre muchas máquinas) y el hardware cuántico es caro. Es una ventaja mucho menor que la de Shor sobre RSA. Sobre AES-128, el NIST dice que probablemente Grover dé poca o ninguna ventaja y que seguirá siendo seguro durante décadas; y para AES-192 y AES-256 cree que seguirán siendo seguros durante mucho tiempo. Su conclusión es que las aplicaciones actuales pueden seguir usando AES con claves de 128, 192 o 256 bits.

Qué estudiar después.

• Autenticación: los códigos MAC y el cifrado autenticado (lo que GCM hace por dentro).
• Funciones hash y cifrados de flujo.
• Criptografía de clave pública: RSA y curvas elípticas.
• Seguridad demostrable, en el libro de Katz y Lindell o en el de Boneh y Shoup, de acceso libre.
• Ataques más finos a cifrados de bloque: criptoanálisis diferencial y lineal.

Hemos pasado de la libreta perfecta a AES, pasando por DES, los cuerpos finitos y los modos de operación.

En resumen

• Un cifrado de bloque cifra un solo bloque; un modo de operación lo extiende a mensajes enteros, y PKCS#7 rellena el último bloque (siempre, incluso si ya encaja).
• ECB cifra cada bloque por separado: bloques iguales dan criptogramas iguales y se ven los patrones.
• CBC encadena con el criptograma anterior y un IV; CTR cifra un contador y hace XOR, como una libreta de un solo uso cuya clave sale de AES. Su regla: nunca repetir contador con la misma clave.
• GCM cifra en modo contador y añade una etiqueta que detecta modificaciones: es la opción habitual, por ejemplo en TLS 1.3.
• Frente al ordenador cuántico, el NIST considera que AES con claves de 128, 192 o 256 bits puede seguir usándose.

Has terminado el curso. Sigue en la guía de criptografía.