🔢 mathematics

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

Cet article présente une attaque de récupération de clé en temps polynomial qui casse tous les ensembles de paramètres proposés du schéma de chiffrement Enhanced Gabidulin Matrix Codes (EGMC) en combinant des techniques combinatoires et algébriques pour récupérer une clé secrète équivalente, réduisant ainsi le niveau de sécurité de 128 bits revendiqué à seulement 35 bits.

Auteurs originaux : Thai Hung Le

Publié 2026-08-05

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Thai Hung Le

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 l'internet comme une ville géante et bouillonnante où tout le monde essaie d'envoyer des messages secrets. Pour garder ces messages à l'abri des regards indiscrets, nous utilisons des verrous numériques appelés chiffrement. Pendant longtemps, les scientifiques ont construit ces verrous en utilisant des énigmes mathématiques complexes qui sont faciles à créer mais incroyablement difficiles à résoudre sans la clé. Récemment, un nouveau type de verrou a été proposé utilisant un genre spécial de mathématiques impliquant des grilles de nombres et le « rang » (qui est juste une façon sophistiquée de mesurer la quantité réelle d'informations contenues dans la grille). Les créateurs de ce nouveau verrou pensaient avoir ajouté une couche de « bruit » — comme des parasites sur une radio — pour cacher la véritable forme du verrou, le faisant ressembler à un désordre aléatoire pour quiconque tenterait de l'ouvrir. Ils affirmaient que ce nouveau design était si sûr que même un ordinateur quantique super rapide ne pourrait pas le casser, et ils promettaient qu'il serait minuscule et efficace, parfait pour l'avenir de la communication sécurisée.

Cependant, tout comme le tour d'un magicien qui repose sur un jeu de mains spécifique, ce nouveau verrou possédait une faille cachée. Un chercheur nommé Thai Hung Le a découvert que le « bruit » ne cachait pas la forme secrète aussi bien que tout le monde le pensait. En utilisant un mélange astucieux de devinettes et de travail de détective algébrique, le chercheur a trouvé un moyen de retirer les couches de parasites pour révéler la structure originale et cachée en dessous. C'est comme si quelqu'un avait construit un château de cartes avec un plan secret, l'avait recouvert de brouillard, puis s'était rendu compte que si l'on regardait simplement le brouillard sous le bon angle, le plan était encore faiblement visible. Cette découverte est importante car elle signifie que les nouveaux verrous ne sont pas aussi sûrs qu'annoncé, et que les personnes qui ont conçu les plans doivent repenser leurs modèles avant de commencer à les utiliser pour protéger nos données.

La grande découverte de l'article

Dans cet article, Thai Hung Le présente un nouveau moyen de briser les schémas de chiffrement « Enhanced Gabidulin Matrix Code » (EGMC). Ces schémas ont été introduits récemment comme un moyen de créer des clés de chiffrement très petites et efficaces qui pourraient survivre aux attaques des futurs ordinateurs quantiques. La sécurité de ces schémas reposait sur l'idée que si vous preniez une grille de nombres spéciale et structurée et que vous y ajoutiez des lignes et des colonnes aléatoires (le « bruit »), il deviendrait impossible de faire la différence entre le code réel et un désordre complètement aléatoire.

L'auteur montre que cette hypothèse est fausse. Au lieu d'essayer de forcer chaque possibilité de suppression du bruit (ce qui prendrait une éternité), l'article introduit une attaque « hybride ». Imaginez que vous essayiez de trouver un motif spécifique dans une immense mosaïque éparpillée. L'ancienne méthode consistait à deviner la position de chaque carreau. Cette nouvelle méthode est plus intelligente : elle devine la position d'une seule ligne de carreaux, puis utilise les mathématiques pour comprendre instantanément où les autres carreaux doivent se trouver.

L'article détaille deux manières principales de procéder :

Deviner les colonnes : l'attaquant devine comment les colonnes de la grille ont été mélangées, puis utilise l'algèbre pour résoudre la manière dont les lignes ont été mélangées.
Deviner les lignes : l'attaquant devine comment les lignes de la grille ont été mélangées, puis résout le problème pour les colonnes.

Une fois que l'attaquant a compris le mélange, il peut retirer le bruit aléatoire et révéler la structure originale cachée. L'article prouve que cette structure est un « code de Gabidulin », qui est un type d'énigme mathématique qui est en fait assez facile à résoudre une fois que l'on connaît le motif secret.

Ce que l'article brise réellement

L'auteur ne trouve pas seulement une petite fissure ; il brise toute la fenêtre. L'article démontre que cette attaque fonctionne contre les 16 ensembles de paramètres proposés pour les schémas de chiffrement EGMC. Cela signifie que chaque version du verrou qui a été suggérée pour une utilisation est désormais considérée comme brisée.

Pour vous donner une idée de l'efficacité de cette attaque, l'article examine un ensemble spécifique de nombres qui était censé offrir une sécurité de 128 bits (un niveau de sécurité standard). L'auteur montre que son attaque réduit ce niveau de sécurité à seulement 35 bits. Dans le monde du chiffrement, c'est comme passer d'un coffre-fort avec une combinaison de un million de chiffres à un verrou qu'un enfant pourrait crocheter en quelques secondes.

L'article fournit un exemple concret de cette puissance : en utilisant leur méthode, les chercheurs ont pu récupérer la clé secrète pour ce niveau de sécurité de 128 bits en moins de 10 minutes. Ce n'était pas seulement une idée théorique ; ils ont réellement construit un programme informatique pour le faire.

Ce que l'article écarte

Il est important de noter ce que cet article ne considère pas comme fonctionnant. L'auteur explique que les tentatives précédentes pour briser ces codes reposaient sur des méthodes « combinatoires », qui consistent à deviner simultanément les mélanges de lignes et de colonnes. L'article soutient que cette ancienne méthode est trop lente et inefficace par rapport à leur nouvelle approche « hybride ».

De plus, l'article soutient l'idée que le simple fait d'agrandir les paramètres (en ajoutant plus de bruit) ne réglera pas le problème dans tous les cas. L'auteur montre que pour certains types de ces codes — spécifiquement lorsque l'un des facteurs de bruit (soit le nombre de lignes supplémentaires, soit le nombre de colonnes supplémentaires) est nul — l'attaque devient si rapide qu'elle s'exécute en « temps polynomial ». Cela signifie que, peu importe l'augmentation de la taille du verrou dans ces cas spécifiques, l'attaque sera toujours assez rapide pour le briser. La seule façon de potentiellement réparer cela, suggère l'article, serait de changer la conception fondamentale afin que les deux facteurs de bruit soient non nuls et suffisamment grands pour arrêter l'attaque, mais l'auteur prévient que cela pourrait rendre les clés et les messages trop volumineux pour être utiles.

À quel point sont-ils sûrs ?

L'article est très confiant dans ses résultats. L'auteur n'a pas seulement fait des suppositions ; il a fourni une preuve mathématique complète du fonctionnement de son attaque et l'a étayée par une implémentation informatique fonctionnelle. Il affirme explicitement que son attaque brise toutes les versions proposées du schéma. Il compare également ses résultats à des attaques précédentes, montant que sa méthode est nettement plus rapide et plus puissante. L'article conclut que les schémas de chiffrement EGMC ne sont plus sûrs pour une utilisation et que la communauté de la sécurité doit passer à d'autres conceptions.

Résumé technique : Rupture des schémas de chiffrement de type Gabidulin MinRank ACDGV sur les codes matriciels

Énoncé du problème
L'article traite de la sécurité des codes matriciels Gabidulin améliorés (EGMC), un schéma de masquage introduit par Aragon et al. à Asiacrypt 2024. L'EGMC a été conçu pour dissimuler la structure algébrique des codes matriciels de Gabidulin, permettant des schémas de chiffrement compacts de type McEliece et Niederreiter avec de petits textes chiffrés (par exemple, 65 octets pour une sécurité de 128 bits). La sécurité de l'EGMC repose sur le problème de l'indistinguabilité décisionnelle EGMC : l'hypothèse qu'un code EGMC masqué est informatiquement indiscernable d'un code matriciel aléatoire. Une cryptanalyse précédente, spécifiquement une attaque par noyau basée sur MinRank par Porwal et al. (Eurocrypt 2026), a démontré des attaques en temps exponentiel qui ont brisé un sous-ensemble des ensembles de paramètres proposés mais en ont laissé d'autres sécurisés. L'auteur examine si la construction EGMC conserve suffisamment de structure cachée pour être brisée plus efficacement.

Méthodologie
L'auteur propose un nouveau discriminateur « hybride » et une attaque de récupération de clé subséquente qui combine le devinage combinatoire avec la résolution algébrique. Contra{irement} aux précédents discriminateurs qui effectuent une recherche par force brute sur les matrices de compression de lignes et de colonnes, cette attaque ne devine qu'une seule matrice de compression et résout l'autre à l'aide de techniques algébriques.

L'attaque opère dans deux directions principales :

Guess- $V$ -solve- $U$ (Deviner $V$ , résoudre $U$ ) : L'attaquant devine une matrice de compression de colonnes $V$ et résout algébriquement une matrice de compression de lignes $U$ .
Guess- $U$ -solve- $V$ (Deviner $U$ , résoudre $V$ ) : L'attaquant devine une matrice de compression de lignes $U$ et résout une matrice de compression de colonnes $V$ .

Modélisation et résolution algébriques
Une fois qu'une matrice de compression valide est devinée, le code public est compressé en un sous-espace équivalent à un code de Gabidulin court (spécifiquement un code $[k+1, k]$ ). L'auteur modélise la condition selon laquelle ce code compressé doit être une hyperplan $F_{q^m}$ annihilée par un vecteur spécifique. Cela conduit à un système d'équations bilinéaires qui, après linéarisation, produit un système linéaire homogène sur le corps d'extension $F_{q^m}$ .

Le cœur de l'attaque consiste à trouver une solution de rang 1 au sein du noyau de ce système linéaire. L'auteur observe que le noyau admet une base dont les entrées appartiennent au corps de base $F_q$ . Par conséquent, le problème se réduit à trouver une combinaison linéaire de ces matrices de base qui résulte en une matrice de rang 1. Cela est formulé comme un système d'équations quadratiques (annihilation des mineurs $2 \times 2$ ).

Pour résoudre ce système quadratique efficacement, l'auteur emploie la méthode des valeurs propres (méthode de l'autovalor de Stickelberger) pour les systèmes polynomiaux de dimension zéro. Ils exploitent la stabilité de Frobenius du noyau pour effectuer les calculs sur le corps plus petit $F_q$ plutôt que sur $F_{q^m}$ , réduisant ainsi considérablement la complexité. Une conjecture clé (Conjecture 1) postule que l'algèbre quotient de l'idéal généré par les mineurs a une dimension égale à $m$ , garantissant que le système est de dimension zéro et soluble via les valeurs propres.

Principales contributions

Discriminateur hybride : L'article introduit un discriminateur qui évite le coût de la force brute complète des méthodes précédentes en résolvant algébriquement une matrice de compression.
Récupération de clé en temps polynomial : L'auteur démontre que si l'un des facteurs d'appendice $\ell_1$ ou $\ell_2$ est nul, l'attaque devient polynomiale. En effet, le facteur de devinage exponentiel disparaît, ne laissant que l'étape de résolution algébrique, qui récupère la matrice de compression cachée efficacement.
Extension de code : Après avoir récupéré un code de Gabidulin ponctué (court), l'auteur fournit un algorithme en temps polynomial pour étendre ce code vers un code de Gabidulin secret complet de longueur équivalente en exploitant la structure $q$ -Frobenius des codes de Gabidulin.
Déchiffrement universel : La clé secrète équivalente récupérée (trappe) permet le déchiffrement des textes chiffrés EGMC-McEliece et EGMC-Niederreiter.

Résultats
L'attaque brise les 16 ensembles de paramètres proposés pour les schémas de chiffrement EGMC-Niederreiter.

Réduction de sécurité : Pour l'ensemble de paramètres ciblant une sécurité de 128 bits avec les paramètres $(2, 17, 37, 4, 0)$ , l'attaque réduit le niveau de sécurité revendiqué de 186 bits à environ 35 bits.
Efficacité : Dans l'implémentation de l'auteur, la clé secrète équivalente pour l'ensemble de paramètres de 128 bits est récupérée en moins de 10 minutes.
Comparaison : L'attaque surpasse largement les meilleures attaques précédentes (combinatoires et basées sur MinRank), comme le montre le Tableau 1 de l'article.

Signification et affirmations
L'article affirme que la construction EGMC, telle que proposée, ne parvient pas à fournir une sécurité post-quantique pour les familles de paramètres spécifiques où $\ell_1 = 0$ ou $\ell_2 = 0$ . L'auteur soutient que le simple fait d'augmenter les paramètres sans changer la construction de masquage ne restaure pas la sécurité pour ces familles, car l'étape de résolution algébrique reste de temps polynomial.

L'auteur note qu'une réparation potentielle nécessiterait de maintenir $\ell_1$ et $\ell_2$ non nuls et suffisamment grands pour garantir que le minimum des deux directions d'attaque dépasse le niveau de sécurité cible. Cependant, il avertit qu'augmenter ces paramètres augmente directement la taille des clés publiques et des textes chiffrés, et qu'il reste à déterminer si une telle réparation resterait compétitive par rapport aux autres schémas basés sur les codes. L'article conclut que les paramètres actuels de l'EGMC sont peu sûrs et que l'attaque proposée fournit à la fois un discriminateur et un mécanisme complet de récupération de clé.

La grande découverte de l'article

Ce que l'article brise réellement

Ce que l'article écarte

À quel point sont-ils sûrs ?

Articles similaires