Reunión en el método del medio

En criptoanálisis , el método de encuentro en el medio o el “ ataque de encuentro en el medio ” es una clase de ataques a algoritmos criptográficos que reducen asintóticamente el tiempo de una enumeración completa debido al principio de “ divide y vencerás ”. , además de aumentar la cantidad de memoria necesaria . Este método fue propuesto por primera vez por Whitfield Diffie y Martin Hellman en 1977 [1] .

Condiciones iniciales

Se dan los textos abiertos (sin cifrar) y cifrados . Un criptosistema consta de ciclos de cifrado . Las claves cíclicas son independientes y no comparten bits comunes. La clave del sistema es una combinación de claves cíclicas . La tarea es encontrar la llave . $h$ $k$ $h$ ${\displaystyle k_{1},k_{2}...k_{h))$ $k$

Solución de caso simple

Un ejemplo simple es el cifrado de bloque secuencial doble con dos claves diferentes y . El proceso de cifrado se ve así: $K_1$ $K_{2}$

$s=ENC_{K_{2}}(ENC_{K_{1}}(p))$ ,

donde está el texto sin formato, es el texto cifrado y es la operación de cifrado de una sola vez con la clave . En consecuencia, la operación inversa, el descifrado, se ve así: $pags$ $s$ $ENC_{K_{i}}()$ $K_{yo}$

$p=ENC_{K_{1}}^{-1}(ENC_{K_{2}}^{-1}(s))$

A primera vista, parece que el uso de doble cifrado aumenta considerablemente la seguridad de todo el esquema, ya que ahora se deben clasificar dos claves y no una. En el caso del algoritmo DES , la seguridad aumenta de a . Sin embargo, no lo es. Un atacante puede crear dos tablas: $2^{56}$ $2^{112}$

Todos los valores para todos los valores posibles , $m_{1}=ENC_{K_{1}}(p)$ $K_1$
Todos los valores para todos los valores posibles . $m_{2}=ENC_{K_{2}}^{-1}(s)$ $K_{2}$

Entonces solo necesita encontrar coincidencias en estas tablas, es decir, tales valores y , que . Cada coincidencia corresponde a un conjunto de claves que satisface la condición. $m_1$ $m_2$ $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$ ${\ estilo de visualización (K_{1},K_{2})}$

Este ataque requirió operaciones de cifrado y descifrado (solo el doble que para la enumeración de una clave) y memoria. Optimizaciones adicionales: uso de tablas hash , cálculos para solo la mitad de las claves (para DES , la búsqueda exhaustiva, de hecho, solo requiere operaciones), pueden reducir estos requisitos. El resultado principal del ataque es que el cifrado secuencial de dos claves solo duplica el tiempo de fuerza bruta. ${\ estilo de visualización 2^{57}}$ ${\ estilo de visualización 2^{57}}$ $2^{55}$

Solución general

Denotemos la transformación del algoritmo como , donde es el texto sin formato y es el texto cifrado. Se puede representar como una composición , donde hay una transformación cíclica en la clave . Cada clave es un vector de longitud binario y la clave pública del sistema es un vector de longitud . $E_{k}(a)=b$ $a$ $b$ $E_{k_{1}}E_{k_{2}}...E_{k_{h}}(a)=b$ ${\ Displaystyle E_ {k_ {i}}}$ $k_i$ $k_i$ $norte$ ${\ estilo de visualización n \ veces h}$

Llenando la memoria

Todos los valores están ordenados , es decir, las primeras claves cíclicas. En cada una de esas claves, encriptamos el texto sin formato ( es decir, pasamos por ciclos de encriptación en lugar de ). Lo consideraremos como una determinada dirección de memoria y escribiremos el valor en esta dirección . Es necesario iterar sobre todos los valores . $k'=(k_{1},k_{2}...k_{r})$ $r$ $k'$ $a$ $E_{k'}(a)=E_{k_{1}}E_{k_{2}}...E_{k_{r}}(a)=S$ $r$ $h$ $S$ $k'$ $k'$

Definición clave

Todos los posibles están resueltos . En las claves recibidas , el texto cifrado se descifra . Si la dirección no está vacía, obtenemos la clave de allí y obtenemos un candidato clave . $k''=(k_{r+1},k_{r+2}...k_{h})$ $b$ $E_{k''}^{-1}(b)=E_{k_{h}}^{-1}...E_{k_{r+1}}^{-1}(b) =S'$ $S'$ $k'$ ${\ estilo de visualización (k', k'') = k}$

Sin embargo, debe tenerse en cuenta que el primer candidato recibido no es necesariamente la verdadera clave. Sí, para data y , pero en otros valores del texto cifrado de texto sin formato obtenido de la clave verdadera, se puede violar la igualdad. Todo depende de las características específicas del criptosistema . Pero a veces es suficiente obtener una clave "pseudoequivalente". En caso contrario, tras la realización de los trámites, se obtendrá un determinado conjunto de claves , entre las que se encuentra la clave verdadera. $k$ $a$ $b$ $E_{k}(a)=b$ $a'$ $b'$ $a'$ ${\ estilo de visualización {k', k''...))$

Si consideramos una aplicación específica, entonces el texto cifrado y el texto sin formato pueden ser grandes (por ejemplo, archivos gráficos) y representar una cantidad suficientemente grande de bloques para un cifrado de bloque . En este caso, para acelerar el proceso, puede cifrar y descifrar no todo el texto, sino solo su primer bloque (que es mucho más rápido) y luego, habiendo recibido muchos candidatos, busque la clave verdadera en él, verificándolo en los bloques restantes.

Ataque con la división de la secuencia de teclas en 3 partes

En algunos casos, puede ser difícil separar los bits de una secuencia de teclas en partes relacionadas con diferentes claves. En este caso, se utiliza el algoritmo de ataque MITM de 3 subconjuntos propuesto por Bogdanov y Richberger en 2011 basado en el método habitual de reunión en el medio. Este algoritmo es aplicable cuando no es posible dividir las secuencias de bits clave en dos partes independientes. Consta de dos fases: extracción y verificación de claves [2] .

Fase de extracción de claves

Al comienzo de esta fase, el cifrado se divide en 2 subcifrados y , como en el caso general del ataque, sin embargo, permite el posible uso de algunos bits de un subcifrado en otro. Entonces, si , entonces ; en este caso, los bits de la clave utilizados en se denotarán por , y en — por . Entonces la secuencia de teclas se puede dividir en 3 partes: $F$ $gramo$ $b=E_{k}(a)$ $E_{k}(*)=f(g(*))$ $k$ $F$ ${\ Displaystyle k_ {f}}$ $gramo$ $kg}$

$A_0$ es la intersección de los conjuntos y , ${\ Displaystyle k_ {f}}$ $kg}$
$A_{1}$ - bits clave que solo están en , ${\ Displaystyle k_ {f}}$
$A_{2}$ - bits de clave que solo están en . $kg}$

A continuación, se lleva a cabo un ataque por el método de reunión en el medio de acuerdo con el siguiente algoritmo:

Para cada elemento de $A_0$

Calcule el valor intermedio , donde está el texto sin formato, y son algunos bits clave de y , es decir, es el resultado del cifrado intermedio del texto sin formato en la clave . ${\ estilo de visualización i = f (k_ {f}, a)}$ $a$ ${\ Displaystyle k_ {f}}$ $A_0$ $A_{1}$ $i$ ${\ Displaystyle k_ {f}}$
Calcule el valor intermedio , donde está el texto privado, y son algunos bits de clave de y , es decir, es el resultado del descifrado intermedio del texto privado en la clave . $j=g^{-1}(k_{g},b)$ $b$ $kg}$ $A_0$ $A_{2}$ $j$ $kg}$
Compara y . En caso de coincidencia, obtenemos un candidato para las claves. $i$ $j$

Fase de validación de claves

Para verificar las claves, los candidatos recibidos se comparan con varios pares de textos público-privados conocidos. Por lo general, no se requiere una gran cantidad de tales pares de textos para la verificación [2] .

Ejemplo

Como ejemplo, tomemos un ataque a la familia de cifrado KTANTAN [3] , que hizo posible reducir la complejidad computacional de obtener una clave de (ataque de fuerza bruta) a [1] . $2^{80}$ ${\ estilo de visualización 2^{75,170}}$

Preparando un ataque

Cada una de las 254 rondas de cifrado que utilizan KTANTAN utiliza 2 bits aleatorios de la clave de un conjunto de 80 bits. Esto hace que la complejidad del algoritmo dependa únicamente del número de rondas. Al comenzar el ataque, los autores notaron las siguientes características:

En las rondas 1 a 111, no se utilizaron los siguientes bits de clave: . ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75))$
En las rondas 131 a 254, no se utilizaron los siguientes bits de clave: . ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74))$

Esto hizo posible dividir los bits clave en los siguientes grupos:

$A_0$ - bits de clave comunes: aquellos 68 bits no mencionados anteriormente.
$A_{1}$ - bits utilizados solo en el primer bloque de rondas (del 1 al 111),
$A_{2}$ - bits utilizados solo en el segundo bloque de rondas (del 131 al 254).

Fase uno: Extracción de claves

Hubo un problema al calcular los valores de y descritos anteriormente , ya que faltan las rondas de 112 a 130 en la consideración, pero luego se realizó una comparación parcial : los autores del ataque notaron una coincidencia de 8 bits en y , controlándolos con un ataque normal usando el método de reunión en el medio en la ronda 127. Al respecto, en esta fase se compararon los valores de estos 8 bits en los subcifrados y . Esto aumentó el número de candidatos clave, pero no la complejidad computacional. $i$ $j$ $i$ $j$ $i$ $j$

Segunda fase: verificación de claves

Para probar candidatos clave para el algoritmo KTANTAN32, se necesitó un promedio de dos pares de texto público-privado más para extraer la clave.

Resultados

KTANTAN32: complejidad computacional de adivinación de claves reducida al uso de tres pares de texto público-privado. ${\ estilo de visualización 2^{75,170}}$
KTANTAN48: Complejidad computacional de adivinación de claves reducida al uso de dos pares de texto público-privado. ${\ estilo de visualización 2 ^ {75,044}}$
KTANTAN64: Complejidad computacional de adivinación de claves reducida al uso de dos pares de texto público-privado. ${\ estilo de visualización 2 ^ {75,584}}$

Sin embargo, este no es el mejor ataque a la familia de cifrado KTANTAN. En 2011, se realizó un ataque [4] que redujo la complejidad computacional del algoritmo al uso de cuatro pares de texto abierto-cerrado. ${\ estilo de visualización 2^{72,9}}$

Ataque a un grafo bipartito completo

El ataque de gráfico bipartito completo se utiliza para aumentar el número de intentos de ataque de proxy mediante la creación de un gráfico bipartito completo . Propuesto por Diffie y Hellman en 1977.

Algoritmo multivariante

El algoritmo multidimensional de reunión en el medio se usa cuando se usa una gran cantidad de ciclos de cifrado con diferentes claves en cifrados de bloque . En lugar de la habitual "reunión en el medio", este algoritmo utiliza la división del criptotexto por varios puntos intermedios [5] .

Se supone que el texto atacado se cifra un cierto número de veces con un cifrado de bloque:

$C=ENC_{k_{n}}(ENC_{k_{n-1}}(...(ENC_{k_{1}}(P)))...))$ $P=DEC_{k_{1}}(DEC_{k_{2}}(...(DEC_{k_{n}}(C)))...))$

Algoritmo

Calculado:

sC_{1}=ENC_{f_{1}}(k_{f_{1}},P)

\forall k_{f_{1}}\in K

sC_{1}

se almacena junto con d .

k_{1}

H_1

sC_{n+1}=DEC_{b_{n+1}}(k_{b_{n+1}}),C)

\forall k_{b_{n+1}}\in K

sC_{n+1}

se almacena junto con d .

k_{b_{n+1))

{\ estilo de visualización H_ {b_ {n + 1}}}

Para cada estado intermedio posible , calcule: $s_{1}$

sC_{1}=DEC_{b_{1}}(k_{b_{1}},s_{1})

\forall k_{b_{1}}\in K

para cada coincidencia con un elemento de a , y se almacenan .

sC_{1}

H_1

T_{1}

{\ Displaystyle k_ {b_ {1}}}

{\ Displaystyle k_ {f_ {1}}}

sC_{2}=ENC_{f_{2}}(k_{f_{2}},s_{1})

\forall k_{f_{2}}\in K

{\ Displaystyle sC_ {2}}

guardado con en .

{\ Displaystyle k_ {f_ {2}}}

H_2

Para cada estado intermedio posible , calcule: $s_{2}$

sC_{2}=DEC_{b_{2}}(k_{b_{2}},s_{2})

\forall k_{b_{2}}\in K

para cada coincidencia con un elemento de , se comprueba una coincidencia con , después de lo cual y se almacenan en .

{\ Displaystyle sC_ {2}}

H_2

T_{1}

T_{2}

k_{b_{2))

{\ Displaystyle k_ {f_ {2}}}

sC_{3}=ENC_{f_{3}}(k_{f_{3}},s_{2})

\forall k_{f_{3}}\in K

sC_{3}

guardado con en .

k_{f_{3))

H_3

Para cada estado intermedio posible , calcule: $s_{n}$

sC_{n}=DEC_{b_{n}}(k_{b_{n}},s_{n})

\forall k_{b_{n}}\in K

y para cada coincidencia con un elemento de , se verifica una coincidencia con , después de lo cual y se almacenan en .

sC_{n}

H_n

{\ Displaystyle T_ {n-1}}

Tennesse}

{\ Displaystyle k_ {b_ {n}}}

{\ Displaystyle k_ {f_ {n}}}

sC_{n+1}=ENC_{f_{n+1}}(k_{f_{n+1}},s_{n})

\forall k_{f_{n+1}}\in K

y por cada coincidencia con , una coincidencia con

sC_{n+1}

H_{n+1}

Tennesse}

A continuación, la secuencia de candidatos encontrada se prueba en otro par de texto público-privado para confirmar la validez de las claves. Cabe señalar que el algoritmo es recursivo: la selección de claves para el estado se basa en los resultados para el estado . Esto introduce un elemento de complejidad exponencial en este algoritmo [5] . $s_{j}$ ${\ estilo de visualización s_ {j-1}}$

Dificultad

La complejidad temporal de este ataque es $2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}\cdot (2^{| k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}\cdot (2^{|k_{b_{2}}|} +2^{|k_{f_{3}}|}+...))$

Hablando de uso de memoria, es fácil ver que a medida que aumenta cada uno , se imponen más y más restricciones, lo que reduce la cantidad de candidatos escritos en él. Esto significa mucho menos . $i$ $T_{yo}$ ${\displaystyle T_{2},T_{3},...,T_{n))$ $T_{1}$

El límite superior de la cantidad de memoria utilizada:

2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s+n|}+...

donde es la longitud total de la clave.

k

La complejidad de usar los datos depende de la probabilidad de "pasar" una clave falsa. Esta probabilidad es igual a , donde es la longitud del primer estado intermedio, que suele ser igual al tamaño del bloque. Dado el número de candidatos clave después de la primera fase, la complejidad es . ${\ estilo de visualización 1/2 ^ {l}}$ $yo$ $2^{|k|-|l|}$

Como resultado, obtenemos , donde es el tamaño del bloque. ${\ estilo de visualización 2^{|k|-2b))$ ${\ estilo de visualización | b |}$

Cada vez que se prueba una secuencia de clave candidata en un nuevo par de texto público-privado, el número de claves que pasan la prueba se multiplica por la probabilidad de pasar la clave, que es . ${\ estilo de visualización 1/2 ^ {| b |}}$

Parte del ataque de fuerza bruta (comprobación de claves con nuevos pares de texto público-privado) tiene complejidad temporal , en la que, obviamente, los términos subsiguientes tienden a cero cada vez más rápido. $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$

Como resultado, la complejidad de los datos por juicios similares se limita a aproximadamente pares de claves públicas y privadas. $\left\lceil |k|/n\right\rceil$

Notas

↑ 12 Diffie , Whitfield; Hellman, Martin E. Criptoanálisis exhaustivo del estándar de cifrado de datos NBS (inglés) // Computadora: revista. - 1977. - junio ( vol. 10 , no. 6 ). - Pág. 74-84 . -doi : 10.1109/ CM.1977.217750 . Archivado desde el original el 14 de mayo de 2009.
↑ 1 2 Andrey Bogdanov y Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptoanalysis of the Lightweight Block Cipher KTANTAN" Archivado el 7 de noviembre de 2018 en Wayback Machine .
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. "KATAN & KTANTAN - A Family of Small and Efficient Hardware-Oriented Block Ciphers" Archivado el 20 de abril de 2018 en Wayback Machine .
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang y San Ling. "Cryptoanálisis mejorado de reunión en el medio de KTANTAN" Archivado el 7 de noviembre de 2018 en Wayback Machine .
↑ 1 2 3 Zhu, Bo; Guan Gong. Ataque MD-MITM y sus aplicaciones a GOST, KTANTAN y Hummingbird-2 (inglés) // eCrypt: revista. — 2011.

Literatura

Moore, Stephane. Ataques de reunión en el medio (neopr.) . - 2010. - 16 de noviembre. - S. 2 .