💻 computer science

A Novel Memory-Efficient MitM Attack on Ascon-Hash

Cet article propose une nouvelle attaque de type « Meet-in-the-Middle » économisant la mémoire sur Ascon-Hash à nombre de tours réduit, qui exploite la modélisation SAT, l'élimination de Gauss et la triangulation pour réduire considérablement la complexité en mémoire tout en maintenant les meilleures complexités temporelles connues.

Auteurs originaux : Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

Publié 2026-08-31

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

Article original sous licence CC BY 4.0 (https://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

Dans le monde numérique, la sécurité repose souvent sur un équilibre délicat entre force et efficacité. Pour les milliards de petits appareils alimentés par batterie qui constituent l'Internet des Objets — capteurs dans les usines, compteurs intelligents et moniteurs médicaux — la puissance de calcul est rare, et la mémoire est encore plus rare. Ces appareils ont besoin d'outils cryptographiques suffisamment robustes pour protéger les données, mais assez légers pour fonctionner sans épuiser une batterie ou saturer une puce minuscule. Ascon est une solution de premier plan pour ce défi, une famille de méthodes de chiffrement et de hachage conçues spécifiquement pour ces environnements à ressources limitées. Pour garantir qu'Ascon reste sûr, les chercheurs testent constamment sa résistance contre des attaques sophistiquées, tentant de trouver le chemin le plus court pour briser son code. L'un des outils les plus puissants de cet arsenal est l'attaque par « rencontre au milieu » (meet-in-the-middle), une stratégie où un attaquant travaille à rebours depuis le résultat final et vers l'avant depuis le point de départ, espérant se rencontrer au milieu avec une correspondance. Cependant, cette stratégie a traditionnellement nécessité une quantité massive de mémoire pour stocker les millions d'étapes intermédiaires, une exigence qui rendait souvent l'attaque impraticable pour les très mêmes dispositifs qu'Ascon est censé protéger.

Une équipe de chercheurs a maintenant développé une nouvelle façon d'exécuter cette attaque qui réduit considérablement la mémoire nécessaire, rendant le test bien plus réaliste pour les systèmes légers. Dans une étude axée sur la fonction Ascon-Hash, les auteurs ont démontré qu'ils pouvaient effectuer l'attaque sur une version réduite du système en utilisant beaucoup moins d'espace de stockage que ce que l'on pensait possible, sans sacrifier la vitesse de calcul. En traitant le problème comme un puzzle complexe de contraintes logiques, ils ont trouvé un moyen de filtrer les données inutiles avant même qu'elles n'aient besoin d'être stockées. Leur travail montre que pour une version à trois tours du hachage, la mémoire requise peut être réduite d'une complexité de 2^24 à 2^14. Pour une version à quatre tours, la réduction est encore plus spectaculaire, faisant chuter l'exigence d'une complexité de 2^34 à 2^12. Cette réussite ne fait pas que abaisser le coût de l'attaque ; elle fournit une image plus nette et plus précise de la sécurité réelle d'Ascon face à un adversaire disposant de ressources limitées.

Les chercheurs ont commencé par reconnaître que les tentatives précédentes pour briser Ascon à l'aide d'outils de recherche automatisés s'étaient heurtées à un mur d'utilisation de la mémoire. Bien que les ordinateurs soient devenus plus rapides pour trouver le bon chemin à travers le chiffrement, le processus exigeait toujours que l'attaquant conserve une vaste bibliothèque de résultats intermédiaires en mémoire, un peu comme essayer de résoudre un labyrinthe en écrivant chaque tour pris sur un morceau de papier séparé. Si le labyrinthe est assez grand, on tombe à court de papier bien avant de trouver la sortie. L'équipe a réalisé que la clé pour résoudre cela n'était pas seulement de trouver le chemin plus vite, mais d'être plus intelligent sur ce qu'ils notaient. Ils ont utilisé une méthode appelée résolution de satisfiabilité (satisfiability solving), qui consiste essentiellement à demander à un ordinateur de trouver un ensemble de conditions qui rendent une proposition logique complexe vraie. Cela leur a permis de cartographier les points spécifiques dans le processus de chiffrement où les calculs directs et inverses pourraient potentiellement se rencontrer.

Une fois ces points de rencontre potentiels cartographiés, les chercheurs ont appliqué une série de filtres algébriques pour nettoyer les données. Ils ont remarqué que de nombreuses contraintes régissant le chiffrement pouvaient être séparées en relations linéaires simples et en relations non linéaires plus complexes. Les parties linéaires étaient straightforward ; elles pouvaient être simplifiées à l'aide de techniques mathématiques standard pour éliminer les informations redondantes, réduisant ainsi efficacement la liste des possibilités que l'ordinateur devait suivre. Les parties non linéaires étaient plus délicates, mais l'équipe a développé une méthode pour les réorganiser sous une forme triangulaire, permettant de résoudre certaines variables en fonction d'autres. Ce processus éliminait la nécessité de calculer et de stocker explicitement ces variables spécifiques, réduisant davantage l'empreinte mémoire.

L'innovation la plus significative est venue de la manière dont ils ont géré les contraintes complexes restantes qui ne pouvaient pas être facilement simplifiées. Au lieu de stocker chaque résultat possible, les chercheurs ont utilisé ces contraintes restantes pour créer un « indice résiduel », une sorte de marque numérique ou d'étiquette. À mesure qu'ils généraient la liste des chemins directs potentiels, ils assignaient à chacun une étiquette basée sur ses propriétés spécifiques. Crucialement, ils ont réalisé que le chemin inverse ne pouvait correspondre à un chemin direct que si leurs étiquettes étaient compatibles. Cela signifiait que l'ordinateur n'avait pas besoin de conserver tous les chemins directs en mémoire ; il n'avait besoin de garder que ceux qui portaient une étiquette que le chemin inverse pourrait potentiellement atteindre. Dans les configurations spécifiques qu'ils ont testées, ce filtrage était si efficace qu'il a réduit l'intégralité de la liste des chemins directs nécessaires à un seul et minuscule compartiment de données.

Les résultats de cette nouvelle approche ont été frappants. Appliquée à une version à trois tours d'Ascon-Hash, la méthode a conservé la même vitesse que les attaques précédentes tout en réduisant la mémoire requise d'une complexité de 2^24 à 2^14. Pour la version à quatre tours, la réduction est encore plus profonde, coupant le besoin de mémoire d'une complexité de 2^34 à 2^12 par rapport à la meilleure méthode précédente. Les chercheurs ont vérifié que ce filtrage agressif ne rejetait pas accidentellement des solutions valides ; ils ont vérifié que les données restantes satisfaisaient toujours toutes les règles originales du système de chiffrement. L'étude confirme qu'en analysant soigneusement la structure du chiffrement et en appliquant ces filtres logiques, il est possible de réaliser des tests de sécurité approfondis avec une fraction des ressources auparavant jugées nécessaires. Ce travail suggère que la marge de sécurité d'Ascon dans les environnements à ressources limitées est évaluée avec une plus grande précision, garantissant que les normes cryptographiques protégeant notre monde connecté sont aussi robustes qu'elles le paraissent.

Résumé Technique : Une nouvelle attaque de type MitM économique en mémoire sur Ascon-Hash

Énoncé du Problème
Ascon est un standard cryptographique léger sélectionné par le NIST et normalisé dans le SP 800-232, spécifiquement conçu pour les environnements à ressources contraintes tels que l'Internet des Objets (IoT). Dans ces contextages, la mémoire est souvent une contrainte plus critique que le calcul. Bien que les attaques de type Rencontre au Milieu (Meet-in-the-Middle ou MitM) soient un outil principal pour évaluer la résistance aux préimages d'Ascon à nombre de tours réduit, les approches automatisées existantes font face à d'importants goulots d'étranglement en termes de mémoire. Les cadres précédents basés sur SAT, tels que celui proposé par Degré et al., ont réussi à réduire la complexité temporelle mais nécessitaient toujours une mémoire substantielle (par exemple, $2^{34}$ pour Ascon-Hash à 4 tours) pour stocker les valeurs intermédiaires dans des tables de hachage lors de la phase en ligne. Cet article traite du défi consistant à minimiser l'utilisation totale de la mémoire des attaques MitM sur Ascon-Hash tout en préservant les meilleures complexités temporelles connues.

Méthodologie
Les auteurs proposent un nouveau cadre qui s'appuie sur la recherche MitM basée sur SAT, mais introduit une étape de raffinement algébrique post-traitement pour réduire drastiquement la taille de la table du côté RED (RED-side) stockée. La méthodologie procède selon les étapes suivantes :

Recherche de Configuration Basée sur SAT : Le processus commence par l'utilisation d'un solveur SAT pour identifier des configurations MitM valides (définissant les variables du côté RED, les variables du côté BLUE, les positions de correspondance et les positions de l'annulation) qui atteignent un exposant de temps cible.
Séparation Algébrique : Pour chaque configuration temporellement optimale trouvée, les relations d'annulation induites sont reconstruites et séparées en parties linéaires et non linéaires selon leurs formes algébriques.
Réduction Linéaire : Les relations d'annulation linéaires (contraintes XOR) sont extraites et réduites par élimination de Gauss sur GF(2). Le rang de ce système linéaire détermine la réduction du nombre de variables libres du côté RED.
Triangulation des Relations Non Linéaires : Les relations d'annulation non linéaires sont traitées à l'aide d'un algorithme de triangulation sur des polynômes booléens. Cette étape tente d'exprimer certaines variables du côté RED en fonction d'autres, les éliminant ainsi de l'énumération explicite.
Filtrage par Indice Résiduel : Pour les relations non linéaires qui ne peuvent être éliminées par triangulation, les auteurs définissent un « indice résiduel ». Cet indice partitionne les affectations du côté RED en compartiments (buckets). Pendant l'attaque, seuls les compartiments RED dont les indices sont cohérents avec les valeurs calculables depuis le côté BLUE sont conservés. Cette étape de filtrage rejette les affectations RED incompatibles avant la phase de correspondance finale.
Vérification de la Compatibilité : Les auteurs vérifient que le processus de filtrage ne modifie pas l'ensemble des solutions des équations de correspondance. Ils prouvent que si les monômes mixtes RED-BLUE dans les expressions de correspondance s'annulent sur le domaine conservé, la jointure séparable utilisée dans l'attaque MitM reste équivalente à la résolution des équations de correspondance complètes.

Contributions Clés

Cadre d'Optimisation de la Mémoire : L'article introduit une méthode systématique pour affiner les configurations MitM dérivées de SAT en traitant algébriquement les relations d'annulation, ciblant spécifiquement la réduction de la complexité de la mémoire en ligne.
Triangulation et Filtrage : L'intégration de la triangulation de polynômes booléens et du filtrage par indice résiduel permet l'élimination de variables et l'élagage de l'espace de recherche sans augmenter la complexité temporelle.
Validation de la Séparabilité : Le travail fournit une vérification formelle (Proposition 1) garantissant que les techniques de réduction de mémoire ne compromettent pas la correction de l'attaque MitM en vérifiant l'annulation des termes mixtes sur le domaine conservé.

Résultats Expérimentaux
Les auteurs ont évalué leur méthode sur Ascon-Hash à 3 et 4 tours, comparant leurs résultats à la base de référence SAT de Degré et al. [1].

Ascon-Hash à 3 Tours :
- Complexité Temporelle : Préservée à $2^{114}$ .
- Complexité Mémoire : Réduite de $2^{24}$ (base de référence) à $2^{14}$ .
- Mécanisme : La configuration utilisait 14 variables RED. Après la réduction de rang linéaire (rang 1) et le filtrage par indice résiduel (ne conservant que le compartiment d'indice zéro), la taille de la table RED conservée a été réduite à $2^7$ dans le modèle réduit par symétrie, ce qui correspond à $2^{14}$ dans le cadre complet.
Ascon-Hash à 4 Tours :
- Complexité Temporelle : Préservée à $2^{124}$ .
- Complexité Mémoire : Réduite de $2^{34}$ (base de référence) à $2^{12}$ .
- Mécanisme : La configuration utilisait 38 variables RED. La triangulation a éliminé 5 variables, et le filtrage par indice résiduel a encore réduit la table conservée. La complexité mémoire finale dans le cadre complet de 64 colonnes était de $2^{12}$ .

Le Tableau 1 de l'article résume ces améliorations, montrant une réduction constante des exposants de mémoire tout en maintenant les exposants temporels de l'état de l'art précédent.

Signification et Revendications
L'article affirme que sa principale importance réside dans la fourniture d'une évaluation plus précise de la marge de sécurité des versions à nombre de tours réduit d'Ascon dans le contexte des environnements à mémoire contrainte. Puisqu'Ascon est conçu pour l'IoT et les systèmes embarqués où la mémoire est rare, démontrer que les attaques MitM peuvent être exécutées avec des exigences de mémoire nettement inférieures (par exemple, passant de $2^{34}$ à $2^{12}$ pour 4 tours) est crucial pour une évaluation de sécurité précise.

Les auteurs déclarent que leur cadre démontre qu'au-delà de la recherche de configurations temporellement optimales, le traitement algébrique supplémentaire des relations d'annulation peut effectivement réduire les besoins de stockage en ligne. Ils ne prétendent pas casser le standard Ascon complet, mais plutôt affiner l'analyse de ses variantes à nombre de tours réduit. Le travail suggère que les recherches futures pourraient étendre cette approche à plus de tours, à d'autres modes d'Ascon et à d'autres primitives légères de type éponge.

Articles similaires