Ataque de encuentro en el medio

Ataque criptográfico genérico de compensación espacio-tiempo

El ataque de encuentro en el medio ( MITM ), un conocido ataque de texto simple, ^[1] es un ataque criptográfico genérico de compensación de espacio-tiempo contra esquemas de cifrado que se basan en la realización de múltiples operaciones de cifrado en secuencia. El ataque MITM es la razón principal por la que no se utiliza Double DES y por la que un atacante puede forzar una clave Triple DES (168 bits) ^{[ aclaración necesaria ]} con 2 operaciones de espacio ⁵⁶ y 2 operaciones ^{de 112. [2]}

Descripción

Al intentar mejorar la seguridad de un cifrado de bloques, una idea tentadora es cifrar los datos varias veces utilizando claves múltiples. Se podría pensar que esto duplica o incluso multiplica por n 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) requeriría 2 ^{n · k} intentos si los datos se cifran con claves de k bits n veces.

El MITM es un ataque genérico que debilita los beneficios de seguridad del uso de cifrados múltiples al almacenar valores intermedios de los cifrados o descifrados y utilizarlos para mejorar el tiempo necesario para extraer por fuerza bruta ^{[ aclaración necesaria ]} las claves de descifrado. Esto hace que el ataque Meet-in-the-Middle (MITM) sea un ataque criptográfico genérico de compensación espacio-tiempo ^[3] .

El ataque MITM intenta encontrar las claves utilizando tanto el rango (texto cifrado) como el dominio (texto sin formato) de la composición de varias funciones (o cifrados en bloque) de modo que la asignación hacia delante a través de las primeras funciones sea la misma que la asignación hacia atrás (imagen inversa) a través de las últimas funciones, encontrándose literalmente en el medio de la función compuesta. Por ejemplo, aunque Double DES cifra los datos con dos claves diferentes de 56 bits, Double DES se puede romper con 2 operaciones de cifrado y descifrado de ^{57 bits} .

El MITM multidimensional (MD-MITM) utiliza una combinación de varios ataques MITM simultáneos como el descrito anteriormente, donde el encuentro 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 de bloque en 1977. ^[4] Su ataque utilizó un equilibrio espacio-temporal para romper el esquema de doble cifrado en solo el doble del tiempo necesario para romper el esquema de cifrado simple.

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)

Supongamos que alguien quiere atacar un esquema de cifrado con las siguientes características para un texto simple P y un texto cifrado C determinados :

${\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\P&={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(C))\\\end{aligned}}}$

donde ENC es la función de cifrado, DEC la función de descifrado definida como ENC ⁻¹ (mapeo inverso) y k ₁ y k ₂ son dos claves.

El enfoque ingenuo para aplicar fuerza bruta a este esquema de cifrado es descifrar el texto cifrado con cada k ₂ posible y descifrar cada una de las salidas intermedias con cada k ₁ posible , para un total de 2 ^{|k ₁ |} × 2 ^{|k ₂ |} (o 2 ^{|k ₁ |+|k ₂ |} ) operaciones.

El ataque de encuentro en el medio utiliza un enfoque más eficiente. Al descifrar C con k ₂ , se obtiene la siguiente equivalencia:

${\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {DEC}}_{k_{2}}({\mathit {ENC}}_{k_{2}}[{\mathit {ENC}}_{k_{1}}(P)])\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {ENC}}_{k_{1}}(P)\\\end{aligned}}}$

El atacante puede calcular ENC _{k 1} ( P ) para todos los valores de k ₁ y DEC _{k 2} ( C ) para todos los valores posibles de k ₂ , para un total de 2 operaciones ^{|k ₁ |} + 2 ^{|k ₂ |} (o 2 ^{|k ₁ |+1} , si k ₁ y k ₂ tienen el mismo tamaño). Si el resultado de cualquiera de las operaciones ENC _{k 1} ( P ) coincide con un resultado de las operaciones DEC _{k 2} ( C ), el par de k ₁ y k ₂ 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 simple y texto cifrado.

El ataque MITM es una de las razones por las que el Estándar de cifrado de datos (DES) se reemplazó por Triple DES y no por Double DES. Un atacante puede usar un ataque MITM para forzar bruscamente Double DES con 2 ⁵⁷ operaciones y espacio 2 ⁵⁶ , lo que lo convierte en una pequeña mejora con respecto a DES. ^[5] Triple DES usa una clave de "longitud triple" (168 bits) y también es vulnerable a un ataque de encuentro en el medio en espacio 2 ⁵⁶ y 2 ¹¹² operaciones, pero se considera seguro debido al tamaño de su espacio de claves. ^{[2] [6]}

Una ilustración del ataque 1D-MITM

Algoritmo MITM

Calcular lo siguiente:

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P),\;\forall k_{f_{1}}\in K}$:

  y guardar cada uno junto con el correspondiente en un conjunto A ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},C),\;\forall k_{b_{1}}\in K}$:

  y comparar cada nuevo con el conjunto A ${\displaystyle {\mathit {SubCipher}}_{1}}$

Cuando se encuentra una coincidencia, se guarda como par de claves candidato en una tabla T. Se prueban los pares en T en un nuevo par de ⁠ ⁠ para confirmar la validez. Si el par de claves no funciona en este nuevo par, se realiza MITM nuevamente en un nuevo par de ⁠ ⁠ . ${\displaystyle k_{f_{1}},k_{b_{1}}}$ ${\displaystyle (P,C)}$ ${\displaystyle (P,C)}$

Complejidad MITM

Si el tamaño de la clave es k , este ataque utiliza solo 2 ^{k +1} cifrados (y descifrados) y O (2 ^k ) de memoria para almacenar los resultados de los cálculos hacia adelante en una tabla de búsqueda , en contraste con el ataque ingenuo, que necesita 2 ^{2· k} cifrados pero O (1) espacio.

MITM multidimensional (MD-MITM)

Si bien el ataque 1D-MITM puede ser eficiente, se ha desarrollado un ataque más sofisticado: el ataque multidimensional de encuentro en el medio , también abreviado como MD-MITM . Este es el preferido 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 en el cifrado. ^[5]

Supongamos que el ataque debe montarse en un cifrado de bloque, donde el cifrado y descifrado se definen como antes:

${\displaystyle C={\mathit {ENC}}_{k_{n}}({\mathit {ENC}}_{k_{n-1}}(...({\mathit {ENC}}_{k_{1}}(P))...))}$

${\displaystyle P={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(...({\mathit {DEC}}_{k_{n}}(C))...))}$

Es decir, un texto simple P se cifra varias veces utilizando una repetición del mismo cifrado de bloque.

Una ilustración del ataque MD-MITM

El MD-MITM se ha utilizado para el criptoanálisis de, entre muchos, el cifrado de bloques GOST , donde se ha demostrado que un 3D-MITM ha reducido significativamente la complejidad temporal de un ataque al mismo. ^[5]

Algoritmo MD-MITM

Calcular lo siguiente:

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}$

y guardar cada uno junto con el correspondiente en un conjunto . ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$ ${\displaystyle H_{1}}$

${\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {DEC}}_{b_{n+1}}(k_{b_{n+1}},C)\qquad \forall k_{b_{n+1}}\in K}$

y guardar cada uno junto con el correspondiente en un conjunto . ${\displaystyle {\mathit {SubCipher}}_{n+1}}$ ${\displaystyle k_{b_{n+1}}}$ ${\displaystyle H_{n+1}}$

Para cada posible estimación del estado intermedio, calcule lo siguiente: ${\displaystyle s_{1}}$

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s_{1})\qquad \forall k_{b_{1}}\in K}$

y para cada partido entre este y el conjunto , guardar y en un nuevo conjunto . ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle H_{1}}$ ${\displaystyle k_{b_{1}}}$ ${\displaystyle k_{f_{1}}}$ ${\displaystyle T_{1}}$

${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s_{1})\qquad \forall k_{f_{2}}\in K}$^{[ verificación necesaria ]}

y guardar cada uno junto con el correspondiente en un conjunto . ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle k_{f_{2}}}$ ${\displaystyle H_{2}}$

Para cada posible conjetura sobre un estado intermedio, calcule lo siguiente: ${\displaystyle s_{2}}$

• ${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},s_{2})\qquad \forall k_{b_{2}}\in K}$

  y para cada partido entre este y el conjunto , comprobar también si ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle H_{2}}$

  Coincide con y luego guarda la combinación de subclaves juntas en un nuevo conjunto . ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

• Para cada posible conjetura sobre un estado intermedio, calcule lo siguiente: ${\displaystyle s_{n}}$

1. ${\displaystyle {\mathit {SubCipher}}_{n}={\mathit {DEC}}_{b_{n}}(k_{b_{n}},s_{n})\qquad \forall k_{b_{n}}\in K}$y para cada coincidencia entre este y el conjunto , comprobar también si coincide con , guardar y en un nuevo conjunto . ${\displaystyle {\mathit {SubCipher}}_{n}}$ ${\displaystyle H_{n}}$ ${\displaystyle T_{n-1}}$ ${\displaystyle k_{b_{n}}}$ ${\displaystyle k_{f_{n}}}$ ${\displaystyle T_{n}}$
2. ${\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {ENC}}_{f_{n}+1}(k_{f_{n}+1},s_{n})\qquad \forall k_{f_{n+1}}\in K}$y para cada coincidencia entre este y el conjunto , verifique también si coincide con . Si este es el caso, entonces: " ${\displaystyle {\mathit {SubCipher}}_{n+1}}$ ${\displaystyle H_{n+1}}$ ${\displaystyle T_{n}}$

Utilice la combinación encontrada de subclaves en otro par de texto simple/texto cifrado para verificar la exactitud de la clave. ${\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}},...,k_{f_{n+1}},k_{b_{n+1}})}$

Tenga en cuenta el elemento anidado en el algoritmo. La estimación de cada valor posible en s _j se realiza para cada estimación del s _{j -1} anterior . Esto constituye un elemento de complejidad exponencial para la complejidad temporal total de este ataque MD-MITM.

Complejidad MD-MITM

La complejidad temporal de este ataque sin fuerza bruta es ⋅ ⋅ ${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}}$ ${\displaystyle (2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}}$ ${\displaystyle (2^{|k_{b_{2}}|}+2^{|k_{f_{3}}|}+\cdots ))}$

Respecto a la complejidad de la memoria, es fácil ver que son mucho más pequeñas que la primera tabla construida de valores candidatos: a medida que i aumenta, los valores candidatos contenidos en deben satisfacer más condiciones, por lo que menos candidatos pasarán al destino final . ${\displaystyle T_{2},T_{3},...,T_{n}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{i}}$ ${\displaystyle T_{n}}$

Un límite superior de la complejidad de memoria de MD-MITM es entonces

${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s_{n}|}\cdots }$

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 suelen ser los mismos! Si se considera también la cantidad de claves que quedan para probar después de la primera fase MITM, es . ${\displaystyle 1/2^{|l|}}$ ${\displaystyle 2^{|k|}/2^{|l|}}$

Por lo tanto, después de la primera fase MITM, hay , donde es el tamaño del bloque. ${\displaystyle 2^{|k|-b}\cdot 2^{-b}=2^{|k|-2b}}$ ${\displaystyle |b|}$

Cada vez que se prueba el valor candidato final de las claves en un nuevo par de texto simple/texto cifrado, la cantidad de claves que pasarán se multiplicará por la probabilidad de que una clave pase, que es . ${\displaystyle 1/2^{|b|}}$

La parte de la prueba de fuerza bruta (probar la clave candidata en nuevos pares ⁠ ⁠ ${\displaystyle (P,C)}$ , tiene complejidad temporal , claramente para múltiplos crecientes de b en el exponente, el número tiende a cero. ${\displaystyle 2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots }$

La conclusión sobre la complejidad de los datos se ve restringida por un razonamiento similar al de los pares ⁠ ⁠ . ${\displaystyle \lceil |k|/n\rceil }$ ${\displaystyle (P,C)}$

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

En el MITM bidimensional (2D-MITM), el método consiste en alcanzar dos estados intermedios dentro del cifrado múltiple del texto sin formato. Véase la siguiente figura:

Una ilustración del ataque 2D-MITM

Algoritmo 2D-MITM

Calcular lo siguiente:

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}$

y guardar cada uno junto con el correspondiente en un conjunto A ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$

${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},C)\qquad \forall k_{b_{2}}\in K}$

y guardar cada uno junto con el correspondiente en un conjunto B. ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle k_{b_{2}}}$

Para cada posible estimación de un estado intermedio s entre y calcule lo siguiente: ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle {\mathit {SubCipher}}_{2}}$

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s)\qquad \forall k_{b_{1}}\in K}$

  y para cada partido entre este y el conjunto A, guardar y en un nuevo conjunto T. ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{b_{1}}}$ ${\displaystyle k_{f_{1}}}$

• ${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s)\qquad \forall k_{f_{2}}\in K}$

  y para cada coincidencia entre este y el conjunto B, comprobar también si coincide con T para ${\displaystyle {\mathit {SubCipher}}_{2}}$

  Si este es el caso entonces:

Utilice la combinación encontrada de subclaves en otro par de texto simple/texto cifrado para verificar la exactitud de la clave. ${\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}})}$

Complejidad 2D-MITM

La complejidad temporal de este ataque sin fuerza bruta es

${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{2}}|}+2^{|s|}\cdot \left(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}\right)}$

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.

Véase también

• Ataque de cumpleaños
• Seguridad inalámbrica
• Criptografía
• Ataque de encuentro en el medio de 3 subconjuntos
• Ataque de encuentro en el medio con coincidencia parcial

Referencias

1. "Cripto-TI".
2. Moore, Stephane (16 de noviembre de 2010). "Ataques de encuentro intermedio" (PDF) : 2. {{cite journal}}: Requiere citar revista |journal=( ayuda )
3. victoria, jaynor. "victoria15". victoria14 . Archivado desde el original el 14 de julio de 2021 . Consultado el 14 de julio de 2021 .
4. ^ Diffie, Whitfield; Hellman, Martin E. (junio de 1977). "Criptoanálisis exhaustivo del estándar de cifrado de datos NBS" (PDF) . Computer . 10 (6): 74–84. doi :10.1109/CM.1977.217750. S2CID  2412454.
5. Zhu, Bo; Gong, Guang (2014). "Ataque de encuentro en el medio multidimensional y sus aplicaciones a KATAN32/48/64". Criptografía y comunicaciones . 6 : 313–333. doi :10.1007/s12095-014-0102-9 – vía Springer Link.
6. Blondeau, Céline. "Conferencia 3: Cifrados en bloque" (PDF) . CS-E4320 Criptografía y seguridad de datos . Archivado desde el original (PDF) el 23 de febrero de 2018. Consultado el 22 de febrero de 2018 .