💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

Este artículo investiga sistemáticamente la existencia de estructuras diferenciales relacionadas en las capas lineales de cifradores tipo AES, demostrando que tales vulnerabilidades son inevitables para todas las matrices no MDS, todas las matrices MDS simétricas de orden impar y la mayoría de las matrices circulantes, al tiempo que proporciona una caracterización completa para las matrices MDS de $3 \times 3$ sobre $\mathbb{F}_{2^m}$ .

Autores originales: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Publicado 2026-05-28

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás construyendo una bóveda de alta seguridad (un candado digital) para proteger tus secretos. Para asegurarte de que nadie pueda descifrarla, utilizas una máquina de mezcla especial llamada Capa Lineal. Esta máquina toma tus datos, los baraja y los dispersa de modo que un pequeño cambio en la entrada provoque un cambio enorme y caótico en la salida. Esto se llama "difusión".

Durante décadas, los criptógrafos han utilizado un tipo específico de máquina de mezcla llamada Matriz MDS porque es el "estándar de oro" para dispersar las cosas perfectamente. Pensaban: "Si usamos una matriz MDS, estamos a salvo".

Sin embargo, este artículo revela un defecto oculto en ese razonamiento. Resulta que, incluso si tu máquina de mezcla es el "estándar de oro" (MDS), podría tener aún una debilidad secreta llamada Diferenciales Relacionados.

Aquí está el desglose de lo que descubrieron los autores, usando analogías sencillas:

1. El "Estándar de Oro" no es suficiente

Piensa en la propiedad MDS como una garantía de que tu máquina de mezcla dispersa una gota de tinta por toda una página de papel.

La antigua creencia: Si la máquina dispersa la tinta perfectamente (MDS), es segura.
El nuevo descubrimiento: Los autores demostraron que si una máquina no dispersa la tinta perfectamente (No-MDS), está garantizado que tiene una debilidad secreta.
La analogía: Imagina intentar ocultar un mensaje secreto en una habitación. Si la habitación es pequeña y desordenada (No-MDS), un ladrón puede encontrar fácilmente un patrón para colarse. Los autores demostraron que solo una habitación perfectamente espaciosa y organizada (MDS) tiene posibilidades de ser segura. Pero simplemente tener la habitación espaciosa no garantiza la seguridad; la forma de la habitación también importa.

2. La "Trampa de la Simetría"

Muchas máquinas de mezcla están diseñadas para ser Simétricas, lo que significa que se ven iguales si las volteas (como una mariposa). Esto es popular porque es fácil de construir.

El descubrimiento: Los autores encontraron que si una máquina simétrica tiene un número impar de partes (como 3x3 o 5x5), es siempre vulnerable.
La analogía: Imagina una pista de baile con un número impar de bailarines. No importa cómo intenten emparejarse, siempre queda un bailarín de pie en el medio, creando un patrón predecible. Los autores demostraron que para cualquier máquina simétrica de tamaño impar, siempre hay un patrón "sobrante" que un hacker puede explotar. No importa cuán bien la hayas construido; el número impar la hace inherentemente débil contra este tipo específico de ataque.

3. El problema del "Patrón Circular"

Otro diseño popular es la Matriz Circulante. Imagina una cinta transportadora donde el patrón de engranajes se repite en círculo. Esto es eficiente y rápido.

El descubrimiento: Los autores examinaron estas máquinas circulares y encontraron una regla basada en su tamaño (llamado $n$ $n$ ).
- Si el tamaño del círculo es un múltiplo de 3 (como 3, 6, 9) o un múltiplo de 4 (como 4, 8, 12), es vulnerable.
- De hecho, demostraron que a menos que el tamaño sea un número muy específico (específicamente, números que no estén a 2 o a 10 unidades de distancia de un múltiplo de 12), la máquina es vulnerable.
La analogía: Piensa en la esfera de un reloj. Si intentas caminar alrededor del reloj dando pasos de 3 o de 4, eventualmente darás vueltas sobre los mismos puntos una y otra vez de una manera predecible. Los autores mostraron que para la mayoría de los diseños circulares, un hacker puede encontrar un "atajo" a través de los engranajes que elude la seguridad.

4. La "Receta Perfecta" para máquinas 3x3

Finalmente, los autores se centraron en el tamaño más pequeño y común: Matrices 3x3.

El problema: Los intentos anteriores de encontrar una máquina 3x3 "segura" estaban incompletos. Ofrecían una receta que omitía algunos ingredientes.
La solución: Los autores escribieron una receta completa que consiste en 15 reglas específicas (ecuaciones matemáticas).
La analogía: Imagina hornear un pastel. Los chefs anteriores decían: "No uses sal". Los autores dijeron: "En realidad, debes evitar la sal, el azúcar, la harina, los huevos, la leche y 11 otros ingredientes específicos en combinaciones exactas". Proporcionaron una lista de verificación de 15 cosas que evitar. Si tu máquina 3x3 sigue las 15 reglas, es segura. Si rompe incluso una, es vulnerable.
El resultado: Contaron cuántas máquinas 3x3 existen y cuántas son realmente seguras. Descubrieron que las "seguras" son mucho más raras de lo que pensábamos.

Resumen de la conclusión

Este artículo es como un inspector de seguridad para candados digitales. Nos dijeron:

Las máquinas No-MDS son definitivamente inseguras. (Debes usar MDS).
Las máquinas Simétricas de tamaño impar son definitivamente inseguras. (No uses números impares si quieres simetría).
La mayoría de las máquinas Circulares son inseguras. (A menos que el tamaño sea muy específico).
Para máquinas 3x3, aquí está la lista de verificación exacta para asegurarte de que no estás construyendo un candado débil.

Los autores no inventaron un candado nuevo; simplemente nos dieron una mejor manera de verificar si los candados que ya estamos construyendo tienen grietas ocultas.

Resumen Técnico: Análisis de Capas Lineales en Criptanálisis Diferencial Relacionado

Enunciado del Problema
En los cifrados de bloque basados en SPN (por ejemplo, AES), la capa de difusión lineal se instancia típicamente utilizando matrices de Máxima Distancia Separable (MDS) para garantizar números de rama óptimos y resistencia contra el criptanálisis diferencial y lineal clásico. Sin embargo, trabajos recientes de Daemen y Rijmen (2009) y Bardeh y Rijmen (2022) revelaron que las matrices MDS pueden exhibir estructuras de "diferencial relacionado". Estas estructuras permiten la construcción de características diferenciales relacionadas que pueden ser explotadas en ataques, como el ataque de recuperación de clave de 7 rondas sobre AES-128. Aunque estudios anteriores han identificado diferenciales relacionados en instancias específicas (por ejemplo, matrices circulares de 4×4, matrices involutorias de 3×3), una comprensión sistemática de qué estructuras de capas lineales evitan o admiten inherentemente estos diferenciales permanece incompleta. Este artículo investiga las condiciones bajo las cuales las capas lineales sobre cuerpos finitos evitan los diferenciales relacionados, con el objetivo de identificar clases de matrices que sean inherentemente resistentes a este vector de criptanálisis específico.

Metodología
Los autores emplean un enfoque algebraico teórico sobre cuerpos finitos de característica 2 ( $\mathbb{F}_{2^m}$ ). La metodología implica:

Definición de Diferenciales Relacionados: Utilizando las definiciones de Daemen y Rijmen, donde dos diferenciales $(u, Mu) $y$ (v, Mv)$ son "relacionados" si el par de entrada $(u, v)$ y el par de salida $(Mu, Mv)$ satisfacen la condición $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ para todas las coordenadas.
Análisis Estructural: Investigar la relación entre las propiedades de la matriz (estado MDS, simetría, estructura circular) y la existencia de pares diferenciales relacionados no triviales.
Descomposición Polinómica: Para matrices circulares, los autores mapean las operaciones de la matriz a la multiplicación de polinomios en el anillo cociente $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ . Descomponen el polinomio de transformación basándose en la aritmética modular de los exponentes (módulo 2, 3 y 4) para construir pares específicos de diferencias de entrada que produzcan diferencias de salida relacionadas.
Enumeración Caso por Caso: Para el caso $3 \times 3$ , los autores utilizan la descomposición de cualquier matriz MDS en una forma representativa $M = D_1 M_1 D_2$ (donde $D_i$ son diagonales y $M_1$ es un representante específico). Analizan sistemáticamente todos los patrones posibles de peso de Hamming de las ternas de diferencias de entrada $(u, v, u \oplus v)$ para derivar condiciones algebraicas necesarias y suficientes para la ausencia de diferenciales relacionados.

Contribuciones y Resultados Clave

Necesidad de la Propiedad MDS:
El artículo demuestra que la propiedad MDS es una condición necesaria para evitar los diferenciales relacionados. Específicamente, el Teorema 2 demuestra que toda matriz no MDS admite al menos un par no trivial de diferenciales relacionados. Esto reduce el espacio de búsqueda para capas lineales resistentes estrictamente a la clase de matrices MDS.
Vulnerabilidad de las Matrices Simétricas:
Los autores establecen que la simetría en dimensiones impares es una vulnerabilidad inherente. El Teorema 4 demuestra que toda matriz MDS simétrica de orden impar admite diferenciales relacionados. Este resultado descarta amplias familias de construcciones, incluidas las matrices MDS basadas en Cauchy de Tipo 2 y las matrices circulares a la izquierda de orden impar (Corolarios 2 y 3), ya que son inherentemente simétricas y, por tanto, vulnerables.
Vulnerabilidad de las Matrices Circulares:
El artículo proporciona una caracterización completa para las matrices circulares. Mediante el análisis de las propiedades modulares del orden de la matriz $n$ , los autores prueban en el Teorema 5 que una matriz MDS circular de orden $n$ admite diferenciales relacionados siempre que $n \not\equiv \pm 2 \pmod{12}$ . Esto generaliza hallazgos anteriores para los casos de $3 \times 3$ y $4 \times 4$ , identificando una amplia clase de órdenes vulnerables.
Caracterización Completa de Matrices $3 \times 3$ :
Revisando el caso $3 \times 3$ , los autores derivan una caracterización algebraica completa. El Teorema 7 proporciona un conjunto explícito de 15 restricciones polinómicas necesarias y suficientes sobre los parámetros de una matriz MDS representativa $3 \times 3$ . Si se cumple alguna de estas 15 condiciones, la matriz admite diferenciales relacionados; si ninguna se cumple, la matriz es resistente.
- El artículo señala que las caracterizaciones anteriores (por ejemplo, de Otal et al.) eran incompletas.
- Utilizando esta caracterización, los autores calculan el número exacto de matrices MDS $3 \times 3$ sobre varios cuerpos finitos ( $\mathbb{F}_{2^m}$ ) que no poseen diferenciales relacionados, demostrando que el conjunto de matrices resistentes es un subconjunto estricto de todas las matrices MDS (Tabla I).

Significado y Afirmaciones
El artículo afirma proporcionar una investigación sistemática sobre los prerrequisitos estructurales para resistir el criptanálisis diferencial relacionado. Su significado principal radica en:

Establecimiento de Límites: Demostrar que la propiedad MDS por sí sola es insuficiente para la resistencia y que propiedades estructurales específicas (simetría de orden impar, órdenes circulares específicos) garantizan la vulnerabilidad.
Refinamiento de Criterios de Diseño: Ofrecer un conjunto concreto y verificable de 15 restricciones algebraicas para matrices $3 \times 3$ , permitiendo a los diseñadores verificar exhaustivamente o construir matrices resistentes en esta dimensión.
Orientación de la Construcción Futura: Al identificar que las matrices no MDS son inherentemente vulnerables y que muchas construcciones simétricas comunes fallan, el trabajo dirige la investigación futura hacia la construcción de matrices MDS que sean tanto asimétricas (o simétricas de orden par) como que cumplan las restricciones algebraicas específicas derivadas para la resistencia.

Los autores concluyen que, aunque el caso $3 \times 3$ está completamente caracterizado, extender estos resultados a matrices $4 \times 4$ y construir matrices MDS ligeras y eficientes sin diferenciales relacionados siguen siendo desafíos abiertos. También señalan que los casos no resueltos para matrices circulares (donde $n \equiv \pm 2 \pmod{12}$ ) presentan una conjetura para una futura demostración.