Un ataque biclicuo es una variante del método de criptoanálisis de encuentro en el medio (MITM) . Utiliza una estructura biclicua para extender el número de rondas posiblemente atacadas por el ataque MITM. Dado que el criptoanálisis biclicua se basa en ataques MITM, es aplicable tanto a cifrados de bloque como a funciones hash (iteradas) . Los ataques biclique son conocidos por haber roto tanto el AES completo [1] como el IDEA completo , [2] aunque solo con una ligera ventaja sobre la fuerza bruta. También se ha aplicado al cifrado KASUMI y a la resistencia de preimagen de la madeja-512 yFunciones hash SHA-2 . [3]
El ataque biclique sigue siendo (en abril de 2019 [actualizar]) el ataque de clave única más conocido públicamente en AES . La complejidad computacional del ataque es, y para AES128, AES192 y AES256, respectivamente. Es el único ataque de clave única conocido públicamente en AES que ataca el número completo de rondas. [1] Los ataques anteriores han atacado variantes de rondas reducidas (típicamente variantes reducidas a 7 u 8 rondas).
Como la complejidad computacional del ataque es , es un ataque teórico, lo que significa que la seguridad de AES no se ha roto y el uso de AES sigue siendo relativamente seguro. Sin embargo, el ataque biclicuo es un ataque interesante, que sugiere un nuevo enfoque para realizar criptoanálisis en cifrados de bloque. El ataque también ha proporcionado más información sobre AES, ya que ha puesto en duda el margen de seguridad en el número de rondas utilizadas en el mismo.
Historia
El ataque MITM original fue sugerido por primera vez por Diffie y Hellman en 1977, cuando discutieron las propiedades criptoanalíticas de DES. [4] Argumentaron que el tamaño de la clave era demasiado pequeño y que volver a aplicar DES varias veces con claves diferentes podría ser una solución para el tamaño de la clave; sin embargo, desaconsejaron el uso de doble DES y sugirieron triple DES como mínimo, debido a los ataques MITM (los ataques MITM se pueden aplicar fácilmente a doble DES para reducir la seguridad de para sólo , ya que uno puede aplicar fuerza bruta de forma independiente al primer y segundo cifrado DES si tienen el texto plano y cifrado).
Desde que Diffie y Hellman sugirieron ataques MITM, han surgido muchas variaciones que son útiles en situaciones en las que el ataque MITM básico es inaplicable. La variante de ataque biclicua fue sugerida por primera vez por Dmitry Khovratovich , Rechberger y Savelieva para su uso con el criptoanálisis de función hash. [5] Sin embargo, fueron Bogdanov, Khovratovich y Rechberger quienes mostraron cómo aplicar el concepto de bicliques a la configuración de clave secreta, incluido el criptoanálisis de cifrado en bloque, cuando publicaron su ataque a AES. Antes de esto, los ataques MITM en AES y muchos otros cifrados de bloque habían recibido poca atención, principalmente debido a la necesidad de bits de clave independientes entre los dos 'subcifradores MITM' para facilitar el ataque MITM, algo que es difícil de lograr con muchos horarios clave modernos, como el de AES.
El biclique
Para obtener una explicación general de qué es una estructura biclicua, consulte el artículo sobre bicliques .
En un ataque MITM, los keybits y , pertenecientes al primer y segundo cifrado, deben ser independientes; es decir, deben ser independientes entre sí, de lo contrario, los valores intermedios coincidentes para el texto plano y cifrado no se pueden calcular de forma independiente en el ataque MITM (hay variantes de ataques MITM, donde los bloques pueden tener bits de clave compartidos. Ver el ataque MITM de 3 subconjuntos ). Esta propiedad a menudo es difícil de explotar en un mayor número de rondas, debido a la difusión del cifrado atacado.
En pocas palabras: cuantas más rondas ataque, mayores subcifradores tendrá. Cuantos más subcifradores tenga, menos claves independientes entre los subcifradores tendrá que aplicar la fuerza bruta de forma independiente. Por supuesto, el número real de bits de clave independientes en cada subcifrador depende de las propiedades de difusión del programa de claves.
La forma en que el biclique ayuda a abordar lo anterior es que permite, por ejemplo, atacar 7 rondas de AES usando ataques MITM, y luego utilizando una estructura biclicua de longitud 3 (es decir, cubre 3 rondas del cifrado), puede mapear el estado intermedio al comienzo de la ronda 7 hasta el final de la última ronda, por ejemplo, 10 (si es AES128), atacando así el número total de rondas del cifrado, incluso si no fue posible atacar esa cantidad de rondas con un ataque MITM básico.
El significado del biclique es, por lo tanto, construir una estructura de manera efectiva, que puede asignar un valor intermedio al final del ataque MITM al texto cifrado al final. El texto cifrado al que se asigna el estado intermedio al final, por supuesto, depende de la clave utilizada para el cifrado. La clave utilizada para asignar el estado al texto cifrado en el biclique se basa en los bits de clave forzados en el primer y segundo subcifrado del ataque MITM.
La esencia de los ataques bicliques es, por tanto, además del ataque MITM, poder construir una estructura biclique de forma eficaz, que dependiendo de los keybits y puede mapear un cierto estado intermedio al texto cifrado correspondiente.
Cómo construir el biclique
Fuerza bruta
Obtener estados intermedios y textos cifrados, luego calcule las claves que se asignan entre ellos. Esto requiere recuperaciones de claves, ya que cada estado intermedio debe estar vinculado a todos los textos cifrados.
(Este método fue sugerido por Bogdanov, Khovratovich y Rechberger en su artículo: Criptoanálisis Biclique del AES completo [1] )
Preliminar:
Recuerde que la función del biclique es mapear los valores intermedios,, a los valores de texto cifrado, , basado en la clave tal que:
Procedimiento:
Paso uno: Un estado intermedio (), un texto cifrado () y una llave () se elige de manera que: , dónde es la función que mapea un estado intermedio a un texto cifrado usando una clave dada. Esto se denota como el cálculo base.
Paso dos: dos conjuntos de claves de tamaño relacionadasesta elegido. Las claves se eligen de manera que:
- El primer conjunto de claves son claves, que cumplen los siguientes requisitos diferenciales sobre con respecto al cálculo base:
- El segundo conjunto de claves son claves, que cumplen los siguientes requisitos diferenciales sobre con respecto al cálculo base:
- Las claves se eligen de modo que los senderos del - y Los diferenciales son independientes, es decir, no comparten ningún componente activo no lineal.
En otras palabras:
una diferencia de entrada de 0 debe corresponder a una diferencia de salida de bajo una diferencia clave de . Todas las diferencias se refieren al cálculo base.
Una diferencia de entrada de debe asignarse a una diferencia de salida de 0 bajo una diferencia clave de . Todas las diferencias se refieren al cálculo base.
Paso tres: dado que los senderos no comparten ningún componente no lineal (como cajas S), los senderos se pueden combinar para obtener:
,
que se ajusta a las definiciones de ambos diferenciales del paso 2.
Es trivial ver que la tupladel cálculo base, también se ajusta por definición tanto a los diferenciales, como los diferenciales con respecto al cálculo base. Sustituyendo en cualquiera de las dos definiciones, producirá desde y .
Esto significa que la tupla del cálculo base también se puede aplicar XOR a los senderos combinados:
Paso cuatro: Es trivial ver que:
Si esto se sustituye por los senderos diferenciales combinados anteriores, el resultado será:
Que es la misma que la definición, anteriormente se tenía arriba para un biclique:
Por tanto, es posible crear un biclique de tamaño ( puesto que todos llaves del primer juego de llaves, se pueden combinar con el llaves del segundo juego de llaves). Esto significa un biclique de tamaño se puede crear usando solo cálculos de los diferenciales y encima . Si por luego todas las llaves también será diferente en el biclique.
Así es como se construye el biclicuo en el ataque biclicuo principal en AES. Existen algunas limitaciones prácticas al construir bicliques con esta técnica. Cuanto más largo sea el biclicuo, más vueltas tendrán que cubrir los senderos diferenciales. Las propiedades de difusión del cifrado, por lo tanto, juegan un papel crucial en la efectividad de la construcción del biclicuo.
Otras formas de construir el biclique
Bogdanov, Khovratovich y Rechberger también describen otra forma de construir el biclicuo, llamado 'Interleaving Related-Key Differential Trails' en el artículo: "Criptoanálisis Biclique del AES completo [1] ".
Procedimiento de criptoanálisis biclique
Paso uno: el atacante agrupa todas las claves posibles en subconjuntos de claves de tamaño para algunos , donde la clave de un grupo se indexa como en una matriz de tamaño . El atacante divide el cifrado en dos subcifrados, y (tal que ), como en un ataque MITM normal. El conjunto de claves para cada uno de los subcifrados es de cardinalidad, y se llama y . La clave combinada de los subcifrados se expresa con la matriz antes mencionada.
Paso dos: el atacante crea un biclique para cada grupo dellaves. El biclique es de dimensión-d, ya que mapea estados internos, , a textos cifrados, , utilizando llaves. La sección "Cómo construir el biclique" sugiere cómo construir el biclique usando "Diferenciales independientes de clave relacionada". En ese caso, el biclique se construye utilizando los diferenciales del juego de llaves, y , perteneciente a los subciphers.
Paso tres: el atacante toma el posibles textos cifrados, y solicita a un oráculo de descifrado que proporcione los textos sin formato correspondientes, .
Paso cuatro: el atacante elige un estado interno, y el texto sin formato correspondiente, y realiza el ataque MITM habitual sobre y atacando desde el estado interno y el texto llano.
Paso cinco: siempre que se encuentre un candidato clave que coincida con , esa clave se prueba en otro par de texto sin formato / cifrado. si la clave se valida en el otro par, es muy probable que sea la clave correcta.
Ataque de ejemplo
El siguiente ejemplo se basa en el ataque biclicuo en AES del artículo "Criptoanálisis Biclique del AES completo [1] ".
Las descripciones del ejemplo utilizan la misma terminología que utilizaron los autores del ataque (es decir, para nombres de variables, etc.).
Por simplicidad, es el ataque a la variante AES128 que se cubre a continuación.
El ataque consiste en un ataque MITM de 7 rondas con el biclique cubriendo las últimas 3 rondas.
Partición de claves
El espacio de claves está dividido en grupos de llaves, donde cada grupo consta de llaves.
Para cada uno de los grupos, una clave base única para el cálculo base está seleccionado.
La clave base tiene dos bytes específicos establecidos en cero, que se muestran en la siguiente tabla (que representa la clave de la misma manera que lo hace AES en una matriz 4x4 para AES128):
A continuación, se enumeran los 14 bytes restantes (112 bits) de la clave. Esto produceclaves base únicas; uno para cada grupo de llaves.
Lo ordinarioLas claves de cada grupo se eligen con respecto a su clave base. Se eligen de modo que sean casi idénticos a la clave base. Solo varían en 2 bytes (ya sea eles o el 's) de los 4 bytes que se muestran a continuación:
Esto da y , que combinado da diferentes llaves, . estas Las claves constituyen las claves del grupo para una clave base respectiva.
Construcción biclique
bicliques se construye utilizando la técnica "Diferenciales independientes de clave relacionada", como se describe en la sección "Cómo construir el biclique".
El requisito para usar esa técnica era que los senderos diferenciales hacia adelante y hacia atrás que deben combinarse no compartieran ningún elemento no lineal activo. ¿Cómo se sabe que este es el caso?
Debido a la forma en que se eligen las claves en el paso 1 en relación con la clave base, el diferencial usando las llaves nunca comparta ninguna caja S activa (que es el único componente no lineal en AES), con las pistas diferenciales usando la llave . Por lo tanto, es posible XOR de los caminos diferenciales y crear el biclicuo.
Ataque MITM
Cuando se crean los bicliques, el ataque MITM casi puede comenzar. Antes de realizar el ataque MITM, el valores intermedios del texto plano:
,
el valores intermedios del texto cifrado:
,
y los correspondientes estados intermedios y subclaves o , sin embargo, se calculan y almacenan previamente.
Ahora se puede llevar a cabo el ataque MITM. Para probar una clave, solo es necesario recalcular las partes del cifrado, que se sabe variará entre y . Para el cálculo hacia atrás de a , se trata de 4 cajas S que deben volver a calcularse. Para el cálculo hacia adelante de a , son solo 3 (se puede encontrar una explicación detallada de la cantidad de recálculo necesario en el artículo "Criptoanálisis Biclique del AES completo [1] ", de donde se tomó este ejemplo).
Cuando los valores intermedios coinciden, un candidato clave Entre y es encontrado. El candidato a clave se prueba luego en otro par de texto sin formato / cifrado.
Resultados
Este ataque reduce la complejidad computacional de AES128 a , que es de 3 a 5 veces más rápido que un enfoque de fuerza bruta. La complejidad de los datos del ataque es y la complejidad de la memoria es .
Referencias
- ^ a b c d e f Bogdanov, Andrey; Khovratovich, Dmitry; Rechberger, Christian. "Criptoanálisis Biclique del AES completo" (PDF) . Archivado desde el original (PDF) el 8 de junio de 2012. Cite journal requiere
|journal=
( ayuda ) - ^ "Bicliques estrechos: criptoanálisis de IDEA completa". CiteSeerX 10.1.1.352.9346 . Cite journal requiere
|journal=
( ayuda ) - ^ Bicliques para preimágenes: ataques a la madeja-512 y la familia SHA-2
- ^ Diffie, Whitfield; Hellman, Martin E. "Criptoanálisis exhaustivo del estándar de cifrado de datos NBS" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Khovratovich, Dmitry; Rechberger, Christian; Savelieva, Alexandra. "Bicliques para preimágenes: ataques a la madeja-512 y la familia SHA-2" (PDF) . Cite journal requiere
|journal=
( ayuda )