Criptoanálisis diferencial de orden superior

En criptografía , el criptoanálisis diferencial de orden superior es una generalización del criptoanálisis diferencial , un ataque utilizado contra cifrados de bloques . 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 mayor de textos. Xuejia Lai , en 1994, sentó las bases al demostrar que los diferenciales son un caso especial del caso más general de derivadas de orden superior. ^{[ 1 ]} Lars Knudsen , ese mismo año, demostró cómo el concepto de derivadas de orden superior puede utilizarse para realizar ataques contra cifrados de bloques. ^{[ 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 se había demostrado inmune al criptoanálisis diferencial estándar. ^{[ 3 ]}

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

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

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

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

${\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, tal como se definen aquí, comparten muchas propiedades con las derivadas ordinarias, como la regla de la suma y la regla del producto . Además, es importante destacar que al calcular la derivada se reduce el grado algebraico de la función.

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 suele ser un problema complejo, pero si se sabe que el cifrado en cuestión tiene un grado algebraico bajo , se puede aprovechar el hecho de que las derivadas reducen este grado. Por ejemplo, si se sabe que un cifrado (o la función S-box que se analiza) tiene un grado algebraico de solo 8, cualquier derivada de noveno orden debe ser 0.

Por lo tanto, es importante que cualquier cifrado o función S-box en particular tenga un grado máximo (o casi máximo) para resistir este ataque.

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

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

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