💻 computer science

Full-Key Recovery and Forgery from One MQOM v2.1 Signature

Cet article présente une attaque par récupération de clé complète et par contrefaçon sur le candidat à la signature MQOM v2.1 du Round-3 du NIST, démontrant qu'une seule signature acceptée est suffisante pour dériver la clé secrète complète et forger de nouvelles signatures, avec des coûts computationnels inférieurs aux seuils de sécurité du NIST pour toutes les catégories.

Auteurs originaux : José Luis Delgado

Publié 2026-08-11

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : José Luis Delgado

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 essayez d'envoyer un message secret à un ami, mais que vous vivez dans un monde où des ordinateurs super-rapides (appelés ordinateurs quantiques) pourraient un jour exister. Ces machines futures pourraient briser la plupart des verrous que nous utilisons aujourd'hui pour garder nos secrets en sécurité. Pour se préparer à cela, des scientifiques construisent de nouveaux verrous numériques super-résistants appelés « signatures post-quantiques ». Considérez cela comme une sorte de sceau de cire spécial sur une lettre. Même si un voleur possède un marteau magique capable de briser les verrous normaux, ce nouveau sceau de cire est fait d'un matériau qui devrait résister.

L'un des nouveaux verrous les plus prometteurs en cours de test est appelé MQOM. Il fonctionne un peu comme un puzzle géant et complexe. Pour signer une lettre, l'expéditeur utilise un « témoin » secret (une clé cachée) pour résoudre un problème mathématique impliquant de nombreuses variables. Pour prouver qu'il a résolu le problème sans révéler le secret, il utilise un tour astucieux appelé « MPC-in-the-head » (MPC dans la tête). Imaginez que l'expéditeur prétende être toute une équipe de personnes, chacune détenant un petit morceau du secret. Ils jouent un jeu où ils révèlent juste assez pour prouver que l'équipe a résolu le puzzle ensemble, mais pas assez pour révéler les morceaux réels du secret. Si les mathématiques sont cohérentes, la signature est valide. Nous nous en soucions parce que si ces nouveaux verrous présentent une fissure cachée, notre sécurité numérique future pourrait s'effondrer avant même que nous y arrivions.

Parlons maintenant de l'histoire de ce document. Un chercheur nommé José Luis Delgado a examiné de près une version spécifique de ce verrou MQOM (version 2.1) et a découvert un moyen étonnamment simple de le briser. Le document soutient que si un attaquant obtient seulement une seule signature valide du système, il peut découvrir l'intégralité de la clé secrète et falsifier de nouvelles signatures pour n'importe quel message qu'il souhaite. C'est comme si un voleur vous voyait ouvrir votre porte d'entrée une seule fois, et que ce seul regard lui suffisait pour fabriquer une clé maîtresse qui ouvre toutes les serrures de votre maison.

Voici comment le « tour de magie » fonctionne, expliqué à travers une histoire. Imaginez que la clé secrète soit une longue carte au trésor cachée. Le système MQOM cache cette carte à l'intérieur d'un arbre géant composé de branches. Lorsque vous signez un message, le système vous montre un chemin montant dans l'arbre vers une feuille cachée spécifique (un endroit sur la carte), mais il garde la feuille elle-même couverte. Cependant, il vous donne également un « chemin frère » (sibling path) — une liste des branches situées à côté de la feuille cachée. En raison de la façon dont l'arbre est construit, si vous connaissez les branches à côté de la feuille, vous pouvez déterminer exactement ce que la feuille cachée serait si vous connaissiez un petit préfixe de la carte secrète.

Le document a découvert que le système laisse également un « engagement » (commitment), qui est comme une enveloppe scellée contenant la feuille cachée. Le chercheur a réalisé qu'en combinant le chemin frère (les branches) avec l'enveloppe scellée, ils pouvaient écrire une seule équation géante. Cette équation possède une inconnue : le petit préfixe de la carte secrète. L'attaquant n'a pas besoin de deviner toute la carte ; il doit simplement résoudre cette équation pour trouver ce petit préfixe.

Une fois qu'il a trouvé ce préfixe, la signature qu'il possède déjà lui donne un « suffixe de correction » — une petite note qui dit : « Voici le reste de la carte pour accompagner le préfixe que vous venez de trouver ». En assemblant le préfixe et la note, l'attaquant reconstruit l'intégralité de la carte secrète (la clé de signature complète). Avec cette clé, il peut signer tout nouveau message, et le système l'acceptera comme réel.

Le document ne se contente pas de supposer que cela fonctionne ; les auteurs ont réellement fait les calculs et le travail informatique pour le prouver. Ils ont calculé exactement la puissance de calcul nécessaire pour résoudre cette équation pour les différents niveaux de force du verrou (appelés Catégories I, III et V). Ils ont trouvé que pour toutes les catégories, l'effort requis est inférieur à la limite de sécurité que le NIST a fixée pour ces verrous.

Pour le niveau le plus facile (Catégorie I), l'attaque prend environ $2^{142.335112}$ opérations. Pour le niveau intermédiaire (Catégorie III), cela prend environ $2^{206.774558}$ ou $2^{206.988685}$ opérations, selon la partie de la carte qu'ils scannent. Pour le niveau le plus difficile (Catégorie V), cela prend environ $2^{271.794162}$ opérations. Dans chaque cas, le nombre d'étapes que l'attaquant doit accomplir est inférieur au nombre d'étapes que le verrou est censé exiger pour être sûr.

Les chercheurs ne se sont pas arrêtés aux mathématiques. Ils ont construit un programme informatique qui a réellement exécuté l'attaque. Ils ont pris une signature réelle, ont résolu l'équation, ont récupéré la clé secrète exacte octet par octet, puis ont utilisé cette clé pour signer un tout nouveau message. Le vérificateur du système a examiné la nouvelle signature et a déclaré : « Oui, elle est valide ! ». Cela a prouvé que l'attaque fonctionne dans le monde réel, et pas seulement sur papier.

Le document a également examiné si le changement de certains paramètres permettrait de régler le problème. Ils ont découvert que le simple fait d'ajouter un « sel » (un nombre aléatoire) au processus modifie les nombres dans l'équation, mais n'arrête pas l'attaque. L'équation existe toujours ; elle a simplement une apparence légèrement différente. Pour vraiment corriger cela, les concepteurs devraient changer la façon dont le chemin de l'arbre est lié au secret, la façon dont la feuille est engagée, ou la façon dont la note de correction est générée.

En résumé, ce document montre que l'actuelle version du verrou MQOM possède un trou par lequel on peut passer facilement. Il transforme une seule signature en une clé maîtresse, permettant de falsifier des messages avec moins d'effort que ce que le verrou est censé supporter. L'auteur a partagé son code et ses résultats afin que d'autres puissent vérifier son travail, et il suggère que les concepteurs de MQOM doivent corriger ces parties spécifiques du système avant qu'il ne puisse être considéré comme sûr pour l'avenir.

Résumé technique : Récupération complète de la clé et forge à partir d'une seule signature MQOM v2.1

Énoncé du problème
Cet article présente une attaque cryptanalytique contre MQOM v2.1, un candidat de la troisième ronde du processus de signature supplémentaire du NIST. L'attaque démontre qu'une seule signature acceptée est suffisante pour récupérer la clé de signature à long terme complète. Une fois récupérée, cette clé permet à un adversaire de forger des signatures sur de nouveaux messages qui sont acceptées par le vérificateur de référence. La vulnérabilité provient de l'interaction entre les arbres de graines GGM corrélés, le mécanisme d'engagement de feuille cachée et le suffixe de correction du témoin contenu dans le transcript de la signature.

Méthodologie
L'attaque procède par une reconstruction déterministe du témoin de signature basé sur les champs publics du transcript. La méthodologie centrale implique les étapes suivantes :

Dérivation d'une équation publique :
La signature révèle un chemin de sibling dans un arbre de graines binaire corrélé. En raison de la construction de l'arbre (où le parent est le XOR de ses enfants), la feuille cachée $s_e$ peut être exprimée comme une fonction affine du préfixe du témoin à long terme $\delta = \text{FirstBits}_\lambda(x)$ et des valeurs de chemin publiques $A_e$ :
$s_e = \delta \oplus A_e$
La signature contient également un engagement vers cette feuille cachée : $C_{e,c} = \text{Enc}_{K_{e,c}}(s_e) \oplus \text{LinOrtho}(s_e)$ . En substituant l'identité affine dans l'engagement, on obtient une équation publique où $\delta$ est l'unique inconnue :
$\text{Enc}_{K_{e,c}}(\delta \oplus A_e) = T_{e,c} \oplus \text{LinOrtho}(\delta)$
Ici, $K$ , $T$ et $A$ sont dérivés entièrement du transcript accepté.
Énumération de candidats via un parcours à état conservé :
Pour résoudre $\delta$ , l'attaquant doit évaluer l'équation sur le domaine de $\lambda$ bits. Plutôt que de réévaluer le circuit AES/Rijndael fixe pour chaque candidat, l'article emploie un parcours par code de Gray réfléchi. En conservant l'état du circuit entre des candidats adjacents (qui diffèrent de seulement un bit), l'attaquant met à jour uniquement le cône de dépendance du bit d'entrée modifié. Cette « computation à état conservé » réduit considérablement le nombre total de portes logiques requis pour le balayage.
Reconstruction du témoin et récupération de la clé :
Pour chaque candidat $\hat{\delta}$ satisfaisant l'équation publique, l'attaquant utilise le suffixe de correction publié ( $\text{NextBits}_\lambda(\Delta x)$ ) et le chemin de sibling pour reconstruire le témoin MQ complet $\hat{x}$ . La relation MQ publique $Q(\hat{x}) = y$ est ensuite évaluée. Si la relation est vérifiée, $\hat{x}$ est sérialisé en une clé secrète valide.
Forge :
La clé récupérée est utilisée pour signer un nouveau message. Le vérificateur de référence accepte cette signature, confirmant une récupération complète de la clé et une rupture de l'Unforgeabilité Existentielle sous Attaque à Choix de Message (EUF-CMA).

Contributions clés et résultats

Récupération de la clé complète à partir d'une seule signature : L'article prouve que pour les catégories NIST I, III et V (utilisant des représentants fast-r3 F256), une seule signature brise le schéma.
Évaluation concrète du coût : L'auteur fournit les nombres exacts de portes booléennes pour l'attaque, en utilisant des circuits de syntaxe source générés indépendamment pour les permutations AES/Rijndael.
- Catégorie I : $2^{142.335112}$ portes (Référence : $2^{143}$ ).
- Catégorie III : $2^{206.774558}$ portes (couverture partielle) et $2^{206.988685}$ portes (haute couverture) (Référence : $2^{207}$ ).
- Catégorie V : $2^{271.794162}$ portes (Référence : $2^{272}$ ).
  Tous les coûts d'attaque se situent strictement en dessous des seuils de sécurité correspondants du NIST.
Validation de la forge : Les exécutions de référence ont réussi à récupérer des témoins et des clés octet par octet, produisant des forges de messages frais acceptées par le vérificateur de référence.
Limites théoriques : L'article établit une borne exacte de moment factoriel pour le nombre de faux positifs (préimages supplémentaires de l'équation) atteignant l'étape de validation MQ publique. Sous le Modèle de Chiffre Idéal (ICM), la probabilité de dépasser 64 validations sur un domaine complet est bornée par $1/64!$ , garantissant que l'attaque reste informatiquement réalisable.

Signification et revendications
L'article affirme que la conception spécifique de l'interface de MQOM v2.1 — spécifiquement la combinaison de l'identité chemin-préfixe, de l'attribut d'engagement de la feuille cachée et de la carte de correction-vers-témoin — crée un « canal de récupération par une seule signature ».

Indépendance du transcript : L'attaque s'applique aux transcripts générés via le Modèle d'Oracle Aléatoire (ROM), le Modèle d'Oracle Aléatoire Quantique (QROM) ou des instanciations concrètes de SHAKE, car l'équation dépend uniquement de champs publics fixes.
Persistance liée au sel : L'auteur démontre que même si l'expansion de la racine globale est liée au sel de la signature (changeant les constantes publiques $A_e$ et $T_{e,c}$ ), la forme de l'équation de récupération reste inchangée, préservant ainsi le vecteur d'attaque.
Implications de conception : L'article conclut que la prévention de cette attaque nécessite de modifier les cartes fondamentales : changer l'identité chemin-préfixe (par exemple, utiliser des ouvertures non affines), modifier l'attribut de la feuille cachée (par exemple, utiliser un état secret par signature), ou découpler la correction de la récupération du témoin à long terme.

L'auteur fournit un artefact public reproduisant tous les résultats de calcul et le code source de l'attaque et de la génération de circuits.

Articles similaires