El ataque de rebote es una herramienta en el criptoanálisis de funciones hash criptográficas . El 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 luego se demostró que también era aplicable a otros diseños como Keccak , JH y Skein .
El Rebound Attack es un tipo de ataque estadístico a 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 en bloque (o en una parte del mismo), una permutación u otro tipo de primitiva . Encontrar valores que cumplan la característica se logra dividiendo el primitivo en tres partes de modo que . se llama fase de entrada y juntas se llaman fase de salida. Luego, el atacante elige valores que realizan parte de la característica diferencial en la fase de entrada de manera determinista y cumplen el resto de la característica de manera probabilística.
Así, el ataque de rebote consta de 2 fases:
La ventaja de utilizar una fase de entrada y dos de salida es la capacidad de calcular las partes difíciles de la característica diferencial en la fase de entrada de manera eficiente. Además, garantiza una alta probabilidad en la fase de salida. La probabilidad global de encontrar una característica diferencial es, por tanto, mayor que si se utilizaran técnicas diferenciales estándar.
Considere una función hash que utiliza un cifrado de bloque de permutación-sustitución similar a AES como función de compresión . Esta función de compresión consta de una serie de rondas compuestas por cajas S y transformaciones lineales. La idea general del ataque es construir una característica diferencial que tenga en el medio su parte más costosa computacional. Esta parte quedará entonces cubierta por la fase de entrada, mientras que la parte de la característica que se logra más fácilmente se cubrirá en la fase de salida. El sistema de ecuaciones que describe la característica en la fase de entrada debe estar 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 está contenida en la fase de entrada, es posible utilizar aquí diferenciales estándar, mientras que en la fase de salida se utilizan diferenciales truncados para lograr mayores probabilidades.
La fase entrante normalmente tendrá una pequeña cantidad de bytes de estado activo ( bytes con diferencias distintas de cero) al principio, que luego se propagan a una gran cantidad de bytes activos en la mitad de la ronda, antes de regresar a una cantidad baja de bytes activos. bytes al final de la fase. La idea es tener una gran cantidad de bytes activos en la entrada y salida de una S-box en medio de la fase. Luego, las características se pueden calcular de manera eficiente eligiendo valores para las diferencias al inicio y al final de la fase entrante, propagándolos hacia el medio y buscando coincidencias en la entrada y salida de la S-box . Para cifrados como AES, esto normalmente se puede hacer por filas o columnas, lo que hace que el procedimiento sea relativamente eficiente. La elección de diferentes valores iniciales y finales conduce a muchas características diferenciales diferentes en la fase entrante.
En la fase de salida, el objetivo es propagar las características encontradas en la fase de entrada hacia adelante y hacia atrás, y comprobar si se siguen las características deseadas. Aquí se suelen utilizar diferenciales truncados , ya que dan mayores probabilidades 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 conseguir una colisión no basta con que los diferenciales en la fase de salida sean de algún tipo concreto; cualquier byte activo al inicio y al final de la característica también debe tener un valor tal que se cancele cualquier operación de avance. Por lo tanto, al diseñar la característica, cualquier número de bytes activos al inicio y al final de la fase de salida deben 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 iniciando y finalizando la fase de salida con varios bytes activos que no se cancelan.
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 bloque tipo AES , W) se reduce a 4,5 o 5,5 rondas. Se pueden encontrar casi colisiones en rondas 6,5 y 7,5. A continuación se muestra una descripción del ataque de 4,5 rondas.
Para que el ataque de rebote sea efectivo, antes del ataque se calcula una tabla de búsqueda de diferencias de caja S. Representemos la caja S. Luego, para cada par encontramos las soluciones (si las hay) a la ecuación.
donde representa la diferencia de entrada y representa la diferencia de salida de la S-box . Esta tabla de 256 por 256 (llamada tabla de distribución de diferencias, DDT) permite encontrar valores que siguen la característica para cualquier par de entrada/salida específico que pase por la S-box . La tabla de la derecha muestra el número posible de soluciones a la ecuación y con qué frecuencia ocurren. La primera fila describe diferenciales imposibles, mientras que la última fila describe el diferencial cero.
Para encontrar una colisión en 4,5 rondas de Whirlpool , se debe encontrar una característica diferencial del tipo que se muestra en la siguiente tabla. 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 por el número de bytes activos en cada ronda, por ejemplo, 1 → 8 → 64 → 8 → 1 → 1.
El objetivo de la fase entrante 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:
Estos pasos se pueden repetir con 2.64 valores iniciales diferentes en el paso 1, lo que da como resultado un total de 2.128 valores reales que siguen la característica diferencial en la fase entrante. Cada conjunto de 2 64 valores se puede encontrar con una complejidad de 2 8 transformaciones redondas debido al paso de precálculo.
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 entrante se propaga hacia adelante y hacia atrás. Para seguir la característica deseada, 8 bytes activos deben propagarse a un solo byte activo en ambas direcciones. Una de esas transiciones de 8 a 1 ocurre con una probabilidad de 2 −56 , [1] por lo que cumplir la característica tiene una probabilidad de 2 −112 . Para garantizar una colisión , los valores al inicio y al final de la característica deben cancelarse durante la operación de avance. Esto sucede con una probabilidad de aproximadamente 2 −8 y, por tanto, la probabilidad general de la fase de salida es 2 −120 .
Para encontrar una colisión , es necesario generar 2.120 puntos de partida en la fase de aproximación. Dado que esto se puede hacer con una complejidad promedio de 1 por punto de partida, [2] la complejidad general del ataque es 2 120 .
El ataque básico de 4,5 asaltos se puede ampliar a un ataque de 5,5 asaltos utilizando dos estados completamente activos en la fase entrante. Esto aumenta la complejidad a aproximadamente 2 184 . [3]
Ampliar la fase de salida para que comience y termine con 8 bytes activos conduce a una casi colisión en 52 bytes en Whirlpool reducida a 7,5 rondas con una complejidad de 2.192 . [4]
Suponiendo que el atacante tiene control sobre el valor de encadenamiento y, por lo tanto, la entrada a la programación 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 128 . [5]
