Confusión y difusión: de DES a AES

Los cifrados de la era del ordenador cifran bits, y la mayoría trabaja por bloques: 64 o 128 bits a la vez. Un cifrado en bloque es una familia de permutaciones $E_k:\{0,1{\}}^n\to \{0,1{\}}^n$, una para cada clave $k$. Lo que le pedimos es fácil de enunciar y difícil de conseguir: para quien no conozca $k$, $E_k$ debe ser indistinguible de una permutación elegida completamente al azar entre las $(2^n)!$ posibles. Es una permutación pseudoaleatoria. Cómo cifrar mensajes de más de un bloque es el tema del capítulo siguiente; este trata del bloque en sí.

§La red de Horst Feistel

Horst Feistel emigró de Alemania a Estados Unidos en 1934 y, tras años trabajando en criptografía para la Fuerza Aérea, entró en IBM, donde a comienzos de los setenta diseñó Lucifer, un cifrado para bancos. Su estructura, hoy llamada red de Feistel, resuelve con elegancia un problema de diseño: cómo construir una función invertible a partir de funciones de ronda que no tienen por qué serlo.

Se parte el bloque en dos mitades $(L_0,R_0)$. Cada ronda, con su propia subclave $k_i$, hace

Demostración

A partir de $(L_{i+1},R_{i+1})$ se lee directamente $R_i=L_{i+1}$. Entonces se puede recalcular $F(R_i,k_i)$, y $L_i=R_{i+1}\oplus F(R_i,k_i)$ porque $x\oplus y\oplus y=x$. A $F$ solo se la evalúa, nunca se la invierte.

En 1988 Michael Luby y Charles Rackoff demostraron lo que Feistel había encontrado por ingeniería: si las funciones de ronda son funciones aleatorias, tres rondas ya dan una permutación pseudoaleatoria, y cuatro dan una que resiste incluso a un adversario que también puede pedir descifrados. Los cifrados reales usan muchas más rondas porque sus funciones de ronda no son aleatorias, solo rápidas.

§DES: el Data Encryption Standard

En 1973 la Oficina Nacional de Estándares de Estados Unidos pidió un cifrado público para proteger datos gubernamentales y comerciales. IBM presentó una versión de Lucifer; tras la revisión de la NSA se publicó en 1977 como DES (FIPS 46): una red de Feistel de 16 rondas sobre bloques de 64 bits con una clave de 56 bits. Su función de ronda expande la media palabra a 48 bits, la combina con la subclave, pasa el resultado por ocho S-boxes (pequeñas tablas de 6 bits de entrada y 4 de salida, la única parte no lineal) y permuta los bits.

Dos cambios de la NSA fueron polémicos. La clave se acortó de los 128 bits de Lucifer a 56, y Whitfield Diffie y Martin Hellman calcularon en 1977 que una máquina de 20 millones de dólares encontraría una clave DES en un día. Y las S-boxes se cambiaron sin explicación, lo que hizo sospechar una puerta trasera. La verdad salió en 1990, cuando Eli Biham y Adi Shamir publicaron el criptoanálisis diferencial, que sigue cómo se propagan por las rondas las diferencias entre parejas de textos en claro: DES lo resistía mucho mejor de lo que lo harían unas S-boxes aleatorias. En 1994 Don Coppersmith, de IBM, confirmó que los diseñadores conocían la técnica desde 1974 y habían elegido las S-boxes contra ella. En 1993 Mitsuru Matsui descubrió el criptoanálisis lineal, que aproxima el cifrado por ecuaciones lineales que se cumplen algo más de la mitad de las veces; rompe DES con $2^{43}$ textos en claro conocidos, lo que tampoco era práctico.

Lo que mató a DES fue la longitud de la clave. En 1998 la Electronic Frontier Foundation construyó Deep Crack, una máquina de 1.856 chips a medida que costó unos 250.000 dólares y encontró una clave DES en 56 horas; en enero de 1999, con ayuda de los voluntarios de distributed.net, tardó 22 horas y 15 minutos. Hoy una clave cae en minutos. La aplicación de escritorio conserva DES solo para leer datos antiguos, y lo marca en rojo.

¿Por qué no un doble DES?

El arreglo evidente, cifrar dos veces con dos claves, $c=E_{k_2}(E_{k_1}(m))$, apenas ayuda.

El ataque

Se cifra $m$ con todas las $k_1$ y se guardan los $2^n$ resultados $E_{k_1}(m)$ en una tabla. Después se descifra $c$ con todas las $k_2$ y se busca $D_{k_2}(c)$ en la tabla: una coincidencia significa $E_{k_1}(m)=D_{k_2}(c)$, así que $(k_1,k_2)$ es candidata. Una segunda pareja conocida elimina los falsos candidatos. Las dos mitades se encuentran en el medio.

De ahí el triple DES, $E_{k_3}(D_{k_2}(E_{k_1}(m)))$, con una fuerza efectiva de unos 112 bits. Mantuvo funcionando a bancos y tarjetas de pago veinte años más. Su bloque de 64 bits fue su perdición: tras unos $2^{32}$ bloques con la misma clave, las colisiones de bloques se vuelven probables (la cota del cumpleaños), y el ataque Sweet32 de 2016 lo explotó en HTTPS y OpenVPN. El NIST prohibió el triple DES para cifrar a partir de 2023.

§Blowfish

En 1993 Bruce Schneier publicó Blowfish, una alternativa a DES rápida, libre y sin patentes: una red de Feistel de 16 rondas sobre bloques de 64 bits con claves de hasta 448 bits, cuyas S-boxes se generan a partir de la clave con un procedimiento deliberadamente lento. No se conoce ningún ataque práctico contra Blowfish completo, pero su bloque de 64 bits tiene el mismo problema del cumpleaños que el triple DES, y el propio Schneier recomienda sus sucesores. Su lenta preparación de clave sobrevive en bcrypt, el hash de contraseñas. cryptoKit 1.0 ofrecía Blowfish, así que la versión 2 lo mantiene, marcado como heredado.

§El concurso AES

En 1997 el NIST hizo algo nuevo: en vez de diseñar el sustituto de DES a puerta cerrada, organizó un concurso internacional abierto. En 1998 se presentaron quince candidatos de doce países; la comunidad criptográfica los atacó en público durante dos años; quedaron cinco finalistas (MARS, RC6, Rijndael, Serpent y Twofish). En octubre de 2000 el NIST eligió Rijndael, de los criptógrafos belgas Joan Daemen y Vincent Rijmen, por su combinación de seguridad, rapidez en todo, desde tarjetas inteligentes hasta servidores, y claridad matemática. Se convirtió en el Advanced Encryption Standard, FIPS 197, en noviembre de 2001. El modelo de concurso funcionó tan bien que se ha repetido para las funciones hash (SHA-3), el hash de contraseñas (Argon2) y la criptografía poscuántica.

§Dentro de AES

AES no es una red de Feistel sino una red de sustitución y permutación: cada ronda transforma el bloque entero de 128 bits, dispuesto como una cuadrícula de $4\times 4$ bytes llamada estado. Su aritmética vive en un cuerpo finito.

Demostración

Los polinomios módulo un polinomio irreducible forman un cuerpo (como los enteros módulo un primo): si $a(x)\ne 0$, entonces $\mathrm{mcd}(a(x),m(x))=1$ y el algoritmo de Euclides extendido da un $u(x)$ con $u(x)a(x)\equiv 1(\mathrm{mod}m(x))$. Los elementos no nulos forman un grupo de orden 255, así que $a^{255}=1$ por el teorema de Lagrange y $a^{-1}=a^{254}$.

Cada una de las 10 rondas de AES-128 (12 en AES-192, 14 en AES-256) aplica cuatro pasos:

1. SubBytes: cada byte $a$ se sustituye por $S(a)=A\cdot a^{-1}\oplus \text{63}$, el inverso en $\mathrm{GF}(2^8)$ seguido de una transformación afín fija $A$ sobre los bits. La inversión es muy no lineal; la transformación afín elimina sus puntos fijos. Es la confusión.
2. ShiftRows: la fila $r$ del estado rota $r$ bytes a la izquierda.
3. MixColumns: cada columna se multiplica por la matriz de filas $(2311)$, $(1231)$, $(1123)$, $(3112)$ sobre $\mathrm{GF}(2^8)$. Es de distancia máxima separable: cambiar $t$ bytes de una columna cambia al menos $5-t$ bytes del resultado. Junto con ShiftRows, es la difusión.
4. AddRoundKey: XOR con una subclave derivada de la clave por la expansión de clave.

La última ronda omite MixColumns, y hay un AddRoundKey adicional antes de la primera ronda. La estrategia de rastro ancho de Daemen y Rijmen demuestra que cualquier rastro diferencial o lineal a lo largo de cuatro rondas activa al menos 25 S-boxes, lo que acota la probabilidad del mejor rastro muy por debajo de nada aprovechable.

§El efecto avalancha

La difusión tiene una firma visible: si se invierte un bit del texto en claro, tras unas pocas rondas cambia aproximadamente la mitad de los bits de salida, con un patrón que parece aleatorio. Horst Feistel lo llamó efecto avalancha. AES alcanza la difusión completa en dos rondas: tras la segunda, cada byte de salida depende de todos los bytes de entrada.

§AES hoy

Un cuarto de siglo después de su elección, el mejor ataque contra AES-128 completo, el ataque biclique de 2011, necesita $2^{126,1}$ operaciones: un factor cuatro mejor que la fuerza bruta, y sin importancia práctica. Los ataques reales han sido contra las implementaciones: Daniel Bernstein mostró en 2005 que el software basado en tablas filtra la clave a través de los tiempos de la caché. Desde 2010 casi todos los procesadores incluyen instrucciones AES-NI, que ejecutan cada ronda en hardware, rápido y en tiempo constante. Frente a los ordenadores cuánticos, el algoritmo de Grover reduciría la seguridad de una clave de $k$ bits a unos $k/2$ bits, así que AES-256 es la opción prudente para datos que deban seguir secretos durante décadas (ver el capítulo 10).

§Para saber más

1. Horst Feistel, «Cryptography and Computer Privacy», Scientific American 228(5), 1973.
2. Don Coppersmith, «The Data Encryption Standard (DES) and its strength against attacks», IBM Journal of Research and Development 38(3), 1994.
3. Electronic Frontier Foundation, Cracking DES (1998).
4. Joan Daemen y Vincent Rijmen, The Design of Rijndael (2002; 2.ª ed. 2020).
5. NIST, FIPS 197, Advanced Encryption Standard (2001, actualizado en 2023).