Ataque Meet-in-the-middle

[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.

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.