Criptoanálisis diferencial

El criptoanálisis diferencial es una forma general de criptoanálisis aplicable principalmente a cifrados por bloques , pero también a cifrados de flujo y funciones hash criptográficas. En su sentido más amplio, estudia cómo las diferencias en la información de entrada pueden afectar la diferencia resultante en la salida. En el caso de un cifrado por bloques , se refiere a un conjunto de técnicas para rastrear las diferencias a través de la red de transformación, descubrir dónde el cifrado presenta un comportamiento no aleatorio y explotar dichas propiedades para recuperar la clave secreta (clave criptográfica).

El descubrimiento y la divulgación pública del criptoanálisis diferencial se atribuyen generalmente a Eli Biham y Adi Shamir a finales de la década de 1980, quienes publicaron varios ataques contra diversos cifrados de bloques y funciones hash, incluyendo una debilidad teórica en el Estándar de Cifrado de Datos (DES). Biham y Shamir observaron que el 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, Don Coppersmith , miembro del equipo original de IBM DES, publicó un artículo en el que afirmaba que IBM conocía el criptoanálisis diferencial desde 1974 y que defenderse contra él había sido un objetivo de diseño. ^{[ 2 ]} Según el autor Steven Levy , IBM había descubierto el criptoanálisis diferencial por su cuenta, y la NSA aparentemente estaba al tanto de la técnica. ^{[ 3 ]} IBM guardaba algunos secretos, como explica Coppersmith: «Tras conversaciones 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 ]}

Si bien DES se diseñó teniendo en cuenta la resistencia al criptoanálisis diferencial, otros cifrados contemporáneos demostraron ser vulnerables. Uno de los primeros objetivos del ataque fue el cifrado de bloques FEAL . La versión original propuesta con cuatro rondas (FEAL-4) puede romperse utilizando solo ocho textos planos elegidos , e incluso una versión de 31 rondas de FEAL es susceptible al ataque. En contraste, el esquema puede criptoanalizar con éxito DES con un esfuerzo del orden de 2⁴⁷ ^textos planos elegidos.

El criptoanálisis diferencial suele ser un ataque de texto plano elegido , lo que significa que el atacante debe poder obtener textos cifrados para algún conjunto de textos planos de su elección. Sin embargo, existen extensiones que permitirían un texto plano conocido o incluso un ataque solo de texto cifrado . El método básico utiliza pares de textos planos relacionados por una diferencia constante . La diferencia se puede definir de varias maneras, pero la operación OR exclusivo (XOR) es la habitual. El atacante calcula entonces 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 los diferenciales.${\displaystyle (\Delta _ {x}, \Delta _ {y})}$dónde $${\displaystyle \Delta _{y}=S(x\oplus \Delta _{x})\oplus S(x)}$$ (y ⊕ denota disyunción exclusiva) para cada S-box S. En el ataque básico, se espera que una diferencia particular en el texto cifrado sea especialmente frecuente. De esta manera, el cifrado se puede distinguir de uno aleatorio . 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 para un gran número de pares de texto plano y asume que la diferencia se mantiene durante al menos r − 1 rondas, donde r es el número total de rondas. A continuación, el atacante deduce qué claves de ronda (para la ronda final) son posibles, asumiendo 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 texto cifrados una ronda con cada clave de ronda posible. Cuando una clave de ronda se ha considerado una clave de ronda potencial con mucha más frecuencia que cualquier otra, se asume 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 la estructura interna del algoritmo; el método estándar consiste en rastrear 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 fundamental para los diseñadores de cifrado. Se espera que los nuevos diseños vayan acompañados de pruebas de que el algoritmo es resistente a este ataque, y muchos, incluido el Estándar de Cifrado Avanzado (ACE) , han demostrado ser seguros frente a él. ^{[ 5 ]}

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. Generalmente, el ataque se aplica a los componentes no lineales como si fueran un componente sólido (normalmente se trata de tablas de búsqueda o cajas S ). Observar la diferencia de salida deseada (entre dos entradas de texto plano elegidas o conocidas) sugiere posibles valores clave.

Por ejemplo, si un 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 para solo 4 valores (o 2 pares) de entradas es posible ese diferencial. Supongamos que tenemos una función no lineal donde la clave se combina con XOR antes de la evaluación y los valores que permiten el diferencial son {2,3} y {4,5}. Si el atacante envía los valores {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 ocurre, el ataque diferencial requiere tanto trabajo para determinar la clave como si se tratara de un ataque de fuerza bruta. ^{[ 6 ]}

La función no lineal AES tiene una probabilidad diferencial máxima de 4/256 (aunque 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 del esfuerzo que con la fuerza bruta; sin embargo, la rama alta de AES impide que existan rastros de alta probabilidad a lo largo de 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 (conteo de S-box activas) de 25 sobre 4R significa que, a lo largo de 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) ⁵⁰ o 2 ⁻³⁰⁰ , que es mucho menor que el umbral requerido de 2 ⁻¹²⁸ para un cifrado de bloques de 128 bits. Esto habría permitido espacio para una S-box más eficiente, incluso si es 16-uniforme la probabilidad de ataque habría seguido siendo 2 ⁻²⁰⁰ .

No existen biyecciones para entradas/salidas de tamaño par con 2-uniformidad. Existen en campos impares (como GF(2 ⁷ )) usando cubo o inversión (también se pueden usar otros exponentes). Por ejemplo, S(x) = x ³ en cualquier campo 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 frente a ataques algebraicos. Es decir, es posible describirlas y resolverlas mediante un solucionador SAT . Esta es en parte la razón por la que AES (por ejemplo) tiene un mapeo afín después de la inversión.

• Criptoanálisis diferencial de orden superior
• Criptoanálisis diferencial truncado
• Criptoanálisis diferencial imposible
• Ataque bumerán

• Criptografía
• Criptoanálisis integral
• Criptoanálisis lineal
• Ecuaciones diferenciales de adición

• Un tutorial sobre criptoanálisis diferencial (y lineal)
• Enlaces de Helger Lipmaa sobre criptoanálisis diferencial
• Descripción del ataque aplicado a DES en Wayback Machine (archivado el 19 de octubre de 2007).