Ataque del cubo

El ataque del cubo es un método de criptoanálisis aplicable a una amplia variedad de algoritmos de clave simétrica , publicado por Itai Dinur y Adi Shamir en una versión preliminar de septiembre de 2008. Una versión revisada de esta versión preliminar se publicó en línea en enero de 2009 ^{[ 1 ]} y el artículo también fue aceptado para su presentación en Eurocrypt 2009.

Un cifrado es vulnerable si un bit de salida puede representarse como un polinomio de grado suficientemente bajo sobre GF(2) de bits de clave y de entrada; en particular, esto describe muchos cifrados de flujo basados ​​en LFSR . ^{[ 2 ]} Se cree que DES y AES son inmunes a este ataque. ^{[ 2 ]} Funciona sumando el valor de un bit de salida para todos los valores posibles de un subconjunto de bits de entrada públicos, elegidos de tal manera que la suma resultante sea una combinación lineal de bits secretos; la aplicación repetida de esta técnica proporciona un conjunto de relaciones lineales entre bits secretos que pueden resolverse para descubrir estos bits. Los autores muestran que si el cifrado se asemeja a un polinomio aleatorio de grado suficientemente bajo, entonces tales conjuntos de bits de entrada públicos existirán con alta probabilidad y pueden descubrirse en una fase de precomputación mediante una "sondeo de caja negra" de la relación entre entrada y salida para varias elecciones de bits de entrada públicos y secretos sin utilizar ninguna otra información sobre la construcción del cifrado.

El artículo presenta un ataque práctico, implementado y probado por los autores, contra un cifrador de flujo contra el cual ningún ataque conocido previamente sería efectivo. Su estado es un LFSR de 10 000 bits con un polinomio de retroalimentación denso secreto, filtrado por una matriz de 1000 cajas S secretas de 8 bits a 1 bit , cuya entrada se basa en accesos secretos al estado del LFSR y cuya salida se combina mediante una operación XOR. Cada bit del LFSR se inicializa con un polinomio cuadrático denso secreto diferente en 10 000 bits de clave e IV . El LFSR se activa un gran número de veces, de forma secreta, sin producir ninguna salida, y luego solo la primera salida, un bit para cualquier IV dado, se pone a disposición del atacante. Tras una breve fase de preprocesamiento en la que el atacante puede consultar los bits de salida para diversas combinaciones de clave e IV, solo se requieren ^{2³⁰ operaciones de 30} bits para descubrir la clave de este cifrador.

Los autores también afirman haber logrado un ataque a una versión de Trivium reducida a 735 rondas de inicialización con una complejidad de ^2³⁰ , y conjeturan que estas técnicas podrían extenderse a romper 1100 de las 1152 rondas de inicialización de Trivium y "quizás incluso el cifrado original". A diciembre de 2008. Este es el mejor ataque conocido contra Trivium.

Sin embargo, el ataque está envuelto en dos controversias distintas. En primer lugar, Daniel J. Bernstein ^{[ 3 ]} refuta la afirmación de que no existía ningún ataque previo al cifrador de flujo basado en LFSR de 10 000 bits, y sostiene que el ataque al Trivium de ronda reducida "no da ninguna razón real para pensar que el Trivium (completo) pueda ser atacado". Afirma que el artículo de Cube no citó un artículo existente de Xuejia Lai que detalla un ataque a cifradores con polinomios de bajo grado, y que cree que el ataque a Cube es simplemente una reinvención de esta técnica existente.

En segundo lugar, Dinur y Shamir atribuyen al " Ataque Diferencial Algebraico IV " (AIDA) de Michael Vielhaber el precedente del ataque Cube. ^{[ 4 ]} Dinur afirmó en Eurocrypt 2009 que Cube generaliza y mejora AIDA. Sin embargo, Vielhaber sostiene que el ataque Cube no es más que su ataque con otro nombre. ^{[ 5 ]} No obstante, todas las partes involucradas reconocen que el uso por parte de Cube de una prueba de linealidad eficiente, como la prueba BLR, hace que el nuevo ataque requiera menos tiempo que AIDA, aunque la magnitud de este cambio en particular sigue siendo objeto de debate. Esta no es la única diferencia entre Cube y AIDA. Vielhaber afirma, por ejemplo, que los polinomios lineales en los bits de la clave que se obtienen durante el ataque serán inusualmente dispersos. Aún no ha aportado pruebas de ello, pero afirma que dichas pruebas aparecerán en un próximo artículo suyo titulado "El Ataque Diferencial Algebraico IV: AIDA atacando el Trivium completo". (No está claro si esta supuesta escasez se aplica a algún otro cifrado aparte de Trivium).