La coincidencia parcial es una técnica que se puede utilizar con un ataque MITM . La coincidencia parcial es cuando los valores intermedios del ataque MITM y , calculados a partir del texto sin formato y el texto cifrado, coinciden solo en unos pocos bits seleccionados, en lugar de en el estado completo.
Una limitación de los ataques MITM es la cantidad de valores intermedios que deben almacenarse. Para comparar los valores intermedios y , todos deben calcularse y almacenarse primero, antes de que cada uno de los calculados pueda compararse con ellos. Si los dos subcifrados identificados por el ataque MITM tienen una subclave suficientemente grande, entonces es necesario almacenar una cantidad inviable de valores intermedios. Si bien existen técnicas como los algoritmos de detección de ciclos [1] que permiten realizar un ataque MITM sin almacenar todos los valores de o , estas técnicas requieren que los subcifrados del ataque MITM sean simétricos. Por lo tanto, es una solución que permite realizar un ataque MITM en una situación en la que las subclaves tienen una cardinalidad lo suficientemente grande como para hacer que la cantidad de valores temporales que deben almacenarse sea inviable. Si bien esto permite almacenar más valores temporales, su uso aún es limitado, ya que solo permite realizar un ataque MITM en un subcifrado con unos pocos bits más. Como ejemplo: si solo se almacena 1/8 del valor intermedio, entonces la subclave solo necesita ser 3 bits más grande, antes de que se requiera la misma cantidad de memoria de todos modos, ya que
En la mayoría de los casos, una característica mucho más útil proporcionada por la coincidencia parcial en los ataques MITM es la capacidad de comparar valores intermedios calculados en diferentes rondas en el cifrado atacado. Si la difusión en cada ronda del cifrado es lo suficientemente baja, podría ser posible en un lapso de rondas encontrar bits en los estados intermedios que no hayan cambiado con una probabilidad de 1. Estos bits en los estados intermedios aún se pueden comparar.
La desventaja de ambos usos es que habrá más falsos positivos para los candidatos clave, que deben probarse. Como regla general, la probabilidad de un falso positivo viene dada por la probabilidad , donde es la cantidad de bits coincidentes.
Para ver un ejemplo paso a paso del ataque completo a KTANTAN, [2] consulte el ejemplo en la página MITM de 3 subconjuntos . Este ejemplo solo trata la parte que necesita una coincidencia parcial. Lo que es útil saber es que KTANTAN es un cifrado de bloques de 254 rondas, donde cada ronda utiliza 2 bits de la clave de 80 bits.
En el ataque de 3 subconjuntos a la familia de cifrados KTANTAN, fue necesario utilizar una coincidencia parcial para organizar el ataque. Se necesitaba una coincidencia parcial, porque los valores intermedios del texto plano y cifrado en el ataque MITM se calcularon al final de la ronda 111 y al comienzo de la ronda 131, respectivamente. Como tenían un lapso de 20 rondas entre ellos, no se podían comparar directamente.
Los autores del ataque, sin embargo, identificaron algunas características útiles de KTANTAN que se mantenía con una probabilidad de 1. Debido a la baja difusión por ronda en KTANTAN (la seguridad está en el número de rondas), lo descubrieron calculando los avances de ronda 111 y hacia atrás desde la ronda 131 que en la ronda 127, 8 bits de ambos estados intermedios permanecerían sin cambios. (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). Al comparar solo los 8 bits de cada valor intermedio, los autores pudieron orquestar un ataque MITM al cifrado, a pesar de que había 20 rondas entre los dos subcifrados.
El uso de coincidencias parciales aumentó la cantidad de falsos positivos, pero nada que aumentara notablemente la complejidad del ataque.
