El ataque meet-in-the-middle ( MITM ), un ataque de texto plano conocido, [1] es un ataque criptográfico de compensación de espacio-tiempo genérico contra esquemas de cifrado que se basan en realizar múltiples operaciones de cifrado en secuencia. El ataque MITM es la razón principal por la que no se usa Double DES y por qué un atacante puede forzar brutalmente una clave Triple DES (168 bits) con 2 56 espacios y 2 112 operaciones. [2] [3]
Descripción
Cuando se intenta mejorar la seguridad de un cifrado en bloque, una idea tentadora es cifrar los datos varias veces utilizando varias claves. Se podría pensar que esto duplica o incluso n- tuplica la seguridad del esquema de cifrado múltiple, dependiendo del número de veces que se cifran los datos, porque una búsqueda exhaustiva de todas las combinaciones posibles de claves (fuerza bruta simple) tomaría 2 n · K intenta si los datos están cifrados con claves de k bits n veces.
El MITM es un ataque genérico que debilita los beneficios de seguridad de usar múltiples cifrados al almacenar valores intermedios de los cifrados o descifrados y usarlos para mejorar el tiempo requerido para forzar las claves de descifrado. Esto hace que un ataque Meet-in-the-Middle (MITM) sea un ataque criptográfico de compensación de espacio-tiempo genérico .
El ataque MITM intenta encontrar las claves utilizando tanto el rango (texto cifrado) como el dominio (texto plano) de la composición de varias funciones (o cifrados de bloque) de modo que el mapeo hacia adelante a través de las primeras funciones es el mismo que el mapeo hacia atrás (inverso image) a través de las últimas funciones, encontrándose literalmente en medio de la función compuesta. Por ejemplo, aunque Double DES cifra los datos con dos claves diferentes de 56 bits, Double DES puede romperse con 2 57 operaciones de cifrado y descifrado.
El MITM multidimensional (MD-MITM) utiliza una combinación de varios ataques MITM simultáneos como se describió anteriormente, donde la reunión ocurre en múltiples posiciones en la función compuesta.
Historia
Diffie y Hellman propusieron por primera vez el ataque de encuentro en el medio en una expansión hipotética de un cifrado en bloque en 1977. [4] Su ataque utilizó una compensación espacio-tiempo para romper el esquema de doble cifrado en solo el doble del tiempo necesario para romper el esquema de cifrado único.
En 2011, Bo Zhu y Guang Gong investigaron el ataque multidimensional de encuentro en el medio y presentaron nuevos ataques a los cifrados de bloque GOST , KTANTAN y Hummingbird-2 . [5]
Encuentro en el medio (1D-MITM)
Suponga que alguien quiere atacar un esquema de cifrado con las siguientes características para un texto plano P y un texto cifrado C dado :
donde ENC es la función de cifrado, DEC la función de descifrado definida como ENC −1 (mapeo inverso) y k 1 y k 2 son dos claves.
El enfoque ingenuo para forzar este esquema de cifrado es descifrar el texto cifrado con cada k 2 posible , y descifrar cada una de las salidas intermedias con cada k 1 posible , para un total de 2 k 1 × 2 k 2 (o 2 k 1 + k 2 ) operaciones.
El ataque de encuentro en el medio utiliza un enfoque más eficiente. Al descifrar C con k 2 , se obtiene la siguiente equivalencia:
El atacante puede calcular ENC k 1 ( P ) para todos los valores de k 1 y DEC k 2 ( C ) para todos los valores posibles de k 2 , para un total de 2 k 1 + 2 k 2 (o 2 k 1 +1 , si k 1 y k 2 son del mismo tamaño) operaciones. Si el resultado de cualquiera de las operaciones ENC k 1 ( P ) coincide con el resultado de las operaciones DEC k 2 ( C ), el par de k 1 y k 2 es posiblemente la clave correcta. Esta clave potencialmente correcta se denomina clave candidata . El atacante puede determinar qué clave candidata es correcta probándola con un segundo conjunto de prueba de texto sin formato y texto cifrado.
El ataque MITM es una de las razones por las que el Estándar de cifrado de datos (DES) fue reemplazado por Triple DES y no Doble DES. Un atacante puede usar un ataque MITM para fuerza bruta Double DES con 2 57 operaciones y 2 56 de espacio, lo que lo convierte en una pequeña mejora con respecto a DES. [6] Triple DES utiliza una clave de "longitud triple" (168 bits) y también es vulnerable a un ataque de encuentro en el medio en 2 56 espacios y 2 112 operaciones, pero se considera seguro debido al tamaño de su espacio de teclas. [2] [3]
Algoritmo MITM
Calcule lo siguiente:
- :
- y guarda cada uno junto con el correspondiente en un conjunto A
- :
- y comparar cada nuevo con el conjunto A
Cuando se encuentra una coincidencia, mantenga como candidato a la par de claves en una tabla T . Pruebe los pares en T en un nuevo par depara confirmar la validez. Si el par de claves no funciona en este nuevo par, vuelva a realizar MITM en un nuevo par de.
Complejidad MITM
Si el tamaño de la clave es k , este ataque utiliza solo 2 k + 1 cifrados (y descifrados) y memoria O (2 k ) para almacenar los resultados de los cálculos directos en una tabla de búsqueda , en contraste con el ataque ingenuo, que necesita 2 2 · K encriptaciones pero O (1) espacio.
MITM multidimensional (MD-MITM)
Si bien 1D-MITM puede ser eficiente, se ha desarrollado un ataque más sofisticado: ataque multidimensional encuentro en el medio , también abreviado MD-MITM . Esto se prefiere cuando los datos se han cifrado utilizando más de 2 cifrados con claves diferentes. En lugar de encontrarse en el medio (un lugar en la secuencia), el ataque MD-MITM intenta alcanzar varios estados intermedios específicos utilizando los cálculos hacia adelante y hacia atrás en varias posiciones del cifrado. [5]
Suponga que el ataque debe montarse en un cifrado de bloque, donde el cifrado y descifrado se define como antes:
que es un texto sin formato P se cifra varias veces utilizando una repetición del mismo cifrado de bloque
El MD-MITM se ha utilizado para el criptoanálisis de, entre muchos, el cifrado de bloque GOST , donde se ha demostrado que un 3D-MITM ha reducido significativamente la complejidad del tiempo para un ataque. [5]
Algoritmo MD-MITM
Calcule lo siguiente:
- y guarda cada uno junto con el correspondiente en un set .
- y guarda cada uno junto con el correspondiente en un set .
Para cada posible suposición sobre el estado intermedio calcular lo siguiente:
- y para cada partido entre este y el set , ahorrar y en un nuevo set .
- [ verificación necesaria ]
- y guarda cada uno junto con el correspondiente en un set .
- Para cada posible suposición en un estado intermedio calcular lo siguiente:
- y para cada partido entre este y el set , compruebe también si
- coincide con y luego guarde la combinación de subclaves juntas en un nuevo conjunto .
- Para cada posible suposición en un estado intermedio calcular lo siguiente:
- y para cada partido entre este y el set , compruebe también si coincide con , ahorrar y en un nuevo set .
- y para cada partido entre este y el set , revisa también
si coincide con . Si este es el caso, entonces: "
Utilice la combinación de subclaves encontrada en otro par de texto sin formato / texto cifrado para verificar la exactitud de la clave.
Tenga en cuenta el elemento anidado en el algoritmo. La estimación de cada valor posible de s j se realiza para cada estimación de la anterior s j -1 . Esto constituye un elemento de complejidad exponencial a la complejidad temporal general de este ataque MD-MITM.
Complejidad MD-MITM
La complejidad del tiempo de este ataque sin fuerza bruta, es ⋅⋅
En cuanto a la complejidad de la memoria, es fácil ver que son mucho más pequeños que la primera tabla construida de valores candidatos: a medida que aumenta, los valores candidatos contenidos en debe satisfacer más condiciones, por lo que menos candidatos pasarán al destino final .
Un límite superior de la complejidad de la memoria de MD-MITM es entonces
donde k denota la longitud de toda la clave (combinada).
La complejidad de los datos depende de la probabilidad de que pase una clave incorrecta (obtener un falso positivo), que es , donde l es el estado intermedio en la primera fase MITM. ¡El tamaño del estado intermedio y el tamaño del bloque es a menudo el mismo! Teniendo en cuenta también cuántas claves quedan para probar después de la primera fase MITM, es.
Por lo tanto, después de la primera fase MITM, hay , dónde es el tamaño del bloque.
Por cada vez que el valor candidato final de las claves se prueba en un nuevo par de texto plano / texto cifrado, el número de claves que pasarán se multiplicará por la probabilidad de que pase una clave que es .
La parte de la prueba de fuerza bruta (probar la clave candidata en nuevos -pares, tienen complejidad de tiempo , claramente para aumentar múltiplos de b en el exponente, el número tiende a cero.
La conclusión sobre la complejidad de los datos está restringida por un razonamiento similar por el de -pares.
A continuación se muestra un ejemplo específico de cómo se monta un 2D-MITM:
Un ejemplo general de 2D-MITM
Esta es una descripción general de cómo se monta 2D-MITM en un cifrado de cifrado de bloque.
En MITM bidimensional (2D-MITM) el método consiste en alcanzar 2 estados intermedios dentro del cifrado múltiple del texto sin formato. Vea la siguiente figura:
Algoritmo 2D-MITM
Calcule lo siguiente:
- y guarda cada uno junto con el correspondiente en un conjunto A
- y guarda cada uno junto con el correspondiente en un conjunto B.
Para cada posible conjetura sobre un estado intermedio s entre y calcular lo siguiente:
- y para cada partido entre este y el conjunto A, guarda y en un nuevo set T.
- y para cada partido entre este y el conjunto B, compruebe también si coincide con T para
- si este es el caso, entonces:
Utilice la combinación de subclaves encontrada en otro par de texto sin formato / texto cifrado para verificar la exactitud de la clave.
Complejidad 2D-MITM
La complejidad del tiempo de este ataque sin fuerza bruta, es
donde | ⋅ | denota la longitud.
El consumo de memoria principal está restringido por la construcción de los conjuntos A y B donde T es mucho más pequeño que los demás.
Para conocer la complejidad de los datos, consulte la subsección sobre complejidad para MD-MITM .
Ver también
Referencias
- ^ http://www.crypto-it.net/eng/attacks/meet-in-the-middle.html
- ↑ a b Moore, Stephane (16 de noviembre de 2010). "Ataques de encuentro en el medio" (PDF) : 2. Cite journal requiere
|journal=
( ayuda ) - ^ a b Blondeau, Céline. "Lección 3: Block Ciphers" (PDF) . CS-E4320 Criptografía y seguridad de datos .
- ^ ^Diffie, Whitfield; Hellman, Martin E. (junio de 1977). "Criptoanálisis exhaustivo del estándar de cifrado de datos NBS" (PDF) . Computadora . 10 (6): 74–84. doi : 10.1109 / CM.1977.217750 . S2CID 2412454 .
- ^ a b c Zhu, Bo; Guang Gong (2011). "MD-MITM Attack y sus aplicaciones a GOST, KTANTAN y Hummingbird-2" . eCrypt .
- ^ Zhu, Bo; Guang Gong (2011). "MD-MITM Attack y sus aplicaciones a GOST, KTANTAN y Hummingbird-2". eCrypt .