Criptoanálisis diferencial

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

Historia

El descubrimiento del criptoanálisis diferencial generalmente se atribuye a Eli Biham y Adi Shamir a fines de la década de 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 señalaron que DES era sorprendentemente resistente al criptoanálisis diferencial, pero pequeñas modificaciones al algoritmo lo harían mucho más susceptible.

En 1994, un miembro del equipo DES original de IBM, Don Coppersmith, publicó un artículo en el que se afirmaba que IBM conocía el criptoanálisis diferencial desde 1974 y que la defensa contra el criptoanálisis diferencial había sido un objetivo de diseño. Según el autor Steven Levy, IBM había descubierto el criptoanálisis diferencial por su cuenta, y aparentemente la NSA conocía bien la técnica. IBM guardó algunos secretos, como explica Coppersmith: “Después de conversaciones con la NSA, se decidió que la divulgación de las consideraciones de diseño revelaría la técnica de criptoanálisis diferencial, una técnica poderosa que podría usarse contra muchas cifras. Esto, a su vez, debilitaría la ventaja competitiva que disfrutaba Estados Unidos sobre otros países en el campo de la criptografía." En IBM, el criptoanálisis diferencial se conocía como el "ataque T" o "ataque de cosquillas".

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 bloque FEAL. La versión original propuesta con cuatro rondas (FEAL-4) se puede romper utilizando solo ocho textos sin formato elegidos, e incluso una versión de 31 rondas de FEAL es susceptible al ataque. Por el contrario, el esquema puede criptoanalizar con éxito DES con un esfuerzo del orden de 2⁴⁷ textos sin formato elegidos.

Mecánica de ataque

El criptanálisis diferencial es generalmente un ataque de texto simple elegido, lo que significa que el atacante debe ser capaz de obtener criptografías para algunos conjuntos de texto claros de su elección. Sin embargo, hay extensiones que permitirían un texto conocido o incluso un ataque solo con cifertexto. El método básico utiliza pares de texto simple relacionados por una constante diferencia. La diferencia se puede definir de varias maneras, pero la operación eXclusiva OR (XOR) es habitual. El atacante calcula entonces las diferencias de los criptotextos correspondientes, esperando detectar patrones estadísticos en su distribución. El par de diferencias resultante se llama un diferencial. Sus propiedades estadísticas dependen de la naturaleza de los S-boxes utilizados para la encriptación, por lo que el atacante analiza diferenciales ${displaystyle (Delta _{x},Delta _{y})}$ Donde

$${displaystyle Delta _{y}=S(xoplus Delta _{x})oplus S(x)}$$

En la forma más básica de recuperación de claves a través del criptoanálisis diferencial, un atacante solicita los textos cifrados para una gran cantidad de pares de texto sin formato, luego asume que el diferencial se mantiene durante al menos r − 1 rondas, donde r es el número total de rondas. Luego, el atacante deduce qué teclas de ronda (para la ronda final) son posibles, asumiendo la diferencia entre los bloques antes de que se fije la ronda final. Cuando las claves de ronda son cortas, esto se puede lograr simplemente descifrando exhaustivamente los pares de texto cifrado 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 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 lleva a cabo un análisis de las partes internas del algoritmo; el método estándar consiste en trazar una ruta de diferencias altamente probables a través de las diversas etapas del cifrado, lo que se denomina característica diferencial.

Desde que el criptoanálisis diferencial se convirtió en conocimiento público, se ha convertido en una preocupación básica de los diseñadores de cifrado. Se espera que los nuevos diseños estén 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.

Ataque en detalle

El ataque se basa principalmente en el hecho de que un patrón de diferencia de entrada/salida dado solo ocurre para ciertos valores de entradas. Por lo general, el ataque se aplica en esencia a los componentes no lineales como si fueran un componente sólido (por lo general, en realidad son tablas de consulta o S-boxes). Al observar la diferencia de salida deseada (entre dos entradas de texto simple 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) luego solo por 4 valores (o 2 pares) de entradas es ese diferencial posible. Supongamos que tenemos una función no lineal donde la clave se aplica 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 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 una función no lineal de n bits, lo ideal sería buscar lo más cerca posible de 2^{−(n − 1)} para lograr uniformidad diferencial. Cuando esto sucede, el ataque diferencial requiere tanto trabajo para determinar la clave como simplemente fuerza bruta en la clave.

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). Lo que significa que, en teoría, uno podría determinar la clave con la mitad de trabajo que la fuerza bruta, sin embargo, la rama alta de AES evita que existan rastros de alta probabilidad en múltiples rondas. De hecho, el cifrado AES sería igual de inmune a ataques diferenciales y lineales con una función no lineal mucho más débil. La rama increíblemente alta (recuento de cajas S activas) de 25 sobre 4R significa que durante 8 rondas ningún ataque implica menos de 50 transformaciones no lineales, lo que significa que la probabilidad de éxito no excede Pr[ataque] ≤ Pr[mejor ataque en caja S]⁵⁰. Por ejemplo, con el S-box actual, AES no emite un diferencial fijo con una probabilidad superior a (4/256)⁵⁰ o 2⁻³⁰⁰, que es mucho menor que el requerido umbral de 2⁻¹²⁸ para un cifrado de bloque de 128 bits. Esto habría dejado espacio para un S-box más eficiente, incluso si fuera uniforme 16, la probabilidad de ataque habría sido de 2⁻²⁰⁰.

No existen biyecciones para entradas/salidas de tamaño uniforme con uniformidad de 2. Existen en campos impares (como GF(2⁷)) usando el cubo o la inversión (hay otros exponentes que también se pueden usar). 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 los ataques diferenciales y lineales lo pierden a los ataques algebraicos. Es decir, son posibles de describir y resolver a través de 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.

Tipos especializados

• criptanálisis diferencial de orden superior
• criptanálisis diferencial truncado
• criptanálisis diferencial imposible
• Ataque de Boomerang