La caída de DES y el Triple DES: cuando 56 bits no bastan

Ya conoces DES por dentro: sus rondas, su función $f$ con las cajas S y sus subclaves. En el relato del curso, DES reinó unos veinte años y cayó por una razón sencilla: su clave de 56 bits se quedó corta. Esta lección cuenta cómo cayó, qué intentó la gente para arreglarlo (cifrar dos veces, que no funciona) y qué sí funcionó (cifrar tres veces). De paso, aprenderás un truco que reaparece por todas partes en criptografía: el encuentro a medio camino.

La idea

DES tiene $2^{56}$ claves posibles, unos $7{,}2 \cdot 10^{16}$. Es un número enorme para una persona, pero no para una máquina. Eva solo necesita un par (mensaje, criptograma) conocido: prueba todas las claves hasta que una convierte el mensaje en el criptograma. Eso es la fuerza bruta de la lección 1.

El diseño de DES resistió bien durante décadas los ataques más ingeniosos. Lo que no resistió fue el paso del tiempo: los ordenadores se abarataron y las $2^{56}$ pruebas dejaron de ser una barrera.

Cuando una clave se queda corta, la reacción natural es alargarla. Como cambiar DES por completo era caro, surgió la idea de reutilizarlo: cifrar el mensaje con DES y volver a cifrar el resultado con otra clave. Si una clave son 56 bits, dos claves serían 112. ¿Verdad? Falso, y la razón es la mitad de la lección.

La caída: Deep Crack

Ya en 1977 Diffie y Hellman propusieron una máquina dedicada a la búsqueda exhaustiva de claves de DES. Desde entonces, la clave de 56 bits estuvo bajo sospecha.

En julio de 1998 la Electronic Frontier Foundation (EFF) lo demostró en la práctica con una máquina construida para ello, apodada Deep Crack. Según la EFF:

• Costó menos de 250.000 dólares.
• Resolvió el «DES Challenge II» de RSA Laboratories, dotado con 10.000 dólares, en unas 56 horas.
• Probaba más de 88.000 millones de claves por segundo.
• El récord anterior eran 39 días, logrados con una gran red de ordenadores.

Mira las cifras con calma. A $88 \cdot 10^9$ claves por segundo, recorrer las $2^{56}$ claves enteras llevaría unas 227 horas, casi 9 días y medio. Encontrar la clave en 56 horas significa que la máquina tuvo algo de suerte: de media, la clave aparece a mitad de camino, hacia las 114 horas. (Este cálculo es nuestro, no de la EFF.)

Medio año después, en enero de 1999, la EFF repitió la hazaña con el reto siguiente junto a distributed.net, una red de casi 100.000 ordenadores de voluntarios, en 22 horas y 15 minutos. Ya no había discusión: DES no protegía ningún secreto que valiera más que una pequeña inversión.

El NIST (la agencia estadounidense que había publicado el estándar) acabó retirando FIPS 46-3, la última versión de DES, en 2005, como vimos en la lección 5.

El doble cifrado

Sea $E_k$ el cifrado de un bloque con la clave $k$. El doble cifrado usa dos claves independientes $k_1$ y $k_2$:

$$c = E_{k_2}\bigl(E_{k_1}(m)\bigr).$$

Si cada clave tiene $n$ bits, hay $2^{2n}$ parejas de claves. Para DES, $n=56$ y $2^{112}$ parejas: inalcanzable por fuerza bruta. Pero Eva no tiene por qué probar parejas.

El encuentro a medio camino

Eva conoce un par $(m, c)$. Si la pareja $(k_1,k_2)$ es la correcta, entonces

$$E_{k_1}(m) = D_{k_2}(c),$$

porque ambos lados son el valor intermedio que hay entre los dos cifrados. Así que:

1. Eva calcula $E_{k}(m)$ para todas las claves $k$ y guarda las parejas (valor, $k$) en una tabla $A$.
2. Calcula $D_{k}(c)$ para todas las claves $k$ y guarda la tabla $B$.
3. Busca los valores que aparecen en las dos tablas. Cada coincidencia es una pareja de claves candidata.

Son $2^n$ cifrados más $2^n$ descifrados, no $2^{2n}$. Para el doble DES, unas $2^{57}$ operaciones de tiempo ($2^{56}$ cifrados y $2^{56}$ descifrados) y una tabla de $2^{56}$ entradas. Esto lo señalaron ya Diffie y Hellman en 1977, y por eso recomendaron cifrar al menos tres veces; Merkle (1979) y Merkle y Hellman analizaron después el cifrado triple (así lo cuenta el Handbook of Applied Cryptography, capítulo 7). Cifrar dos veces apenas duplica el trabajo de Eva: la seguridad pasa de «$2^{56}$» a «$2^{57}$», no a «$2^{112}$». Se paga con memoria, y mucha: ver el ejercicio 3.

Ejemplo resuelto

Usamos el Feistel de juguete de la lección 4 (bloques de 8 bits, tres rondas, caja S de PRESENT) con una simplificación para que el espacio de claves sea manejable a mano: cada clave es un solo número $k$ de 4 bits, y de él salen las tres subclaves rotándolo, como en DES: $K_1 = k$, $K_2$ es $k$ rotada una posición a la izquierda y $K_3$, $k$ rotada dos. Por ejemplo, $k = 0110$ da las subclaves $0110$, $1100$ y $1001$. Hay $16$ claves por cifrado, así que $16 \cdot 16 = 256$ parejas. Descifrar $D_k$ es, como siempre en Feistel, aplicar las mismas rondas con las subclaves al revés ($K_3$, $K_2$, $K_1$).

Ojo con cuatro claves, $0000$, $0101$, $1010$ y $1111$: sus tres subclaves se leen igual al derecho y al revés, así que para ellas $D_k = E_k$ y cifrar dos veces devuelve el mensaje. Son las «claves débiles» del juguete, como las de la lección 7.

Alicia y Bernardo comparten dos claves secretas (ninguna débil), $k_1 = 0110$ y $k_2 = 1100$, y cifran dos veces. Eva conoce el par

$$m = 1011\,0010, \qquad c = E_{k_2}(E_{k_1}(m)) = 0000\,1001.$$

Fuerza bruta. Probar las $256$ parejas, con dos cifrados cada una: 512 cifrados.

Encuentro a medio camino. Cuesta $16 + 16 = 32$ cifrados, más buscar coincidencias.

Para ver cómo se calcula una entrada, tomamos $k=0110$ (subclaves $0110$, $1100$, $1001$) y $m=1011\,0010$, con $L_0=1011$ y $R_0=0010$:

• Ronda 1: $R_0 \oplus 0110 = 0100$, que es la entrada 4 de la caja S, con salida $\texttt{9}=1001$. Luego $L_1 = 0010$ y $R_1 = 1011 \oplus 1001 = 0010$.
• Ronda 2: $0010 \oplus 1100 = 1110$, entrada 14, salida $\texttt{1}=0001$. Luego $L_2 = 0010$ y $R_2 = 0010\oplus 0001 = 0011$.
• Ronda 3: $0011 \oplus 1001 = 1010$, entrada 10, salida $\texttt{F} = 1111$. Luego $L_3 = 0011$ y $R_3 = 0010\oplus 1111 = 1101$.

La salida es $R_3L_3 = 1101\,0011$. Así se rellenan las dos tablas completas (la columna $k$ en binario):

$k$	$A$: $E_k(m)$	$B$: $D_k(c)$
0000	11010101	11011000
0001	11000100	01001001
0010	00101001	01001100
0011	10010001	11000011
0100	01101100	00110001
0101	11010110	00111000
0110	11010011	01110101
0111	10010010	00100100
1000	10000010	10100111
1001	00001110	00101100
1010	10100101	11011000
1011	10100100	10100110
1100	01011001	11010011
1101	00100100	10010110
1110	11010100	01000001
1111	01101001	00001001

Buscamos valores presentes en las dos columnas. Hay exactamente dos:

• $11010011$ está en $A$ con $k_1 = 0110$ y en $B$ con $k_2 = 1100$. Pareja candidata $(0110, 1100)$.
• $00100100$ está en $A$ con $k_1 = 1101$ y en $B$ con $k_2 = 0111$. Pareja candidata $(1101, 0111)$.

Una pareja es falsa. No es un error: los bloques son de solo 8 bits, así que hay solo 256 valores intermedios posibles y es normal que dos de ellos coincidan por azar. En DES esto se arregla con otro par $(m', c')$ conocido: se prueban solo las parejas candidatas. Con el juguete, el segundo par $m' = 0110\,1001$, $c' = 0010\,1110$ descarta $(1101,0111)$ y deja $(0110, 1100)$. Un tercer par, $m''=1110\,0001$ y $c'' = 1001\,1110$, la confirma. Eva ha encontrado ambas claves sin probar las 256 parejas.

Triple DES

Si dos cifrados no bastan, ¿y tres? El Triple DES (también llamado TDEA o 3DES) cifra con la secuencia cifrar-descifrar-cifrar (EDE, de encrypt-decrypt-encrypt):

$$c = E_{K_3}\bigl(D_{K_2}(E_{K_1}(m))\bigr).$$

El descifrado del medio no añade seguridad: es una comodidad. Si $K_1=K_2=K_3$, los dos primeros pasos se anulan y queda un DES normal, así que un equipo con Triple DES puede hablar con otro que solo tenga DES. Hay dos variantes:

• Tres claves independientes: 168 bits de clave en total.
• Dos claves ($K_3 = K_1$): 112 bits.

El encuentro a medio camino también muerde aquí, aunque más flojo: contra el Triple DES con tres claves el ataque cuesta del orden de $2^{112}$ operaciones, no $2^{168}$, y el NIST le asigna una seguridad de 112 bits (SP 800-57). Sigue siendo mucho más que $2^{56}$. Pero hay otro problema, que no es la clave: el bloque sigue siendo de 64 bits, y el NIST limita el uso de un mismo juego de claves a no más de $2^{20}$ bloques. Por qué un bloque de 64 bits obliga a ese límite lo veremos en la lección 13, con el modo CBC.

Estado actual en el NIST

• FIPS 46-3 (DES): retirado en 2005.
• SP 800-131A rev. 2 (marzo de 2019): el Triple DES de dos claves tiene el cifrado no permitido y su descifrado solo para uso heredado. El de tres claves está desaconsejado hasta el 31 de diciembre de 2023, con un máximo de $2^{20}$ bloques por juego de claves; después de esa fecha, el cifrado no se permite salvo que otra norma del NIST lo autorice, y el descifrado se admite como uso heredado.

En resumen, el Triple DES ya solo se tolera para descifrar datos antiguos. El relevo es AES.

Ejercicios

Ejercicio 1

Con claves de $n$ bits, ¿cuántos cifrados necesita la fuerza bruta contra un doble cifrado y cuántos el encuentro a medio camino? Calcúlalo para $n=4$ (el juguete) y para $n=8$.

Ver la solución

La fuerza bruta prueba $2^n \cdot 2^n = 2^{2n}$ parejas, cada una con dos cifrados. El encuentro a medio camino hace $2^n$ cifrados para la tabla $A$ y $2^n$ descifrados para la $B$: $2^{n+1}$ operaciones.

Para $n=4$: $2^8=256$ parejas (512 cifrados) frente a $2^5=32$ operaciones. Para $n=8$: $2^{16}=65\,536$ parejas ($131\,072$ cifrados) frente a $2^9=512$ operaciones. La ventaja crece muy rápido con $n$.

Ejercicio 2

En el ejemplo, comprueba que la pareja falsa $(1101,0111)$ no sirve para el segundo par ($m' = 0110\,1001$, $c' = 0010\,1110$) calculando $E_{0111}(E_{1101}(m'))$, y que la pareja verdadera sí encaja con su valor intermedio.

Ver la solución

Con $k_1 = 1101$ se obtiene $E_{1101}(m') = 0010\,0000$, y con $k_2=0111$ se obtiene $E_{0111}(0010\,0000) = 1100\,0101$, que no es $c' = 0010\,1110$. La pareja falsa se descarta.

Para la verdadera: $E_{0110}(m') = 1111\,1010$, y $D_{1100}(c') = 1111\,1010$ también. Coinciden, como debe ser en la pareja correcta.

Ejercicio 3

Para el doble DES con un par conocido $(m,c)$: (a) ¿cuántas parejas de claves $(k_1,k_2)$ hay y cuántos valores de 64 bits?, (b) ¿cuántas parejas falsas se esperan tras el encuentro a medio camino con un solo par? ¿y con dos pares? (c) ¿Cuánta memoria exige la tabla $A$ si cada entrada ocupa 8 bytes?

Ver la solución

(a) Hay $2^{112}$ parejas de claves y $2^{64}$ valores de bloque.

(b) Con un par, cada pareja de claves tiene una probabilidad de $2^{-64}$ de «encajar por azar», así que se esperan $2^{112}/2^{64} = 2^{48}$ parejas candidatas (casi todas falsas). Con un segundo par, cada candidata debe superar otra prueba de probabilidad $2^{-64}$: quedan $2^{48}\cdot 2^{-64} = 2^{-16}$ falsas esperadas, es decir, prácticamente solo la verdadera.

(c) $2^{56}\cdot 8 = 2^{59}$ bytes, unos $5{,}8\cdot 10^{17}$ bytes, es decir, unos 576 petabytes (solo los valores, sin contar las claves). Por eso el encuentro a medio camino, aunque ahorra tiempo, es caro en memoria.

En resumen

• DES cayó por su clave de 56 bits: en 1998 la EFF construyó Deep Crack por menos de 250.000 dólares y recuperó una clave en unas 56 horas.
• El doble cifrado parece dar $2^{112}$ claves, pero el encuentro a medio camino (Diffie y Hellman, 1977) lo rompe con unas $2^{57}$ operaciones y $2^{56}$ entradas de memoria.
• El Triple DES (EDE, con dos o tres claves) alarga la vida de DES, con una seguridad efectiva de 112 bits para tres claves.
• Estado en el NIST: FIPS 46-3 retirado en 2005, y el cifrado con Triple DES no se permite a partir de 2024 salvo excepciones.
• Hacía falta un cifrado nuevo, diseñado a plena luz y con bloque más grande: AES.

Siguiente lección: El cuerpo de 256 elementos