Ataque de interpolación

Un ataque de interpolación es un tipo de ataque criptoanalítico en cifrados de bloque en criptografía .

Para romper los cifrados en bloque, había 2 tipos de ataques: criptoanálisis diferencial y criptoanálisis lineal . Con el tiempo, se introdujeron algunos cifrados en bloque, que demostraron su seguridad frente a ataques diferenciales y lineales. Estos cifrados eran cifrados: KN-Cipher y SHARK . Sin embargo, a finales de los 90, Thomas Jacobsen y Lars Knudsen demostraron que estos cifrados eran fáciles de descifrar al introducir un nuevo ataque llamado ataque de interpolación.

En este ataque, se usa una función algebraica para representar un S-Box . Puede ser una función cuadrática simple , un polinomio o una función racional sobre un campo de Galois . Sus coeficientes se pueden determinar usando métodos estándar de interpolación de Lagrange , usando textos claros conocidos como puntos de datos. Además, se pueden usar textos sin formato seleccionados para simplificar las ecuaciones y optimizar el ataque. En su forma más simple, el ataque de interpolación expresa el texto cifrado como un polinomio en el texto. Si el polinomio tiene un número relativamente bajo de coeficientes desconocidos, entonces con un conjunto de pares de texto sin formato/texto cifrado, se puede recuperar el polinomio. Conociendo el polinomio de recuperación, el atacante tiene una idea sobre el cifrado sin conocer la clave secreta exacta . Un ataque de interpolación no es posible si se utiliza una función discontinua .

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

Ejemplo

Deje que la iteración de cifrado se dé como

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

¿Dónde está el texto sin formato, es la clave de ronda secreta, es el texto cifrado para la iteración de cifrado de ronda? $c_{0}$ $k_{i}\en K$ $c_{r}$ $r$

Considere un cifrado de 2 rondas. Sea un mensaje y sea un texto cifrado, luego a la salida de la primera ronda obtenemos $X$ $C$

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 a la salida de la 2da ronda:

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

=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},

Texto cifrado como un polinomio de las salidas de texto sin formato

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 es una clave que depende de una constante $ai}$

Si usamos tantos pares de texto sin formato/texto cifrado como coeficientes desconocidos hay en el polinomio , entonces podemos construir un polinomio. Esto se puede hacer, por ejemplo, mediante la interpolación de Lagrange. Cuando se determinen los coeficientes desconocidos, tendremos una representación de encriptación , sin conocer la clave secreta . $p(x)$ $p(x)$ $k$

Existencia

Deje entrar un cifrado de bloque de bits, es decir, posibles textos sin formato, por lo tanto, diferentes pares de proporciones de texto sin formato a texto cifrado . Sean coeficientes desconocidos en . Necesitamos tantos pares como coeficientes desconocidos haya en el polinomio. Que. el ataque de interpolación existe solo para . $metro$ $2^{m}$ $2^{m}$ $ordenador personal$ $norte$ $p(x)$ $ordenador personal$ $n\leq 2^{m}$

Complejidad del tiempo

Suponga que el tiempo para construir un polinomio usando pares es corto en comparación con el tiempo que lleva cifrar los textos sin formato. Sean coeficientes desconocidos en . Entonces la complejidad de este ataque es , y se requieren diferencias conocidas de los pares . $p(x)$ $ordenador personal$ $norte$ $p(x)$ $norte$ $norte$ $ordenador personal$

Ataque de interpolación Meet-In-The-Middle (método de negociación)

A menudo, este método es efectivo. ¿Cómo trabaja?

Sea un cifrado redondo con longitud de bloque , sea la salida del cifrado después de las rondas . Expresaremos el valor como un polinomio de texto plano y como un polinomio de texto cifrado . Let expresa a través , y deja expresa a través . Obtendremos el polinomio calculando con anticipación y no usando fórmulas de cifrado repetidas antes de la ronda, incluido . Obtenemos el polinomio calculando hacia atrás y usando la fórmula de cifrado repetido antes de la ronda. $r$ $metro$ $z$ $s$ $s<r$ $z$ $X$ $C$ $g(x)\en GF(2^{m})[x]$ $z$ $X$ $h(c)\in GF(2^{m})[c]$ $z$ $C$ $g(x)$ $s$ $h(c)$ $s+1$

Así resulta que

g(x)=h(c),

y si ambos son polinomios y con pocos coeficientes, entonces podemos resolver la ecuación para coeficientes desconocidos. $gramo$ $h$

Complejidad del tiempo

Supongamos que se puede expresar en términos de coeficientes y se puede expresar en términos de coeficientes . Entonces necesitaríamos las diferencias conocidas de los pares para resolver la ecuación estableciéndola como una ecuación matricial. Sin embargo, esta ecuación matricial tiene solución hasta la multiplicación y la suma. Por lo tanto, para asegurarnos de obtener una solución única y distinta de cero, establecemos el coeficiente correspondiente a la potencia más alta en 1 y el término constante en cero. Por lo tanto, se requiere una diferencia conocida del par . Entonces, la complejidad de tiempo para este ataque es . El enfoque Meet-In-The-Middle generalmente tiene menos coeficientes que el método convencional. Esto hace que este método sea más eficiente ya que necesitamos menos pares de . $g(x)$ $pags$ $h(c)$ $q$ $p+q$ $ordenador personal$ $p+q-2$ $ordenador personal$ $p+q-2$ $ordenador personal$

Clave de recuperación

También podemos usar un ataque de interpolación para recuperar la clave secreta . Si eliminamos la última ronda , un nuevo cifrado de ronda con longitud de bloque , la salida del cifrado se convierte en . Resulta un cifrado con una complejidad de cifrado reducida. La idea es adivinar la clave de la última ronda, podemos descifrar una ronda para obtener el resultado del cifrado dado. Luego, para probar la conjetura, uno debe usar un ataque de interpolación en el cifrado reducido, ya sea de la manera habitual o usando el método Meet-In-The-Middle. $k$ $r$ $metro$ ${\tilde {y}}=c_{{r-1}}$ $k_{r}$ ${\ tilde {y}}$

De la forma habitual, expresamos la salida del cifrado dado como un polinomio de texto sin formato . Resulta un polinomio . Entonces, si podemos expresar con coeficientes, usando las diferencias conocidas del par , podemos construir un polinomio. Para verificar la conjetura en la última ronda de la llave, uno tiene que verificar con un par adicional si cree que ${\ tilde {y}}$ $X$ $p(x)\en GF(2^{m})[x]$ $p(x)$ $norte$ $norte$ $ordenador personal$ $ordenador personal$

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

entonces, con un alto grado de probabilidad, la suposición de la última ronda de la clave fue correcta. Si no, entonces se necesita hacer una conjetura clave más.

Con el método Meet-In-The-Middle, expresamos la salida redonda como un polinomio de texto sin formato y como un polinomio de salida de cifrado reducido . Deje que los polinomios se expresen en términos de y coeficientes, respectivamente. Entonces, con una diferencia conocida entre los pares, podemos encontrar los coeficientes. Para verificar la conjetura en la última ronda de la clave, verificamos con un par adicional si la igualdad $z$ $s<r$ $X$ ${\ tilde {y}}$ $pags$ $q$ $q+p-2$ $ordenador personal$ $ordenador personal$

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

está satisfecho, entonces, con un alto grado de probabilidad, la suposición de la clave de la última ronda fue correcta. Si no, entonces hacemos otra suposición de la clave.

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

Complejidad del tiempo

Cuando hay una clave secreta de longitud , entonces hay diferentes claves. La probabilidad de que una clave elegida al azar sea correcta es . Por lo tanto, en promedio, se deben hacer conjeturas antes de encontrar la clave correcta. Que. el método convencional tiene una complejidad de tiempo promedio y requiere pares distintos conocidos , mientras que el método Meet-In-The-Middle tiene complejidad y requiere pares distintos conocidos . $metro$ $2^{m}$ $1/2^{m}$ $1/2\cdot 2^{m}$ $2^{{m-1}}(n+1)$ $n+1$ $c/p$ $2^{{m-1}}(p+q-1)$ $p+q-1$ $c/p$

Uso

El ataque Meet-in-the-Middle se puede usar en una variante para atacar S-boxes que usan una función inversa porque con un S-box de -bit, en . El cifrado en bloque SHARK utiliza una red SP con S-boxes . 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 Jacobsen y Lars Knudsen, quienes utilizaron un ataque de interpolación. Denota por SHARK una versión de SHARK con un tamaño de bloque de bits usando S-boxes de bits paralelos con el número de rondas . Jacobsen y Knudsen encontraron que hay un ataque de interpolación en SHARK (cifrado de bloque de 64 bits) usando textos sin formato casi elegidos y un ataque de interpolación en SHARK (cifrado de bloque de 128 bits) usando cerca de los textos sin formato elegidos. $metro$ $S:f(x)=x^{{-1}}=x^{{2^{m}-2}}$ $FG(2^{m})$ $S:f(x)=x^{{-1}}$ $(n, m, r)$ $Nuevo Méjico$ $norte$ $metro$ $r$ $(8,8,4)$ $2^{21}$ $(8,16,7)$ $2^{61}$

Asimismo, Thomas Jacobsen presentó una variante probabilística del ataque de interpolación utilizando el algoritmo Madhu Sudan para mejorar la decodificación de códigos Reed-Solomon . Este ataque puede funcionar incluso si la relación algebraica entre textos sin formato y textos cifrados tiene solo una fracción de los significados.

Notas

Literatura

Thomas Jakobsen, Lars Knudsen. El ataque de interpolación a los cifrados en bloque . — Springer-Verlag, enero de 1997. — págs . 28–40 . — ISBN 3-540-63247-6 .
E.Biham y A.Shamir. Criptoanálisis diferencial de criptosistemas tipo DES. - 1991. - ISBN 3-89649-079-6 .