Ataque de rebote

El ataque de rebote es una tecnología para el criptoanálisis de funciones hash criptográficas . Este ataque fue publicado por primera vez por Florian Mendel, Christian Rechberger, Martin Schlaffer y Soren Thompson en 2009. Estaba destinado a atacar algoritmos similares a AES como Whirlpool y Grøstl , pero luego se demostró que también era aplicable a otras construcciones como Keccak , JH y Skein .

Idea principal

Rebound Attack  es un ataque hash estadístico que utiliza criptoanálisis rotacional y diferencial para encontrar colisiones de funciones y vulnerabilidades .

La idea principal del ataque es estudiar las características diferenciales de un cifrado de bloque (o sus fragmentos), permutación u otros algoritmos criptográficos de bajo nivel. Encontrar valores que satisfagan las características se logra dividiendo el algoritmo primitivo en 3 partes: .  - la fase interna, y juntos forman la fase externa. El atacante elige valores que implementan de forma determinista parte de las características diferenciales de la fase externa, y complementa el resto de características de forma probabilística.

El ataque de rebote incluye 2 etapas:

  1. La fase interna cubre una parte de las características diferenciales que son difíciles de realizar en forma probabilística. Aquí el objetivo es encontrar muchas soluciones para esta parte de las características con una complejidad de tiempo promedio baja . Para lograr este objetivo, se debe subdeterminar el sistema de ecuaciones correspondiente que describe la característica en esta fase . Al buscar una solución, hay muchos grados de libertad que dan muchos puntos de partida. La fase de entrada se puede repetir varias veces para obtener suficientes puntos para ejecutar con éxito la fase de salida.
  2. En la fase exterior , los pares emparejados de la fase interior se utilizan en los cálculos directos e inversos. Por lo general y tienen una probabilidad baja, por lo que es necesario repetir la fase interna para obtener más puntos de partida.

La ventaja de usar una entrada y dos fases de salida del algoritmo es la capacidad de calcular características diferenciales complejas de manera más eficiente y precisa. Este método es más eficiente que los métodos diferenciales estándar.

Una descripción detallada de cómo atacar funciones hash con funciones de compresión similares a AES

Considere las funciones hash que usan cifrados de bloques de sustitución y permutación similares a AES como funciones de compresión . Esta función de compresión consta de una serie de rondas de S-boxes y transformaciones lineales. La idea principal del ataque es construir una característica diferencial, que tiene la parte computacional más compleja en el medio. Esta parte se utilizará en la fase interna, mientras que las partes más fáciles de calcular de la característica estarán en la fase externa. El sistema de ecuaciones que describe las características en la fase interna debe subdeterminarse para obtener un conjunto de puntos de partida en la fase externa. Dado que las partes más difíciles de la característica están contenidas en la fase interna, la fase externa usa funciones simples para calcular las características diferenciales. Al principio, la fase interna tiene una pequeña cantidad de bytes activos (distintos de cero) , hacia la mitad su número aumenta significativamente y al final de la fase vuelve a disminuir a una pequeña cantidad. La idea principal es obtener una gran cantidad de bytes activos dentro y fuera del S-box en el medio de la fase. Las características se pueden calcular de manera eficiente utilizando los valores de diferencia al principio y al final de la fase y haciendo coincidir la entrada y la salida del S-box.

En la fase externa, las características coincidentes se verifican en las direcciones de avance y retroceso para determinar si coinciden con las características diferenciales deseadas. Por lo general, está dirigido a encontrar pares de valores eficientes de algoritmos truncados, ya que es donde tiene la mayor probabilidad de éxito. La posibilidad de encontrar las características deseadas en la fase externa depende directamente del número de bytes activos y su ubicación en la característica. Para lograr la colisión , no basta con tener diferencias de algún tipo en particular; cualquier byte activo en la entrada y salida de la característica debe tener un valor que cancele todas las operaciones posteriores del algoritmo. Así, al diseñar una característica, cualquier número de bytes activos al principio y al final de la fase externa debe estar en la misma posición. La obtención de tales valores de bytes aumenta la probabilidad de obtener características de fase exterior.

En general, es necesario generar tantas características de fase interna como para obtener más de un conjunto esperado de características de fase externa. Además, existe la posibilidad de obtener una colisión cercana, donde algunos bytes activos al principio y al final de la fase externa no cancelan más acciones del algoritmo.

Un ejemplo de un ataque a Whirlpool

Se puede usar un ataque de rebote en la función hash de Whirlpool para encontrar colisiones en 4.5 o 5.5 rondas. Casi colisiones se pueden encontrar en 6.5 y 7.5 rondas. El ataque de 4.5 rondas se describe a continuación.

Precálculos

Número de decisiones Frecuencia
0 39655
2 20018
cuatro 5043
6 740
ocho 79
256 una

Para que el ataque de rebote sea más eficiente, la tabla de diferencia de S-box se calcula antes de que comience el ataque. Deje denotar S-bloque. Luego, para cada par, encontramos soluciones (si las hay) a la siguiente igualdad

,

donde  es la diferencia en la entrada y  es la diferencia en la salida del S-box. Esta tabla de 256x256 permite encontrar valores que satisfagan las características para todos los posibles pares que pasan por la S-box. La tabla de la derecha muestra el número posible de soluciones y la probabilidad de que ocurran. La primera línea muestra el caso sin soluciones, la última describe el caso con diferencia cero.

Realizando un ataque

Para encontrar una colisión de Whirlpool en 4.5 rondas, se deben calcular las características diferenciales en la tabla a continuación. La característica con la menor cantidad de bytes activos está marcada en rojo. La característica se puede describir por el número de bytes activos en cada ronda, por ejemplo, 1 → 8 → 64 → 8 → 1 → 1.

Característica diferencial truncada en 4.5 rondas de la función hash Whirlpool.
Fase interna

El propósito de la fase interna es completar las diferencias características en el paso 8 → 64 → 8. Esto se puede hacer en 3 pasos:

  1. Elija un valor arbitrario distinto de cero para los 8 bytes activos en la salida de la operación de difusión lineal en la ronda 3. Estas diferencias luego se propagan de nuevo a la salida de la operación de permutación circular en la ronda 3. Debido a las propiedades de la operación de difusión lineal , todos los bytes se activan. Esto se puede hacer de forma independiente para cada fila.
  2. Elija un valor para cada byte activo en la entrada de la operación de difusión lineal en la ronda 2 y propague estas diferencias hacia la entrada de la operación de permutación circular en la ronda 3. Haga esto para las 255 diferencias distintas de cero de cada byte. Nuevamente, esto se puede hacer de forma independiente para cada fila.
  3. En la fase interna, utilizando la tabla de diferencias (DDT), se pueden igualar las diferencias de entrada y salida (tal como se encuentran en los pasos 1 y 2) de la operación de permutación cíclica en la ronda 3. Cada fila se puede probar de forma independiente y se esperan 2 soluciones por S-box. En total, el número esperado de valores que satisfacen la característica diferencial es 2 64 .

Estos pasos se pueden repetir con 264 valores de entrada diferentes en el paso 1, dando como resultado un total de 2128 valores que satisfacen la característica diferencial de fase interna. Cada conjunto de 2 64 valores se puede encontrar con una complejidad de 2 8 rondas de transformaciones debido al paso de precálculo.

Fase externa

La fase externa complementa estas características de forma probabilística. Utiliza diferenciales truncados en lugar de fase interna. Cada punto de referencia se cuenta hacia adelante y hacia atrás. Para obtener las características originales, 8 bytes activos deben formar 1 byte activo en ambas direcciones. La conversión de 8 bytes a 1 ocurre con una probabilidad de 2 −56 , [1] , por lo que obtener características tiene una probabilidad de 2 −112 . Para obtener una colisión sin ambigüedades, es necesario que los bytes en la entrada y la salida bloqueen todas las operaciones posteriores. Esto sucede con una probabilidad de aproximadamente 2 −8 , en general la probabilidad de éxito de la fase externa es de 2 −120 .

Para detectar una colisión, se deben generar al menos 2.120 puntos en la fase interna. Después de eso, la operación de descubrimiento se puede realizar con una complejidad de tiempo de 1 por punto de partida, [2] por lo tanto, la complejidad de tiempo final del ataque es 2 120 .

Actualizaciones de ataque

Un ataque básico de 4.5 rondas se puede actualizar a un ataque de 5.5 rondas agregando 1 ronda más a la fase interna. Esto aumentará la complejidad temporal del algoritmo a 2184 . [3]

La mejora de la fase exterior para comenzar y finalizar con 8 bytes activos resultó en una casi colisión de 52 bytes Whirlpool , extendiendo el ataque a 7.5 rondas con una complejidad de tiempo de 2192 . [3]

Suponiendo que el atacante tiene control sobre el valor de la cadena y, por lo tanto, la entrada en el gráfico de claves de Whirlpool, el ataque puede extenderse a 9,5 rondas con una colisión condicionalmente libre de 52 bytes con una complejidad de tiempo de 2128 . [cuatro]

Notas

  1. ↑ Lamberger, Mendel, Rechberger, Rijmen, Schlaffer, 2010, pág. Dieciocho
  2. ↑ Lamberger, Mendel, Rechberger, Rijmen, Schlaffer, 2010, pág. 22
  3. ↑ 1 2 Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 25
  4. ↑ Lamberger, Mendel, Rechberger, Rijmen, Schlaffer, 2010, pág. 31

Literatura