Criptoanálisis lineal

En criptografía, el criptoanálisis lineal es una forma general de criptoanálisis basada en encontrar 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 los cifrados en bloque; el otro es el criptoanálisis diferencial.

El descubrimiento se atribuye a Mitsuru Matsui, quien fue el primero en aplicar la técnica al cifrado FEAL (Matsui y Yamagishi, 1992). Posteriormente, Matsui publicó un ataque al Estándar de cifrado de datos (DES), lo que eventualmente condujo al primer criptoanálisis experimental del cifrado informado en la comunidad abierta (Matsui, 1993; 1994). El ataque a DES generalmente no es práctico y requiere 2⁴⁷ textos sin formato conocidos.

Se ha sugerido una variedad de refinamientos para el ataque, incluido el uso de aproximaciones lineales múltiples o la incorporación de expresiones no lineales, lo que lleva a un criptoanálisis de partición generalizado. Por lo general, se espera evidencia de seguridad contra el criptoanálisis lineal de los nuevos diseños de cifrado.

Resumen

Hay dos partes en el criptoanálisis lineal. El primero es construir ecuaciones lineales que relacionen texto sin formato, texto cifrado y bits de clave que tengan un alto sesgo; es decir, cuyas probabilidades de retención (en el espacio de todos los valores posibles de sus variables) estén lo más cerca posible de 0 o 1. La segunda es usar estas ecuaciones lineales junto con pares conocidos de texto simple-texto cifrado para derivar bits clave.

Construcción de ecuaciones lineales

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 sin formato (como en un bloque de cifrado de bloque) y el primer bit de texto cifrado es igual al segundo bit de la clave:

${displaystyle P_{1}oplus P_{3}oplus C_{1}=K_{2}$

En un cifrado ideal, cualquier ecuación lineal que relacione texto sin formato, texto cifrado y bits clave se mantendría con una probabilidad de 1/2. Dado que las ecuaciones tratadas en el criptoanálisis lineal variarán en probabilidad, se denominan con mayor 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, la operación 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 los mejores. Luego, las aproximaciones lineales para S-boxes deben combinarse con otras acciones del cifrado, como la permutación y la combinación de claves, para llegar a aproximaciones lineales para todo el cifrado. El lema de acumulación es una herramienta útil para este paso de combinación. También existen técnicas para mejorar iterativamente las aproximaciones lineales (Matsui 1994).

Derivar bits clave

Habiendo obtenido una aproximación lineal de la forma:

${displaystyle P_{i_{1}oplus P_{i_{2}oplus cdots oplus C_{j_{1}oplus C_{j_{2}oplus cdots =K_{k_{1}oplus K_{k_{2}oplus cdots }$

A continuación, podemos aplicar un algoritmo sencillo (Algoritmo 2 de Matsui), usando pares conocidos de texto sin formato y texto cifrado, para adivinar los valores de los bits clave involucrados en la aproximación.

Para cada conjunto de valores de los bits clave en el lado derecho (denominado clave parcial), cuente cuántas veces la aproximación se cumple en todos los pares conocidos de texto sin formato-texto cifrado.; llame a este conteo T. La clave parcial cuya T tiene la mayor diferencia absoluta de la mitad del número de pares de texto sin formato-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 mantenga con un alto sesgo. La magnitud del sesgo es significativa aquí, a diferencia de la magnitud de la probabilidad misma.

Este procedimiento se puede repetir con otras aproximaciones lineales, obteniendo conjeturas en los valores de los bits de clave, hasta que el número de bits de clave desconocidos sea lo suficientemente bajo como para que puedan ser atacados con fuerza bruta.