El ataque por encuentro a medio camino o meet-in-the-middle es un ataque similar al ataque de cumpleaños, que utiliza un compromiso entre tiempo y espacio.

Mientras que el ataque de cumpleaños trata de encontrar dos valores del dominio de una función que tienen como imagen el mismo resultado, este ataque 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 da lo mismo que la imagen inversa de la segunda función - de ahí el nombre del ataque-.

Fue desarrollado en 1977 por Whitfield Diffie y Martin Hellman, en un intento de expandir un bloque cifrado. En la búsqueda de una mejor seguridad del cifrado de un bloque, se podría intentar la idea de usar simplemente dos claves criptográficas para cifrar dos veces los datos. A priori, se podría pensar que esto debería elevar al cuadrado la seguridad del esquema de doble cifrado.

Ciertamente, una búsqueda exhaustiva de todas las claves posibles requeriría 2²ⁿ intentos, si cada clave fuera de n bits, comparado con los 2ⁿ intentos requeridos para una clave única.

Sin embargo, Diffie y Hellman encontraron un compromiso entre tiempo y memoria que podría quebrar el cifrado en solamente el doble de tiempo.^[1] El ataque se basa en el cifrado por un extremo y el descifrado por el otro, buscando un encuentro a medio camino.

Supongamos que el atacante conoce el texto P y su cifrado C, o sea: , donde K₁ y K₂ son las dos claves.

El atacante, entonces, puede calcular E_K(P) para todas las claves posibles K y guardar los resultados en memoria. Luego, puede calcular D_K(C) para cada clave K y compararla con la tabla en memoria. Si llega a una coincidencia, es plausible que el atacante haya descubierto ambas claves, y puede verificarlo con un segundo par de texto original y texto cifrado.

Si la longitud de clave es n, este ataque solamente necesita 2^{n + 1} cifrados (y un espacio del orden de O(2ⁿ) claves), comparado con el ataque de fuerza bruta, el cual necesita un espacio de O(1) claves a costa de ejecutar 2²ⁿ cifrados.

Véase también

• Ataque de cumpleaños
• Ataque Man-in-the-middle — un ataque con un nombre similar pero en un contexto distinto.
• Triple DES

Referencias