El ataque de encuentro en el medio de 3 subconjuntos (en adelante, abreviado MITM ) es una variante del ataque de encuentro en el medio genérico , que se utiliza en criptología para el criptoanálisis de cifrado de bloque y hash . La variante de 3 subconjuntos abre la posibilidad de aplicar ataques MITM a cifrados, donde no es trivial dividir los bits clave en dos espacios clave independientes, como lo requiere el ataque MITM.
La variante de 3 subconjuntos relaja la restricción de que los espacios clave sean independientes, moviendo las partes que se cruzan de los espacios clave en un subconjunto, que contiene los bits clave comunes entre los dos espacios clave.
El ataque MITM original fue sugerido por primera vez en un artículo de Diffie y Hellman en 1977, donde discutieron las propiedades criptoanalíticas de DES. [1] Argumentaron que el tamaño de clave de DES era demasiado pequeño y que volver a aplicar DES varias veces con diferentes claves podría ser una solución al tamaño de clave; sin embargo, desaconsejaron el uso de doble DES y sugirieron triple DES como mínimo, debido a los ataques MITM (el doble DES es muy susceptible a un ataque MITM, ya que DES podría dividirse fácilmente en dos subcifrados (el primer y segundo cifrado DES ) con claves independientes entre sí, lo que permite un ataque MITM básico que reduce la complejidad computacional de a .
Han surgido muchas variaciones, desde que Diffie y Hellman sugirieron ataques MITM. Estas variaciones hacen que los ataques MITM sean más efectivos o permiten su uso en situaciones en las que la variante básica no puede. Bogdanov y Rechberger mostraron la variante de 3 subconjuntos en 2011, [2] y ha demostrado su uso en criptoanálisis de cifrados, como la familia ligera de cifrado de bloques KTANTAN.
Al igual que con los ataques MITM generales, el ataque se divide en dos fases: una fase de reducción de claves y una fase de verificación de claves. En la primera fase, se reduce el dominio de los candidatos clave mediante la aplicación del ataque MITM. En la segunda fase, las claves candidatas encontradas se prueban en otro par de texto plano/cifrado para filtrar las claves incorrectas.
En la fase de reducción de claves, el cifrado atacado se divide en dos subcifrados, cada uno con sus bits de clave independientes, como es normal con los ataques MITM. En lugar de tener que cumplir con la limitación de que los bits clave de los dos subcifrados deben ser independientes, el ataque de 3 subconjuntos permite dividir el cifrado en dos subcifrados, donde algunos de los bits pueden usarse en ambos subcifrados.
Esto se hace dividiendo la clave en tres subconjuntos, a saber:
Para llevar a cabo ahora el ataque MITM, los 3 subconjuntos se someten a fuerza bruta individualmente, de acuerdo con el siguiente procedimiento:
Cada candidato clave encontrado en la fase de reducción de claves ahora se prueba con otro par de texto plano/cifrado. Esto se hace simplemente viendo si el cifrado del texto plano, P, produce el texto cifrado conocido, C. Por lo general, aquí solo se necesitan unos pocos pares más, lo que hace que el ataque MITM de 3 subconjuntos tenga muy poca complejidad de datos.
El siguiente ejemplo se basa en el ataque realizado por Rechberger y Bogdanov a la familia de cifrado KTANTAN. Las convenciones de nomenclatura utilizadas en su artículo también se utilizan para este ejemplo. El ataque reduce la complejidad computacional de KTANTAN32 a , en comparación con un ataque de fuerza bruta. La complejidad computacional de 2014 todavía no es práctica de romper y, por lo tanto, el ataque no es computacionalmente factible a partir de ahora. Lo mismo ocurre con KTANTAN48 y KTANTAN64, cuyas complejidades se pueden ver al final del ejemplo.
El ataque es posible debido a las debilidades explotadas en la programación de claves bit a bit de KTANTAN. Es aplicable tanto a KTANTAN32, KTANTAN48 como a KTANTAN64, ya que todas las variaciones utilizan la misma programación de claves. No es aplicable a la familia KANTAN de cifrados de bloque relacionada, debido a las variaciones en la programación de claves entre KTANTAN y KANTAN.
KTANTAN es un cifrado de bloques liviano, destinado a plataformas restringidas como etiquetas RFID , donde una primitiva criptográfica como AES sería imposible (dado el hardware) o demasiado costosa de implementar. Fue inventado por Canniere, Dunkelman y Knezevic en 2009. [3] Toma un tamaño de bloque de 32, 48 o 64 bits y lo cifra utilizando una clave de 80 bits en 254 rondas. Cada ronda utiliza dos bits de la clave (seleccionados por el programa de claves ) como clave de ronda.
En preparación para el ataque, se identificaron debilidades en el programa clave de KTANTAN que permite el ataque MITM de 3 subconjuntos. Dado que sólo se utilizan dos puntas de llave en cada ronda, la difusión de la llave por ronda es pequeña; la seguridad reside en el número de rondas. Debido a esta estructura del programa de claves, fue posible encontrar una gran cantidad de rondas consecutivas, que nunca utilizaron ciertos bits de clave.
Más precisamente, los autores del ataque descubrieron que:
Esta característica del programa de claves se utiliza para preparar el ataque MITM de 3 subconjuntos, ya que ahora podemos dividir el cifrado en dos bloques con bits de clave independientes. Los parámetros para el ataque son así:
Se puede notar un problema con el paso 1.3 en la fase de reducción de claves. No es posible comparar directamente los valores de y , como se calcula al final de la ronda 111 y al comienzo de la ronda 131. Esto se mitiga con otra técnica MITM llamada coincidencia parcial . Al calcular hacia adelante a partir del valor intermedio y hacia atrás a partir del valor intermedio, los autores descubrieron que en la ronda 127, 8 bits seguían sin cambios en ambos y con una probabilidad de uno. Por lo tanto, solo compararon parte del estado, comparando esos 8 bits (eran 8 bits en la ronda 127 para KTANTAN32. Eran 10 bits en la ronda 123 y 47 bits en la ronda 131 para KTANTAN48 y KTANTAN64, respectivamente). Hacer esto produce más falsos positivos, pero nada que aumente notablemente la complejidad del ataque.
KTANTAN32 ahora requiere un promedio de 2 pares para encontrar el candidato clave, debido a los falsos positivos al coincidir solo en parte del estado de los valores intermedios. KTANTAN48 y KTANTAN64 en promedio todavía solo requieren un par de texto plano/cifrado para probar y encontrar las claves candidatas correctas.
Para:
Los resultados proceden del artículo de Rechberger y Bogdanov.
Este ya no es el mejor ataque a KTANTAN. El mejor ataque de 2011 lo contribuyeron Wei, Rechberger, Guo, Wu, Wang y Ling, que mejoraron el ataque MITM a la familia KTANTAN. [4] Llegaron a una complejidad computacional de 4 pares de texto plano/cifrado elegidos utilizando técnicas MITM de coincidencia parcial indirecta y empalme y corte.
