Ataque de cizalla

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 6 de mayo de 2018; las comprobaciones requieren 9 ediciones .

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] .

Historial de creación

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] .

Descripción general

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] :

  1. Identidad de rondas (que se garantiza usando la misma función y la misma clave en cada ronda)
  2. La capacidad de encontrar fácilmente la clave , conociendo el texto en la entrada y el texto en la salida de alguna ronda .

El algoritmo del ataque más simple

Paso 1. Tomemos un poco de texto sin formato en la entrada y el texto cifrado correspondiente en la salida del algoritmo de cifrado. Paso 2. Tome algún otro texto sin formato y su correspondiente texto cifrado de modo que el par sea diferente del par ya elegido . Paso 3. Supongamos que está relacionado con la relación = , y está relacionado con la relación , es decir y son los resultados del cifrado de una ronda y respectivamente. Llamemos a ese par un "par deslizante" (par deslizado) [1] . Usando la afirmación de que la clave de encriptación se puede calcular fácilmente, conociendo el texto en la entrada y el texto en la salida de alguna ronda, calculamos la clave en la primera ronda de encriptación por la relación y la clave en la última ronda de cifrado por la relación . Paso 4. Comprobemos la igualdad . Porque por condición, todas las claves de ronda son iguales, entonces esta igualdad debe ser satisfecha, de lo contrario la suposición hecha en el paso 3 es incorrecta, y es necesario volver al paso 2, excluyendo el par probado de la lista de posibles candidatos. El cumplimiento de la igualdad indica que la clave es potencialmente la clave redonda deseada. Paso 5. Para verificar la clave encontrada en busca de falsos positivos, debe sustituirla en el algoritmo de encriptación y verificar la operación correcta en varios pares conocidos diferentes de "texto sin formato - texto cifrado ". A pesar de que es posible que la clave equivocada pase esta prueba, en el caso de buenos cifrados, la probabilidad de que esto ocurra es extremadamente pequeña [7] , lo que significa que la clave verificada es con una alta probabilidad la clave redonda deseada. Así, en caso de verificación exitosa, declaramos la clave a buscar, de lo contrario volvemos al paso 2, excluyendo el par verificado y la clave de la lista de posibles candidatos.

Notas sobre el algoritmo

Cambio de modificaciones de ataque

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.

Planteamiento del problema

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.

El caso de una red de Feistel con autosimilitud de dos vueltas

Diapositiva  de complementación [ 5 ]

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.

Otras modificaciones

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).

Algoritmos de cifrado vulnerables al ataque de cambio y sus modificaciones

Descrito en los artículos originales: [1] [5]

Descrito en otras fuentes

Ataques de desplazamiento de la clase de funciones hash [13]

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.

Funciones hash vulnerables al ataque shift: [13]

Formas de aumentar la resistencia criptográfica a las modificaciones de los ataques de desplazamiento [7] [16]

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.

Notas

  1. 1 2 3 4 5 6 7 Alex Biryukov, David Wagner. Ataques deslizantes  //  Cifrado rápido de software. Sexto Taller Internacional, FSE'99 Roma, Italia, 24 al 26 de marzo de 1999 Actas. - Springer Berlín Heidelberg, 1999. - Pág. 245-259 . - ISBN 978-3-540-66226-6 .  (enlace no disponible)
  2. EK Grossman, Thomas J. Watson División de investigación del Centro de investigación de IBM, B. Tuckerman. Análisis de un cifrado tipo Feistel debilitado por no tener clave giratoria . - IBM Thomas J. Watson Research Division, 1977. - 33 p.
  3. Eli Biham, Adi Shamir. Criptoanálisis diferencial de criptosistemas similares a DES  //  Avances en criptología-CRYPT0' 90 Procedimientos. - Springer Berlín Heidelberg, 1990. - P. 2-21 . — ISBN 978-3-540-54508-8 .  (enlace no disponible)
  4. B. Preneel, V. Rijmen, A. Bosselears. Principios y rendimiento de los algoritmos criptográficos  //  Dr. Diario de Dobb. - Miller Freeman, 1998. - vol. 23 , núm. 12 _ - pág. 126-131 .
  5. 1 2 3 4 5 6 Alex Biryukov, David Wagner. Advanced Slide Attacks  (inglés)  // Avances en criptología - EUROCRYPT 2000. Conferencia internacional sobre teoría y aplicación de técnicas criptográficas Brujas, Bélgica, 14 al 18 de mayo de 2000 Actas. - Springer Berlín Heidelberg, 2000. - Pág. 589-606 . — ISBN 978-3-540-67517-4 .  (enlace no disponible)
  6. 1 2 Panasenko S.P. Shift attack // Algoritmos de cifrado. Libro de referencia especial - San Petersburgo. : BHV-SPb , 2009. - S. 40-42. — 576 pág. — ISBN 978-5-9775-0319-8
  7. 1 2 3 4 5 Chalermpong Worawannotai, Isabelle Stanton. Un tutorial sobre ataques deslizantes  . Archivado desde el original el 29 de noviembre de 2014.
  8. Rafael C.-W. Fan. Ataques avanzados de diapositivas revisados: realineación de diapositivas en DES  //  Progreso en criptología: Mycrypt 2005. Primera conferencia internacional sobre criptología en Malasia, Kuala Lumpur, Malasia, 28-30 de septiembre de 2005. Actas. - Springer Berlín Heidelberg, 2005. - Pág. 263-276 . — ISBN 978-3-540-28938-8 . Archivado desde el original el 12 de junio de 2018.
  9. 1 2 Soichi Furuya. Ataques de diapositivas con un criptoanálisis de texto sin formato conocido  (inglés)  // Seguridad de la información y criptología - ICISC 2001. Cuarta Conferencia Internacional Seúl, Corea, 6 y 7 de diciembre de 2001 Actas. - Springer Berlín Heidelberg, 2002. - Pág. 214-225 . - ISBN 978-3-540-43319-4 . Archivado desde el original el 9 de junio de 2018.
  10. Eli Biham, Orr Dunkelman, Nathan Keller. Ataques deslizantes mejorados  //  Cifrado rápido de software. 14th International Workshop, FSE 2007, Luxemburgo, Luxemburgo, 26-28 de marzo de 2007, Documentos seleccionados revisados. - Springer Berlín Heidelberg, 2007. - Pág. 153-166 . — ISBN 978-3-540-74617-1 .  (enlace no disponible)
  11. Selçuk Kavut, Melek D. Yücel. Slide Attack on Spectr-H64  //  Progress in Cryptology - INDOCRYPT 2002. Tercera Conferencia Internacional sobre Criptología en India Hyderabad, India, 16 al 18 de diciembre de 2002 Actas. - Springer Berlín Heidelberg, 2002. - Pág. 34-47 . - ISBN 978-3-540-00263-5 . Archivado desde el original el 11 de junio de 2018.
  12. Nicolás T. Courtois, Gregory V. Bard, David Wagner. Ataques algebraicos y deslizantes en KeeLoq  //  Cifrado rápido de software. 15º Taller Internacional, FSE 2008, Lausana, Suiza, 10-13 de febrero de 2008, Documentos seleccionados revisados. - Springer Berlín Heidelberg, 2008. - Pág. 97-115 . — ISBN 978-3-540-71038-7 . Archivado desde el original el 30 de octubre de 2018.
  13. 1 2 Michael Gorski, Stefan Lucks, Thomas Peyrin. Slide Attacks on a Class of Hash Functions  //  Advances in Cryptology - ASIACRYPT 2008. 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, del 7 al 11 de diciembre de 2008. Actas. - Springer Berlín Heidelberg, 2008. - Pág. 143-160 . - ISBN 978-3-540-89254-0 .  (enlace no disponible)
  14. Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro. Recuperación de contraseña en desafío y respuesta: ataque diferencial imposible en la función hash  //  Progreso en criptología: AFRICACRYPT 2008. Primera conferencia internacional sobre criptología en África, Casablanca, Marruecos, 11 al 14 de junio de 2008. Actas. - Springer Berlín Heidelberg, 2008. - Pág. 290-307 . — ISBN 978-3-540-68159-5 . Archivado desde el original el 6 de junio de 2018.
  15. 1 2 Markku-Juhani O. Saarinen. Criptoanálisis de cifrados de bloques basados ​​en SHA-1 y MD5  //  Cifrado rápido de software. 10º Taller Internacional, FSE 2003, Lund, Suecia, 24-26 de febrero de 2003. Documentos revisados. - Springer Berlín Heidelberg, 2003. - Pág. 36-44 . - ISBN 978-3-540-20449-7 .  (enlace no disponible)
  16. Francois-Xavier Standaert, Gilles Piret, Jean-Jacques Quisquater. Criptoanálisis de cifrados de bloque: una encuesta  //  Serie de informes técnicos de UCL Crypto Group. - 2003. Archivado el 10 de febrero de 2014.