El ataque al 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 preimpresión de septiembre de 2008.
Ataque
Una versión revisada de esta preimpresión se colocó en línea en enero de 2009, [1] y el documento también ha sido 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 clave y bits 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 un valor de bit de salida para todos los valores posibles de un subconjunto de bits de entrada públicos, elegidos de manera que la suma resultante sea una combinación lineal de bits secretos; La aplicación repetida de esta técnica da 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 se pueden descubrir en una fase de precomputación mediante una "prueba de caja negra" de la relación entre la entrada y la salida para varias opciones 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, que los autores han implementado y probado, en un cifrado de flujo en el que ningún ataque conocido anterior sería efectivo. Su estado es un LFSR de 10,000 bits con un polinomio de retroalimentación denso secreto, que es filtrado por una matriz de 1000 cajas S secretas de 8 bits a 1 bit , cuya entrada se basa en tomas secretas en el estado LFSR y cuya salida es XORed. juntos. Cada bit en el LFSR es inicializado por un polinomio cuadrático denso secreto diferente en 10, 000 claves y bits IV . El LFSR se sincroniza un número grande y secreto de veces sin producir ninguna salida, y luego solo el primer bit de salida para cualquier IV dado está disponible para el atacante. Después de una breve fase de preprocesamiento en la que el atacante puede consultar los bits de salida para una variedad de combinaciones de clave y IV, solo se requieren 2 operaciones de 30 bits para descubrir la clave de este cifrado.
Los autores también afirman un ataque a una versión de Trivium reducida a 735 rondas de inicialización con complejidad 2 30 , y conjeturan que estas técnicas pueden extenderse a romper 1100 de las 1152 rondas de inicialización de Trivium y "tal vez incluso el cifrado original". A diciembre de 2008[actualizar] 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] cuestiona la afirmación de que no existió ningún ataque previo al cifrado de flujo basado en LFSR de 10,000 bits, y afirma que el ataque al Trivium de ronda reducida "no da ninguna razón real para pensar que ( el completo) Trivium puede ser atacado ". Afirma que el artículo del Cubo no citó un artículo existente de Xuejia Lai que detallaba un ataque a los cifrados con polinomios de pequeño grado, y que cree que el ataque del Cubo es simplemente una reinvención de esta técnica existente.
En segundo lugar, Dinur y Shamir dan crédito al " Ataque diferencial algebraico IV " (AIDA) de Michael Vielhaber como un precursor del ataque del Cubo. [4] Dinur ha declarado en Eurocrypt 2009 que Cube generaliza y mejora AIDA. Sin embargo, Vielhaber sostiene que el ataque del cubo no es más que su ataque con otro nombre. [5] Sin embargo, todas las partes involucradas reconocen que el uso de Cube de una prueba de linealidad eficiente como la prueba BLR da como resultado que el nuevo ataque requiera menos tiempo que AIDA, aunque la importancia de este cambio en particular permanece en disputa. No es la única diferencia entre Cube y AIDA. Vielhaber afirma, por ejemplo, que los polinomios lineales en los bits clave que se obtienen durante el ataque serán inusualmente escasos. Aún no ha proporcionado evidencia de esto, pero afirma que dicha evidencia aparecerá en un próximo artículo de él mismo titulado "El Ataque Diferencial Algebraico IV: AIDA atacando el Trivium completo". (No está claro si esta supuesta escasez se aplica a otros cifrados que no sean Trivium).
Referencias
- ^ Dinur, Itai; Shamir, Adi (26 de enero de 2009). "Ataques de cubo en polinomios de caja negra modificables" (PDF) . Archivo ePrint de criptología . ePrint 20090126: 174453. Cite journal requiere
|journal=
( ayuda ) - ^ a b Bruce Schneier (19 de agosto de 2008). "Ataques del cubo de Adi Shamir" . Consultado el 4 de diciembre de 2008 .
- ^ Daniel J. Bernstein (14 de enero de 2009). "¿Por qué los ataques de cubos no han roto nada?" . Consultado el 27 de febrero de 2009 .
- ^ Michael Vielhaber (28 de octubre de 2007). "Rompiendo ONE.FIVIUM por AIDA un Ataque Diferencial Algebraico IV" . Cite journal requiere
|journal=
( ayuda ) - ^ Michael Vielhaber (23 de febrero de 2009). "El" ataque del cubo de Shamir ": un remake de AIDA, el ataque diferencial algebraico IV" (PDF) .[ enlace muerto permanente ]