Ataque de cambio ( ing. slide attack ): ataque criptográfico , que es, en el caso general, un ataque basado en texto sin formato seleccionado , que permite el criptoanálisis de cifrados de múltiples rondas en bloque, independientemente de la cantidad de rondas utilizadas. Propuesto por Alex Biryukov y David Wagner en 1999 [1] .
La idea de crear un ataque de cizalla surgió por primera vez con Edna Grossman y Brian Tuckerman en 1977. El informe correspondiente fue publicado [2] conjuntamente con IBM . Grossman y Tuckerman pudieron mostrar la posibilidad de un ataque a un cifrado New Data Seal (NDS) bastante débil . El ataque explota el hecho de que el cifrado en cada ronda solo mezcla la misma clave, usando la misma tabla en cada ronda. El uso de textos sin formato evita esto y nos permite considerarlo como la primera versión del ataque shift.
En 1990, se propuso el criptoanálisis diferencial , demostrando la vulnerabilidad de los criptosistemas similares a DES de rondas múltiples [3] . Una forma de garantizar su fortaleza criptográfica fue aumentar la cantidad de rondas utilizadas, lo que aumentó la complejidad computacional del ataque en proporción a su número. El uso de esta mejora para muchos algoritmos de cifrado se basó, en particular, en el juicio empírico de que cualquiera, incluso los cifrados más débiles, pueden volverse criptográficamente fuertes repitiendo las operaciones de cifrado muchas veces:
Con la excepción de unos pocos casos degenerados, el algoritmo puede hacerse arbitrariamente seguro aumentando el número de rondas.
Texto original (inglés)[ mostrarocultar] Excepto en unos pocos casos degenerados, un algoritmo puede hacerse arbitrariamente seguro agregando más rondas. — B. Preneel, V. Rijmen, A. Bosselears: Principios y rendimiento de los algoritmos criptográficos [4]Por ejemplo, algunos cifrados propuestos como candidatos para la competencia AES en 1997 tenían un número bastante grande de rondas: RC6(20), MARS(32), SERPENT(32), CAST(48) [1] .
Sin embargo, en 1999, se publicó un artículo de Alex Biryukov y David Wagner que describía un ataque de cizalla, que refutó esta suposición. Una característica de este ataque fue que no dependía del número de rondas de cifrado; su éxito requería solo la identidad de las rondas y la posibilidad de criptoanálisis de la función de cifrado en una ronda separada. El artículo también describe la aplicación de este ataque al cifrado TREYFER y versiones simplificadas de los cifrados DES (2K-DES) y BLOWFISH [1] .
En 2000, se publicó un segundo artículo que demostraba versiones mejoradas del ataque de cambio: "Deslizamiento con un giro" y "Deslizamiento de complemento", lo que permite extenderlo a cifrados cuyas rondas tienen pequeñas diferencias. Entonces, con la ayuda de estas mejoras, se descifraron algunas modificaciones del cifrado DES , así como una versión simplificada de 20 rondas del estándar de cifrado GOST 28147-89 [5] [6] .
En el caso más simple [7] , se aplica un ataque de desplazamiento a los algoritmos de cifrado, que son múltiples repeticiones de alguna función de cifrado , cuya entrada en cada ronda es el texto cifrado (el resultado del cifrado en la ronda anterior) y alguna clave de ronda. , que es el mismo para todas las rondas. Los requisitos principales para la implementación exitosa de este ataque son [7] :
En el caso de los cifrados de bloque modernos, las claves redondas no suelen ser las mismas. Esto lleva al hecho de que el algoritmo utilizado en la construcción del ataque más simple es generalmente inaplicable para tales cifrados y requiere algunas adiciones.
Sea un algoritmo de encriptación No. 1, que consiste en bloques, tal que la clave se use en la ronda th (supondremos que el número total de claves , la clave se necesitará más adelante), y elijamos algún par de "texto plano - texto cifrado" . A la salida de la primera ronda, obtenemos el texto , donde está la función de cifrado.
Además, el ataque de cambio implica cifrar el texto con un nuevo cifrado de bloque No. 2, que consta de bloques de a . Denotemos el texto cifrado en la salida del bloque -th como . Es fácil ver que en este caso, a la salida del i-ésimo bloque, obtendremos el texto que ya se encuentra arriba , lo que significa que el texto y el texto cifrado están relacionados por la relación .
Así, hemos obtenido un par que satisface las relaciones y , que no es más que un par de desplazamiento general. Por tanto, en el caso más simple, estas relaciones tomarán la forma y .
Suponiendo que algún texto esté relacionado con la proporción , debemos obtener el texto cifrado en la salida del algoritmo de cifrado n.° 2 con el texto en la entrada, para confirmarlo o refutarlo mediante las proporciones . En el caso de un programa de clave trivial, los algoritmos de cifrado n.º 1 y n.º 2 son idénticos, lo que significa que se puede obtener cifrando el texto con un cifrado de bloque ya existente. De lo contrario, los algoritmos de cifrado n.° 1 y n.° 2 son diferentes, y el criptoanalista no puede construir el algoritmo n.° 2, lo que significa que no se puede obtener el texto cifrado.
Como se mencionó en las notas del algoritmo de ataque, el caso de criptoanálisis de cifrados con autosimilitud de ronda p se puede reducir fácilmente al caso más simple de un ataque de cambio combinando varias rondas en una, lo que equivale a cambiar bloques de cifrado por rondas En el caso de una red Feistel con alternancia de claves redondas y , es decir, Con la autosimilitud de dos rondas, este enfoque puede aumentar la complejidad del criptoanálisis y, por lo tanto, hacer que el ataque de desplazamiento sea ineficaz. En cambio, se propuso, como antes, cambiar solo una ronda en lugar de dos, pero al mismo tiempo cambiar ligeramente los requisitos impuestos al par de turnos.
En la descripción del problema considerado anteriormente, se indicó que para buscar un par de desplazamiento, en el caso general, es necesario poder trabajar con cifrados de dos bloques: el original, que consta de bloques de a , y el nuevo, que consta de bloques de a . La diapositiva de complementación le permite trabajar solo con el cifrado de bloque original.
Aunque el siguiente razonamiento se demostrará utilizando un cifrado de 4 rondas, se puede extender a cualquier número de rondas. Primero, veamos cómo cambia el texto sin formato en diferentes rondas de encriptación. Representemos el texto sin formato como , donde y son las partes izquierda y derecha del texto, respectivamente.
Número redondeado | Lado izquierdo | parte derecha |
---|---|---|
una | ||
2 | ||
3 | ||
cuatro |
Denotemos el texto en la salida de la ronda 1 y el texto cifrado . Ahora, tenga en cuenta que para encontrar el texto cifrado en la salida de un cifrado de bloque de 4 rondas con un programa clave , es suficiente agregar la diferencia al lado derecho de cada ronda del cifrado original y luego cifrar el texto con el cifrado resultante (Fig. 2, diagrama de la derecha). Para ello, proporcionaremos el texto a la entrada del cifrado inicial . Denotemos el texto cifrado como . Consideremos cómo cambia el texto en diferentes rondas de encriptación.
Número redondeado | Lado izquierdo | parte derecha |
---|---|---|
una | ||
2 | ||
3 | ||
cuatro |
De esto se puede ver que la diferencia introducida se conserva en cada ronda, lo que significa que los textos cifrados y están relacionados por las relaciones: y , y los pares "texto simple - texto cifrado" y por las relaciones y .
Si los textos están relacionados por una razón , se dice que los textos y tienen una diferencia de corte (en inglés , slide difference ) .
Así, se obtienen las siguientes ecuaciones para el par de cortantes:
Como antes, en el caso de textos de bits, se requieren textos sin formato para encontrar el par de desplazamiento . El par de cortante ahora debe satisfacer la ecuación (ver Fig. 2). En el caso de encontrar un par de desplazamiento potencial, la segunda ecuación permite encontrar un candidato , y si la función es lo suficientemente vulnerable al criptoanálisis, entonces estas ecuaciones nos permiten encontrar las claves deseadas potenciales y . Después de eso, solo queda comprobar si hay falsos positivos.
Deslizarse con un giro [ 5 ]El requisito especificado en el enunciado del problema para poder trabajar con el cifrado n.º 1 original, que consta de bloques desde hasta , y el nuevo cifrado n.º 2, que consta de bloques desde hasta , se puede transformar fácilmente mediante el llamado shift- y enfoque de rotación.
Si excluimos la última permutación de las partes izquierda y derecha del texto e invertimos el orden de las claves, entonces el descifrado en la red Feistel ocurrirá exactamente de la misma manera que el cifrado [1] . El enfoque de cambio y rotación utiliza esta propiedad, es decir, propone utilizar el algoritmo de descifrado como cifrado n.º 2 (consulte la figura 3).
Este enfoque no tiene diferencias fundamentales con el algoritmo más simple. Como en el caso más simple, los requisitos para el par de turnos , donde . Así, obtenemos las ecuaciones:
y una condición que hace que sea más fácil encontrar pares de cambios:
Como de costumbre, en el caso de textos de bits, se necesitan textos sin formato para encontrar el par de desplazamiento . Si se encuentra, la vulnerabilidad de la función le permite encontrar la clave de las ecuaciones .
El número de textos requeridos en este paso se puede reducir a . Para hacer esto, ciframos varios textos del formulario y desciframos varios textos del formulario , donde y son fijos y cumplen la condición . Por lo tanto, dado que ahora estamos trabajando, de hecho, con textos de bits, de acuerdo con la paradoja del cumpleaños, entre estos pares de "texto sin formato-texto cifrado", existe una alta probabilidad de un par de cambio.
La clave se puede encontrar aplicando el método descrito para el caso general de cifrados de bloque con autosimilitud de ronda p, es decir, combinando cada dos rondas posteriores en una; por lo tanto, reducimos el problema al caso más simple. Aunque el tamaño de la clave redonda se duplicará, esto no complicará el criptoanálisis, ya que la clave , que es la mitad de la nueva clave redonda, ya se conoce, y necesitamos encontrar solo la segunda mitad, igual en tamaño a la clave redonda. clave en el problema original.
Se puede considerar una modificación separada del uso simultáneo de los dos enfoques descritos anteriormente: deslizamiento de complemento y deslizamiento con un giro, que permite extender el ataque de cambio a cifrados con autosimilitud de 4 rondas [5] .
El problema del criptoanálisis de cifrados con rondas desiguales difiere de todos los casos considerados hasta ahora, en cuya solución no se puede utilizar ninguna de las modificaciones de ataque consideradas. Para el caso de tales cifrados, se propuso un ataque deslizante de realineación [ 8 ] , demostrado en el ejemplo de modificaciones del cifrado DES , en particular, en el ejemplo de la versión completa de 16 rondas de DES
El ataque lineal deslizante ( en inglés slide-linear attack ) [9] es un ejemplo de la implementación de un ataque de desplazamiento utilizando los principios del criptoanálisis lineal . El trabajo de este ataque se mostró en el cifrado 4K-DES.
También hay mejoras para acelerar la implementación de modificaciones ya existentes del ataque de corte. En particular, una de estas mejoras, descrita en el trabajo de Eli Biham, Orr Dunkelman, Nathan Keller: Enhanced Slide Attacks [10] , hace posible encontrar pares de turnos mucho más rápido utilizando una estructura de cifrado cíclico y las permutaciones de clave correspondientes. El funcionamiento de esta modificación se mostró en el ejemplo de varias variantes del cifrado GOST 28147-89 (GOST).
Además de su propósito original: atacar cifrados de bloque, los principios del ataque de cambio también han encontrado aplicación en el campo del criptoanálisis de funciones hash. Al igual que en el caso de los cifrados de bloque, donde se ha utilizado un ataque de desplazamiento para encontrar el programa clave, se ha demostrado que es potencialmente aplicable para encontrar la clave secreta utilizada para generar y validar el hash del mensaje transmitido. En particular, este enfoque se demostró en el ejemplo de generación de inserción simulada (MAC) .
El ataque shift también resultó ser útil no solo en el caso de funciones hash criptográficas que toman el valor de alguna clave secreta como parámetro, sino también en el caso de funciones hash que producen un hash basado únicamente en un mensaje. Un análisis de tales funciones basado en un ataque de cambio permite identificar, con un alto grado de probabilidad, algunas propiedades de cambio y, como resultado, ciertos patrones en la operación de los algoritmos hash.
Dado que las vulnerabilidades de la programación clave se utilizan durante el ataque de turno, una de las medidas es complicarlo. En particular, es necesario evitar repeticiones cíclicas en el programa clave si es posible, o al menos utilizar un período de repetición suficientemente grande. En el caso de un pequeño número de claves, en lugar de una simple repetición periódica, se debe utilizar algún orden aleatorio de su secuencia.
Además de la debilidad del calendario clave, el ataque por turnos también explota las mismas rondas. Una forma de evitar esto es usar algunas constantes de ronda diferentes como parámetro de la función de encriptación en rondas separadas; esto le permite hacer diferencias en la operación de bloques de encriptación individuales sin complicar significativamente el algoritmo de encriptación como un todo.
Además, la efectividad de un ataque de turno puede reducirse significativamente aumentando la fuerza criptográfica de la función de cifrado circular. Por lo tanto, su resistencia a los ataques basados en textos sin formato hará que sea mucho más difícil encontrar la clave redonda, incluso en presencia de un par de turnos.