Meet-in-the-middle y compromisos entre tiempo y memoria

Los ataques MITM dividen un cifrado en dos mitades y las atacan de forma independiente. El atacante construye una tabla desde un extremo y después busca una coincidencia desde el otro extremo. Esto reduce la complejidad del ataque de O(2^{2n}) a O(2^n), a cambio de utilizar O(2^n) de memoria.

Double-DES aplica DES dos veces: C = DES_{K2}(DES_{K1}(P)). El espacio de claves es de 2^{112}. Ataque MITM: para los 2^{56} valores de K1, calcule DES_{K1}(P) y almacénelo. Para los 2^{56} valores de K2, calcule DES_{K2}^{-1}(C) y búsquelo en la tabla. Una coincidencia → candidato (K1, K2). Solo requiere un trabajo total de 2^{57}.

Paso 1: cifre el texto plano P con todos los K1 posibles → tabla T[DES_{K1}(P)] = K1. Paso 2: para cada K2, descifre el texto cifrado C: v = DES^{-1}_{K2}(C). Compruebe si v ∈ T. Si existe T[v] = K1, verifique (K1, K2) con un segundo par de texto plano y texto cifrado. Se esperan entre 1 y 2 coincidencias falsas; descártelas.

Triple-DES (3DES) utiliza tres claves K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM sigue siendo aplicable, aunque de forma más limitada: 3DES de dos claves (K3=K1) se reduce a un trabajo de 2^{112}. Para 3DES de tres claves existe un ataque MITM de 2^{112}, lo que explica por qué 3DES proporciona solo aproximadamente 112 bits de seguridad efectiva a pesar de tener una clave de 168 bits.

Hellman (1980) propuso precalcular una tabla de cadenas (punto_inicial, punto_final) para acelerar la búsqueda de claves sin conexión. Dado un hash o texto cifrado objetivo, busque en la tabla de Hellman una cadena que lo contenga. Compromiso: P = N (el producto de tiempo y memoria es constante). Es la base de las tablas arcoíris.

Las tablas arcoíris (Oechslin, 2003) mejoran las tablas de Hellman mediante el uso de distintas funciones de reducción en cada posición de la cadena, lo que elimina las falsas alarmas (cadenas fusionadas). Son eficaces para crackear hashes de contraseñas sin sal. Una consulta tarda O(table_size/chain_length).

Una sal es un valor aleatorio que se antepone a la contraseña antes de aplicar el hash: H(salt||password). Las distintas sales producen hashes diferentes para una misma contraseña; una tabla arcoíris para "password" no sirve de nada si se utilizó una sal diferente. Las sales deben almacenarse junto con el hash.

Los ataques MITM contra AES-128 (10 rondas) dividen el algoritmo en la ronda 5: cifran hacia delante 5 rondas, descifran hacia atrás 5 rondas y se encuentran en el centro. El mejor ataque conocido es el ataque de bicliques, que reduce 2^{128} a 2^{126.1}; no es práctico, pero demuestra que AES no tiene margen de seguridad frente a enfoques de tipo MITM.

En las funciones hash de Merkle-Damgård, MITM puede encontrar preimágenes más rápido que la fuerza bruta en algunas construcciones. El ataque consiste en construir una tabla a partir de bloques del mensaje comenzando en IV y buscar hacia atrás desde el hash objetivo. Contra SHA-256 con todas sus rondas, el coste sigue siendo de aproximadamente 2^{255}; no hay ninguna mejora frente a la fuerza bruta.

El ataque de disección generaliza MITM a divisiones en r partes. Para una división del cifrado en 3 partes, cifra hacia delante 1/3 de las rondas, encuentra el punto intermedio de la cadena y después descifra hacia atrás 1/3. Requiere un tiempo de O(2^{n*2/3}) y una memoria de O(2^{n/3}), lo que ofrece un compromiso más equilibrado.

En los protocolos, los ataques MITM pueden evitarse utilizando claves largas derivadas mediante KDF a partir de contraseñas con alta entropía (lo que reduce el espacio de claves que se puede enumerar), tokens de hardware (FIDO2) cuya clave nunca abandona el dispositivo o autenticación mediante clave pública (no hay ningún secreto compartido que enumerar).

Los ataques MITM dividen los cifrados en mitades y reducen el tiempo de 2^{2n} a 2^n utilizando 2^n de memoria. Rompen Double-DES; 3DES ofrece cierta mitigación, pero tiene una seguridad efectiva de 112 bits. Las tablas arcoíris utilizan una lógica MITM para crackear contraseñas, pero se contrarrestan mediante el uso de sales. A continuación: ataques de temporización y ataques de canal lateral.