El criptoanálisis diferencial es una forma general de criptoanálisis aplicable principalmente a los cifrados de bloque, pero también a los cifrados de flujo y a las funciones hash criptográficas. En el sentido más amplio, es el estudio de cómo las diferencias en la información de entrada pueden afectar la diferencia resultante en la salida. En el caso de un cifrado de bloque , se refiere a un conjunto de técnicas para rastrear diferencias a través de la red de transformación, descubrir dónde el cifrado exhibe un comportamiento no aleatorio y explotar dichas propiedades para recuperar la clave secreta (clave criptográfica).
El descubrimiento del criptoanálisis diferencial se atribuye generalmente a Eli Biham y Adi Shamir a finales de los años 1980, quienes publicaron una serie de ataques contra varios cifrados de bloque y funciones hash, incluida una debilidad teórica en el Estándar de cifrado de datos (DES). Biham y Shamir observaron que DES era sorprendentemente resistente al criptoanálisis diferencial, pero pequeñas modificaciones al algoritmo lo harían mucho más susceptible. [1] : 8–9
En 1994, un miembro del equipo original de IBM DES, Don Coppersmith , publicó un artículo en el que afirmaba que IBM conocía el criptoanálisis diferencial desde 1974 y que defenderse contra el criptoanálisis diferencial había sido un objetivo de diseño. [2] Según el autor Steven Levy , IBM había descubierto el criptoanálisis diferencial por sí sola y la NSA aparentemente conocía bien la técnica. [3] IBM guardaba algunos secretos, como explica Coppersmith: "Después de las discusiones con la NSA, se decidió que la divulgación de las consideraciones de diseño revelaría la técnica del criptoanálisis diferencial, una técnica poderosa que podría usarse contra muchos cifrados. Esto, a su vez, debilitaría la ventaja competitiva que Estados Unidos disfrutaba sobre otros países en el campo de la criptografía". [2] Dentro de IBM, el criptoanálisis diferencial se conocía como el "ataque T" [2] o "ataque Tickle". [4]
Aunque DES fue diseñado teniendo en mente la resistencia al criptoanálisis diferencial, otros cifrados contemporáneos demostraron ser vulnerables. Uno de los primeros objetivos del ataque fue el cifrado en bloque FEAL . La versión propuesta originalmente con cuatro rondas (FEAL-4) puede ser descifrada utilizando solo ocho textos simples seleccionados , e incluso una versión de FEAL de 31 rondas es susceptible al ataque. En contraste, el esquema puede criptoanalizar DES con éxito con un esfuerzo del orden de 247 textos simples seleccionados.
El criptoanálisis diferencial es generalmente un ataque de texto simple elegido , lo que significa que el atacante debe poder obtener textos cifrados para algún conjunto de textos simples de su elección. Sin embargo, existen extensiones que permitirían un ataque de texto simple conocido o incluso un ataque de solo texto cifrado . El método básico utiliza pares de textos simples relacionados por una diferencia constante . La diferencia se puede definir de varias formas, pero la operación OR exclusiva (XOR) es la habitual. El atacante luego calcula las diferencias de los textos cifrados correspondientes, con la esperanza de detectar patrones estadísticos en su distribución. El par de diferencias resultante se llama diferencial . Sus propiedades estadísticas dependen de la naturaleza de las cajas S utilizadas para el cifrado, por lo que el atacante analiza diferenciales donde (y ⊕ denota OR exclusivo) para cada una de esas cajas S S. En el ataque básico, se espera que una diferencia de texto cifrado en particular sea especialmente frecuente. De esta manera, el cifrado se puede distinguir de aleatorio . Las variaciones más sofisticadas permiten recuperar la clave más rápido que una búsqueda exhaustiva .
En la forma más básica de recuperación de claves mediante criptoanálisis diferencial, un atacante solicita los textos cifrados de una gran cantidad de pares de textos simples y luego supone que el diferencial se mantiene durante al menos r − 1 rondas, donde r es el número total de rondas. [5] Luego, el atacante deduce qué claves de ronda (para la ronda final) son posibles, suponiendo que la diferencia entre los bloques antes de la ronda final es fija. Cuando las claves de ronda son cortas, esto se puede lograr simplemente descifrando exhaustivamente los pares de textos cifrados una ronda con cada clave de ronda posible. Cuando una clave de ronda se ha considerado una clave de ronda potencial considerablemente más a menudo que cualquier otra clave, se supone que es la clave de ronda correcta.
Para cualquier cifrado en particular, la diferencia de entrada debe seleccionarse cuidadosamente para que el ataque tenga éxito. Se realiza un análisis de los componentes internos del algoritmo; el método estándar consiste en trazar una ruta de diferencias altamente probables a través de las distintas etapas del cifrado, denominada característica diferencial .
Desde que el criptoanálisis diferencial se hizo público, se ha convertido en una preocupación básica de los diseñadores de sistemas de cifrado. Se espera que los nuevos diseños vengan acompañados de evidencia de que el algoritmo es resistente a este ataque y muchos, incluido el Estándar de cifrado avanzado , han demostrado ser seguros contra el ataque. [6]
El ataque se basa principalmente en el hecho de que un patrón de diferencia de entrada/salida determinado solo se produce para ciertos valores de entrada. Por lo general, el ataque se aplica en esencia a los componentes no lineales como si fueran un componente sólido (normalmente, de hecho, son tablas de consulta o cajas S ). La observación de la diferencia de salida deseada (entre dos entradas de texto sin formato elegidas o conocidas) sugiere posibles valores clave.
Por ejemplo, si una diferencial de 1 => 1 (lo que implica que una diferencia en el bit menos significativo (LSB) de la entrada conduce a una diferencia de salida en el LSB) ocurre con una probabilidad de 4/256 (posible con la función no lineal en el cifrado AES , por ejemplo), entonces solo para 4 valores (o 2 pares) de entradas es posible esa diferencial. Supongamos que tenemos una función no lineal donde la clave se XOR antes de la evaluación y los valores que permiten la diferencial son {2,3} y {4,5}. Si el atacante envía los valores de {6, 7} y observa la diferencia de salida correcta, significa que la clave es 6 ⊕ K = 2 o 6 ⊕ K = 4, lo que significa que la clave K es 2 o 4.
En esencia, para proteger un cifrado del ataque, para una función no lineal de n bits lo ideal sería buscar un valor lo más cercano posible a 2 −( n − 1) para lograr uniformidad diferencial . Cuando esto sucede, el ataque diferencial requiere tanto trabajo para determinar la clave como simplemente forzar la clave. [7]
La función no lineal AES tiene una probabilidad diferencial máxima de 4/256 (sin embargo, la mayoría de las entradas son 0 o 2). Esto significa que, en teoría, se podría determinar la clave con la mitad de trabajo que con la fuerza bruta; sin embargo, la rama alta de AES evita que existan rastros de alta probabilidad en varias rondas. De hecho, el cifrado AES sería igual de inmune a los ataques diferenciales y lineales con una función no lineal mucho más débil . La rama increíblemente alta (número de S-box activas) de 25 sobre 4R significa que, en 8 rondas, ningún ataque implica menos de 50 transformaciones no lineales, lo que significa que la probabilidad de éxito no supera Pr[ataque] ≤ Pr[mejor ataque en S-box] 50 . Por ejemplo, con la S-box actual, AES no emite ningún diferencial fijo con una probabilidad superior a (4/256) 50 o 2 −300 , que es mucho menor que el umbral requerido de 2 −128 para un cifrado de bloque de 128 bits. Esto habría dejado espacio para una S-box más eficiente, incluso si es 16-uniforme, la probabilidad de ataque habría sido todavía 2 −200 .
No existen biyecciones para entradas/salidas de tamaño par con 2-uniformidad. Existen en cuerpos impares (como GF(2 7 )) utilizando cubos o inversión (hay otros exponentes que también se pueden usar). Por ejemplo, S(x) = x 3 en cualquier cuerpo binario impar es inmune al criptoanálisis diferencial y lineal. Esta es en parte la razón por la que los diseños MISTY usan funciones de 7 y 9 bits en la función no lineal de 16 bits. Lo que estas funciones ganan en inmunidad a ataques diferenciales y lineales, lo pierden ante ataques algebraicos. [ ¿por qué? ] Es decir, es posible describirlas y resolverlas a través de un solucionador SAT . Esta es en parte la razón por la que AES (por ejemplo) tiene una asignación afín después de la inversión.
