Ataque de interpolación

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

Tras la presentación de los dos ataques, el criptoanálisis diferencial y el criptoanálisis lineal , contra los cifrados de bloques, se introdujeron algunos nuevos cifrados de bloques que demostraron ser seguros frente a los ataques diferenciales y lineales. Entre ellos se encontraban algunos cifrados de bloques iterados, como el cifrado KN y el cifrado SHARK . Sin embargo, a finales de la década de 1990, Thomas Jakobsen y Lars Knudsen demostraron que estos cifrados eran fáciles de descifrar mediante un nuevo ataque denominado ataque de interpolación.

En el ataque, se utiliza una función algebraica para representar una caja S. Esta puede ser una función cuadrática simple , o una función polinómica o racional sobre un campo de Galois . Sus coeficientes se pueden determinar mediante técnicas estándar de interpolación de Lagrange , utilizando textos planos conocidos como puntos de datos. Alternativamente, se pueden usar textos planos seleccionados 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 plano. Si el polinomio tiene un número relativamente bajo de coeficientes desconocidos, entonces, con un conjunto de pares texto plano/texto cifrado (p/c), el polinomio puede reconstruirse. Una vez reconstruido el polinomio, el atacante obtiene una representación del cifrado, sin conocer con exactitud la clave secreta.

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

La forma más sencilla de describir el método es con un ejemplo.

Sea un cifrado iterado dado por

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

dónde${\displaystyle c_{0}}$es el texto plano,${\displaystyle c_{i}}$el resultado de la${\displaystyle i^{th}}$redondo,${\displaystyle k_{i}}$el secreto${\displaystyle i^{th}}$llave redonda (derivada de la llave secreta)${\displaystyle K}$por algún cronograma clave ), y para un${\displaystyle r}$-cifrado iterado de ronda,${\displaystyle c_{r}}$es el texto cifrado.

Consideremos el cifrado de 2 rondas. Sea${\displaystyle x}$denotan el mensaje y${\displaystyle c}$denota el texto cifrado.

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 el resultado 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 plano produce

${\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 el${\displaystyle a_{i}}$Las son constantes dependientes clave.

Utilizar tantos pares de texto plano/texto cifrado como el número de coeficientes desconocidos en el polinomio.${\displaystyle p(x)}$, entonces 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, entonces tenemos una representación${\displaystyle p(x)}$del cifrado, sin conocimiento de la clave secreta${\displaystyle K}$.

Considerando un${\displaystyle m}$cifrado de bloques de bits, entonces hay${\displaystyle 2^{m}}$posibles textos planos y, por lo tanto,${\displaystyle 2^{m}}$distinto${\displaystyle p/c}$parejas. Que haya${\displaystyle n}$coeficientes desconocidos en${\displaystyle p(x)}$. Dado que requerimos tantos${\displaystyle p/c}$pares como el número de coeficientes desconocidos en el polinomio, entonces un ataque de interpolación existe solo si${\displaystyle n\leq 2^{m}}$.

Supongamos que el tiempo para construir el polinomio${\displaystyle p(x)}$usando${\displaystyle p/c}$Los pares son pequeños, en comparación con el tiempo necesario para cifrar los textos planos requeridos. Supongamos que hay${\displaystyle n}$coeficientes desconocidos en${\displaystyle p(x)}$Entonces, la complejidad temporal para este ataque es${\displaystyle n}$, que requiere${\displaystyle n}$conocido distinto${\displaystyle p/c}$pares.

A menudo, este método es más eficiente. Así es como se hace.

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

Por lo tanto, debería sostener que

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

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

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

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

Mediante el método normal expresamos la salida${\displaystyle {\tilde {y}}}$del cifrado reducido como un polinomio del texto plano${\displaystyle x}$. Llama al polinomio${\displaystyle p(x)\in GF(2^{m})[x]}$Entonces, si podemos expresar${\displaystyle p(x)}$con${\displaystyle n}$coeficientes, luego usando${\displaystyle n}$conocido distinto${\displaystyle p/c}$pares, podemos construir el polinomio. Para verificar la suposición de la clave de la última ronda, luego verifique con uno adicional${\displaystyle p/c}$emparejar si se mantiene eso

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

Si la respuesta es sí, entonces es muy probable que la adivinanza de la llave de la ronda anterior haya sido correcta. Si la respuesta es no, entonces vuelva a adivinar la llave.

Mediante el método Meet-In-The-Middle expresamos la salida${\displaystyle z}$de ronda${\displaystyle s<r}$como un polinomio del texto plano${\displaystyle x}$y como un polinomio de la salida del cifrado reducido${\displaystyle {\tilde {y}}}$. Llama a los polinomios${\displaystyle g(x)}$y${\displaystyle h({\tilde {y}})}$y que sean expresados ​​por${\displaystyle p}$y${\displaystyle q}$coeficientes, respectivamente. Luego con${\displaystyle q+p-2}$conocido distinto${\displaystyle p/c}$pares podemos encontrar los coeficientes. Para verificar la suposición de la última ronda clave, luego verifique con uno adicional${\displaystyle p/c}$emparejar si se mantiene eso

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

Si la respuesta es sí, entonces es muy probable que la adivinanza de la llave de la ronda anterior haya sido correcta. Si la respuesta es no, entonces vuelva a adivinar la llave.

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

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${\displaystyle m}$-bit S-box entonces${\displaystyle S:f(x)=x^{-1}=x^{2^{m}-2}}$en${\displaystyle GF(2^{m})}$.

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

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

• Thomas Jakobsen , Lars Knudsen (enero de 1997). El ataque de interpolación a los cifrados de bloques ( PDF / PostScript ) . 4.º Taller Internacional sobre Cifrado Rápido de Software (FSE '97), LNCS 1267. Haifa : Springer-Verlag . págs. 28-40 . Consultado el 3 de julio de 2007 . 
• Thomas Jakobsen (25 de agosto de 1998). Criptoanálisis de cifrados de bloques 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 la presentación en Google Video — utiliza Flash )
• Shiho Moriai; Takeshi Shimoyama; Toshinobu Kaneko (marzo de 1999). Ataques de interpolación del cifrado por bloques: 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). Sobre los ataques de interpolación a los cifrados de bloques (PDF) . FSE 2000. Ciudad de Nueva York : Springer-Verlag. págs. 109–120 . Recuperado el 6 de julio de 2007 . 
• Kaoru Kurosawa; Tetsu Iwata; Viet Duong Quang (agosto de 2000). Ataque de interpolación para la búsqueda de raíces (PDF/PostScript) . Actas del 7.º Taller Internacional Anual sobre Áreas Seleccionadas en Criptografía (SAC 2000). Waterloo, Ontario : Springer-Verlag. págs. 303–314 . Consultado el 6 de julio de 2007 .