De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

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 bloques y cifrados de flujo . El criptoanálisis lineal es uno de los dos ataques más utilizados a los cifrados en bloque; el otro es el criptoanálisis diferencial .

El descubrimiento se atribuye a Mitsuru Matsui , quien primero aplicó la técnica al cifrado FEAL (Matsui y Yamagishi, 1992). [1] Posteriormente, Matsui publicó un ataque al Estándar de cifrado de datos (DES), que finalmente condujo al primer criptoanálisis experimental del cifrado informado en la comunidad abierta (Matsui, 1993; 1994). [2] [3] El ataque a DES no es generalmente práctico, requiriendo 2 47 textos sin formato conocidos . [3]

Se ha sugerido una variedad de mejoras al 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 particiones generalizado . Por lo general, se espera evidencia de seguridad contra el criptoanálisis lineal de los nuevos diseños de cifrado.

Resumen [ editar ]

El criptoanálisis lineal consta de dos partes. La primera es construir ecuaciones lineales que relacionen texto plano, texto cifrado y bits 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. El segundo es usar estas ecuaciones lineales junto con pares de texto plano-texto cifrado conocidos para derivar bits clave.

Construir ecuaciones lineales [ editar ]

A los efectos del criptoanálisis lineal, una ecuación lineal expresa la igualdad de dos expresiones que constan de variables binarias combinadas con la operación exclusiva o (XOR). Por ejemplo, la siguiente ecuación, a partir de un cifrado hipotético, establece la suma XOR del primer y tercer bits 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:

En un cifrado ideal, cualquier ecuación lineal que relacione texto plano, texto cifrado y bits de clave se mantendría con probabilidad 1/2. Dado que las ecuaciones tratadas en el criptoanálisis lineal variarán en probabilidad, se las conoce con mayor precisión como aproximaciones lineales .

El procedimiento para construir aproximaciones es diferente para cada cifra. 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 las mejores. Las aproximaciones lineales para cajas S deben combinarse 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 acumulativoes una herramienta útil para este paso de combinación. También existen técnicas para mejorar iterativamente las aproximaciones lineales (Matsui 1994).

Derivación de bits clave [ editar ]

Habiendo obtenido una aproximación lineal de la forma:

luego podemos aplicar un algoritmo sencillo (Algoritmo 2 de Matsui), utilizando pares de texto claro-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 en el lado derecho (denominado clave parcial ), cuente cuántas veces la aproximación es verdadera en todos los pares de texto plano-texto cifrado conocidos; llamar a este número de camiseta . 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 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 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 .

Ver también [ editar ]

Referencias [ editar ]

  1. ^ Matsui, M. & Yamagishi, A. "Un nuevo método para el ataque de texto plano conocido del cifrado FEAL". Avances en Criptología - EUROCRYPT 1992 .
  2. ^ Matsui, M. "El primer criptoanálisis experimental del estándar de cifrado de datos". Avances en criptología - CRYPTO 1994 .
  3. ^ a b Matsui, M. "Método de criptoanálisis lineal para cifrado DES" (PDF) . Avances en Criptología - EUROCRYPT 1993 . Archivado desde el original (PDF) el 26 de septiembre de 2007 . Consultado el 22 de febrero de 2007 .

Enlaces externos [ editar ]