Ataque bumerán

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de diciembre de 2014; las comprobaciones requieren 34 ediciones .

Un ataque boomerang es un ataque criptográfico a un cifrado de bloque basado en métodos de criptoanálisis diferencial . El algoritmo de ataque fue publicado en 1999 por el profesor de la Universidad de Berkeley, David Wagner, quien lo usó para descifrar los cifrados COCONUT98 , Khufu y CAST-256 [1] .

Este método hizo posible llevar a cabo ataques exitosos en muchos cifrados previamente reconocidos como resistentes al criptoanálisis diferencial "clásico".

Hay modificaciones de este método de criptoanálisis: ataque de boomerang mejorado (ataque de boomerang amplificado) y ataque rectangular (ataque de rectángulo).

Características generales

El ataque boomerang se basa en los principios del criptoanálisis diferencial . El método boomerang consiste en utilizar un cuarteto de textos sin formato y sus correspondientes textos cifrados, en lugar de un par, como en el criptoanálisis diferencial.

Otra diferencia notable entre el método boomerang y el criptoanálisis diferencial clásico, donde los cambios en el texto cifrado causados por cambios en el texto sin formato cubren todo el cifrado, es que los cambios en el texto sin formato solo pueden cubrir parte del cifrado.

En algunos casos, el uso de este método de ataque puede reducir significativamente la cantidad de datos necesarios (en comparación con el criptoanálisis diferencial). Además, el ataque es aplicable a algoritmos con una estructura redonda heterogénea.

Una de las características más interesantes del algoritmo de ataque es que funciona muy bien con cifrados que tienen funciones de ronda asimétricas. Las funciones de ronda asimétrica se pueden dividir en dos tipos: rondas de tipo A, que tienen una mejor difusión hacia adelante que hacia atrás, y rondas de tipo B, que tienen una mejor difusión hacia atrás. Se observa que si la primera mitad del cifrado consta de rondas de tipo B y la segunda de rondas de tipo A, dicho cifrado será más vulnerable a un ataque de boomerang.

Algoritmo de ataque

Supongamos primero que el algoritmo de cifrado se puede dividir en dos partes consecutivas, aproximadamente iguales en complejidad , y , y , donde hay texto sin formato. Por ejemplo, un algoritmo DES de 16 rondas con rondas de estructura similar se puede dividir en dos partes de 8 rondas $mi$ $E_{0}$ $E_1$ $E(M)=E_{1}(E_{0}(M))$ $METRO$
Elijamos un par de textos abiertos y con diferencia . Como resultado del procesamiento de estos textos por la función, obtenemos la diferencia $PAGS$ $P^{'}$ $\Delta =P\o más P'$ $E_{0}$ $\Delta ^{*}=E_{0}(P)\o más E_{0}(P^{'})$
Continuamos cifrando textos sin formato y funciones y obtenemos dos textos cifrados y $PAGS$ $PAGS'$ $E_1$ $C=E_{1}(E_{0}(P))$ $C^{'}=E_{1}(E_{0}(P^{'}))$
Usamos y para obtener otros dos textos cifrados y asociados a la diferencia anterior $C$ $C^{'}$ $D$ $D^{'}$ $\nabla =C\oplus D=C^{'}\oplus D'$
Además, la formación del cuarteto continúa en la dirección opuesta: las funciones de "semidescifrado" se aplican a y y para obtener la diferencia $D$ $D^{'}$ $E_{{1}}^{{-1}}$ $E_{{0}}^{{-1}}$ $\nabla ^{*}=E_{{1}}^{{-1}}(D)\oplus E_{{0}}(P)=E_{{1}}^{{-1}}(D ^{'})\oplus E_{{0}}(P^{'})$
Descifrado adicional de textos cifrados y da dos textos sin formato y $D$ $D^{'}$ $Q=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D))$ $Q^{'}=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D^{'}))$

Además, en su trabajo [1] , Wagner prueba que la diferencia entre los textos claros así obtenidos y es igual a la diferencia entre los textos claros originales y y es igual a . $q$ $P^{'}$ $PAGS$ $P^{'}$ $\Delta$

Al analizar un conjunto de cuartetos de textos con una cierta diferencia, se puede seleccionar una determinada clave (o su fragmento), que es la clave deseada sin ambigüedades o con la probabilidad más alta (en comparación con otras claves).

Ataque boomerang mejorado [2]

El ataque de boomerang mejorado es un ataque de texto sin formato , mientras que el ataque de boomerang clásico es un ataque de texto sin formato elegido de forma adaptativa .

Al comparar estos dos algoritmos, en igualdad de condiciones, el ataque boomerang clásico requiere muchos menos datos que el mejorado. A primera vista, tal cambio en el algoritmo no trae beneficios. Sin embargo, hay tres puntos que lo distinguen del ataque clásico, que hacen que valga la pena usar un ataque mejorado en algunos casos:

En un ataque de texto sin formato, es posible adivinar la clave al final del cifrado sin tener que aumentar el número de textos sin formato elegidos.
Es posible aplicar un ataque boomerang mejorado no solo a pares, sino también a K-sets de textos.
Se puede usar un ataque de refuerzo para obtener un par (o K) de textos para alguna parte del cifrado y luego usar otros algoritmos para las rondas restantes del cifrado. Por lo tanto, se puede usar el criptoanálisis diferencial truncado , que define solo una pequeña parte del bloque, y no se puede usar con un ataque de boomerang estándar.

Algoritmos de cifrado vulnerables a ataques boomerang

Descrito en el artículo original [1]

COCONUT98 se descompone con textos sin formato y textos cifrados elegidos de forma adaptativa . $2^{16}$
El Khufu de 16 rondas se descifra con textos sin formato y textos cifrados elegidos de forma adaptativa. $2^{18}$
Grietas CAST-256 de 16 rondas con textos conocidos. $2^{{49.3}}$

Descrito en otras fuentes

El KASUMI de 6 rondas se descifra con textos sin formato y cifrados elegidos de forma adaptativa [3] . $2^{13}$
Grietas MARS de 11 rondas con textos famosos [2] . $2^{{65}}$
Grietas de serpiente de 8 rondas con letras famosas [2] . $2^{{114}}$
Grietas AES de 5 rondas con textos conocidos [4] . $2^{{39}}$
Grietas AES de 6 rondas con textos conocidos [4] . $2^{{71}}$

Aplicación a AES completo [5]

Los principios del ataque boomerang y el ataque boomerang mejorado se aplicaron para realizar un ataque de clave vinculada en cifrados completos AES -192 y AES-256. Este método se basa en la detección de colisiones locales en cifrados de bloque y el uso de interruptores boomerang.

De forma predeterminada, el cifrado se divide en rondas, pero esta división no siempre es la mejor para un ataque de boomerang. Se propuso dividir las rondas en operaciones simples y utilizar el paralelismo existente en estas operaciones. Por ejemplo, algunos bytes se pueden procesar de forma independiente. En tal caso, el algoritmo de cifrado puede procesar primero un byte antes de la conversión, después de lo cual pasa a procesar otro byte después de la conversión. Hay interruptores de escalera, interruptores Feistel e interruptores s-box.

Este método de ataque es más efectivo que el ataque de fuerza bruta . Pero al mismo tiempo, se observa que el método es principalmente de valor teórico para los especialistas y no representará una amenaza para las implementaciones prácticas de AES en el futuro cercano debido a los altos requisitos de tiempo de procesamiento y potencia informática. Por otro lado, esta técnica se puede aplicar con bastante eficacia a los ataques de función hash criptográfica .

Aplicación a funciones hash

Dado que muchas funciones hash se basan en cifrados de bloques , es natural intentar ataques boomerang sobre ellas, pero existen varios obstáculos. En particular, el descifrado, que es una parte integral de un ataque boomerang, puede no estar disponible en el contexto de las funciones hash.

Sin embargo, se ha demostrado [6] que un ataque boomerang, es decir, una variante del mismo, un ataque boomerang basado en texto sin formato mejorado, se puede utilizar para descifrar una función hash. Este tipo de ataque proporciona una mejora sobre los ataques diferenciales utilizados anteriormente .

La idea principal de la adaptación de ataque es utilizar, además de la ruta diferencial global cuidadosamente elegida que se usa en los ataques diferenciales clásicos, varias rutas diferenciales adicionales que son muy buenas en un número limitado de etapas, pero que no cubren toda la función por completo. . Para combinar estas rutas diferenciales, se utiliza un esquema de ataque de cifrado de bloque básico que utiliza el método boomerang.

Este ataque se ha aplicado con éxito al algoritmo SHA-1 .

Desventajas del algoritmo

Un ataque boomerang es una elección adaptativa de ataque de texto plano y de texto cifrado. Este es uno de los tipos de ataques criptográficos más difíciles de implementar en la práctica.

En cuanto al método de criptoanálisis diferencial, la aplicación práctica del ataque boomerang está limitada por los altos requisitos de tiempo de procesamiento y volumen de datos.

En la práctica, el ataque boomerang se aplicó principalmente a cifrados con un número reducido de rondas.

En este sentido, el algoritmo es más un logro teórico.

Notas

↑ 1 2 3 David Wagner. El Ataque Boomerang .
↑ 1 2 3 John Kelsey , Tadayoshi Kohno, Bruce Schneier . Ataques de boomerang amplificados contra MARS y Serpent de ronda reducida .
↑ Eli Biham , Orr Dunkelman, Nathan Keller. Un ataque de rectángulo de clave relacionada en el KASUMI completo .
↑ 12 Alex Biryukov . El Ataque Boomerang en AES Reducido de 5 y 6 rondas .
↑ Alex Biryukov , Dmitry Khovratovich. Criptoanálisis de clave relacionada de Full AES-192 y AES-256 .
↑ Antoine Joux, Thomas Peyrin. Funciones Hash y el Ataque Boomerang (Amplificado) .

Literatura

Panasenko S. P. Algoritmos de cifrado. Libro de referencia especial - San Petersburgo. : BHV-SPb , 2009. - 576 p. — ISBN 978-5-9775-0319-8