Ataque Meet-in-the-middle

El ataque por encuentro a medio camino, también conocido por su término inglés meet-in-the-middle o por sus siglas en inglés MITM, consiste en aprovechar el diseño de un sistema G modelándolo como una secuencia de dos procesos A y B, en el que la salida de A será la entrada de B. El objetivo del ataque consiste en, dados los valores preestablecidos de entrada y salida E y S del sistema global G, encontrar la definición de los procesos A y B de tal forma que haya un I tal que:

Entorno de aplicación de ataque meet-in-the-middle

Expresado en lenguaje formal: Se trata de encontrar un valor en el rango del dominio de composición de dos funciones, de tal manera que la imagen de la primera función dé lo mismo que la imagen inversa de la segunda función. Por tanto para poder aplicar este ataque es necesario conocer la inversa del proceso B.

La forma en la que funciona el ataque es el siguiente: Se atacan de forma independiente ambas funciones, A y B, por fuerza bruta sobre el espacio de claves obteniendo por un lado el conjunto de posibles valores de I que puede producir como valor entrada E (probando todas las claves) y por el otro lado se obtiene el conjunto de posibles valores I que pueden producir como valor de salida S (probando todas las claves). Si entre estos dos conjuntos de posible valores de I, encontramos un valor que está en ambos, entonces probablemente hayamos encontrado las claves correctas. Para verificar que las claves son las correctas habría que probar con otros valores de E y S y comprobar que los resultados coinciden.

Observar que el ataque meet-in-the-middle es un claro ejemplo de algoritmo que reduce el tiempo de ejecución a costa de tener más necesidades de memoria (hay que almacenar los valores resultado de probar con todos las posibles claves del proceso A). Es una situación de compromiso espacio-tiempo.

Ideado en 1977 por Whitfield Diffie y Martin Hellman^[1]​ aplicado para reducir la seguridad de cifradores simétricos por bloques obtenidos a partir de 2 cifradores simétricos en bloque iguales puestos uno a continuación uno del otro, lo que se suele implementar mediante 2 rondas de cifrado. Es decir, los llamados doble cifrado (en inglés double encryption). Posteriormente este esquema se ha aplicado para atacar la seguridad de otros tipos de sistemas como las funciones hash criptográficas llamadas 'códigos de detección de modificaciones'.

Ejemplos de áreas de aplicación

Dos áreas de la criptografía en las que más se ha aplicado el ataque meet-in-the-middle han sido son el cifrado simétrico por bloque múltiple y la funciones hash criptográficas llamadas códigos de detección de manipulaciones.

Cifrado simétrico por bloques múltiple

^[2]​ Supongamos un cifrador simétrico por bloques implementado por doble cifrado de un cifrador por bloques, A, cuya clave kes de la forma ${\displaystyle k=k1k2}$ , con n la longitud de la clave del cifrador (i. e. k tendrá longitud 2n), y puede ser modelizado por el siguiente esquema:

 

Meet-in-the-middle en cifrado simétrico por bloques

Si hacemos directamente un ataque por fuerza bruta probando con todas las posibles combinaciones de la clave hasta dar con aquellas que a partir de x produce y, tenemos que probar como máximo 2²ⁿ posibilidades (las posible claves).

Observar que en un sistema de cifrado simétrico por bloques invertir la función consiste en descifrar y para descifrar se usa la misma clave que para cifrar. Por tanto conocido el algoritmo de cifrado es inmediato conocer el algoritmo de descifrado.

Si hacemos un ataque meet-in-the-middle podemos realizar menos comprobaciones. Si primero atacamos por fuerza bruta el cifrado de la izquierda, tenemos que comprobar 2ⁿ claves. Este conjunto de valores hay que guardarlos en una tabla. Si ahora operamos con el cifrado de la derecha realizamos otras 2ⁿ y según vamos obteniendo los valores comprobamos si cada valor está en la tabla previa almacenado. Los valores que están en ambos conjuntos corresponden con posibles claves correctas del sistema (habrá que volver a verificar cual es la correcta en un test posterior con nuevos valores de entrada y salida). Por tanto podemos obtener la clave del sistema haciendo 2ⁿ+ 2ⁿ= 2ⁿ⁺¹ operaciones en lugar de las 2²ⁿ si operaramos directamente. Por tanto se mejora mucho la complejidad computacional. Observar que estamos ignorando las múltiples comprobaciones y búsquedas que hay que hacer sobre si un valor obtenido en la segunda fase está entre los valores almacenados en la primera fase. Sin embargo, el coste adicional de computación y el incremento en las necesidades de almacenamiento (la tabla con los primeros 2ⁿ valores obtenidos) es compensado con mucho por la reducción en la complejidad computacional del procedimiento de ataque.

Cabe preguntarse, ¿Qué probabilidad hay de que valores que coinciden en el punto medio no sean soluciones que realmente se corresponden con la solución correcta? y por tanto ¿Una vez encontrada una solución es 'muy' necesario encontrar todas las restantes?. Es decir, hay que medir los falsos positivos producidos por claves falsas. Para ello podemos apoyarnos en el siguiente Teorema:^[3]​

Sea un cifrado simétrico por bloques con una longitud de clave de k bits, un tamaño de bloque de n bits y con t pares de valores (texto plano, texto cifrado). En este caso el número esperado de claves falsas en las cuales el texto plano se corresponde con un texto cifrado dado es ${\displaystyle 2^{k-tn}}$ .

Aplicando este teorema a un doble cifrado con DES obtenemos que el número claves falsas es ${\displaystyle 2^{80-2*64}=2^{-48}}$ . Este valor es muy pequeño y por tanto es factible el uso de ataques meet-in-the-middle. Si en lugar de doble cifrado usamos triple cifrado la probabilidad se reduce aún más.

Por el uso de este tipo de ataques no se debería usar doble cifrados. Este tipo de ataque se puede anular haciendo triple cifrado en lugar de doble cifrado. Por esta razón es por ejemplo mucho más común el algoritmo de cifrado triple DES que el doble DES.

Código de detección de manipulaciones

En el ámbito de los códigos de detección de manipulaciones los ataques meet in the middle se suelen usar para realizar ataques preimagen, es decir, el objetivo del ataque es encontrar un valor (preimagen) cuya imagen colisione con el valor hash dado.

^[4]​^[5]​^[6]​ En este tipo de ataques, lo que se hace es partir el algoritmo en dos partes. Por un lado se tienen los pasos que van hacia adelante hasta llegar a un punto intermedio. En ese punto se obtiene un conjunto de resultados intermedios. Por otro lado se computan una serie de pasos hacia atrás hasta llegar al mismo punto intermedio y ahí se obtienen otro conjunto de resultados intermedios. Los dos conjuntos de resultados tienen que ser independientes unos de otros. Estos dos conjuntos se comparan para así obtener los que coinciden y que serán los que se ponen de acuerdo con la solución concreta.

Véase también

• Ataque de cumpleaños
• Triple DES

Referencias

1. Diffie, W. y Hellman, M. (junio de 1977). «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74-84. 
2. Christof Paar, Jan Pelzl,"Understanding cryptography,A Textbook for Students and Practitioners". Springer 2010
3. Christof Paar, Jan Pelzl, "Understanding cryptography". Springer 1998.
4. Bart Preneel,"Cryptographic Primitives for Information Authentication-State fo the Art", Katholieke Universiteit Leuven. Heverlee, Belgium
5. Kazumaro Aoki, Yu Sasaki,"Meet-in-the-middle preimage Attacks Against Reduced SHA-0 and SHA-1" In Proceedings of the 29th Annual International Cryptology Conference on Advances in Cryptology, 2009, pp. 70-89
6. JINMIN ZHONG AND XUEJIA LAI,"Preimage Attack on Reduced DHA-256",JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 27

•   Datos: Q938066