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 .
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:
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.
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.
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.
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.
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.
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:
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 externaLa 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 .
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]