💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

Ce papier étudie systématiquement l'existence de structures de différences liées dans les couches linéaires de chiffrements de type AES, démontrant que de telles vulnérabilités sont inévitables pour toutes les matrices non-MDS, toutes les matrices MDS symétriques d'ordre impair et la plupart des matrices circulantes, tout en fournissant une caractérisation complète pour les matrices MDS $3 \times 3$ sur $\mathbb{F}_{2^m}$ .

Auteurs originaux : Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Publié 2026-05-28

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous construisez un coffre-fort haute sécurité (un verrou numérique) pour protéger vos secrets. Pour vous assurer que personne ne puisse le crack, vous utilisez une machine de mélange spéciale appelée Couche Linéaire. Cette machine prend vos données, les brouille et les disperse de sorte qu'un minuscule changement dans l'entrée provoque un changement énorme et chaotique dans la sortie. Cela s'appelle la « diffusion ».

Pendant des décennies, les cryptographes ont utilisé un type spécifique de machine de mélange appelé Matrice MDS car c'est la « référence absolue » pour disperser les choses parfaitement. Ils pensaient : « Si nous utilisons une matrice MDS, nous sommes en sécurité. »

Cependant, cet article révèle un défaut caché dans cette pensée. Il s'avère que même si votre machine de mélange est la « référence absolue » (MDS), elle peut toujours présenter une faiblesse secrète appelée Différentiels Liés.

Voici la décomposition de ce que les auteurs ont découvert, en utilisant des analogies simples :

1. La « Référence Absolue » ne suffit pas

Considérez la propriété MDS comme une garantie que votre machine de mélange étale une goutte d'encre sur toute une page de papier.

L'Ancienne Croyance : Si la machine étale l'encre parfaitement (MDS), elle est sécurisée.
La Nouvelle Découverte : Les auteurs ont prouvé que si une machine ne répand pas l'encre parfaitement (Non-MDS), elle possède garanti une faiblesse secrète.
L'Analogie : Imaginez essayer de cacher un message secret dans une pièce. Si la pièce est petite et encombrée (Non-MDS), un voleur peut facilement trouver un motif pour s'insinuer. Les auteurs ont prouvé que seule une pièce parfaitement spacieuse et organisée (MDS) a une chance d'être sûre. Mais simplement avoir la pièce spacieuse ne garantit pas la sécurité ; la forme de la pièce compte aussi.

2. Le « Piège de la Symétrie »

De nombreuses machines de mélange sont conçues pour être Symétriques, ce qui signifie qu'elles semblent identiques si vous les retournez (comme un papillon). C'est populaire car c'est facile à construire.

La Découverte : Les auteurs ont découvert que si une machine symétrique possède un nombre impair de parties (comme 3x3 ou 5x5), elle est toujours vulnérable.
L'Analogie : Imaginez une piste de danse avec un nombre impair de danseurs. Peu importe comment ils tentent de se mettre par deux, un danseur reste toujours debout au milieu, créant un motif prévisible. Les auteurs ont prouvé que pour toute machine symétrique de taille impaire, il existe toujours un motif « résiduel » qu'un pirate peut exploiter. Peu importe la qualité de sa construction ; le nombre impair la rend intrinsèquement faible contre ce type spécifique d'attaque.

3. Le Problème du « Motif Circulaire »

Un autre design populaire est la Matrice Circulante. Imaginez un tapis roulant où le motif des engrenages se répète en cercle. C'est efficace et rapide.

La Découverte : Les auteurs ont examiné ces machines circulaires et ont trouvé une règle basée sur leur taille (appelée $n$ $n$ ).
- Si la taille du cercle est un multiple de 3 (comme 3, 6, 9) ou un multiple de 4 (comme 4, 8, 12), elle est vulnérable.
- En fait, ils ont prouvé que sauf si la taille est un nombre très spécifique (spécifiquement, des nombres qui ne sont ni à 2 ni à 10 d'un multiple de 12), la machine est vulnérable.
L'Analogie : Pensez à un cadran d'horloge. Si vous essayez de faire le tour de l'horloge par pas de 3 ou de 4, vous finirez par retomber sur les mêmes endroits encore et encore de manière prévisible. Les auteurs ont montré que pour la plupart des designs circulaires, un pirate peut trouver un « raccourci » à travers les engrenages qui contourne la sécurité.

4. La « Recette Parfaite » pour les Machines 3x3

Enfin, les auteurs se sont concentrés sur la taille la plus petite et la plus courante : les matrices 3x3.

Le Problème : Les tentatives précédentes pour trouver une machine 3x3 « sûre » étaient incomplètes. Elles donnaient une recette qui omettait certains ingrédients.
La Solution : Les auteurs ont écrit une recette complète composée de 15 règles spécifiques (équations mathématiques).
L'Analogie : Imaginez faire un gâteau. Les chefs précédents disaient : « N'utilisez pas de sel. » Les auteurs ont dit : « En fait, vous devez éviter le sel, le sucre, la farine, les œufs, le lait et 11 autres ingrédients spécifiques dans des combinaisons exactes. » Ils ont fourni une liste de contrôle de 15 choses à éviter. Si votre machine 3x3 suit les 15 règles, elle est sûre. Si elle en enfreint une seule, elle est vulnérable.
Le Résultat : Ils ont compté combien de machines 3x3 existent et combien sont réellement sûres. Ils ont découvert que les « sûres » sont beaucoup plus rares que nous ne le pensions.

Résumé de la Conclusion

Cet article est comme un inspecteur de sécurité pour les verrous numériques. Ils nous ont dit :

Les machines Non-MDS sont définitivement non sécurisées. (Vous devez utiliser du MDS).
Les machines symétriques de taille impaire sont définitivement non sécurisées. (N'utilisez pas de nombres impairs si vous voulez de la symétrie).
La plupart des machines circulaires sont non sécurisées. (Sauf si la taille est très spécifique).
Pour les machines 3x3, voici la liste de contrôle exacte pour vous assurer de ne pas construire un verrou faible.

Les auteurs n'ont pas inventé un nouveau verrou ; ils nous ont simplement donné un meilleur moyen de vérifier si les verrous que nous construisons déjà ont des fissures cachées.

Résumé Technique : Analyse des Couches Linéaires en Cryptanalyse Différentielle Liée

Énoncé du Problème
Dans les chiffrements par blocs basés sur les réseaux de substitution-permutation (SPN) (par exemple, AES), la couche de diffusion linéaire est généralement mise en œuvre à l'aide de matrices à distance séparatrice maximale (MDS) pour garantir des nombres de branches optimaux et une résistance contre la cryptanalyse différentielle et linéaire classique. Cependant, des travaux récents de Daemen et Rijmen (2009) et de Bardeh et Rijmen (2022) ont révélé que les matrices MDS peuvent toujours présenter des structures « différentielles liées ». Ces structures permettent la construction de caractéristiques différentielles liées qui peuvent être exploitées dans des attaques, telles que l'attaque de récupération de clé sur 7 tours d'AES-128. Bien que des études précédentes aient identifié des différentielles liées dans des cas spécifiques (par exemple, matrices circulantes 4×4, matrices involutrices 3×3), une compréhension systématique des structures de couches linéaires qui évitent ou admettent intrinsèquement ces différentielles reste incomplète. Cet article examine les conditions selon lesquelles les couches linéaires sur des corps finis évitent les différentielles liées, visant à identifier des classes de matrices intrinsèquement résistantes à ce vecteur cryptanalytique spécifique.

Méthodologie
Les auteurs emploient une approche algébrique théorique sur des corps finis de caractéristique 2 ( $\mathbb{F}_{2^m}$ ). La méthodologie comprend :

Définition des Différentielles Liées : Utilisation des définitions de Daemen et Rijmen, où deux différentielles $(u, Mu)$ et $(v, Mv)$ sont « liées » si la paire d'entrées $(u, v)$ et la paire de sorties $(Mu, Mv)$ satisfont la condition $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ pour toutes les coordonnées.
Analyse Structurelle : Investigation de la relation entre les propriétés des matrices (statut MDS, symétrie, structure circulaire) et l'existence de paires de différentielles liées non triviales.
Décomposition Polynomiale : Pour les matrices circulantes, les auteurs transposent les opérations matricielles en multiplication polynomiale dans l'anneau quotient $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ . Ils décomposent le polynôme de transformation en fonction de l'arithmétique modulaire des exposants (modulo 2, 3 et 4) pour construire des paires spécifiques de différences d'entrée qui produisent des différences de sortie liées.
Énumération Cas par Cas : Pour le cas $3 \times 3$ , les auteurs utilisent la décomposition de toute matrice MDS en une forme représentative $M = D_1 M_1 D_2$ (où $D_i$ sont diagonales et $M_1$ est un représentant spécifique). Ils analysent systématiquement tous les motifs possibles de poids de Hamming des triplets de différence d'entrée $(u, v, u \oplus v)$ pour dériver des conditions algébriques nécessaires et suffisantes pour l'absence de différentielles liées.

Contributions et Résultats Clés

Nécessité de la Propriété MDS :
L'article démontre que la propriété MDS est une condition nécessaire pour éviter les différentielles liées. Plus précisément, le Théorème 2 montre que toute matrice non MDS admet au moins une paire non triviale de différentielles liées. Cela restreint strictement l'espace de recherche des couches linéaires résistantes à la classe des matrices MDS.
Vulnérabilité des Matrices Symétriques :
Les auteurs établissent que la symétrie dans les dimensions impaires constitue une vulnérabilité intrinsèque. Le Théorème 4 prouve que toute matrice MDS symétrique d'ordre impair admet des différentielles liées. Ce résultat élimine de larges familles de constructions, y compris les matrices MDS basées sur le type 2 de Cauchy et les matrices circulaires gauches d'ordre impair (Corollaires 2 et 3), car elles sont intrinsèquement symétriques et donc vulnérables.
Vulnérabilité des Matrices Circulaires :
L'article fournit une caractérisation complète pour les matrices circulaires. En analysant les propriétés modulaires de l'ordre de la matrice $n$ , les auteurs prouvent dans le Théorème 5 qu'une matrice MDS circulaire d'ordre $n$ admet des différentielles liées dès que $n \not\equiv \pm 2 \pmod{12}$ . Cela généralise les résultats précédents pour les cas $3 \times 3$ et $4 \times 4$ , identifiant une large classe d'ordres vulnérables.
Caractérisation Complète des Matrices $3 \times 3$ :
En réexaminant le cas $3 \times 3$ , les auteurs dérivent une caractérisation algébrique complète. Le Théorème 7 fournit un ensemble explicite de 15 contraintes polynomiales nécessaires et suffisantes sur les paramètres d'une matrice MDS représentative $3 \times 3$ . Si l'une de ces 15 conditions est remplie, la matrice admet des différentielles liées ; si aucune n'est remplie, la matrice est résistante.
- L'article note que les caractérisations précédentes (par exemple, par Otal et al.) étaient incomplètes.
- En utilisant cette caractérisation, les auteurs calculent le nombre exact de matrices MDS $3 \times 3$ sur divers corps finis ( $\mathbb{F}_{2^m}$ ) qui ne possèdent aucune différentielle liée, démontrant que l'ensemble des matrices résistantes est un sous-ensemble strict de toutes les matrices MDS (Tableau I).

Signification et Revendications
L'article prétend fournir une enquête systématique sur les prérequis structurels pour résister à la cryptanalyse différentielle liée. Sa signification principale réside dans :

Établissement des Limites : Prouver que la propriété MDS seule est insuffisante pour la résistance et que des propriétés structurelles spécifiques (symétrie d'ordre impair, ordres circulaires spécifiques) garantissent la vulnérabilité.
Affinement des Critères de Conception : Offrir un ensemble concret et vérifiable de 15 contraintes algébriques pour les matrices $3 \times 3$ , permettant aux concepteurs de vérifier ou de construire exhaustivement des matrices résistantes dans cette dimension.
Orientation de la Construction Future : En identifiant que les matrices non MDS sont intrinsèquement vulnérables et que de nombreuses constructions symétriques courantes échouent, ce travail oriente les recherches futures vers la construction de matrices MDS qui sont à la fois asymétriques (ou symétriques d'ordre pair) et satisfont les contraintes algébriques spécifiques dérivées pour la résistance.

Les auteurs concluent que, bien que le cas $3 \times 3$ soit entièrement caractérisé, l'extension de ces résultats aux matrices $4 \times 4$ et la construction de matrices MDS légères et efficaces sans différentielles liées restent des défis ouverts. Ils notent également que les cas non résolus pour les matrices circulaires (où $n \equiv \pm 2 \pmod{12}$ ) constituent une conjecture pour une preuve future.