Ataque XSL

En criptografía , el ataque eXtended Sparse Linearization (XSL) es un método de criptoanálisis para cifrados de bloques . El ataque fue publicado por primera vez en 2002 por los investigadores Nicolas Courtois y Josef Pieprzyk . Ha causado cierta controversia ya que se afirmó que tenía el potencial de romper el cifrado Advanced Encryption Standard (AES) , también conocido como Rijndael , más rápido que una búsqueda exhaustiva . Dado que AES ya se usa ampliamente en el comercio y el gobierno para la transmisión de información secreta, encontrar una técnica que pueda acortar la cantidad de tiempo que lleva recuperar el mensaje secreto sin tener la clave podría tener amplias implicaciones.

El método tiene un alto factor de trabajo, lo que, a menos que se reduzca, significa que la técnica no reduce el esfuerzo necesario para descifrar el AES en comparación con una búsqueda exhaustiva. Por lo tanto, no afecta a la seguridad real de los cifrados por bloques en el futuro cercano. No obstante, el ataque ha provocado que algunos expertos expresen un mayor malestar por la simplicidad algebraica del AES actual.

En resumen, el ataque XSL se basa en analizar primero los elementos internos de un cifrado y derivar un conjunto de ecuaciones cuadráticas simultáneas . Estos sistemas de ecuaciones suelen ser muy grandes, por ejemplo, 8000 ecuaciones con 1600 variables para el AES de 128 bits. Se conocen varios métodos para resolver dichos sistemas. En el ataque XSL, se aplica un algoritmo especializado, denominado eXtended Sparse Linearization , para resolver estas ecuaciones y recuperar la clave .

El ataque se caracteriza por requerir solo un puñado de textos simples conocidos para funcionar; los métodos anteriores de criptoanálisis, como el criptoanálisis lineal y diferencial , a menudo requieren cantidades irrealmente grandes de textos simples conocidos o elegidos .

La resolución de ecuaciones cuadráticas multivariadas (MQ) sobre un conjunto finito de números es un problema NP-hard (en el caso general) con varias aplicaciones en criptografía. El ataque XSL requiere un algoritmo eficiente para abordar MQ. En 1999, Kipnis y Shamir demostraron que un algoritmo de clave pública particular , conocido como esquema de ecuaciones de campo oculto (HFE), podría reducirse a un sistema sobredeterminado de ecuaciones cuadráticas (más ecuaciones que incógnitas). Una técnica para resolver tales sistemas es la linealización, que implica reemplazar cada término cuadrático con una variable independiente y resolver el sistema lineal resultante utilizando un algoritmo como la eliminación gaussiana . Para tener éxito, la linealización requiere suficientes ecuaciones linealmente independientes (aproximadamente tantas como el número de términos). Sin embargo, para el criptoanálisis de HFE había muy pocas ecuaciones, por lo que Kipnis y Shamir propusieron la relinealización , una técnica en la que se añaden ecuaciones no lineales adicionales después de la linealización y el sistema resultante se resuelve mediante una segunda aplicación de linealización. La relinealización resultó lo suficientemente general como para ser aplicable a otros esquemas.

En 2000, Courtois et al. propusieron un algoritmo mejorado para MQ conocido como XL (por eXtended Linearization ), que aumenta el número de ecuaciones multiplicándolas por todos los monomios de un cierto grado . Las estimaciones de complejidad mostraron que el ataque XL no funcionaría contra las ecuaciones derivadas de cifrados de bloque como AES. Sin embargo, los sistemas de ecuaciones producidos tenían una estructura especial, y el algoritmo XSL se desarrolló como un refinamiento de XL que podría aprovechar esta estructura. En XSL, las ecuaciones se multiplican solo por monomios cuidadosamente seleccionados, y se han propuesto varias variantes.

La investigación sobre la eficiencia de XL y sus algoritmos derivados continúa (Yang y Chen, 2004).

Courtois y Pieprzyk (2002) observaron que AES (Rijndael) y parcialmente también Serpent podrían expresarse como un sistema de ecuaciones cuadráticas. Las variables representan no solo el texto simple , el texto cifrado y los bits de clave, sino también varios valores intermedios dentro del algoritmo. La caja S de AES parece ser especialmente vulnerable a este tipo de análisis, ya que se basa en la función inversa algebraicamente simple . Posteriormente, se han estudiado otros cifrados para ver qué sistemas de ecuaciones se pueden producir ( Biryukov y De Cannière, 2003), incluidos Camellia , KHAZAD , MISTY1 y KASUMI . A diferencia de otras formas de criptoanálisis, como el criptoanálisis diferencial y lineal , solo se requieren uno o dos (en el caso de un tamaño de bloque de 128 bits y un tamaño de clave de 256 bits) textos simples conocidos .

El algoritmo XSL está diseñado para resolver el tipo de sistemas de ecuaciones que se producen. Courtois y Pieprzyk estiman que "una evaluación optimista muestra que el ataque XSL podría ser capaz de romper Rijndael [con] 256 bits y Serpent para longitudes de clave [de] 192 y 256 bits". Sin embargo, su análisis no es aceptado universalmente. Por ejemplo:

Creo que el trabajo de Courtois-Pieprzyk es defectuoso. Cuentan en exceso el número de ecuaciones linealmente independientes. El resultado es que, de hecho, no tienen suficientes ecuaciones lineales para resolver el sistema, y ​​el método no rompe con el método de Rijndael… El método tiene cierto mérito y vale la pena investigarlo, pero no rompe con el método de Rijndael tal como está.

—  Don Coppersmith , Crypto-Gram 15 de octubre de 2002: Comentarios de los lectores

En la conferencia AES 4, Bonn 2004, uno de los inventores de Rijndael, Vincent Rijmen , comentó: "El ataque XSL no es un ataque. Es un sueño". Courtois respondió de inmediato: "XSL puede ser un sueño. También puede ser un mal sueño y convertirse en una pesadilla". ^[1] Sin embargo, ningún artículo posterior ni ninguna acción de la NSA o el NIST respaldan esta observación de Courtois.

En 2003, Murphy y Robshaw descubrieron una descripción alternativa de AES, incorporándola en un cifrado más grande llamado "BES", que puede describirse utilizando operaciones muy simples sobre un solo campo , GF(2 ⁸ ). Un ataque XSL montado sobre este sistema produce un conjunto más simple de ecuaciones que romperían AES con una complejidad de alrededor de 2 ¹⁰⁰ , si el análisis de Courtois y Pieprzyk es correcto. En 2005, Cid y Leurent dieron evidencia de que, en su forma propuesta, el algoritmo XSL no proporciona un método eficiente para resolver el sistema de ecuaciones AES; sin embargo, Courtois cuestionó sus hallazgos. ^{[ cita requerida ]} En FSE 2007, Chu-Wee Lim y Khoongming Khoo demostraron que el ataque XSL era peor que la fuerza bruta en BES. ^{[ cita requerida ]}

Incluso si XSL funciona contra algunos algoritmos modernos, el ataque actualmente plantea poco peligro en términos de seguridad práctica. Como muchos resultados criptoanalíticos modernos, sería una de las llamadas "debilidades de certificación": si bien es más rápido que un ataque de fuerza bruta , los recursos necesarios siguen siendo enormes y es muy poco probable que los sistemas del mundo real puedan verse comprometidos al usarlo. Sin embargo, las mejoras futuras podrían aumentar la practicidad de un ataque. Debido a que este tipo de ataque es nuevo e inesperado, algunos criptógrafos han expresado su inquietud por la simplicidad algebraica de los cifrados como Rijndael. Bruce Schneier y Niels Ferguson escriben: "Tenemos una crítica a AES: no confiamos del todo en la seguridad... Lo que más nos preocupa de AES es su estructura algebraica simple... Ningún otro cifrado de bloques que conozcamos tiene una representación algebraica tan simple. No tenemos idea de si esto conduce a un ataque o no, pero no saberlo es razón suficiente para ser escépticos sobre el uso de AES". ( Criptografía práctica , 2003, págs. 56-57)

• Biryukov, Alex; Cannière, Christophe De (2003). "Cifrados en bloque y sistemas de ecuaciones cuadráticas". En Johansson, Thomas (ed.). Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, Suecia, 24-26 de febrero de 2003, Documentos revisados . Lecture Notes in Computer Science. Vol. 2887. Springer. págs. 274–289. doi : 10.1007/978-3-540-39887-5_21 .
• Courtois, Nicolas T.; Klimov, Alexander; Patarin, Jacques; Shamir, Adi (2000). "Algoritmos eficientes para resolver sistemas sobredefinidos de ecuaciones polinómicas multivariadas" (PDF) . En Preneel, Bart (ed.). Avances en criptología - EUROCRYPT 2000, Conferencia internacional sobre la teoría y aplicación de técnicas criptográficas, Brujas, Bélgica, 14-18 de mayo de 2000, Actas . Apuntes de clase en informática. Vol. 1807. Springer. págs. 392–407. doi : 10.1007/3-540-45539-6_27 .
• Courtois, Nicolas T.; Pieprzyk, Josef (2002). "Criptoanálisis de cifrados de bloques con sistemas de ecuaciones sobredefinidos". En Zheng, Yuliang (ed.). Avances en criptología - ASIACRYPT 2002, 8.ª Conferencia internacional sobre la teoría y la aplicación de la criptología y la seguridad de la información, Queenstown, Nueva Zelanda, 1-5 de diciembre de 2002, Actas . Apuntes de clase en informática. Vol. 2501. Springer. págs. 267–287. doi : 10.1007/3-540-36178-2_17 .
• Kipnis, Aviad; Shamir, Adi (1999). "Criptoanálisis del criptosistema de clave pública HFE mediante relinealización". En Wiener, Michael J. (ed.). Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, EE. UU., 15-19 de agosto de 1999, Actas . Lecture Notes in Computer Science. Vol. 1666. Springer. págs. 19–30. doi : 10.1007/3-540-48405-1_2 .
• Lim, Chu-Wee; Khoo, Khoongming (2007). "An Analysis of XSL Applied to BES". En Biryukov, Alex (ed.). Fast Software Encryption, 14th International Workshop, FSE 2007, Luxemburgo, Luxemburgo, 26-28 de marzo de 2007, Documentos revisados ​​seleccionados . Lecture Notes in Computer Science. Vol. 4593. Springer. págs. 242–253. doi : 10.1007/978-3-540-74619-5_16 .
• Dana Mackenzie (2003). "Un juego de azar". New Scientist . 178 (2398): 36.
• Murphy, Sean; Robshaw, Matthew JB (2002). "Estructura algebraica esencial dentro del AES". En Yung, Moti (ed.). Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, EE. UU., 18-22 de agosto de 2002, Actas . Apuntes de clase en informática. Vol. 2442. Springer. págs. 1–16. doi : 10.1007/3-540-45708-9_1 .
• S. Murphy, M. Robshaw Comentarios sobre la seguridad de la técnica AES y XSL.
• Yang, Bo-Yin; Chen, Jiun{-}Ming (2004). "Análisis teórico de XL sobre campos pequeños". En Wang, Huaxiong; Pieprzyk, Josef; Varadharajan, Vijay (eds.). Seguridad de la información y privacidad: Novena Conferencia Australasiana, ACISP 2004, Sydney, Australia, 13-15 de julio de 2004. Actas . Lecture Notes in Computer Science. Vol. 3108. Springer. págs. 277–288. doi :10.1007/978-3-540-27800-9_24.
• Cid, Carlos; Leurent, Gaëtan (2005). "An Analysis of the XSL Algorithm". En Roy, Bimal K. (ed.). Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, 4-8 de diciembre de 2005, Actas . Lecture Notes in Computer Science. Vol. 3788. Springer. págs. 333–352. doi : 10.1007/11593447_18 .
• Diem, Claus (2004). "El algoritmo XL y una conjetura a partir del álgebra conmutativa". En Lee, Pil Joong (ed.). Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Isla de Jeju, Corea, 5-9 de diciembre de 2004, Actas . Apuntes de clase en informática. Vol. 3329. Springer. págs. 323–337. doi : 10.1007/978-3-540-30539-2_23 .

• La página de Courtois en AES
• “Criptoanálisis cuadrático”, una explicación del ataque XSL por JJG Savard
• "AES NO está roto", por T. Moh
• Artículo de Courtois y Pieprzyk sobre ePrint
• Comentario en el boletín Crypto-gram : [1], [2], [3].
• Una descripción general de AES y XSL