Criptoanálisis lineal y tablas de aproximación

El criptoanálisis lineal (Matsui, 1993) es un ataque de texto plano conocido que encuentra aproximaciones lineales (XOR de bits específicos) de un cifrado que se cumplen con una probabilidad p ≠ 1/2. Al utilizar muchos pares de texto plano y texto cifrado, el sesgo estadístico revela bits de la clave.

Una aproximación lineal para una S-box: la suma de bits de entrada seleccionados XOR la suma de bits de salida seleccionados = 0 (mod 2) con una probabilidad p. Se expresa como: P[a·x XOR b·y = 0] = 1/2 + ε, donde a,b son máscaras de bits y ε es el sesgo (|ε| >> 0 es deseable).

La LAT cuenta, para cada máscara de entrada a y máscara de salida b, el número de entradas x para las que (a·x) XOR (b·S(x)) = 0. Reste 2^{n-1} para obtener el sesgo. Una buena S-box tiene |max_bias| = 1 (probabilidad 1/2 ± 1/2^{n/2}), lo más uniforme posible.

Para aproximaciones lineales independientes a través de varias rondas, los sesgos se multiplican: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Cada aproximación de ronda reduce a la mitad el sesgo efectivo. Después de muchas rondas, el sesgo total se aproxima a 0, por lo que se necesitan exponencialmente más pares para detectarlo.

Para atacar un cifrado de r rondas: encuentre una trayectoria lineal ε a través de r-1 rondas. Recopile N = 1/ε^2 textos planos conocidos. Para cada byte de clave candidata de la última ronda k': descifre parcialmente con XOR la última ronda y compruebe si la aproximación lineal se cumple más de N/2 veces. La k' correcta muestra el sesgo correcto.

Matsui atacó DES de 16 rondas en 1993 utilizando una aproximación lineal de 14 rondas con un sesgo de 2^{-21.4}. Necesitó 2^{43} textos planos conocidos. Recuperó 26 bits de la clave en la fase 1 y los 30 restantes mediante búsqueda exhaustiva. Fue el primer ataque práctico más rápido que la fuerza bruta contra DES completo.

La S-box de AES tiene una entrada máxima en la LAT de |ε| = 4/256 = 1/64 por S-box. La estrategia Wide Trail limita a ≥ 25 el número de S-boxes activas en cualquier trayectoria de 4 rondas. El sesgo total es ≤ (1/64)^{25/2} ≈ 2^{-75}. Se necesitarían 2^{150} textos planos conocidos, una cantidad inviable.

Diferencial: pares de textos planos conocidos o elegidos; aprovecha las diferencias de salida. Lineal: textos planos conocidos; aprovecha aproximaciones lineales estadísticas. Ambos son ataques de texto plano elegido en ataques prácticos. Ambos son criterios de diseño: las S-boxes deben resistir ambos ataques (máximo bajo en la DDT Y máximo bajo en la LAT).

Utilice varias aproximaciones lineales simultáneamente para reducir la complejidad de los datos. Nyberg y Leander ampliaron el método de Matsui: combinar M aproximaciones reduce los datos por un factor de log(M). Se aplica a PRESENT, SIMON y otros cifrados ligeros.

La aproximación lineal aplicada a cifrados de flujo busca una correlación entre el flujo de claves y una función lineal de la salida del LFSR. Esta correlación, si no es cero, permite recuperar la clave más rápido que mediante una búsqueda exhaustiva. Este análisis inspiró el diseño de funciones combinadoras no lineales en los cifrados de flujo.

El criptoanálisis integral (Knudsen-Wagner) elige un conjunto de textos planos en el que ciertos bytes adoptan los 256 valores, mientras los demás permanecen fijos. Después de varias rondas, el XOR de todas las salidas en ciertas posiciones es 0 (equilibrado). Aprovecha la estructura de AES y rompe de forma eficiente AES con un número reducido de rondas.

¿Qué establece el lema de acumulación sobre la combinación de aproximaciones lineales?

El criptoanálisis lineal encuentra aproximaciones lineales sesgadas de las S-boxes. AES se defiende mediante su S-box optimizada para la LAT y el diseño Wide Trail. Matsui rompió DES con 2^43 textos planos conocidos utilizando una trayectoria de 14 rondas. Siguiente tema: ataques de cumpleaños y búsqueda de colisiones.