Ataque de rebote

El ataque de rebote es una herramienta en el criptoanálisis de funciones hash criptográficas . Este ataque fue publicado por primera vez en 2009 por Florian Mendel, Christian Rechberger, Martin Schläffer y Søren Thomsen. Fue concebido para atacar funciones similares a AES , como Whirlpool y Grøstl , pero posteriormente se demostró que también era aplicable a otros diseños como Keccak , JH y Skein .

El ataque

El ataque de rebote es un tipo de ataque estadístico contra las funciones hash , que utiliza técnicas como el criptoanálisis rotacional y diferencial para encontrar colisiones y otras propiedades interesantes.

La idea básica del ataque es observar una determinada característica diferencial en un cifrado de bloques (o en una parte del mismo), una permutación u otro tipo de primitiva . Encontrar valores que cumplan la característica se logra dividiendo la primitiva. $E$ en tres partes de tal manera que $E=E_{\text{fw}}\circ E_{\text{in}}\circ E_{\text{bw}}$ . $E_{\text{en}}$ se denomina fase de entrada y $E_{\text{fw}}$ y $E_{\text{bw}}$ En conjunto, se denomina fase de salida. El atacante elige entonces valores que realizan de forma determinista parte de la característica diferencial en la fase de entrada, y completan el resto de la característica de forma probabilística.

Por lo tanto, el ataque de rebote consta de 2 fases:

La fase de entrada (o de coincidencia intermedia) abarca la parte de la característica diferencial que resulta difícil de satisfacer de forma probabilística. El objetivo es encontrar múltiples soluciones para esta parte de la característica con una complejidad media baja . Para ello, el sistema de ecuaciones correspondiente, que describe la característica en esta fase, debe estar subdeterminado. Al buscar una solución, existen, por lo tanto, muchos grados de libertad, lo que genera múltiples soluciones posibles. La fase de entrada puede repetirse varias veces para obtener un número suficiente de puntos de partida que aumenten las probabilidades de éxito de la fase de salida.
En la fase de salida, cada solución de la fase de entrada se propaga hacia afuera en ambas direcciones, comprobando si la característica también se cumple en esta fase. La probabilidad de que la característica se cumpla en la fase de salida debe ser lo más alta posible.

La ventaja de utilizar una fase de entrada y dos de salida radica en la capacidad de calcular de forma eficiente las partes más complejas de la característica diferencial durante la fase de entrada. Además, garantiza una alta probabilidad en la fase de salida. Por lo tanto, la probabilidad global de encontrar una característica diferencial es mayor que la que se obtiene con las técnicas diferenciales estándar.

Descripción detallada del ataque a funciones hash con funciones de compresión tipo AES.

Consideremos una función hash que utiliza un cifrado de bloques de sustitución-permutación tipo AES como función de compresión . Esta función consta de varias rondas compuestas por cajas S y transformaciones lineales. La idea general del ataque es construir una característica diferencial cuya parte más costosa computacionalmente se encuentre en el centro. Esta parte se cubrirá en la fase de entrada, mientras que la parte más fácil de obtener se cubrirá en la fase de salida. El sistema de ecuaciones que describe la característica en la fase de entrada debe ser subdeterminado , de modo que se puedan generar muchos puntos de partida para la fase de salida. Dado que la parte más difícil de la característica se encuentra en la fase de entrada, es posible utilizar diferenciales estándar en esta fase, mientras que en la fase de salida se utilizan diferenciales truncados para lograr mayores probabilidades.

La fase de entrada normalmente tendrá un número reducido de bytes de estado activo ( bytes con diferencias distintas de cero) al principio, que luego se propagan a un gran número de bytes activos en la mitad de la ronda, antes de volver a un número bajo de bytes activos al final de la fase. La idea es tener un gran número de bytes activos en la entrada y salida de una caja S en la mitad de la fase. Las características se pueden calcular de manera eficiente eligiendo valores para las diferencias al inicio y al final de la fase de entrada, propagándolos hacia la mitad y buscando coincidencias en la entrada y salida de la caja S. Para cifrados como AES , esto generalmente se puede hacer por filas o columnas, lo que hace que el procedimiento sea relativamente eficiente. Elegir diferentes valores iniciales y finales da como resultado muchas características diferenciales diferentes en la fase de entrada.

En la fase de salida, el objetivo es propagar las características encontradas en la fase de entrada hacia atrás y hacia adelante, y verificar si se siguen las características deseadas. Aquí, se suelen usar diferenciales truncados , ya que estos dan probabilidades más altas, y los valores específicos de las diferencias son irrelevantes para el objetivo de encontrar una colisión . La probabilidad de que la característica siga el patrón deseado de la fase de salida depende del número de bytes activos y de cómo están dispuestos en la característica. Para lograr una colisión , no basta con que los diferenciales en la fase de salida sean de un tipo específico; cualquier byte activo al principio y al final de la característica también debe tener un valor tal que se cancele cualquier operación de realimentación hacia adelante. Por lo tanto, al diseñar la característica, cualquier número de bytes activos al principio y al final de la fase de salida debe estar en la misma posición. La probabilidad de que estos bytes se cancelen se suma a la probabilidad de la característica de salida.

En general, es necesario generar suficientes características en la fase de entrada para obtener un número esperado de características correctas mayor que uno en la fase de salida. Además, se pueden lograr casi colisiones en un mayor número de rondas al comenzar y terminar la fase de salida con varios bytes activos que no se cancelan.

Ejemplo de ataque a Whirlpool

El ataque de rebote se puede utilizar contra la función hash Whirlpool para encontrar colisiones en variantes donde la función de compresión (el cifrado de bloques tipo AES , W) se reduce a 4,5 o 5,5 rondas. Se pueden encontrar casi colisiones en 6,5 y 7,5 rondas. A continuación se describe el ataque de 4,5 rondas.

Precomputación

Para que el ataque de rebote sea efectivo, se calcula una tabla de búsqueda para las diferencias de la caja S antes del ataque. $S:\{0,1\}^{8}\to \{0,1\}^{8}$ representa la caja S. Luego, para cada par $(a,b)\in \{0,1\}^{8}$ encontramos las soluciones $x$ (si los hay) a la ecuación

S(x)\oplus S(x\oplus a)=b

,

dónde $a$ representa la diferencia de entrada y $b$ representa la diferencia de salida de la caja S. Esta tabla de 256 x 256 (llamada tabla de distribución de diferencias, TDD) permite encontrar valores que siguen la característica para cualquier par de entrada/salida específico que pase por la caja S. La tabla de la derecha muestra el número posible de soluciones de la ecuación y su frecuencia. La primera fila describe diferenciales imposibles, mientras que la última fila describe el diferencial cero.

Realizando el ataque

Para detectar una colisión en 4,5 rondas de Whirlpool , se debe encontrar una característica diferencial del tipo que se muestra en la tabla a continuación. Esta característica tiene un mínimo de bytes activos (bytes con diferencias distintas de cero), marcados en rojo. La característica se puede describir mediante el número de bytes activos en cada ronda, por ejemplo: 1 → 8 → 64 → 8 → 1 → 1.

La fase de entrada

El objetivo de la fase de entrada es encontrar diferencias que cumplan con la parte de la característica descrita por la secuencia de bytes activos 8 → 64 → 8. Esto se puede hacer en los siguientes tres pasos:

Elija una diferencia no nula arbitraria para los 8 bytes activos a la salida de la operación MixRows en la ronda 3. Estas diferencias se propagan hacia atrás hasta la salida de la operación SubBytes en la ronda 3. Debido a las propiedades de la operación MixRows, se obtiene un estado completamente activo. Tenga en cuenta que esto se puede realizar para cada fila de forma independiente.
Seleccione una diferencia para cada byte activo en la entrada de la operación MixRows en la ronda 2 y propague estas diferencias a la entrada de la operación SubBytes en la ronda 3. Repita este proceso para las 255 diferencias distintas de cero de cada byte. Cabe mencionar que esto puede hacerse de forma independiente para cada fila.
En el paso de coincidencia en el medio , usamos la tabla DDT para encontrar diferencias de entrada/salida coincidentes (como se encontró en los pasos 1 y 2) con la operación SubBytes en la ronda 3. Cada fila se puede verificar de forma independiente, y el número esperado de soluciones es 2 por S-box . En total, el número esperado de valores que siguen la característica diferencial es 2 ⁶⁴ .

Estos pasos se pueden repetir con ^2⁶⁴ valores iniciales diferentes en el paso 1, lo que da como resultado un total de 2¹²⁸ ^valores reales que siguen la característica diferencial en la fase de entrada. Cada conjunto de ^2⁶⁴ valores se puede encontrar con una complejidad de ^2⁸ transformaciones de ronda debido al paso de precomputación.

La fase de salida

La fase de salida completa la característica diferencial de forma probabilística. La fase de salida utiliza diferenciales truncados , a diferencia de la fase de entrada. Cada punto de partida encontrado en la fase de entrada se propaga hacia adelante y hacia atrás. Para seguir la característica deseada, 8 bytes activos deben propagarse a un único byte activo en ambas direcciones. Una de estas transiciones de 8 a 1 ocurre con una probabilidad de 2 ⁻⁵⁶ , ^{[ 1 ]} por lo que cumplir la característica tiene una probabilidad de 2 ⁻¹¹² . Para asegurar una colisión , los valores al inicio y al final de la característica deben cancelarse durante la operación de alimentación hacia adelante. Esto ocurre con una probabilidad aproximada de 2 ⁻⁸ , y la probabilidad general de la fase de salida es, por lo tanto, 2 ⁻¹²⁰ .

Para encontrar una colisión , se deben generar 2 ^{120 puntos de inicio en la fase de entrada. Dado que esto se puede hacer con una}complejidad promedio de 1 por punto de inicio, ^{[ 2 ]} la complejidad general del ataque es 2 ¹²⁰ .

Extender el ataque

El ataque básico de 4,5 rondas se puede extender a un ataque de 5,5 rondas utilizando dos estados completamente activos en la fase de entrada. Esto aumenta la complejidad a aproximadamente 2 ¹⁸⁴ . ^{[ 3 ]}

Extender la fase de salida para que comience y termine con 8 bytes activos conduce a una casi colisión en 52 bytes en Whirlpool reducido a 7,5 rondas con una complejidad de 2 ¹⁹² . ^{[ 4 ]}

Suponiendo que el atacante tiene control sobre el valor de encadenamiento y, por lo tanto, sobre la entrada al esquema de claves de Whirlpool , el ataque puede extenderse aún más a 9,5 rondas en una casi colisión de inicio semilibre en 52 bytes con una complejidad de 2 ¹²⁸ . ^{[ 5 ]}

Notas

↑ Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 18
↑ Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 22
↑ Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 25
↑ Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 25
↑ Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 31

Referencias

El ataque de rebote: criptoanálisis de Reduced Whirlpool y Grøstl por Florian Mendel, Christian Rechberger, Martin Schlaffer y Soren S. Thomsen (Fast Software Encryption 2009: 260-276)
El ataque de rebote a la función hash de Grøstl reducida por Florian Mendel, Christian Rechberger, Martin Schlaffer y Soren S. Thomsen (Pista del criptógrafo en la Conferencia RSA 2010: 350-365)
Ataque de rebote no alineado: aplicación a Keccak por Alexandre Duc, Jian Guo, Thomas Peyrin, Lei Wei (Archivo de preimpresiones de criptología de la IACR, año 2011 / 420)
Cómo mejorar los ataques de rebote por María Naya-Plasencia FHNW, Windisch, Suiza (Actas de CRYPTO'11, 31.ª conferencia anual sobre avances en criptología, páginas 188-205)
El ataque de rebote y los distinguidores de subespacio: aplicación a Whirlpool por Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen y Martin Schläffer (Archivo de preimpresiones de criptología de la IACR, año 2010/198).
Criptoanálisis de funciones hash basadas en AES. Tesis doctoral de Martin Schläffer.

[1] Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 18

[2] Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 22

[3] Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 25

[4] Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 25

[5] Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, pág. 31

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]