Cifrados de bloque: barajar bits con una clave corta

En la lección anterior vimos que la libreta de un solo uso es perfecta, pero exige una clave tan larga como el mensaje y que no se reutilice jamás. Necesitamos un compromiso: una clave corta (de 128 bits, por ejemplo) que sirva para cifrar muchísimos datos. La respuesta de la criptografía moderna son los cifrados de bloque. En esta lección vemos qué son, qué propiedades se les pide y cuáles son las dos formas clásicas de construirlos. Es el punto del relato en el que pasamos de lo ideal a lo práctico.

La idea

Un cifrado de bloque no cifra un mensaje entero. Lo parte en trozos de un tamaño fijo, los bloques (64 bits en DES, 128 en AES), y cifra cada trozo por separado con la misma clave. Qué se hace con un mensaje largo lo veremos en la última lección, la de los modos de operación. Ahora nos interesa un solo bloque.

Piensa en una baraja con $2^{64}$ cartas, una por cada bloque posible. Cifrar con una clave es barajar la baraja de una forma concreta: cada carta va a una posición, y ninguna posición se repite. Descifrar es deshacer ese barajado. Matemáticamente, cada clave determina una permutación del conjunto de bloques.

La seguridad se pide así: sin conocer la clave, el barajado debe parecer completamente al azar. Eva puede ver muchos pares (bloque en claro, bloque cifrado) y aun así no debería poder predecir el cifrado de un bloque nuevo.

Repaso Permutaciones y factorial

Una permutación de un conjunto es una forma de reordenar sus elementos: cada elemento va a una posición y no hay dos que vayan a la misma. Con 3 elementos hay $3! = 3\cdot 2\cdot 1 = 6$ permutaciones. Con $N$ elementos hay $N! = N\cdot(N-1)\cdots 2\cdot 1$, una cifra que crece de forma explosiva. Toda permutación se puede deshacer: tiene una inversa.

Definición

Un cifrado de bloque de $n$ bits con clave de $\ell$ bits es una familia de permutaciones del conjunto $\{0,1\}^n$ de bloques de $n$ bits, una para cada clave $k \in \{0,1\}^\ell$:

$$E_k : \{0,1\}^n \to \{0,1\}^n, \qquad c = E_k(m), \qquad m = D_k(c).$$

Que $E_k$ sea una permutación es justo lo que hace que se pueda descifrar: cada criptograma viene de un único mensaje. Además, $E_k$ y $D_k$ deben ser rápidas de calcular sabiendo la clave.

¿Cuántas permutaciones hay? ¿Cuántas usamos?

Aquí aparece la tensión central. El número de permutaciones de $\{0,1\}^n$ es $(2^n)!$. Para $n=64$, solo para decir cuál de ellas usamos haría falta una clave de unos

$$\log_2\big((2^{64})!\big) \approx 1{,}15\cdot 10^{21} \text{ bits}.$$

Equivale a unos $62{,}6\cdot 2^{64}$ bits. Otra forma de verlo: una tabla con los $2^{64}$ resultados de 64 bits ocuparía unos $1{,}48\cdot 10^{20}$ bytes, unos 148 exabytes. Es imposible como clave.

DES usa una clave de 56 bits efectivos: elige entre $2^{56} \approx 7{,}2\cdot 10^{16}$ permutaciones. Y AES-128, entre $2^{128}$. Son una parte ínfima de las permutaciones posibles. Un buen cifrado de bloque es entonces un compromiso: una familia minúscula de permutaciones, descrita con pocos bits, que no obstante se comporta como si cada $E_k$ hubiera sido elegida al azar entre todas. Que esto es así no se demuestra: se trabaja, durante años, para no encontrar la forma de distinguirlas, y por eso los estándares se someten a análisis público.

Para ver la escala con un bloque de 8 bits: hay $256!$ permutaciones, un número de unas 507 cifras decimales ($\log_2(256!) \approx 1684$ bits). El cifrado de juguete de la lección siguiente, con tres subclaves de 4 bits, solo usa $2^{12} = 4096$ de ellas como mucho.

Confusión y difusión

En 1949, Claude Shannon propuso dos ideas que siguen vigentes. Son los dos ingredientes de cualquier cifrado de bloque.

• Confusión: la relación entre la clave y el criptograma debe ser lo más complicada posible. Cada bit del criptograma debe depender de la clave de forma enrevesada, no «lineal». En la práctica la confusión la ponen las cajas S (de substitution box): pequeñas tablas que sustituyen un grupo de bits por otro.
• Difusión: cada bit del mensaje debe repartir su influencia por muchos bits del criptograma. Cambiar un solo bit de $m$ debe alterar, de media, la mitad de los bits de $c$. La difusión la dan las permutaciones de bits y las mezclas lineales.

Ninguna de las dos basta sola. Si solo hubiera cajas S pequeñas, cada trocito del bloque se cifraría por separado y sería fácil atacarlos uno a uno. Si solo hubiera permutaciones de bits, el bloque cifrado conservaría los mismos bits que el original, solo que barajados.

Repaso Qué quiere decir «lineal» aquí

Una operación $T$ sobre bloques de bits es lineal (sobre $\mathbb{F}_2$, los bits con la suma módulo 2) si respeta el XOR: $T(x\oplus y) = T(x)\oplus T(y)$ para todo $x$, $y$. Permutar bits es lineal, y calcular cada bit de salida como XOR de varios bits de la entrada también. Si además se suma un bloque fijo (por ejemplo, la clave), la operación es afín: $T(x) = A(x)\oplus b$, con $A$ lineal. Encadenar operaciones afines da otra afín, y sus ecuaciones se resuelven con álgebra lineal. Una caja S buena no cumple esa regla.

Rondas y subclaves

Una sola pasada de cajas S y de permutación no da suficiente mezcla. La solución es repetir: se define una ronda (añadir clave, sustituir, mezclar) y se aplica varias veces. Cada ronda usa su propia subclave (o clave de ronda), que se obtiene de la clave maestra mediante un procedimiento público llamado expansión de clave o calendario de claves. DES hace 16 rondas, y AES-128, 10.

El efecto avalancha

La consecuencia visible de una buena difusión es el efecto avalancha: cambiar un solo bit de la entrada (o de la clave) cambia, de media, la mitad de los bits de la salida. Un dato real: con DES, la clave $K = \texttt{133457799BBCDFF1}$ y el mensaje $M = \texttt{0123456789ABCDEF}$ dan $C = \texttt{85E813540F0AB405}$. Si cambias el último bit de $M$ (queda $\texttt{0123456789ABCDEE}$), el criptograma pasa a ser $\texttt{28378E295BE22A84}$, que difiere del anterior en 37 de los 64 bits. (La clave y el mensaje son los del ejemplo de J. Orlin Grabbe, «The DES Algorithm Illustrated», que seguiremos en las lecciones 5 a 7; el mensaje modificado y la cuenta de 37 bits son nuestros.)

Dos arquitecturas

Hay dos maneras clásicas de construir un cifrado de bloque con rondas.

Redes de sustitución-permutación (SPN, de substitution-permutation network). En cada ronda se hacen tres cosas sobre el bloque entero: se suma (XOR) la subclave, se pasa cada grupo de bits por una caja S y se mezclan los bits de todo el bloque con una capa lineal (en el caso más simple, una permutación de bits; en AES, algo más elaborado). Todo el bloque cambia en cada ronda. Es la arquitectura de AES.

Redes de Feistel. El bloque se parte en dos mitades. En cada ronda solo se modifica una mitad, sumándole una función de la otra, y luego se intercambian los papeles. Tiene la ventaja de que la función interna no necesita ser invertible. Es la arquitectura de DES. Le dedicamos la próxima lección.

Ejemplo resuelto

Hacemos una ronda de una SPN de juguete con bloques de 8 bits. La ronda tiene tres pasos:

1. Clave: se hace XOR del bloque con la subclave de 8 bits.
2. Sustitución: se parte el resultado en dos mitades de 4 bits y cada una pasa por la caja S de 4 bits del cifrado ligero PRESENT (Bogdanov y otros, 2007), aplicada dos veces (una por mitad):

$$S = (\texttt{C},\texttt{5},\texttt{6},\texttt{B},\texttt{9},\texttt{0},\texttt{A},\texttt{D},\texttt{3},\texttt{E},\texttt{F},\texttt{8},\texttt{4},\texttt{7},\texttt{1},\texttt{2}).$$

La entrada $x$ (de 0 a 15) se sustituye por la posición $x$ de esta lista: $S(\texttt{0}) = \texttt{C}$, $S(\texttt{1}) = \texttt{5}$, y así hasta $S(\texttt{F}) = \texttt{2}$.

3. Permutación: con los bits numerados de 1 a 8 de izquierda a derecha, $b_1b_2\dots b_8$, la salida es $b_1b_5b_2b_6b_3b_7b_4b_8$. Así los bits de cada mitad se reparten entre las dos mitades de la siguiente ronda.

Tomamos el bloque $x = 1011\,0010$ y la subclave $k = 0110\,1001$.

Paso 1. $x \oplus k = 1011\,0010 \oplus 0110\,1001 = 1101\,1011$.

Paso 2. Las mitades son $1101 = \texttt{D}$ y $1011 = \texttt{B}$. Como $\texttt{D}$ es 13 y $\texttt{B}$ es 11: $S(\texttt{D}) = \texttt{7} = 0111$ y $S(\texttt{B}) = \texttt{8} = 1000$. El resultado es $0111\,1000$.

Paso 3. Los bits son $b_1\dots b_8 = 0,1,1,1,1,0,0,0$. Reordenados como $b_1b_5b_2b_6b_3b_7b_4b_8$ da $0,1,1,0,1,0,1,0$. La salida de la ronda es

$$y = 0110\,1010.$$

Avalancha en una ronda

Cambia solo el último bit de la entrada: $x' = 1011\,0011$. Repite las cuentas con la misma subclave.

• $x'\oplus k = 1101\,1010$.
• Mitades $\texttt{D}$ y $\texttt{A}$: $S(\texttt{D}) = \texttt{7} = 0111$ y $S(\texttt{A}) = \texttt{F} = 1111$. Resultado $0111\,1111$.
• Permutación: $b = 0,1,1,1,1,1,1,1$ da $0,1,1,1,1,1,1,1$. Salida $y' = 0111\,1111$.

Comparando $y = 0110\,1010$ con $y' = 0111\,1111$ difieren 3 bits (las posiciones 4, 6 y 8). Un bit de entrada ha cambiado tres de salida: la caja S convirtió el cambio de un bit en el de varios, y la permutación los ha repartido. Pero con 8 bits de bloque lo ideal sería cambiar unos 4, y con una sola ronda eso es solo cuestión de suerte. Haciendo la cuenta con los 256 bloques posibles y los 8 cambios de un bit, en esta ronda cambian 2,5 bits de media. Con una segunda ronda (subclave $\texttt{C5}$, es decir $1100\,0101$) la media sube a 4,1 bits: justo lo que la difusión busca. Por eso se encadenan rondas.

Ejercicios

Ejercicio 1

Una caja S de 4 bits tiene $2^4 = 16$ entradas. ¿Cuántas cajas S distintas biyectivas (que sean permutaciones) puede haber? ¿Cuántos bits de clave harían falta, como mínimo, para poder elegir una cualquiera de ellas? Compáralo con lo que ocupa la tabla de la caja escrita entera.

Ver la solución

Una caja S biyectiva de 4 bits es una permutación de los 16 valores posibles de la entrada, así que hay $16!$ posibles. Es un número de $20\,922\,789\,888\,000$, unos $2{,}1\cdot 10^{13}$. La caja S de PRESENT es una de ellas.

Para poder elegir una cualquiera hacen falta $\log_2(16!)\approx 44{,}25$ bits, es decir, 45 bits. La tabla escrita entera ocupa $16\cdot 4 = 64$ bits: algo más, porque no aprovecha que los 16 valores son distintos. Es la misma cuenta que hicimos con los bloques de 64 bits, en pequeño.

Ejercicio 2

En la SPN de juguete, aplica una ronda a $x = 0000\,0000$ con la subclave $k = 0000\,0001$. ¿Qué bloque sale?

Ver la solución

Paso 1. $x\oplus k = 0000\,0001$.

Paso 2. Las mitades son $0000$ y $0001$. $S(\texttt{0}) = \texttt{C} = 1100$ y $S(\texttt{1}) = \texttt{5} = 0101$. Resultado $1100\,0101$.

Paso 3. $b = 1,1,0,0,0,1,0,1$. Reordenado $b_1b_5b_2b_6b_3b_7b_4b_8$: $1,0,1,1,0,0,0,1$.

La salida es $1011\,0001$.

Ejercicio 3

Explica por qué una ronda formada solo por «XOR con la subclave» y «permutación de bits» (sin cajas S) sería un cifrado muy débil aunque se repitiera muchas veces.

Ver la solución

Las dos operaciones son afines (lineales más una constante) sobre $\mathbb{F}_2$: la salida de cada bit es una suma módulo 2 de bits de la entrada y de la clave. Encadenar operaciones afines da otra operación afín. Si Eva conoce unos pocos pares $(m,c)$, cada uno le da ecuaciones lineales en los bits de la clave y las resuelve con álgebra lineal, por muchas rondas que haya. La caja S es la parte no lineal (la confusión) que lo impide.

En resumen

• Un cifrado de bloque es una familia de permutaciones de $\{0,1\}^n$, una por cada clave: $c = E_k(m)$ y $m = D_k(c)$.
• Hay $(2^n)!$ permutaciones posibles y la clave solo elige entre $2^\ell$ de ellas. El diseño busca que esas pocas parezcan elegidas al azar.
• La confusión (cajas S) y la difusión (permutaciones y mezclas) se combinan en rondas con subclaves.
• El efecto avalancha es la señal de buena difusión: un bit de cambio, la mitad de los bits de salida cambian. En DES, 37 de 64 en el ejemplo.
• Dos arquitecturas: SPN (AES) y Feistel (DES).

Siguiente lección: Redes de Feistel