Ataque de interpolación

Tipo de ataque criptoanalítico

En criptografía , un ataque de interpolación es un tipo de ataque criptoanalítico contra cifrados de bloque .

Después de que se presentaran los dos ataques, el criptoanálisis diferencial y el criptoanálisis lineal , a los cifrados en bloque, se introdujeron algunos nuevos cifrados en bloque , que demostraron ser seguros contra ataques diferenciales y lineales. Entre ellos, había algunos cifrados en bloque iterados, como el cifrado KN y el cifrado SHARK . Sin embargo, Thomas Jakobsen y Lars Knudsen demostraron a finales de la década de 1990 que estos cifrados eran fáciles de romper mediante la introducción de un nuevo ataque llamado ataque de interpolación.

En el ataque, se utiliza una función algebraica para representar una caja S. Puede ser una función cuadrática simple , polinómica o racional sobre un campo de Galois . Sus coeficientes se pueden determinar mediante técnicas de interpolación de Lagrange estándar , utilizando textos simples conocidos como puntos de datos. Alternativamente, se pueden utilizar textos simples elegidos para simplificar las ecuaciones y optimizar el ataque.

En su versión más simple, un ataque de interpolación expresa el texto cifrado como un polinomio del texto simple. Si el polinomio tiene un número relativamente bajo de coeficientes desconocidos, entonces con una colección de pares de texto simple/texto cifrado (p/c), el polinomio puede reconstruirse. Con el polinomio reconstruido, el atacante obtiene una representación del cifrado, sin conocimiento exacto de la clave secreta.

El ataque de interpolación también se puede utilizar para recuperar la clave secreta.

Es más fácil describir el método con un ejemplo.

Ejemplo

Sea un cifrado iterado dado por

${\displaystyle c_{i}=(c_{i-1}\oplus k_{i})^{3},}$

donde es el texto simple, la salida de la ronda, la clave secreta de la ronda (derivada de la clave secreta por algún programa de claves ) y, para un cifrado iterado de -ronda, es el texto cifrado. ${\displaystyle c_{0}}$ ${\displaystyle c_{i}}$ ${\displaystyle i^{th}}$ ${\displaystyle k_{i}}$ ${\displaystyle i^{th}}$ ${\displaystyle K}$ ${\displaystyle r}$ ${\displaystyle c_{r}}$

Consideremos el cifrado de dos rondas. Sea α el mensaje y α el texto cifrado. ${\displaystyle x}$ ${\displaystyle c}$

Entonces la salida de la ronda 1 se convierte en

${\displaystyle c_{1}=(x+k_{1})^{3}=(x^{2}+k_{1}^{2})(x+k_{1})=x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3},}$

y la salida de la ronda 2 se convierte en

${\displaystyle c_{2}=c=(c_{1}+k_{2})^{3}=(x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3}+k_{2})^{3}}$

${\displaystyle =x^{9}+x^{8}k_{1}+x^{6}k_{2}+x^{4}k_{1}^{2}k_{2}+x^{3}k_{2}^{2}+x^{2}(k_{1}k_{2}^{2}+k_{1}^{4}k_{2})+x(k_{1}^{2}k_{2}^{2}+k_{1}^{8})+k_{1}^{3}k_{2}^{2}+k_{1}^{9}+k_{2}^{3},}$

Expresar el texto cifrado como un polinomio del texto simple da como resultado

${\displaystyle p(x)=a_{1}x^{9}+a_{2}x^{8}+a_{3}x^{6}+a_{4}x^{4}+a_{5}x^{3}+a_{6}x^{2}+a_{7}x+a_{8},}$

donde las 's son constantes dependientes de la clave. ${\displaystyle a_{i}}$

Si utilizamos tantos pares de texto simple/texto cifrado como coeficientes desconocidos tenga el polinomio , podemos construir el polinomio. Esto se puede hacer, por ejemplo, mediante la interpolación de Lagrange (véase Polinomio de Lagrange ). Cuando se han determinado los coeficientes desconocidos, tenemos una representación del cifrado, sin conocer la clave secreta . ${\displaystyle p(x)}$ ${\displaystyle p(x)}$ ${\displaystyle K}$

Existencia

Si consideramos un cifrado de bloque de -bits, entonces hay posibles textos simples y, por lo tanto, pares distintos . Sea que haya coeficientes desconocidos en . Como requerimos tantos pares como la cantidad de coeficientes desconocidos en el polinomio, entonces existe un ataque de interpolación solo si . ${\displaystyle m}$ ${\displaystyle 2^{m}}$ ${\displaystyle 2^{m}}$ ${\displaystyle p/c}$ ${\displaystyle n}$ ${\displaystyle p(x)}$ ${\displaystyle p/c}$ ${\displaystyle n\leq 2^{m}}$

Complejidad temporal

Supongamos que el tiempo necesario para construir el polinomio utilizando pares es pequeño, en comparación con el tiempo necesario para cifrar los textos simples necesarios. Sea que haya coeficientes desconocidos en . Entonces, la complejidad temporal para este ataque es , lo que requiere pares distintos conocidos . ${\displaystyle p(x)}$ ${\displaystyle p/c}$ ${\displaystyle n}$ ${\displaystyle p(x)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p/c}$

Ataque de interpolación mediante Meet-In-The-Middle

A menudo, este método es más eficaz. A continuación, se explica cómo se hace.

Dado un cifrado iterado redondo con longitud de bloque , sea la salida del cifrado después de las rondas con . Expresaremos el valor de como un polinomio del texto simple , y como un polinomio del texto cifrado . Sea la expresión de via , y sea la expresión de via . El polinomio se obtiene calculando hacia adelante usando la fórmula iterada del cifrado hasta round , y el polinomio se obtiene calculando hacia atrás a partir de la fórmula iterada del cifrado comenzando desde round hasta round . ${\displaystyle r}$ ${\displaystyle m}$ ${\displaystyle z}$ ${\displaystyle s}$ ${\displaystyle s<r}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle c}$ ${\displaystyle g(x)\in GF(2^{m})[x]}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle h(c)\in GF(2^{m})[c]}$ ${\displaystyle z}$ ${\displaystyle c}$ ${\displaystyle g(x)}$ ${\displaystyle s}$ ${\displaystyle h(c)}$ ${\displaystyle r}$ ${\displaystyle s+1}$

Así que debería ser así

${\displaystyle g(x)=h(c),}$

y si ambos son polinomios con un número bajo de coeficientes, entonces podemos resolver la ecuación para los coeficientes desconocidos. ${\displaystyle g}$ ${\displaystyle h}$

Complejidad temporal

Supongamos que se puede expresar mediante coeficientes, y se puede expresar mediante coeficientes. Entonces necesitaríamos pares distintos conocidos para resolver la ecuación estableciéndola como una ecuación matricial. Sin embargo, esta ecuación matricial se puede resolver hasta una multiplicación y una suma. Entonces, para asegurarnos de que obtenemos una solución única y distinta de cero, establecemos el coeficiente correspondiente al grado más alto en uno y el término constante en cero. Por lo tanto, se requieren pares distintos conocidos . Entonces, la complejidad temporal para este ataque es , lo que requiere pares distintos conocidos . ${\displaystyle g(x)}$ ${\displaystyle p}$ ${\displaystyle h(c)}$ ${\displaystyle q}$ ${\displaystyle p+q}$ ${\displaystyle p/c}$ ${\displaystyle p+q-2}$ ${\displaystyle p/c}$ ${\displaystyle p+q-2}$ ${\displaystyle p+q-2}$ ${\displaystyle p/c}$

Con el método de encuentro en el medio, el número total de coeficientes suele ser menor que con el método normal, lo que hace que el método sea más eficiente, ya que se necesitan menos pares. ${\displaystyle p/c}$

Recuperación de claves

También podemos utilizar el ataque de interpolación para recuperar la clave secreta . ${\displaystyle K}$

Si eliminamos la última ronda de un cifrado iterado de -ronda con longitud de bloque , la salida del cifrado se convierte en . Llamemos al cifrado cifrado reducido. La idea es hacer una suposición sobre la clave de la última ronda , de modo que podamos descifrar una ronda para obtener la salida del cifrado reducido. Luego, para verificar la suposición, utilizamos el ataque de interpolación en el cifrado reducido, ya sea por el método normal o por el método Meet-In-The-Middle. Aquí se explica cómo se hace. ${\displaystyle r}$ ${\displaystyle m}$ ${\displaystyle {\tilde {y}}=c_{r-1}}$ ${\displaystyle k_{r}}$ ${\displaystyle {\tilde {y}}}$

Mediante el método normal, expresamos la salida del cifrado reducido como un polinomio del texto simple . Llamemos al polinomio . Luego, si podemos expresar con coeficientes, entonces, utilizando pares distintos conocidos , podemos construir el polinomio. Para verificar la suposición de la clave de la última ronda, entonces verifique con un par adicional si se cumple que ${\displaystyle {\tilde {y}}}$ ${\displaystyle x}$ ${\displaystyle p(x)\in GF(2^{m})[x]}$ ${\displaystyle p(x)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p/c}$ ${\displaystyle p/c}$

${\displaystyle p(x)={\tilde {y}}.}$

Si es así, entonces es muy probable que la clave de la última ronda haya sido correcta. Si no, vuelva a intentar adivinar la clave.

Mediante el método Meet-In-The-Middle expresamos la salida de round como un polinomio del texto simple y como un polinomio de la salida del cifrado reducido . Llamemos a los polinomios y , y expresémoslos mediante los coeficientes y , respectivamente. Luego, con pares distintos conocidos , podemos encontrar los coeficientes. Para verificar la suposición de la clave de la última ronda, verifique con un par adicional si se cumple que ${\displaystyle z}$ ${\displaystyle s<r}$ ${\displaystyle x}$ ${\displaystyle {\tilde {y}}}$ ${\displaystyle g(x)}$ ${\displaystyle h({\tilde {y}})}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle q+p-2}$ ${\displaystyle p/c}$ ${\displaystyle p/c}$

${\displaystyle g(x)=h({\tilde {y}}).}$

Si es así, entonces es muy probable que la clave de la última ronda haya sido correcta. Si no, vuelva a intentar adivinar la clave.

Una vez que hayamos encontrado la clave correcta para la última ronda, podremos continuar de manera similar con las claves de la ronda restante.

Complejidad temporal

Con una clave secreta de longitud , entonces hay diferentes claves. Cada una con probabilidad de ser correcta si se elige al azar. Por lo tanto, en promedio tendremos que hacer conjeturas antes de encontrar la clave correcta. ${\displaystyle m}$ ${\displaystyle 2^{m}}$ ${\displaystyle 1/2^{m}}$ ${\displaystyle 1/2\cdot 2^{m}}$

Por lo tanto, el método normal tiene una complejidad de tiempo promedio , que requiere pares distintos conocidos , y el método Meet-In-The-Middle tiene una complejidad de tiempo promedio , que requiere pares distintos conocidos . ${\displaystyle 2^{m-1}(n+1)}$ ${\displaystyle n+1}$ ${\displaystyle c/p}$ ${\displaystyle 2^{m-1}(p+q-1)}$ ${\displaystyle p+q-1}$ ${\displaystyle c/p}$

Aplicación en el mundo real

El ataque Meet-in-the-middle se puede utilizar en una variante para atacar S-boxes, que utiliza la función inversa, porque con un S-box de -bit entonces en . ${\displaystyle m}$ ${\displaystyle S:f(x)=x^{-1}=x^{2^{m}-2}}$ ${\displaystyle GF(2^{m})}$

El cifrado de bloques SHARK utiliza una red SP con S-box . El cifrado es resistente al criptoanálisis diferencial y lineal después de una pequeña cantidad de rondas. Sin embargo, fue descifrado en 1996 por Thomas Jakobsen y Lars Knudsen, utilizando un ataque de interpolación. Denotemos por SHARK una versión de SHARK con bits de tamaño de bloque utilizando S-boxes de 128 bits en paralelo en rondas. Jakobsen y Knudsen descubrieron que existe un ataque de interpolación en SHARK (cifrado de bloques de 64 bits) utilizando aproximadamente textos planos elegidos, y un ataque de interpolación en SHARK (cifrado de bloques de 128 bits) utilizando aproximadamente textos planos elegidos. ${\displaystyle S:f(x)=x^{-1}}$ ${\displaystyle (n,m,r)}$ ${\displaystyle nm}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle (8,8,4)}$ ${\displaystyle 2^{21}}$ ${\displaystyle (8,16,7)}$ ${\displaystyle 2^{61}}$

Thomas Jakobsen también introdujo una versión probabilística del ataque de interpolación utilizando el algoritmo de Madhu Sudan para una mejor decodificación de los códigos Reed-Solomon . Este ataque puede funcionar incluso cuando una relación algebraica entre textos simples y textos cifrados se cumple solo para una fracción de valores.

Referencias

• Thomas Jakobsen , Lars Knudsen (enero de 1997). El ataque de interpolación en los cifrados de bloque ( PDF / PostScript ) . 4.º Taller internacional sobre cifrado rápido de software (FSE '97), LNCS 1267. Haifa : Springer-Verlag . pp. 28–40 . Consultado el 3 de julio de 2007 .
• Thomas Jakobsen (25 de agosto de 1998). Criptoanálisis de cifrados en bloque con relaciones no lineales probabilísticas de bajo grado (PDF/PostScript) . Avances en criptología — CRYPTO '98. Santa Bárbara, California : Springer-Verlag. págs. 212–222 . Consultado el 6 de julio de 2007 .(Vídeo de presentación en Google Video —utiliza Flash )
• Shiho Moriai; Takeshi Shimoyama; Toshinobu Kaneko (marzo de 1999). Ataques de interpolación del cifrado de bloque: SNAKE (PDF) . FSE '99. Roma: Springer-Verlag. págs. 275–289. doi :10.1007/3-540-48519-8_20 . Consultado el 6 de noviembre de 2022 .
• Amr M. Youssef; Guang Gong (abril de 2000). On the Interpolation Attacks on Block Ciphers (PDF) ( Sobre los ataques de interpolación en los cifrados de bloque) . FSE 2000. Nueva York : Springer-Verlag. págs. 109-120 . Consultado el 6 de julio de 2007 .
• Kaoru Kurosawa; Tetsu Iwata; Viet Duong Quang (agosto de 2000). Ataque de interpolación para encontrar raíces (PDF/PostScript) . Actas del 7.º Taller internacional anual sobre áreas seleccionadas de criptografía (SAC 2000). Waterloo, Ontario : Springer-Verlag. págs. 303–314 . Consultado el 6 de julio de 2007 .