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 tipo 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 ataque de rebote 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 característica diferencial determinada en un cifrado de bloque (o en una parte de él), una permutación u otro tipo de primitivo . Para encontrar valores que cumplan la característica, se divide el primitivo en tres partes, de modo que . se denomina fase de entrada y y juntas se denominan fase de salida. A continuación, el atacante elige valores que cumplan parte de la característica diferencial en la fase de entrada de forma determinista y cumplan el resto de la característica de forma 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 forma eficiente. Además, garantiza una alta probabilidad en la fase de salida. La probabilidad general de encontrar una característica diferencial es así mayor que utilizando técnicas diferenciales estándar.
Considere una función hash que utiliza un cifrado de bloque de sustitución-permutación similar a AES como su función de compresión . Esta función de compresión consta de una serie de rondas compuestas de S-boxes y transformaciones lineales. La idea general del ataque es construir una característica diferencial que tiene su parte computacionalmente más costosa en el medio. Esta parte será cubierta entonces por la fase de entrada, mientras que la parte más fácil de lograr de la característica se cubre 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 está contenida en la fase de entrada, es posible utilizar diferenciales estándar aquí, mientras que los diferenciales truncados se utilizan en la fase de salida para lograr probabilidades más altas.
La fase de entrada 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 el medio de la ronda, antes de volver a una cantidad baja de bytes activos al final de la fase. La idea es tener la gran cantidad de bytes activos en la entrada y la salida de una S-box en el medio 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 el medio y buscando coincidencias en la entrada y la 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. Elegir diferentes valores iniciales y finales conduce a 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 utilizan generalmente 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 lograr una colisión , no es suficiente que los diferenciales en la fase de salida sean de algún tipo específico; 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 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 una cantidad esperada de características correctas mayor que una en la fase de salida. Además, se pueden lograr colisiones casi totales en una mayor cantidad de rondas iniciando y finalizando la fase de salida con varios bytes activos que no se cancelen.
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 similar a AES , W) se reduce a 4,5 o 5,5 rondas. Se pueden encontrar colisiones cercanas en 6,5 y 7,5 rondas. A continuación se incluye una descripción del ataque de 4,5 rondas.
Para que el ataque de rebote sea efectivo, se calcula una tabla de búsqueda de diferencias de S -box antes del ataque. Sea . Para cada par, encontramos las soluciones (si las hay) de la ecuación.
donde representa la diferencia de entrada y representa la diferencia de salida de la caja S. 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 caja S. La tabla de la derecha muestra el número posible de soluciones a la ecuación y la frecuencia con la que 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 tabla siguiente. 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, p. ej., 1 → 8 → 64 → 8 → 1 → 1.
El objetivo de la fase de entrada es encontrar diferencias que cumplan 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 de partida 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 de entrada. Cada conjunto de 2,64 valores se puede encontrar con una complejidad de 2,8 transformaciones de rondas debido al paso de precomputación.
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 inicio 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 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 el cumplimiento de la característica tiene una probabilidad de 2 −112 . Para asegurar una colisión , los valores al inicio y al final de la característica tienen que cancelarse durante la operación de avance. Esto ocurre con una probabilidad de aproximadamente 2 −8 , y la probabilidad general de la fase de salida es, por lo tanto, 2 −120 .
Para encontrar una colisión , se deben generar 2 120 puntos de partida en la fase de entrada. Dado que esto se puede hacer con una complejidad media de 1 por punto de partida, [2] la complejidad total del ataque es 2 120 .
El ataque básico de 4,5 rondas se puede ampliar a un ataque de 5,5 rondas utilizando dos estados completamente activos en la fase de entrada. Esto aumenta la complejidad a aproximadamente 2 184 . [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 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 al programa de claves de Whirlpool , el ataque se puede extender 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 ]
