Criptoanálisis rotacional

En criptografía, el criptoanálisis rotacional es un ataque criptoanalítico genérico contra algoritmos que se basan en tres operaciones: suma modular , rotación y XOR ( ARX , por sus siglas en inglés). Los algoritmos que se basan en estas operaciones son populares porque son relativamente económicos tanto en hardware como en software y se ejecutan en tiempo constante, lo que los hace seguros frente a ataques de temporización en implementaciones comunes.

La idea básica del criptoanálisis rotacional es que tanto la rotación de bits como las operaciones XOR preservan las correlaciones entre pares de entradas con bits rotados, y que la suma de entradas con bits rotados también preserva parcialmente dichas correlaciones. Por lo tanto, los pares de entradas rotacionales pueden utilizarse para "ver a través" de las operaciones ARX en cascada de los criptosistemas en mayor medida de lo que cabría esperar. ^{[ 1 ]} Esta capacidad de "ver" correlaciones a través de rondas de procesamiento puede explotarse para romper el criptosistema de una manera similar al criptoanálisis diferencial .

El término "criptoanálisis rotacional" fue acuñado por Dmitry Khovratovich e Ivica Nikolić en el artículo de 2010 "Criptoanálisis rotacional de ARX", que presentó los mejores ataques criptoanalíticos de la época contra un cifrado Threefish de rondas reducidas , parte de la función hash Skein , un candidato a la competición SHA-3 . ^{[ 1 ] [ 2 ]} Un ataque posterior de los mismos autores y Christian Rechberger rompe la resistencia a colisiones de hasta 53 de 72 rondas en Skein-256, y 57 de 72 rondas en Skein-512. ^{[ 3 ]} También afecta al cifrado Threefish hasta 39 para claves de 256 bits, 42 rondas para claves de 512 bits y 43 rondas para claves de 1024 bits con complejidades , , y , respectivamente. ^{[ 1 ]}${\displaystyle 2^{252.4}}$${\displaystyle 2^{507}}$${\displaystyle 2^{1014.4}}$

El criptoanálisis rotacional aprovecha el hecho de que la función XOR conserva las rotaciones que se realizan a un dato con una probabilidad de 1, y que, si bien la suma modular no siempre conserva la rotación, la probabilidad puede ser lo suficientemente alta (dependiendo del criptosistema) como para que las versiones con rondas reducidas, los criptosistemas modificados en los que se ha eliminado la suma modular o los criptosistemas ARX extremadamente débiles que no utilizan suficientes sumas puedan volverse fácilmente vulnerables.

Sea cualquier letra una variable dada en binario, y sea cualquier operación o dato entre paréntesis "()" una instrucción dada sobre datos que se han desplazado una cantidad "r".

(x y)=(x) (y)${\displaystyle \oplus }$${\displaystyle \oplus }$ , y " (x)r" es trivialmente igual a "(x desplazado por r)" (ya que x y r son las únicas cosas que determinan la salida).

La suma modular es más complicada, ya que en la mayoría de los casos puede ser no lineal. La probabilidad de que una cadena dada que fue desplazada sobreviva a la suma modular (es decir, "(x+y) = (x)+(y)") es igual a:${\displaystyle 2^{n}}$

${\displaystyle (1/4)(1+2^{rn}+2^{-r}+2^{-n})}$^{[ 1 ]}

donde "n" es el exponente en , y r es la cantidad de rotación como antes.${\displaystyle 2^{n}}$

La probabilidad de que un fragmento binario rotado sobreviva a un criptosistema ARX es , donde "pr" es la probabilidad de sobrevivir a una suma modular singular dada la fórmula anterior, y "q" es la cantidad de sumas dentro del esquema ARX. ^{[ 1 ]} Para que el ataque sea teóricamente relevante, la probabilidad de obtener la clave del ataque debe ser menor que la probabilidad de descubrirla aleatoriamente (es decir, la complejidad promedio del caso del ataque criptoanalítico rotacional debe ser menor que la de la fuerza bruta pura). Las versiones completas de la mayoría de los criptosistemas ARX no son vulnerables, pero sus rondas reducidas sí lo son, ya que la probabilidad de recuperar la clave es mayor al comienzo del proceso de mezcla (las rondas) que al final.${\displaystyle (p{r})^{q}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$

También es importante señalar que muchos esquemas ARX tienen términos constantes que deben combinarse mediante XOR y sumarse dentro del esquema regular. Esto no representa un problema cuando las constantes utilizadas se rotan (como ya se mencionó, (x y)=(x) (y),${\displaystyle \oplus }$${\displaystyle \oplus }$ donde una de las variables puede ser la constante), pero las constantes que no se rotan disminuyen la probabilidad de que las rotaciones sobrevivan. Los autores del documento original sobre el ataque intentan solucionar esto introduciendo variables de "corrección de errores" que se obtuvieron mediante el método de Montecarlo y que buscan maximizar la probabilidad de que las constantes se anulen durante el proceso de ronda. La constante de corrección de errores tiene la posibilidad de eliminar la ofuscación constante para una ronda determinada de un criptosistema al combinar la salida de la función con la constante de error dada mediante XOR.

Por ejemplo, en Skein , la constante de error tiene una probabilidad de crear la siguiente equivalencia, revirtiendo la función de compresión hash al punto anterior a la intervención de las constantes:

${\displaystyle Madeja((X)\oplus {E})=(Madeja(X))}$^{[ 4 ]} donde "e" es la constante de error y "" es la salida de la función de redondeo en el tiempo dado sin la constante involucrada.${\displaystyle (Skein(X))}$

Las constantes de corrección de errores son únicas para cada criptosistema y, presumiblemente, deben obtenerse mediante simulaciones de Montecarlo. Actualmente no existe ninguna fórmula conocida públicamente para determinar la variable de corrección de errores necesaria sobre la marcha.

Además de la naturaleza de rondas reducidas del criptoanálisis rotacional y la suerte necesaria para un ataque exitoso, una importante medida de mitigación consiste en añadir la cantidad necesaria de sumas para ajustarse al nivel de seguridad del cifrado. Para un cifrado ARX que requiere seguridad, debe haber aproximadamente como máximo 128 sumas modulares según la ecuación anterior, sin incluir las demás limitaciones.${\displaystyle 2^{128}}$${\displaystyle (p{r})^{q}}$

El método de ataque de Threefish requiere que se produzca un ataque de texto plano elegido , lo cual conlleva las limitaciones propias de este tipo de ataque.

Otra limitación es que no hay garantía de que la aplicación exitosa de las variables de corrección de errores anule las constantes dentro de las rondas. El artículo original afirma que la probabilidad de que las constantes se anulen aleatoriamente en una ronda determinada disminuye a medida que aumenta el peso de Hamming . ^{[ 1 ]} Aumentar los pesos de Hamming de las constantes en las rondas clave y las rondas de compresión incrementa el margen de seguridad.