En criptografía , el criptoanálisis lineal es una forma general de criptoanálisis basada en la búsqueda de aproximaciones afines a la acción de un cifrado . Se han desarrollado ataques para cifrados de bloque y cifrados de flujo . El criptoanálisis lineal es uno de los dos ataques más utilizados contra cifrados de bloque; el otro es el criptoanálisis diferencial .
El descubrimiento se atribuye a Mitsuru Matsui , quien aplicó por primera vez la técnica al cifrado FEAL (Matsui y Yamagishi, 1992). [1] Posteriormente, Matsui publicó un ataque al Estándar de cifrado de datos (DES), lo que finalmente condujo al primer criptoanálisis experimental del cifrado informado en la comunidad abierta (Matsui, 1993; 1994). [2] [3] El ataque al DES no es generalmente práctico, requiriendo 2 47 textos simples conocidos . [3]
Se han sugerido diversas mejoras al ataque, como el uso de múltiples aproximaciones lineales o la incorporación de expresiones no lineales, lo que conduce a un criptoanálisis de partición generalizado . Por lo general, se espera que los nuevos diseños de cifrado presenten evidencia de seguridad contra el criptoanálisis lineal.
El criptoanálisis lineal consta de dos partes. La primera consiste en construir ecuaciones lineales que relacionen el texto simple, el texto cifrado y los bits clave que tengan un sesgo alto; es decir, cuyas probabilidades de cumplirse (en el espacio de todos los valores posibles de sus variables) sean lo más cercanas posibles a 0 o 1. La segunda consiste en utilizar estas ecuaciones lineales junto con pares conocidos de texto simple y texto cifrado para derivar los bits clave.
Para los fines del criptoanálisis lineal, una ecuación lineal expresa la igualdad de dos expresiones que consisten en variables binarias combinadas con la operación exclusiva-o (XOR). Por ejemplo, la siguiente ecuación, de un cifrado hipotético, establece la suma XOR del primer y tercer bit de texto simple (como en el bloque de un cifrado por bloques) y el primer bit de texto cifrado es igual al segundo bit de la clave:
En un cifrado ideal, cualquier ecuación lineal que relacione el texto simple, el texto cifrado y los bits de la clave se cumpliría con una probabilidad de 1/2. Dado que las ecuaciones que se manejan en el criptoanálisis lineal varían en probabilidad, se las denomina con más precisión aproximaciones lineales .
El procedimiento para construir aproximaciones es diferente para cada cifrado. En el tipo más básico de cifrado de bloques, una red de sustitución-permutación , el análisis se concentra principalmente en las cajas S , la única parte no lineal del cifrado (es decir, el funcionamiento de una caja S no se puede codificar en una ecuación lineal). Para cajas S lo suficientemente pequeñas, es posible enumerar todas las ecuaciones lineales posibles que relacionan los bits de entrada y salida de la caja S, calcular sus sesgos y elegir las mejores. Las aproximaciones lineales para las cajas S se deben combinar con otras acciones del cifrado, como la permutación y la mezcla de claves, para llegar a aproximaciones lineales para todo el cifrado. El lema de apilamiento es una herramienta útil para este paso de combinación. También existen técnicas para mejorar iterativamente las aproximaciones lineales (Matsui 1994).
Habiendo obtenido una aproximación lineal de la forma:
Luego podemos aplicar un algoritmo sencillo (el algoritmo 2 de Matsui), utilizando pares de texto simple y texto cifrado conocidos, para adivinar los valores de los bits clave involucrados en la aproximación.
Para cada conjunto de valores de los bits de clave del lado derecho (denominados clave parcial ), cuente cuántas veces se cumple la aproximación en todos los pares de texto simple y texto cifrado conocidos; llame a este recuento T. La clave parcial cuyo T tiene la mayor diferencia absoluta con respecto a la mitad del número de pares de texto simple y texto cifrado se designa como el conjunto de valores más probable para esos bits de clave. Esto se debe a que se supone que la clave parcial correcta hará que la aproximación se cumpla con un sesgo alto. La magnitud del sesgo es significativa aquí, a diferencia de la magnitud de la probabilidad en sí.
Este procedimiento se puede repetir con otras aproximaciones lineales, obteniendo conjeturas sobre los valores de los bits clave, hasta que el número de bits clave desconocidos sea lo suficientemente bajo como para que puedan ser atacados con fuerza bruta .
