ataque biclique

Variante del método de criptoanálisis de encuentro en el medio

Un ataque biclique es una variante del método de criptoanálisis de encuentro en el medio (MITM) . Utiliza una estructura biclique para ampliar el número de rondas posiblemente atacadas por el ataque MITM. Dado que el criptoanálisis biclique se basa en ataques MITM, es aplicable tanto a cifrados de bloque como a funciones hash (iteradas) . Los ataques biclique son conocidos por haber debilitado tanto AES completo ^[1] como IDEA completo , ^[2] aunque sólo con una ligera ventaja sobre la fuerza bruta. También se ha aplicado al cifrado KASUMI y a la resistencia a la preimagen de las funciones hash Skein-512 y SHA-2 . ^[3]

El ataque biclique sigue siendo (a 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 contra AES que ataca el número completo de rondas. ^[1] Los ataques anteriores han atacado variantes de ronda reducida (normalmente variantes reducidas a 7 u 8 rondas). ${\displaystyle 2^{126.1}}$ ${\displaystyle 2^{189.7}}$ ${\displaystyle 2^{254.4}}$

Dada la complejidad computacional del ataque , 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 biclique es un ataque interesante, que sugiere un nuevo enfoque para realizar criptoanálisis en cifrados en 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. ${\displaystyle 2^{126.1}}$

Historia

El ataque MITM original fue sugerido por primera vez por Diffie y Hellman en 1977, cuando discutieron las propiedades criptoanalíticas del DES. ^[4] Argumentaron que el tamaño de la clave era demasiado pequeño y que volver a aplicar DES varias veces con diferentes claves podría ser una solución al 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 a justo , ya que uno puede aplicar fuerza bruta de forma independiente al primero y al segundo). segundo cifrado DES si tienen texto plano y cifrado). ${\displaystyle 2^{56*2}}$ ${\displaystyle 2*2^{56}}$

Desde que Diffie y Hellman sugirieron los ataques MITM, han surgido muchas variaciones que son útiles en situaciones en las que el ataque MITM básico no es aplicable. La variante del ataque biclique fue sugerida por primera vez por Dmitry Khovratovich , Rechberger y Savelieva para su uso con criptoanálisis con 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 a AES y muchos otros cifrados en 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.

la bicicleta

Para obtener una explicación general de qué es una estructura biclique, consulte el artículo sobre bicliques .

En un ataque MITM, los bits de clave y , que pertenecen al primer y segundo subcifrado, 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 (existen variantes de ataques MITM, donde los bloques pueden tener bits de clave compartidos. Consulte el ataque MITM de 3 subconjuntos ). Esta propiedad suele ser difícil de explotar durante un mayor número de rondas, debido a la difusión del cifrado atacado. ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$

En pocas palabras: cuantas más rondas ataques, más subcifrados tendrás. Cuanto más subcifrados tenga, menos bits de clave independientes entre los subcifrados tendrá que aplicar fuerza bruta de forma independiente. Por supuesto, el número real de bits de clave independientes en cada subcifrado depende de las propiedades de difusión del programa de claves.

La forma en que la biclique ayuda a abordar lo anterior es que permite, por ejemplo, atacar 7 rondas de AES usando ataques MITM y luego utilizando una estructura biclique de longitud 3 (es decir, cubre 3 rondas del cifrado), Puedes asignar el estado intermedio al inicio de la ronda 7 al final de la última ronda, por ejemplo, 10 (si es AES128), atacando así el número completo de rondas del cifrado, incluso si no fuera posible atacar esa cantidad. de rondas con un ataque MITM básico.

Por lo tanto, el significado de biclique es construir una estructura de manera efectiva, que pueda 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 depende, por supuesto, de la clave utilizada para el cifrado. La clave utilizada para asignar el estado al texto cifrado en la biclique se basa en los bits de clave forzados de forma bruta en el primer y segundo subcifrado del ataque MITM.

La esencia de los ataques bicliques es, por lo tanto, además del ataque MITM, poder construir una estructura biclique de manera efectiva, que dependiendo de los bits clave pueda asignar un cierto estado intermedio al texto cifrado correspondiente. ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$

Cómo construir la bicicleta

Fuerza bruta

Obtenga 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. ${\displaystyle 2^{d}}$ ${\displaystyle 2^{d}}$ ${\displaystyle 2^{2d}}$

Diferenciales de claves relacionadas independientes

(Este método fue sugerido por Bogdanov, Khovratovich y Rechberger en su artículo: Biclique Cryptanalysis of the Full AES ^[1] )

Preliminar:
Recuerde que la función de la biclique es asignar los valores intermedios, a los valores de texto cifrado, en función de la clave de modo que: ${\displaystyle S}$ ${\displaystyle C}$ ${\displaystyle K[i,j]}$
${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

Procedimiento:
Paso uno: Se elige un estado intermedio( ), un texto cifrado( ) y una clave( ) de manera que: , donde está la función que asigna un estado intermedio a un texto cifrado usando una clave determinada. Esto se denomina cálculo base. ${\displaystyle S_{0}}$ ${\displaystyle C_{0}}$ ${\displaystyle K[0,0]}$ ${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$ ${\displaystyle f}$

Paso dos: se eligen dos conjuntos de claves de tamaño relacionadas . Las claves se eligen de forma que: ${\displaystyle 2^{d}}$

• El primer conjunto de claves son claves que cumplen los siguientes requisitos diferenciales con respecto al cálculo base: ${\displaystyle f}$ ${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}}$
• El segundo conjunto de claves son claves, que cumplen los siguientes requisitos diferenciales con respecto al cálculo base: ${\displaystyle f}$ ${\displaystyle \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0}$
• Las claves se eligen de manera que las trayectorias de los diferenciales - y - sean independientes, es decir, no comparten ningún componente no lineal activo. ${\displaystyle \Delta _{i}}$ ${\displaystyle \nabla _{j}}$

En otras palabras:
una diferencia de entrada de 0 debe asignarse a una diferencia de salida de bajo una diferencia clave de . Todas las diferencias son con respecto 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 son con respecto al cálculo base. ${\displaystyle \Delta _{i}}$ ${\displaystyle \Delta _{i}^{K}}$
${\displaystyle \nabla _{j}}$ ${\displaystyle \nabla _{J}^{K}}$

Paso tres: dado que los senderos no comparten ningún componente no lineal (como S-boxes), los senderos se pueden combinar para obtener: , que se ajusta a las definiciones de ambos diferenciales del paso 2. Es trivial ver que la tupla del cálculo base también se ajusta por definición a ambos diferenciales, como lo son los diferenciales con respecto al cálculo base. Sustituyendo en cualquiera de las dos definiciones, se obtendrá desde y . Esto significa que la tupla del cálculo base también se puede aplicar XOR a las rutas combinadas:
${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}}$

${\displaystyle (S_{0},C_{0},K[0,0])}$ ${\displaystyle S_{0},C_{0}}$ ${\displaystyle K[0,0]}$ ${\displaystyle 0{\xrightarrow[{f}]{0}}0}$ ${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$ ${\displaystyle \Delta _{0}^{K}=0}$
${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

Paso cuatro: Es trivial ver que: Si esto se sustituye en los senderos diferenciales combinados anteriores, el resultado será: Que es lo mismo que la definición anterior para una biclique:
${\displaystyle S_{j}=S_{0}\oplus \nabla _{j}}$
${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}$
${\displaystyle C_{i}=C_{0}\oplus \Delta _{i}}$

${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

De este modo es posible crear una bicicleta de tamaño ( ya que todas las llaves del primer juego de llaves se pueden combinar con las llaves del segundo juego de llaves). Esto significa que se puede crear una biclique de tamaño usando solo cálculos de los diferenciales y más . Si es así , todas las claves también serán diferentes en la bicicleta. ${\displaystyle 2^{2d}}$ ${\displaystyle 2^{2d}}$ ${\displaystyle 2^{d}}$ ${\displaystyle 2^{d}}$ ${\displaystyle 2^{2d}}$ ${\displaystyle 2*2^{d}}$ ${\displaystyle \Delta _{i}}$ ${\displaystyle \nabla _{j}}$ ${\displaystyle f}$ ${\displaystyle \Delta _{i}\neq \nabla _{j}}$ ${\displaystyle i+j>0}$ ${\displaystyle K[i,j]}$

Así es como se construye la biclique en el ataque biclique líder sobre AES. Existen algunas limitaciones prácticas en la construcción de bicicletas con esta técnica. Cuanto más larga sea la bicicleta, más vueltas deberán recorrer los senderos diferenciales. Las propiedades de difusión del cifrado juegan, por tanto, un papel crucial en la eficacia de la construcción de la biclique.

Otras formas de construir la biclique

Bogdanov, Khovratovich y Rechberger también describen otra forma de construir la biclique, llamada 'Intercalado de senderos diferenciales de claves relacionadas' en el artículo: "Biclique Cryptanalysis of the Full AES ^[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 está indexada como en una matriz de tamaño . El atacante divide el cifrado en dos subcifrados y (de modo que ), como en un ataque MITM normal. El conjunto de claves para cada uno de los subcifradores es de cardinalidad , y se denomina y . La clave combinada de los subcifradores se expresa con la matriz antes mencionada . ${\displaystyle 2^{2d}}$ ${\displaystyle d}$ ${\displaystyle K[i,j]}$ ${\displaystyle 2^{d}\times 2^{d}}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle E=f\circ g}$ ${\displaystyle 2^{d}}$ ${\displaystyle K[i,0]}$ ${\displaystyle K[0,j]}$ ${\displaystyle K[i,j]}$

Paso dos: el atacante construye una biclique para cada grupo de llaves. La biclique es de dimensión-d, ya que asigna estados internos, a textos cifrados, utilizando claves. La sección "Cómo construir la biclique" sugiere cómo construir la biclique usando "Diferenciales de claves relacionadas independientes". La biclique se construye en ese caso utilizando los diferenciales del juego de claves, y , pertenecientes a los subcifrados. ${\displaystyle 2^{2d}}$ ${\displaystyle 2^{d}}$ ${\displaystyle S_{j}}$ ${\displaystyle 2^{d}}$ ${\displaystyle C_{i}}$ ${\displaystyle 2^{2d}}$ ${\displaystyle K[i,0]}$ ${\displaystyle K[0,j]}$

Paso tres: el atacante toma los posibles textos cifrados, y solicita a un oráculo de descifrado que proporcione los textos sin formato correspondientes . ${\displaystyle 2^{d}}$ ${\displaystyle C_{i}}$ ${\displaystyle P_{i}}$

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 sin formato. ${\displaystyle S_{j}}$ ${\displaystyle P_{i}}$ ${\displaystyle f}$ ${\displaystyle g}$

Paso cinco: Siempre que se encuentra una clave candidata que coincide con , esa clave se prueba en otro par de texto plano/cifrado. Si la clave se valida en el otro par, es muy probable que sea la clave correcta. ${\displaystyle S_{j}}$ ${\displaystyle P_{i}}$

Ataque de ejemplo

El siguiente ejemplo se basa en el ataque biclique a AES del artículo "Biclique Cryptanalysis of the Full AES ^[1] ".
Las descripciones del ejemplo utilizan la misma terminología que utilizaron los autores del ataque (es decir, para nombres de variables, etc.).
Para simplificar, a continuación se trata el ataque a la variante AES128.
El ataque consiste en un ataque MITM de 7 asaltos con la biclique cubriendo los últimos 3 asaltos.

Partición de claves

El espacio de claves se divide en grupos de claves, donde cada grupo consta de claves. Para cada uno de los grupos, se selecciona una clave base única para el cálculo base. La clave base tiene dos bytes específicos establecidos en cero, como se muestra en la siguiente tabla (que representa la clave de la misma manera que lo hace AES en una matriz 4x4 para AES128): ${\displaystyle 2^{112}}$ ${\displaystyle 2^{16}}$
${\displaystyle 2^{112}}$ ${\displaystyle K[0,0]}$

${\displaystyle {\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

Luego se enumeran los 14 bytes (112 bits) restantes de la clave. Esto produce claves base únicas; uno para cada grupo de claves. Luego se eligen las claves ordinarias de cada grupo con respecto a su clave base. Se eligen de manera que sean casi idénticas a la clave base. Solo varían en 2 bytes (ya sea 's o 's) de los 4 bytes que se muestran a continuación: ${\displaystyle 2^{112}}$
${\displaystyle 2^{16}}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle {\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

Esto da y , que combinado da claves diferentes ,. estas claves constituyen las claves del grupo para una clave base respectiva. ${\displaystyle 2^{8}K[i,0]}$ ${\displaystyle 2^{8}K[0,j]}$ ${\displaystyle 2^{16}}$ ${\displaystyle K[i,j]}$ ${\displaystyle 2^{16}}$

construcción biclique

${\displaystyle 2^{112}}$bicliques se construye utilizando la técnica "Diferenciales de claves relacionadas independientes", como se describe en la sección "Cómo construir la biclique".
El requisito para utilizar 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 esto es así?
Debido a la forma en que se eligen las claves en el paso 1 en relación con la clave base, los senderos diferenciales que usan las claves nunca comparten ninguna S-box activa (que es el único componente no lineal en AES), y los senderos diferenciales que usan el llave . Por lo tanto, es posible XOR los senderos diferenciales y crear la biclique. ${\displaystyle \Delta _{i}}$ ${\displaystyle K[i,0]}$ ${\displaystyle \nabla _{j}}$ ${\displaystyle K[0,j]}$

Ataque MITM

Cuando se crean las bicliques, el ataque MITM casi puede comenzar. Sin embargo , antes de realizar el ataque MITM, los valores intermedios del texto plano: , los valores intermedios del texto cifrado: y los estados intermedios y subclaves correspondientes o , se calculan previamente y se almacenan. ${\displaystyle 2^{d}}$
${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$
${\displaystyle 2^{d}}$
${\displaystyle {\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}}$
${\displaystyle K[i,0]}$ ${\displaystyle K[0,j]}$

Ahora se puede llevar a cabo el ataque MITM. Para probar una clave , sólo es necesario recalcular las partes del cifrado, que se sabe variarán entre y . Para el cálculo hacia atrás desde hasta , son 4 cajas S las que deben volver a calcularse. Para el cálculo directo desde hasta , es solo 3 (se puede encontrar una explicación detallada de la cantidad de recálculo necesario en el documento "Biclique Cryptanalysis of the full AES ^[1] ", de donde se tomó este ejemplo). ${\displaystyle K[i,j]}$ ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$ ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$ ${\displaystyle S_{j}}$ ${\displaystyle {\xleftarrow[{v_{j}}]{}}}$ ${\displaystyle P_{i}}$ ${\displaystyle {\xrightarrow[{v_{i}}]{}}}$

Cuando los valores intermedios coinciden, se encuentra un candidato clave entre y . Luego, la clave candidata se prueba en otro par de texto plano/cifrado. ${\displaystyle K[i,j]}$ ${\displaystyle P_{i}}$ ${\displaystyle S_{j}}$

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 . ${\displaystyle 2^{126.18}}$ ${\displaystyle 2^{88}}$ ${\displaystyle 2^{8}}$

Referencias

1. Bogdanov, Andrey; Khovratovich, Dmitry; Rechberger, Christian. "Criptoanálisis biclique del AES completo" (PDF) . Archivado desde el original (PDF) el 14 de junio de 2012.
2. Khovratovich, Dmitry; Leurent, Gaëtan; Rechberger, cristiano (2012). "Narrow-Bicliques: criptoanálisis de IDEA completa". Eurocripta 2012 . págs. 392–410. CiteSeerX 10.1.1.352.9346 . 
3. Bicliques para preimágenes: ataques a Skein-512 y la familia SHA-2
4. Diffie, Whitfield; Hellman, Martin E. "Criptoanálisis exhaustivo del estándar de cifrado de datos NBS" (PDF) . Archivado desde el original (PDF) el 3 de marzo de 2016 . Consultado el 11 de junio de 2014 .
5. Khovratovich, Dmitry; Rechberger, cristiano; Savelieva, Alexandra. "Bicliques para preimágenes: ataques a Skein-512 y la familia SHA-2" (PDF) .