Ataque de encuentro en el medio

Paso algorítmico típico

• Fijar un texto plano conocido P y el texto cifrado correspondiente C; a menudo se obtienen en escenarios de texto plano elegido o texto plano conocido (la terminología de texto plano y texto cifrado resulta útil).
• Para cada valor de clave posible K en el primer espacio de claves, calcular X = E_K(P) y almacenar el par (X,K) en una tabla organizada para una búsqueda rápida (por ejemplo, una tabla hash o una lista ordenada).
• Para cada valor de clave posible K' en el segundo espacio de claves, calcular Y = D_{K'}(C) y comprobar si Y aparece en la tabla. Cada coincidencia produce un par candidato (K,K').
• Verificar los pares de claves candidatos usando uno o más pares adicionales de texto plano/texto cifrado para descartar falsos positivos; si es necesario, refinar o repetir el proceso con más datos.

Complejidad y recursos. Para dos claves independientes de n bits, la búsqueda exhaustiva ingenua del espacio conjunto de claves requiere aproximadamente 2^{2n} cifrados. La estrategia de encuentro en el medio reduce esto a un orden de 2^{n+1} cifrados, a la vez que requiere almacenamiento O(2^n) para conservar los valores intermedios. Dicho de otro modo, el tiempo es aproximadamente el doble del necesario para romper una sola clave de n bits, pero no su cuadrado, a costa de una memoria exponencial. Las implementaciones hacen concesiones entre memoria y cómputo adicional; los ataques prácticos usan búsquedas eficientes en memoria y técnicas de almacenamiento como grandes tablas hash y ordenación externa. Para referencias sobre detalles de implementación y estrategias de búsqueda, véase material sobre tablas de consulta.

Historia e impacto. El método fue descrito por Whitfield Diffie y Martin Hellman en 1977 cuando analizaron esquemas simples de doble cifrado diseñados para aumentar la longitud de la clave. Su trabajo mostró que aplicar ingenuamente un cifrado dos veces con dos claves independientes —una construcción a veces llamada doble cifrado— no ofrecía la seguridad cuadrática esperada debido al ataque de encuentro en el medio. Esa observación influyó en el diseño de normas posteriores y fomentó la adopción de construcciones más cuidadosas, como los modos de triple cifrado y modos de operación que impiden deliberadamente una coincidencia intermedia directa. Las extensiones tempranas de cifrados de bloque y las discusiones académicas sobre el diseño de cifrados de bloque suelen mencionar este ataque como un ejemplo de advertencia orientador.

Defensas, limitaciones y hechos destacados. El ataque requiere un almacenamiento viable y la capacidad de calcular muchas operaciones de cifrado y descifrado; por ello está limitado por la memoria y la potencia de procesamiento disponibles. Entre las contramedidas figuran el uso de esquemas criptográficos que vinculan claves y rondas para que los estados intermedios no sean susceptibles a una inversión independiente de la clave, la adopción de tamaños de clave mayores para que O(2^n) de memoria sea impracticable, o el empleo de demostraciones y diseños que eviten debilidades compositivas. Los esquemas de triple cifrado, los modos con mezcla no invertible o los diseños con transformaciones dependientes de la clave son respuestas típicas. Las implementaciones también deben vigilar los canales laterales y asegurarse de que los atacantes no puedan obtener fácilmente varios pares de texto plano/texto cifrado conocidos. Para lecturas prácticas y demostraciones, consulte material algorítmico y normativo disponible en recursos sobre claves y gestión de claves y en introducciones generales al análisis de texto cifrado.