Saltar al contenido
Volver a los resultados

Criptoanálisis Lineal

Propuesto por
Mitsuru Matsui
Año
1993
Tipo
linear approximation attack
Familia
Cryptanalytic technique

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

El criptoanálisis lineal es un ataque de texto plano conocido que explota aproximaciones lineales de las transformaciones no lineales de un cifrador para recuperar bits de clave secreta.

Introducido por Mitsuru Matsui en 1993, el criptoanálisis lineal proporciona ataques prácticos contra cifradores como DES con una complejidad computacional menor que la fuerza bruta. La técnica analiza sesgos estadísticos en cómo las combinaciones lineales de bits de texto plano y texto cifrado se relacionan con los bits de clave, permitiendo la recuperación de la clave con requisitos de datos reducidos.

La intuición detrás del método

El criptoanálisis lineal encuentra ecuaciones lineales que relacionan bits de texto plano, bits de texto cifrado y bits de clave. Debido a la mezcla no perfecta en las rondas del cifrador, estas ecuaciones lineales se cumplen con una probabilidad ligeramente superior a la aleatoria. Al recopilar muchos pares de texto plano-texto cifrado y observar qué valores de clave hacen que estas ecuaciones se cumplan con mayor frecuencia, el atacante puede acotar la clave correcta.

Historia

El criptoanálisis lineal fue introducido por Matsui en 1993 como un ataque de texto plano conocido contra DES. En 1994, Matsui demostró el primer criptoanálisis experimental del estándar DES utilizando criptoanálisis lineal, recuperando una clave con 2^43 textos planos conocidos. Este avance demostró ataques prácticos contra un estándar desplegado e influyó en el desarrollo de AES con límites de resistencia probados.

Cuándo usarlo

El criptoanálisis lineal se utiliza en la investigación de criptoanálisis y la evaluación del diseño de cifradores. Guía a los diseñadores de cifradores en la selección de S-boxes y transformaciones que resistan aproximaciones lineales. Los cifradores modernos se diseñan con límites probados en la fuerza de las aproximaciones lineales.

Limitaciones y consideraciones

  • Los cifradores modernos (AES) están cuidadosamente diseñados para resistir el criptoanálisis lineal con límites demostrables
  • Requiere pares de texto plano-texto cifrado conocidos, que pueden no estar disponibles en todos los escenarios
  • Los requisitos computacionales y de datos pueden exceder la viabilidad práctica para cifradores bien diseñados
  • Descubrir aproximaciones lineales fuertes para cifradores modernos es extremadamente difícil

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Ataque práctico contra DES que requiere 2^43 pares de texto plano-texto cifrado y 2^39 operaciones
  • Marco matemático bien formalizado (lema de apilamiento) para analizar sesgos de aproximación
  • Complementa el criptoanálisis diferencial, encontrando debilidades que el análisis diferencial podría pasar por alto
  • Moldea los requisitos de diseño de cifradores para la selección de S-box y la transformación de ronda

Aplicaciones

  • Criptoanálisis de cifradores de bloque evaluando propiedades de seguridad en investigación y estandarización
  • Diseño de cifradores y selección de S-box para asegurar límites adecuados de aproximación lineal
  • Validación de estándares criptográficos (NIST, ETSI) que requieren análisis de resistencia lineal
  • Evaluación de cifradores heredados para decisiones de retiro y reemplazo

Cómo funciona

Cómo funciona

1

Encontrar aproximaciones lineales: relaciones lineales entre bits de texto plano, bits de texto cifrado y bits de clave que se cumplen con una probabilidad significativamente diferente de 0.5.

2

Estimar el sesgo (desviación de 0.5) de cada aproximación lineal utilizando análisis estadístico de las transformaciones de ronda.

3

Para valores de clave candidatos, contar con qué frecuencia se cumple la aproximación lineal en pares de texto plano-texto cifrado conocidos. La clave correcta hace que la aproximación se cumpla con mayor frecuencia.

4

Verificar los bits de clave recuperados descifrando el texto cifrado y comprobando su corrección.

Errores comunes

  • Asumiendo que todas las aproximaciones lineales son explotables; las aproximaciones débiles proporcionan una ventaja mínima
  • Subestimación de la dificultad práctica del ataque cuando los requisitos teóricos de datos parecen razonables
  • Negligencia de la interacción entre las propiedades lineales y diferenciales en el análisis de cifradores

Preguntas frecuentes

¿Qué es el lema de apilamiento?

El lema de apilamiento proporciona un método para calcular el sesgo de aproximaciones lineales a través de múltiples rondas combinando los sesgos de aproximaciones de ronda individuales. Es fundamental para el criptoanálisis lineal.

¿Cómo resiste AES al criptoanálisis lineal?

AES utiliza S-boxes elegidas para minimizar la probabilidad máxima de aproximación lineal y una capa de difusión que asegura la rápida difusión de los sesgos lineales a través de las rondas. Los límites probados garantizan que no existan aproximaciones lineales prácticas.

¿Cuál es la diferencia entre criptoanálisis lineal y diferencial?

El análisis diferencial estudia las diferencias de entrada-salida, mientras que el análisis lineal estudia las aproximaciones lineales (XOR de bits de texto plano y texto cifrado). Ambos explotan debilidades estructurales en los cifradores.

¿Puede el criptoanálisis lineal romper cifradores modernos?

No prácticamente. Los cifradores modernos como AES tienen límites demostrables en las aproximaciones lineales que hacen que los ataques sean computacionalmente inviables.

¿Cómo evalúo la resistencia lineal en el diseño de mi cifrador?

Analizar las tablas de aproximación lineal de las S-boxes y calcular el sesgo máximo a través de las rondas utilizando el lema de apilamiento. Asegurar que el sesgo máximo sea insignificante en todas las aproximaciones lineales posibles.

Métodos relacionados

Fuentes

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    Abrir referencia DOI
    Copiado.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    Abrir referencia DOI
    Copiado.