Ataque biclicuo

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 extender 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 a AES completo ^[1] como a 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 las funciones hash Skein-512 y SHA-2 . ^[3]

El ataque biclique sigue siendo (a fecha de abril de 2019 ^[actualizar]) el ataque de clave única más conocido públicamente contra AES . La complejidad computacional del ataque es de , 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}}$

Como la complejidad computacional del ataque es 1 , se trata de un ataque teórico, lo que significa que la seguridad de AES no se ha visto vulnerada y su uso sigue siendo relativamente seguro. No obstante, el ataque biclique es un ataque interesante que sugiere un nuevo enfoque para realizar criptoanálisis en cifrados de bloques. El ataque también ha proporcionado más información sobre AES, ya que ha puesto en tela de juicio el margen de seguridad en el número de rondas utilizadas en él. ${\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 de 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 solo , ya que uno puede forzar de forma independiente el primer y el segundo cifrado DES si tiene el texto simple 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 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 de bloque, cuando publicaron su ataque a AES. Antes de esto, los ataques MITM a 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 "subcifrados MITM" para facilitar el ataque MITM, algo que es difícil de lograr con muchos programas de clave modernos, como el de AES.

La biclique

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

En un ataque MITM, los bits de clave y , pertenecientes 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 simple y el 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. Consulte el ataque MITM de 3 subconjuntos ). Esta propiedad suele ser difícil de explotar en una gran cantidad 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 grandes serán los subcifrados que tendrás. Cuanto más grandes sean los subcifrados, menos bits de clave independientes entre los subcifrados tendrás que forzar de forma independiente. Por supuesto, la cantidad real de bits de clave independientes en cada subcifrado depende de las propiedades de difusión del esquema de claves.

La forma en que la estructura biclique ayuda a abordar lo anterior es que permite, por ejemplo, atacar 7 rondas de AES usando ataques MITM y luego, al utilizar una estructura biclique 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 completo de rondas del cifrado, incluso si no fuera posible atacar esa cantidad de rondas con un ataque MITM básico.

El significado de la biclique es, por lo tanto, 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, por supuesto, depende 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 obtenidos por fuerza bruta en el primer y segundo subcifrado del ataque MITM.

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

Cómo construir el biclique

Fuerza bruta

Obtenga estados intermedios y textos cifrados, luego calcule las claves que los relacionan. Esto requiere la recuperación 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 independientes de claves relacionadas

(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 de la biclique es mapear los valores intermedios, , a los valores del texto cifrado, , en función de la clave tal 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 es la función que asigna un estado intermedio a un texto cifrado utilizando una clave dada. 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 relacionadas por tamaño . Las claves se eligen de manera 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 compartan ningún componente no lineal activo. ${\displaystyle \Delta _{i}}$ ${\displaystyle \nabla _{j}}$

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

Paso tres: Dado que los rastros no comparten ningún componente no lineal (como las cajas S), los rastros 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, ya que los diferenciales lo son con respecto al cálculo base. Sustituyendo en cualquiera de las dos definiciones, se obtendrá ya que y . Esto significa que la tupla del cálculo base, también se puede aplicar mediante XOR a los rastros combinados:
${\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 las trayectorias diferenciales combinadas anteriores, el resultado será: Que es lo mismo que la definición que había anteriormente 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}}$

Por lo tanto, es posible crear una biclique de tamaño ( ya que todas las claves del primer conjunto de claves se pueden combinar con las claves del segundo conjunto de claves). Esto significa que se puede crear una biclique de tamaño utilizando solo cálculos de los diferenciales y sobre . Si para entonces todas las claves también serán diferentes en la biclique. ${\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]}$

De esta manera se construye la biclique en el principal ataque biclique en AES. Existen algunas limitaciones prácticas en la construcción de bicliques con esta técnica. Cuanto más larga sea la biclique, más rondas deben cubrir los rastros diferenciales. Por lo tanto, las propiedades de difusión del cifrado desempeñan 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 el biclique, llamada '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 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 subcifrados es de cardinalidad , y se denomina y . La clave combinada de los subcifrados 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 claves. 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 utilizando "Diferenciales de claves relacionadas independientes". La biclique se construye en ese caso utilizando los diferenciales del conjunto 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 pide a un oráculo de descifrado que proporcione los textos simples 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 un candidato a clave que coincide con , esa clave se prueba en otro par de texto simple/cifrado. Si la clave se valida en el otro par, es muy probable que sea la clave correcta. ${\displaystyle S_{j}}$ ${\displaystyle P_{i}}$

Ejemplo de ataque

El siguiente ejemplo se basa en el ataque biclique a 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.).
Para simplificar, se trata a continuación el ataque a la variante AES128.
El ataque consiste en un ataque MITM de 7 rondas, en el que el ataque biclique cubre las últimas 3 rondas.

Particionamiento 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 configurados 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}}}$

A continuación, se enumeran los 14 bytes restantes (112 bits) de la clave. Esto produce claves base únicas; una para cada grupo de claves. Las claves ordinarias de cada grupo se eligen con respecto a su clave base. Se eligen de modo que sean casi idénticas a la clave base. Solo varían en 2 bytes (los o los ) 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 combinados dan 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 de "Diferenciales de claves relacionadas independientes", como se describe en la sección "Cómo construir el biclique".
El requisito para utilizar esa técnica era que los senderos diferenciales hacia adelante y hacia atrás que se deben combinar 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, los senderos diferenciales que utilizan las claves nunca comparten ninguna caja S activa (que es el único componente no lineal en AES), con los senderos diferenciales que utilizan la clave . Por lo tanto, es posible realizar una operación XOR en los senderos diferenciales y crear el 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. Antes de realizar el ataque MITM, los valores intermedios del texto simple: , 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 , solo es necesario recalcular las partes del cifrado, que se sabe que variarán entre y . Para el cálculo hacia atrás de a , se trata de 4 cajas S que deben recalcularse. Para el cálculo hacia delante 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). ${\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 a clave entre y . Luego, el candidato a clave se prueba en otro par de texto simple/cifrado. ${\displaystyle K[i,j]}$ ${\displaystyle P_{i}}$ ${\displaystyle S_{j}}$

Resultados

Este ataque reduce la complejidad computacional de AES128 a , lo que es entre 3 y 5 veces más rápido que un ataque de fuerza bruta. La complejidad de los datos del ataque es de , y la complejidad de la memoria es de . ${\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. Biclicas 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 2016-03-03 . Consultado el 2014-06-11 .
5. Khovratovich, Dmitry; Rechberger, Christian; Savelieva, Alexandra. "Bicliques para preimágenes: ataques a Skein-512 y la familia SHA-2" (PDF) .