Ataque XSL - XSL attack

En criptografía , el ataque de linealización dispersa extendida (XSL) es un método de criptoanálisis para cifrados en bloque . El ataque fue publicado por primera vez en 2002 por los investigadores Nicolas Courtois y Josef Pieprzyk . Ha causado cierta controversia, ya que se decía tener el potencial para romper el Advanced Encryption Standard (AES) de cifrado , 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 factor de trabajo alto, que a menos que se reduzca, significa que la técnica no reduce el esfuerzo para romper AES en comparación con una búsqueda exhaustiva. Por lo tanto, no afecta la seguridad del mundo real de los cifrados en bloque en un futuro próximo. No obstante, el ataque ha provocado que algunos expertos expresen una mayor inquietud ante la simplicidad algebraica del actual AES.sub to Flaming Destruction.

En resumen, el ataque XSL se basa en analizar primero los aspectos internos de un cifrado y derivar un sistema de ecuaciones cuadráticas simultáneas . Estos sistemas de ecuaciones suelen ser muy grandes, por ejemplo, 8.000 ecuaciones con 1.600 variables para el AES de 128 bits. Se conocen varios métodos para resolver tales sistemas. En el ataque XSL , se aplica un algoritmo especializado, denominado linealización dispersa extendida , para resolver estas ecuaciones y recuperar la clave .

El ataque es notable por requerir solo un puñado de textos en claro conocidos para ejecutarse; Los métodos previos de criptoanálisis, como el criptoanálisis lineal y diferencial , a menudo requieren un gran número de textos sin formato conocidos o elegidos que no son realistas .

Resolver ecuaciones cuadráticas multivariadas

Resolver ecuaciones cuadráticas multivariadas (MQ) sobre un conjunto finito de números es un problema NP-difícil (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 en 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 re-linealización , una técnica en la que se agregan 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 re-linealización demostró ser lo suficientemente general como para ser aplicable a otros esquemas.

En 2000, Courtois et al. propuso un algoritmo mejorado para MQ conocido como XL (para linealización extendida ), que aumenta el número de ecuaciones multiplicándolas con todos los monomios de 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 sigue en curso (Yang y Chen, 2004).

Aplicación para bloquear cifrados

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 sin formato , el texto cifrado y los bits 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 textos planos 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 romper Rijndael [con] 256 bits y Serpent para longitudes de clave [de] 192 y 256 bits". Su análisis, sin embargo, no es universalmente aceptado. Por ejemplo:

Creo que el trabajo de Courtois-Pieprzyk es defectuoso. Sobrecuentan 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 a Rijndael ... El método tiene cierto mérito, y vale la pena investigarlo, pero no rompe a 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". De inmediato, Courtois respondió: "XSL puede ser un sueño. También puede ser un muy mal sueño y convertirse en una pesadilla". Sin embargo, ni ningún documento posterior ni ninguna acción de la NSA o NIST respaldan esta observación de Courtois.

En 2003, Murphy y Robshaw descubrieron una descripción alternativa de AES, incrustándola en un cifrado más grande llamado "BES", que se puede describir usando operaciones muy simples en un solo campo , GF ( 28 ). Un ataque XSL montado en este sistema produce un conjunto de ecuaciones más simple que rompería AES con una complejidad de alrededor de 2 100 , 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. En FSE 2007, Chu-Wee Lim y Khoongming Khoo demostraron que no es posible que funcione como se presenta.

Incluso si XSL funciona contra algunos algoritmos modernos, el ataque actualmente presenta 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": aunque 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 cifrados como Rijndael. Bruce Schneier y Niels Ferguson escriben: "Tenemos una crítica de 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)

Referencias

enlaces externos