Ataque de la bicicleta

Conseguir${\displaystyle 2^{d}}$^{[ 7 ]} estados intermedios ^{[ 8 ]} y${\displaystyle 2^{d}}$textos cifrados ^{[ 9 ]} , luego calcula las claves que mapean un único valor intermedio a todos los textos cifrados. Continúa ese proceso de mapeo de claves "uno a muchos" repitiéndolo para todos los valores intermedios.

Este proceso de mapeo requiere${\displaystyle (2^{d})_{\text{número de estados intermedios}}\cdot (2^{d})_{\text{número de textos cifrados por estado intermedio}}=2^{d+d}=2^{2d}}$recuperación de claves, ya que cada estado intermedio debe estar vinculado a todos los textos cifrados (no solo a un texto cifrado). ^{[ 10 ]}

(Este método fue sugerido por Bogdanov, Khovratovich y Rechberger en su artículo: Criptoanálisis biclique del AES completo ^{[ 2 ]} )

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

Procedimiento: Paso uno: Un estado intermedio(${\displaystyle S_{0}}$), un texto cifrado(${\displaystyle C_{0}}$) y una clave(${\displaystyle K[0,0]}$) se elige de tal manera que:${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$, dónde${\displaystyle f}$Es la función que asigna un estado intermedio a un texto cifrado utilizando una clave dada. Esto se denomina cálculo base.

Paso dos: Dos conjuntos de claves relacionadas de tamaño${\displaystyle 2^{d}}$Se elige. Las claves se eligen de tal manera que:

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

En otras palabras: una diferencia de entrada de 0 debería corresponder a una diferencia de salida de${\displaystyle \Delta _{i}}$bajo una diferencia clave de${\displaystyle \Delta _{i}^{K}}$. Todas las diferencias son con respecto al cálculo base. Una diferencia de entrada de${\displaystyle \nabla _{j}}$debería asignarse a una diferencia de salida de 0 bajo una diferencia de clave de${\displaystyle \nabla _{J}^{K}}$Todas las diferencias se refieren al cálculo base.

Paso tres: Dado que las rutas no comparten ningún componente no lineal (por ejemplo, rutas que no comparten ninguna caja S ), las rutas se pueden combinar para obtener: ${\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}}$, que se ajusta a las definiciones de ambos diferenciales del paso 2. Es trivial ver que la tupla ^{[ 11 ]}${\displaystyle (S_{0},C_{0},K[0,0])}$a partir del cálculo base, también se ajusta por definición a ambos diferenciales, ya que los diferenciales son con respecto al cálculo base. Sustituyendo${\displaystyle S_{0},C_{0}}$${\displaystyle K[0,0]}$en cualquiera de las dos definiciones, dará como resultado${\displaystyle 0{\xrightarrow[{f}]{0}}0}$desde${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$y${\displaystyle \Delta _{0}^{K}=0}$Esto significa que la tupla del cálculo base también se puede combinar mediante XOR con los senderos combinados: ${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

Cuarto paso: Es obvio que: ${\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}}$ Si esto se sustituye en las trayectorias diferenciales combinadas anteriores, el resultado será: ${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$Lo cual es lo mismo que la definición que se dio anteriormente para una biclique:${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

Por lo tanto, es posible crear una biclique de tamaño${\displaystyle 2^{2d}}$(${\displaystyle 2^{2d}}$ya que todos${\displaystyle 2^{d}}$Las claves del primer conjunto de claves se pueden combinar con las${\displaystyle 2^{d}}$llaves del segundo conjunto de llaves). Esto significa una biclique de tamaño${\displaystyle 2^{2d}}$se puede crear utilizando únicamente${\displaystyle 2*2^{d}}$cálculos de los diferenciales${\displaystyle \Delta _{i}}$y${\displaystyle \nabla _{j}}$encima${\displaystyle f}$. Si${\displaystyle \Delta _{i}\neq \nabla _{j}}$para${\displaystyle i+j>0}$entonces todas las llaves${\displaystyle K[i,j]}$También será diferente en la biclique.

Así es como se construye la biclique en el ataque de biclique principal contra AES. Existen algunas limitaciones prácticas al construir bicliques con esta técnica. Cuanto más larga sea la biclique, más rondas deben cubrir las rutas diferenciales. Por lo tanto, las propiedades de difusión del cifrado desempeñan un papel crucial en la efectividad de la construcción de la biclique.

Bogdanov, Khovratovich y Rechberger también describen otra forma de construir la biclique, llamada 'Interleaving Related-Key Differential Trails' en el artículo: "Criptoanálisis de biclique del AES completo ^{[ 2 ]} ".

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

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

Luego se enumeran los 14 bytes restantes (112 bits) de la clave. Esto produce:${\displaystyle 2^{112}}$claves base únicas; una para cada grupo de claves. La ordinaria${\displaystyle 2^{16}}$Las claves de cada grupo se eligen 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 el${\displaystyle i}$de o el${\displaystyle j}$'s) de los 4 bytes que se muestran a continuación:

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

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

${\displaystyle 2^{112}}$La biclique se construye utilizando la técnica de "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 las rutas diferenciales hacia adelante y hacia atrás que debían 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, las rutas diferenciales${\displaystyle \Delta _{i}}$usando las teclas${\displaystyle K[i,0]}$nunca comparten ninguna caja S activa (que es el único componente no lineal en AES), con los rastros diferenciales${\displaystyle \nabla _{j}}$usando la clave${\displaystyle K[0,j]}$. Por lo tanto, es posible aplicar la operación XOR a las trayectorias diferenciales y crear la biclique.

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

Ahora se puede llevar a cabo el ataque MITM. Para probar una clave${\displaystyle K[i,j]}$, solo es necesario recalcular las partes del cifrado, que se sabe que variarán entre${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$y${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$Para el cálculo hacia atrás desde${\displaystyle S_{j}}$a${\displaystyle {\xleftarrow[{v_{j}}]{}}}$, esto son 4 cajas S que necesitan ser recalculadas. Para el cálculo hacia adelante desde${\displaystyle P_{i}}$a${\displaystyle {\xrightarrow[{v_{i}}]{}}}$, son solo 3 (una explicación detallada de la cantidad de recálculos necesarios se puede encontrar en el artículo "Criptoanálisis biclique del AES completo ^{[ 2 ]} ", del cual se toma este ejemplo).

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

Este ataque reduce la complejidad computacional de AES128 a${\displaystyle 2^{126.18}}$, 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${\displaystyle 2^{88}}$y la complejidad de la memoria es${\displaystyle 2^{8}}$.