Ataque XSL

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 12 de marzo de 2017; las comprobaciones requieren 19 ediciones .

El ataque XSL ( ing. Extended Sparse Linearization , ataque algebraico) es un método de análisis criptográfico basado en las propiedades algebraicas del cifrado . El método consiste en resolver un sistema especial de ecuaciones .

Este método fue propuesto en 2001 por Nicolas T. Courtois y Josef Pieprzyk.

Anteriormente, los ataques XSL se consideraban imposibles, pero el 26 de mayo de 2006, Courtois demostró la posibilidad de un ataque XSL contra un modelo de cifrado único similar en estructura al cifrado AES [1] .

Como dijo uno de los creadores del cifrado Rijndael en correspondencia privada: "XSL no es un ataque, es solo un sueño". "Este sueño puede convertirse en una pesadilla", respondió Nicolás Courtois [2] .

Si los ataques XSL realmente funcionan, romperán todos los cifrados existentes actualmente. Solo la pura casualidad puede evitar que la clave se rompa. Por otro lado, es muy posible (y desde nuestro punto de vista, lo más probable) que los ataques XSL no sean aplicables en la práctica, o sean aplicables solo a una pequeña cantidad de cifrados altamente estructurados.

— Nils Ferguson , Bruce Schneier Criptografía práctica [3]

Historial de creación

En 2001, Niels Ferguson , Richard Schroeppel y D. Whiting publicaron un artículo [4] en el que pudieron representar el cifrado Rijndael como una fórmula algebraica utilizando las representaciones de las partes lineales del cifrado y S-boxes no lineales en en forma de ecuaciones de orden superior. Llegaron a la conclusión de que todos los cifrados de bloques simétricos se pueden reducir a una ecuación multidimensional sobre algún campo finito . También se preguntaron si conocer la forma algebraica ayudaría a descifrar el cifrado . Si la función que expresa S-boxes no tiene en cuenta argumentos elevados a -1, entonces el cifrado se vuelve afín y se rompe fácilmente de otras formas que no requieren linealización . Si igualamos estos argumentos a , entonces la ecuación resulta polinomialmente compleja. $1/x$ ${\ estilo de visualización x^{254}}$

En esos años aparecieron muchos ataques a las claves públicas: un ataque al sistema Matsumoto-Imai [5] , un ataque a HFE [6] . Estos ataques terminaron con éxito inmediatamente después del descubrimiento del hecho (teórico o experimental) de la existencia de ecuaciones adicionales de muchas variables, que no son obvias y no fueron proporcionadas por los desarrolladores del cifrado original [7] .

Adi Shamir en 1998 demostró que las ecuaciones cuadráticas de muchas variables (MQ) son un problema NP-completo [8] . Su complejidad disminuye notablemente cuando se redefinen las ecuaciones [7] . En el primer estudio, Nicolas Courtois y Jozef Pepshik muestran que los MQ resultantes son escasos y tienen una estructura regular [7] .

El 2 de diciembre de 2002 en ASIACRYPT-2002, Nicolas Courtois y Jozef Pepshik presentaron el artículo "Criptomálisis de cifrados en bloque con sistemas de ecuaciones sobredefinidos", donde presentaron por primera vez dos variaciones del método de ataque XSL [9] . La conclusión de este trabajo es que la seguridad de AES se basa únicamente en la imposibilidad en este momento de resolver el sistema de ecuaciones que describe la estructura algebraica de la cifra.

Cifrado XSL

Generalizando la clase de cifrados SP, que consisten en cajas S y funciones de permutación de bits, Courtois y Pepchik designaron una nueva clase de cifrados SA, que consisten en cajas S y funciones afines [10] . Según un estudio realizado por Adi Shamir y Alex Biryukov , los ataques a los cifrados SA no dependen de las propiedades de un S-box en particular [11] . Después de eso, se introdujo en el artículo el cifrado XSL de la clase SA, que describe la estructura de un cifrado de bloques típico al que se puede aplicar el método.

La estructura de cifrado consta de rondas: $norte$

${\ estilo de visualización X:}$ en la ronda , se realiza una operación de texto sin formato con la clave de sesión ${\ estilo de visualización i = 1}$ ${\ estilo de visualización XOR}$ ${\ Displaystyle K_ {i-1}}$
${\ estilo de visualización S:}$ El resultado se divide en bloques por bits. Cada bloque de este tipo se alimenta en paralelo a la entrada de algún número B de bloques S biyectivos. $s$
${\ estilo de visualización L:}$ luego aplique una capa de dispersión lineal.
${\ estilo de visualización X:}$ aplicar la operación a la siguiente clave de sesión ${\ estilo de visualización XOR}$ $K_{yo}$
si rompemos el bucle, de lo contrario vamos a la siguiente iteración y volvemos al paso . ${\ estilo de visualización i = N}$ $i$ $S$

Fundamentos matemáticos

Las cajas S de los cifrados Rijndael y Serpent se pueden representar como una función de muchas variables de alto grado [12] , el método de Courtois reduce el grado de la función a algún número , donde generalmente se elige que sea 2, expandiendo el espacio argumental. De particular interés es el número de tales funciones . Si , tales ecuaciones describen suficientemente el bloque S. Si , entonces decimos que el sistema está redefinido. $d$ $d$ $r$ ${\ estilo de visualización r = s}$ $r>>s$

Hay dos tipos de ataques XSL. El primero (general) opera con cifrados XSL, independientemente del algoritmo de programación de claves (ver programación de claves ). Luego, el algoritmo requiere tantos textos cifrados como S-boxes haya dentro del cifrado. La segunda versión del ataque XSL tiene en cuenta que el algoritmo de programación de claves es conocido y, por lo tanto, requiere solo un texto cifrado [13] .

Algoritmo para el primer ataque XSL

Cada ronda del bloque S se escribe como una ecuación:

${\displaystyle \sum_{i,j}\alpha_{ijk}*X_{ij}*Y_{jk}+\sum_{i,j}\beta_{ij}*X_{ij} +\sum _{i,j}\gamma _{ij}*Y_{ij}+\delta =0}$

donde están los bits de entrada de la -ésima S-box, son los bits de salida de la -ésima S-box. $X_{{ij}}$ $i$ $Y_{ik}$ $i$

A continuación, se selecciona el parámetro de ataque crítico . Durante el ataque, la ecuación de cada caja S se multiplicará por todos los monomios posibles del subconjunto de las cajas S restantes. Además, al cambiar el número de rondas del cifrado, el parámetro no debería aumentar mucho, como lo demostraron los experimentos de Courtois y Pepshik [14] . $P\en \mathbb {N}$ ${\ estilo de visualización (P-1)}$ $PAGS$

Luego, para encontrar un sistema para el cual existe una solución única, se escribe una nueva ecuación:

$X_{i,j}\bigoplus \sum \alpha _{j}Y_{i-1,j}=X'_{i,j}\bigoplus \sum \alpha _{j}Y'{i -1,j}=X''_{i,j}\sum \alpha _{j}Y''_{i-1,j}=...$

El propósito de todas estas transformaciones es llevar el sistema de ecuaciones a un sistema lineal sobredeterminado en el que no hay ecuaciones linealmente dependientes obvias.

Opinión de la comunidad científica

El método de los ataques algebraicos parecía prometedor para el criptoanálisis, ya que en teoría no requería una gran cantidad de textos cifrados y ofrecía la ruptura del estándar de cifrado más utilizado (AES). Durante los últimos cinco años, se han publicado muchas investigaciones sobre el rendimiento de los ataques XSL.

Así, en el trabajo de Carlos Cid (Carlos Cid) y G. Lauren (Ga¨etan Leurent) se analizó la segunda versión del ataque XSL del artículo original - XSL compacto - sobre AES-128 [15] . El artículo analizó ejemplos en los que este algoritmo colapsa en el llamado T-block, que se utiliza para expandir el espacio de variables. Sin embargo, los científicos concluyeron que el enfoque XSL es el primer intento de encontrar una vulnerabilidad en la parte estructural del cifrado AES.

Por ejemplo, el trabajo de Chu-Wee Lim y Khoongming Khoo [16] investiga un intento de convertir la aplicación BES (Big Encryption System) en AES. Esta extensión traduce todos los cálculos al campo , lo que, en consecuencia, debería reducir el número de operaciones. Sin embargo, los cálculos teóricos han demostrado que aumenta la complejidad del algoritmo para el cifrado BES. Dificultad para las variantes de BES: ${\ estilo de visualización {GF_{256}}}$

BES-128: ${\ estilo de visualización \ aproximadamente 2 ^ {401}}$
BES-192: ${\ estilo de visualización \ aproximadamente 2 ^ {622}}$
BES-256: ${\ estilo de visualización \ aproximadamente 2 ^ {691}}$

Se ha encontrado que el ataque XSL no es efectivo contra los cifrados BES.

Notas

↑ Criptoanálisis algebraico del estándar de cifrado de datos, 2007 , págs. 152-169.
↑ Vicente Rijman. Rijndael y otros cifrados en bloque . Foro NESSIE (18-12-02 18:51). (indefinido)
↑ Nils Ferguson , Bruce Schneier . Criptografía Práctica = Criptografía Práctica: Diseño e Implementación de Sistemas Criptográficos Seguros. - M. : Dialéctica, 2004. - 432 p. - 3000 copias. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
↑ Una representación algebraica simple de Rijndael, 2001 , págs. 1-9.
↑ Jacques Patarín. Criptoanálisis del esquema de clave pública de Matsumoto e Imai de Eurocrypt'88 // Avances en criptología - CRYPT0' 95. - Berlín, Heidelberg: Springer Berlin Heidelberg, 1995. - págs. 248–261 . — ISBN 9783540602217 , 9783540447504 .
↑ Pista de criptógrafos en la Conferencia RSA (2001: San Francisco, California). Temas de criptología, CT-RSA 2001: el seguimiento de los criptógrafos en la Conferencia RSA 2001, San Francisco, CA, EE. UU., abril de 2001: actas . - ISBN 3540418989 , 9783540418986 , 2001020877.
↑ 1 2 3 Criptoanálisis de cifrados en bloque con sistemas de ecuaciones sobredefinidos, 2002 , págs. 2.
↑ Aviad Kipnis, Adi Shamir. Criptoanálisis del criptosistema de clave pública HFE por relinealización // Avances en criptología - CRYPTO' 99. - Berlín, Heidelberg: Springer Berlin Heidelberg, 1999. - pp. 19–30 . - ISBN 9783540663478 , 9783540484059 .
↑ Criptoanálisis de cifrados en bloque con sistemas de ecuaciones sobredefinidos, 2002 , págs. 1-35.
↑ Criptoanálisis de cifrados en bloque con sistemas de ecuaciones sobredefinidos, 2002 , págs. 3.
↑ Alex Biryukov, Adi Shamir. Criptoanálisis estructural de SASAS // Journal of Cryptology. — 2010-06-08. - T. 23 , n. 4 . — S. 505–518 . - ISSN 1432-1378 0933-2790, 1432-1378 . -doi : 10.1007/ s00145-010-9062-1 .
↑ Una representación algebraica simple de Rijndael, 2001 , págs. 1-4.
↑ Criptoanálisis de cifrados en bloque con sistemas de ecuaciones sobredefinidos, 2002 , págs. 6-8.
↑ Criptoanálisis de cifrados en bloque con sistemas de ecuaciones sobredefinidos, 2002 , págs. 12
↑ Conferencia internacional sobre teoría y aplicación de criptología y seguridad de la información (11: 2005: Madrás, India). Avances en criptología: ASIACRYPT 2005, 11ª Conferencia Internacional sobre Teoría y Aplicación de Criptología y Seguridad de la Información, Chennai, India, 4-8 de diciembre de 2005: actas . - Springer, 2005. - ISBN 9783540322672
↑ Análisis de XSL aplicado a BES, 2007 , págs. 7-13.

Literatura

Nicolás T. Courtois, Gregory V. Bard. Criptoanálisis algebraico del estándar de cifrado de datos // Criptografía y codificación. - Berlín, Heidelberg: Springer Berlin Heidelberg, 2007. - ISBN 9783540772712 .
Ferguson N., Schneier B. Criptografía práctica. - 2005. - 424 págs.
Nicolás T. Courtois y Josef Pieprzyk. Criptoanálisis de cifrados en bloque con sistemas de ecuaciones sobredefinidos . - Berlín, Heidelberg: Springer Berlin, 2002. - S. 1-35 .
Chu-Wee Lim, Khoongming Khoo. Un análisis de XSL aplicado a BES // Cifrado rápido de software. - 2007. - S. 13 . Archivado desde el original el 3 de marzo de 2016.
Niels Ferguson, Richard Schroeppel, Doug Whiting. Una representación algebraica simple de Rijndael // Áreas seleccionadas en criptografía. — Berlín, Heidelberg: Springer Berlin Heidelberg, 2001. — págs. 103–111 . - ISBN 9783540430667 , 9783540455370 .