El ataque de encuentro en el medio de 3 subconjuntos (en adelante, MITM ) es una variante del ataque de encuentro en el medio genérico , que se utiliza en criptología para el criptoanálisis de cifrados de hash y de bloques . La variante de 3 subconjuntos abre la posibilidad de aplicar ataques MITM a los cifrados, donde no es trivial dividir los bits de clave en dos espacios de clave independientes, como lo requiere el ataque MITM.
La variante de 3 subconjuntos relaja la restricción de que los espacios de claves sean independientes, moviendo las partes que se cruzan de los espacios de claves a un subconjunto, que contiene los bits de clave comunes entre los dos espacios de claves.
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 variantes desde que Diffie y Hellman sugirieron los ataques MITM. Estas variantes hacen que los ataques MITM sean más efectivos o permiten que se los use en situaciones en las que la variante básica no puede. La variante de 3 subconjuntos fue presentada por Bogdanov y Rechberger en 2011 [2] y ha demostrado su uso en el criptoanálisis de cifrados, como la familia de cifrados de bloque ligeros 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 candidatos a claves mediante la aplicación del ataque MITM. En la segunda fase, los candidatos a claves encontrados se prueban en otro par de texto simple/cifrado para filtrar las claves incorrectas.
En la fase de reducción de clave, el cifrado atacado se divide en dos subcifrados y , cada uno con sus bits de clave independientes, como es normal en los ataques MITM. En lugar de tener que cumplir con la limitación de que los bits de 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 atacan de forma individual, según el siguiente procedimiento:
Cada candidato a clave encontrado en la fase de reducción de claves se prueba ahora con otro par de texto simple/cifrado. Esto se hace simplemente observando si el cifrado del texto simple, P, produce el texto cifrado conocido, C. Por lo general, solo se necesitan algunos otros pares aquí, lo que hace que el ataque MITM de 3 subconjuntos tenga una complejidad de datos muy pequeña.
El siguiente ejemplo se basa en el ataque realizado por Rechberger y Bogdanov a la familia de cifrados KTANTAN. Las convenciones de nombres utilizadas en su artículo también se utilizan para este ejemplo. El ataque reduce la complejidad computacional de KTANTAN32 a , por debajo de si se compara con un ataque de fuerza bruta. Una complejidad computacional de es 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 el esquema de claves bit a bit de KTANTAN. Es aplicable tanto a KTANTAN32, KTANTAN48 como a KTANTAN64, ya que todas las variantes utilizan el mismo esquema de claves. No es aplicable a la familia de cifrados en bloque KANTAN relacionada, debido a las variaciones en el esquema de claves entre KTANTAN y KANTAN.
KTANTAN es un cifrador de bloques ligero, pensado para plataformas limitadas como las etiquetas RFID , donde una primitiva criptográfica como AES sería imposible (dado el hardware) o demasiado cara 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 esquema de claves de KTANTAN que permite el ataque MITM de 3 subconjuntos. Dado que solo se utilizan dos bits de clave por ronda, la difusión de la clave por ronda es pequeña: la seguridad reside en el número de rondas. Debido a esta estructura del esquema 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 encontraron que:
Esta característica de la programación de claves se utiliza para preparar el ataque MITM de tres subconjuntos, ya que ahora podemos dividir el cifrado en dos bloques con bits de clave independientes. Los parámetros para el ataque son los siguientes:
Se puede notar un problema con el paso 1.3 en la fase de reducción de clave. No es posible comparar directamente los valores de y , ya que se calcula al final de la ronda 111, y se calcula al comienzo de la ronda 131. Esto se mitiga con otra técnica MITM llamada coincidencia parcial . Los autores descubrieron al calcular hacia adelante desde el valor intermedio y hacia atrás desde el valor intermedio 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, al comparar 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 la complejidad del ataque de manera notable.
Actualmente, KTANTAN32 requiere, en promedio, dos pares para encontrar el candidato a clave, debido a los falsos positivos que se producen al coincidir solo con una parte del estado de los valores intermedios. KTANTAN48 y KTANTAN64, en promedio, todavía requieren solo un par de texto simple/cifrado para probar y encontrar los candidatos a clave correctos.
Para:
Los resultados están tomados del artículo de Rechberger y Bogdanov.
Este ya no es el mejor ataque a KTANTAN. El mejor ataque hasta 2011 es obra de Wei, Rechberger, Guo, Wu, Wang y Ling, quienes mejoraron el ataque MITM a la familia KTANTAN. [4] Llegaron a una complejidad computacional de con 4 pares de texto simple/cifrado elegidos utilizando técnicas de emparejamiento parcial indirecto y corte y empalme MITM.
