Criptoanálisis diferencial

El descubrimiento del criptoanálisis diferencial se atribuye generalmente a Eli Biham y Adi Shamir a finales de los años 1980, que publicaron una serie de ataques contra varios cifrados de bloque y funciones hash, incluyendo una debilidad teórica en el Data Encryption Standard (DES). Biham y Shamir señalaron que el cifrado DES es 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 original del desarrollo del cifrado DES de IBM, Don Coppersmith, publicó un papel que indicaba que el criptoanálisis diferencial era conocido por IBM en el año 1974, y que una de las grandes metas en el desarrollo fue, precisamente, luchar contra este tipo de criptoanálisis. De acuerdo con el autor Steven Levy, IBM había descubierto el criptoanálisis diferencial por sí mismo, y la NSA era, aparentemente, muy consciente de la técnica. IBM mantuvo algunos secretos, como explica Coppersmith: "Después de las conversaciones con la NSA, se decidió que la divulgación de las decisiones de diseño revelaría la técnica del criptoanálisis diferencial, una poderosa técnica que podría utilizarse contra muchos cifrados, ventaja que los Estados Unidos disfrutaban sobre otros países en el campo de la criptografía ". Dentro de IBM, el criptoanálisis diferencial era conocido como el "ataque T" o "ataque de cosquillas".

Aunque el cifrado DES fue diseñado teniendo en cuenta la resistencia al criptoanálisis diferencial, otros cifrados contemporáneas resultaron ser vulnerables. Un objetivo inicial para el ataque fue el cifrado de bloque FEAL. La versión original propuesta con cuatro rondas (FEAL-4) se puede romper utilizando sólo ocho Chosen-plaintexts attack, e incluso una versión de 31 rondas de FEAL es susceptible al ataque. En contraste, el esquema puede criptoanalizar satisfactoriamente DES con un esfuerzo de orden 2⁴⁷ chosen-plaintexts attack.

El criptoanálisis diferencial suele ser un ataque de diccionario, lo que significa que el atacante debe ser capaz de obtener textos cifrados para un conjunto de textos planos de su elección. Hay, sin embargo, extensiones que permitirían un ataque de texto plano conocido, o incluso un ataque de texto cifrado. El método básico utiliza pares de texto sin formato relacionados por una diferencia constante; Diferencia se puede definir de varias maneras, pero la operación OR exclusiva (XOR) es 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 denomina "diferencial". Sus propiedades estadísticas dependen de la naturaleza de la caja S que es utilizada para el cifrado, por lo que el atacante analiza los diferenciales (Δ_X, Δ_Y), donde Δ_Y = S(X ⊕ Δ_X) ⊕ S(X) (y ⊕ denota la OR exclusiva(XOR)) para cada caja S S. En el ataque básico, se espera que una diferencia particular en el texto cifrado sea especialmente frecuente. Las variaciones más sofisticadas permiten que la clave sea recuperada más rápidamente que mediante una búsqueda exhaustiva.

En la forma más sencilla de recuperación de claves a través del criptoanálisis diferencial, un atacante solicita los textos cifrados para un gran número de pares de texto plano, entonces asume que el diferencial se sostiene por lo menos r − 1 rondas, donde r es el número total de rondas. El atacante deduce entonces qué claves son posibles, suponiendo que la diferencia entre los bloques antes de que se llegue a la ronda final. Cuando las claves son cortas, esto puede lograrse simplemente descifrando de forma exhaustiva los pares de texto cifrado una vuelta con cada clave posible. Cuando una clave se ha observado más a menudo que cualquier otra clave, se asume que es la clave correcta.

Para cualquier cifrado particular, la diferencia de entrada debe seleccionarse cuidadosamente para que el ataque sea exitoso. Se realiza un análisis de los elementos internos del algoritmo; El método estándar consiste en trazar un camino de diferencias altamente probables a través de las diversas etapas de cifrado, denominadas "características diferenciales".

Dado 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 sean acompañados por evidencias de que el algoritmo es resistente a este ataque, y muchos, incluyendo el Estándar de Encriptación Avanzado, han sido probados contra el ataque.

El ataque se basa principalmente en el hecho de que un determinado patrón de diferencia de entrada / salida sólo ocurre para ciertos valores de entradas. Por lo general, el ataque se aplica esencialmente a los componentes no lineales como si fueran un componente sólido (normalmente son en realidad tablas de búsqueda o cajas S). Observando la diferencia de salida deseada (entre dos entradas de texto claro elegidas o conocidas) sugiere posibles claves.

Por ejemplo, si un diferencial de 1 => 1 (que implica 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 cifraso AES por ejemplo), entonces sólo para 4 valores (o 2 pares) de entradas es posible ese diferencial. Supongamos que tenemos una función no lineal donde la clave es 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 el diferencial de salida correcto 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, idealmente se buscaría lo más cerca posible de 2^{−(n − 1)} para lograr la uniformidad diferencial. Cuando esto sucede, el ataque diferencial requiere tanto trabajo para determinar la clave como, simplemente, forzar la clave.

La función no lineal AES tiene una probabilidad máxima diferencial de 4/256 (la mayoría de las entradas sin embargo son 0 o 2). Lo que significa que, en teoría, se podría determinar la clave con la mitad de trabajo que mediante fuerza bruta, sin embargo, la variante fuerte de AES impide cualquier rastro de alta probabilidad a lo largo de múltiples 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 variante fuerte de AES de 25 sobre 4R significa que más de 8 rondas sin ataque implica menos de 50 transformaciones no lineales, lo que significa que la probabilidad de éxito no excede Pr[ataque] ≤ Pr[mejor ataque a caja S]⁵⁰. Por ejemplo, con la actual caja S AES no emite ningún diferencial fijo con una probabilidad mayor que (4/256)⁵⁰ o 2^-300 que es mucho menor que el umbral requerido de 2^-128 para un cifrado de bloques de 128 bits. Esto habría permitido espacio para una caja S más eficiente.

No existen biyecciones para entradas/salidas de tamaño uniforme con uniformidad 2. Existen en campos impares (como GF(2⁷)) utilizando cubing o inversión (hay otros exponentes que se pueden utilizar también). Por ejemplo, S(x) = x³ en cualquier campo binario impar es inmune al criptoanálisis diferencial y lineal. Esto es en parte porque 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. Es decir, son posibles de describir y resolver a través de un SAT solver. Esto es en parte porque AES (por ejemplo) tiene un mapeo afín después de la inversión.

• Criptoanálisis diferencial de orden alto
• Criptoanálisis diferencial truncado
• Criptoanálisis diferencial imposible
• Ataque de Boomerang

• Criptografía

• A tutorial on differential (and linear) cryptanalysis
• Helger Lipmaa's links on differential cryptanalysis