Criptoanálisis diferencial de orden superior

Tipo de ataque criptoanalítico

En criptografía , el criptoanálisis diferencial de orden superior es una generalización del criptoanálisis diferencial , un ataque utilizado contra los cifrados de bloque . Mientras que en el criptoanálisis diferencial estándar se utiliza la diferencia entre solo dos textos, el criptoanálisis diferencial de orden superior estudia la propagación de un conjunto de diferencias entre un conjunto más grande de textos. Xuejia Lai , en 1994, sentó las bases al demostrar que los diferenciales son un caso especial del caso más general de los derivados de orden superior. ^[1] Lars Knudsen , en el mismo año, pudo demostrar cómo el concepto de derivados de orden superior puede usarse para montar ataques a los cifrados de bloque. ^[2] Estos ataques pueden ser superiores al criptoanálisis diferencial estándar. El criptoanálisis diferencial de orden superior se ha utilizado notablemente para romper el cifrado KN , un cifrado que previamente había demostrado ser inmune al criptoanálisis diferencial estándar. ^[3]

Derivadas de orden superior

Un cifrador de bloques que asigna cadenas de -bits a cadenas de -bits puede, para una clave fija, considerarse como una función . En el criptoanálisis diferencial estándar, uno está interesado en encontrar un par de una diferencia de entrada y una diferencia de salida de modo que dos textos de entrada con diferencia tengan probabilidades de dar como resultado textos de salida con una diferencia , es decir, que sea cierto para muchos . Tenga en cuenta que la diferencia utilizada aquí es el XOR, que es el caso habitual, aunque son posibles otras definiciones de diferencia. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f:\mathbb {F} _{2}^{n}\to \mathbb {F} _{2}^{n}}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle f(m\oplus \alpha )\oplus f(m)=\beta }$ ${\displaystyle m\in \mathbb {F} _{2}^{n}}$

Esto motiva definir la derivada de una función en un punto como ^[1] ${\displaystyle f:\mathbb {F} _{2}^{n}\to \mathbb {F} _{2}^{n}}$ ${\displaystyle \alpha }$

${\displaystyle \Delta _{\alpha }f(x):=f(x\oplus \alpha )\oplus f(x)}$.

Usando esta definición, la derivada -ésima en puede definirse recursivamente como ^[1] ${\displaystyle i}$ ${\displaystyle (\alpha _{1},\alpha _{2},\dots ,\alpha _{i})}$

${\displaystyle \Delta _{\alpha _{1},\alpha _{2},\dots ,\alpha _{i}}^{(i)}f(x):=\Delta _{\alpha _{i}}\left(\Delta _{\alpha _{1},\alpha _{2},\dots ,\alpha _{i-1}}^{i-1}f(x)\right)}$.

Así por ejemplo . ${\displaystyle \Delta _{\alpha _{1},\alpha _{2}}^{(2)}f(x)=f(x)\oplus f(x\oplus \alpha _{1})\oplus f(x\oplus \alpha _{2})\oplus f(x\oplus \alpha _{1}\oplus \alpha _{2})}$

Las derivadas de orden superior, como se definen aquí, tienen muchas propiedades en común con las derivadas ordinarias, como la regla de la suma y la regla del producto . También es importante destacar que al tomar la derivada se reduce el grado algebraico de la función.

Ataques diferenciales de orden superior

Para implementar un ataque utilizando derivadas de orden superior, se necesita conocer la distribución de probabilidad de la derivada del cifrado. Calcular o estimar esta distribución es generalmente un problema difícil, pero si se sabe que el cifrado en cuestión tiene un grado algebraico bajo , se puede utilizar el hecho de que las derivadas reducen este grado. Por ejemplo, si se sabe que un cifrado (o la función S-box bajo análisis) solo tiene un grado algebraico de 8, cualquier derivada de noveno orden debe ser 0.

Por lo tanto, es importante que cualquier cifrado o función S-box en específico tenga un grado máximo (o cercano al máximo) para desafiar este ataque.

Los ataques de cubo se han considerado una variante de los ataques diferenciales de orden superior. ^[4]

Resistencia contra ataques diferenciales de orden superior

Limitaciones de los ataques diferenciales de orden superior

Funciona con cajas S pequeñas o de grado algebraico bajo. Además de operaciones AND y XOR.

Véase también

• Criptoanálisis diferencial
• Cifrado KN
• Ataque de cubo

Referencias

1. Lai, Xuejia (1994). "Derivadas de orden superior y criptoanálisis diferencial". Comunicaciones y criptografía . Vol. 276. Springer US. págs. 227–233. doi :10.1007/978-1-4615-2694-0_23. ISBN 978-1-4613-6159-6.
2. Knudsen, Lars (1994). Diferenciales truncados y de orden superior ( PDF / PostScript ) . Fast Software Encryption (FSE 1994). Springer-Verlag . pp. 196–211 . Consultado el 14 de febrero de 2007 .
3. Jakobsen, Thomas y Knudsen, Lars (1997). "El ataque de interpolación en los cifrados de bloques". Fast Software Encryption . Apuntes de clase en informática. Vol. 1267. Springer Berlin Heidelberg. págs. 28–40. doi :10.1007/BFb0052332. ISBN 978-3-540-63247-4.{{cite book}}: CS1 maint: multiple names: authors list (link)
4. Daniel J. Bernstein (14 de enero de 2009). "¿Por qué los ataques con cubos no han roto nada?" . Consultado el 18 de mayo de 2014 .