Fundamentos del criptoanálisis diferencial

El criptoanálisis diferencial (Biham y Shamir, 1990) es un ataque de texto plano elegido que analiza cómo se propagan las diferencias entre pares de textos planos a través de un cifrado. Al encontrar diferencias de entrada que producen diferencias de salida predecibles con alta probabilidad, un atacante recupera bits de la clave mediante métodos estadísticos.

Para cifrados basados en XOR: diferencia ΔX = X XOR X'. Para cifrados basados en suma: diferencia ΔX = X - X' mod 2^n. Las diferencias XOR son las más comunes, ya que XOR conmuta con el uso de claves XOR (los efectos del esquema de claves se cancelan en los pares diferenciales).

Un par diferencial (P, P') tiene una diferencia de entrada ΔP = P XOR P'. Después del cifrado: (C, C'), con una diferencia de salida ΔC = C XOR C'. Una diferencial útil es ΔP → ΔC con una probabilidad p alta, lo que significa que muchos pares (P, P') con diferencia ΔP producen la diferencia de salida ΔC.

La DDT (tabla de distribución diferencial) cuenta, para cada diferencia de entrada Δx y diferencia de salida Δy, cuántas entradas x cumplen S(x) XOR S(x XOR Δx) = Δy. Al dividir por 2^n se obtiene la probabilidad. Una buena S-box tiene un valor máximo de DDT igual a 2 (probabilidad 1/2^{n-1}), sin diferenciales fuertes.

Para un cifrado de bloques con r rondas: encuentre una secuencia ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} en la que cada transición de ronda tenga una probabilidad conocida. Multiplique las probabilidades de todas las rondas: la probabilidad global es p = p1 * p2 * ... * p_{r-1}. El ataque utiliza 2/p pares para recuperar la clave de la última ronda.

Con una diferencial de alta probabilidad de r-1 rondas: recopile N = 2/p pares de textos planos. Para cada clave candidata de la última ronda K', descifre ambos textos cifrados una ronda, aplique XOR a los resultados y compruebe si la diferencia coincide con ΔU_{r-1}. La K' correcta coincide aproximadamente N/2 veces; las claves incorrectas coinciden aproximadamente N/2^{bit_size} veces.

La S-box de AES es la inversa multiplicativa sobre GF(2^8), seguida de una transformación afín. Su valor máximo en la DDT es 4 (de 256), lo que da una probabilidad diferencial ≤ 4/256 = 1/64 por S-box. AES tiene 4 S-boxes por ronda, pero el diseño Wide Trail garantiza que las trayectorias diferenciales completas sean inferiores a 2^{-100}.

El diseño Wide Trail de Joan Daemen (utilizado en AES/Rijndael) define el número de ramas B de MixColumns. Toda trayectoria diferencial no trivial a través de una ronda activa ≥ B S-boxes. 4 rondas × 4 S-boxes por ronda garantizan ≥ 25 S-boxes activas → probabilidad < 2^{-100}.

Las diferenciales truncadas especifican solo una parte de la diferencia, por ejemplo, qué columnas están activas, pero no los valores exactos de las diferencias. Permiten realizar ataques contra más rondas cuando las diferenciales completas son demasiado débiles. Se utilizan contra AES con un número reducido de rondas, SERPENT y otros cifrados SPN.

Una diferencial imposible es un par (ΔP, ΔC) que nunca puede producirse con ninguna clave. Se elimina cualquier clave que transforme un par observado (P, P') con esta diferencia. Al recopilar suficientes pares, se eliminan todas las claves incorrectas y queda la clave correcta.

El ataque de boomerang (Wagner, 1999) combina dos diferenciales cortas en un ataque adaptativo de texto plano o texto cifrado elegido. Divide el cifrado en dos mitades, cada una con una diferencial corta de alta probabilidad, y permite atacar más rondas de las que permitiría una sola diferencial.

¿Cuál es la finalidad de la tabla de distribución diferencial (DDT) en el criptoanálisis?

El criptoanálisis diferencial aprovecha la propagación de diferencias de entrada a salida con alta probabilidad. AES se defiende mediante su S-box optimizada para la DDT y el diseño Wide Trail. Siguiente tema: criptoanálisis lineal y tablas de aproximación.