Un modèle automatisé pour les attaques différentielles meet-in-the-middle sur les chiffrements AndRX

Pourquoi cette recherche est importante

Chaque fois que nous utilisons un smartphone, payons en ligne ou connectons un dispositif médical, de petites serrures numériques appelées chiffrements par blocs protègent nos données. Les experts en sécurité tentent constamment de casser ces serrures afin de concevoir des versions plus sûres. Cet article présente une nouvelle façon d’automatiser un style d’attaque puissant contre une famille populaire de chiffrements légers, aidant les chercheurs à évaluer la solidité réelle de ces verrous numériques.

Comment fonctionne le cassage de code moderne

Les chiffrements par blocs modernes brouillent les données en de nombreux petits pas, ou tours, contrôlés par une clé secrète. Pour juger si un chiffrement est sûr, les cryptanalystes recherchent des motifs qui ne devraient pas exister si le système se comportait comme un pur aléatoire. Deux outils classiques sont la cryptanalyse différentielle, qui suit comment de petites modifications à l’entrée se répercutent sur la sortie, et les attaques meet-in-the-middle, qui calculent depuis les deux bouts du chiffrement et cherchent des correspondances au milieu. Chacun de ces outils a ses limites, mais les combiner crée une sonde plus fine de la structure d’un chiffrement.

Mélanger deux idées d’attaque

L’étude se concentre sur une technique hybride appelée attaque différentielle meet-in-the-middle. Ici, le chiffrement est divisé en trois parties : une section d’entrée, une section centrale et une section de sortie. Au cœur, l’attaquant recherche un « distinguo différentiel », un motif de différences d’entrée et de sortie qui survient plus souvent que le hasard sur plusieurs tours. Autour de ce noyau, l’attaquant chiffre partiellement depuis le début et déchiffre partiellement depuis la fin, en ne devinant que des morceaux sélectionnés de la clé. Quand les deux directions se rejoignent dans le même état interne, les devinements ont plus de chances de correspondre à la vraie clé, ce qui réduit l’espace de recherche.

Transformer un savoir-faire manuel en outil automatisé

Concevoir manuellement de telles attaques combinées est extrêmement délicat, surtout pour des chiffrements orientés bit dont l’état interne peut avoir 64, 96 ou 128 bits. Les auteurs construisent un cadre automatisé qui utilise la programmation par contraintes, une méthode pour décrire des conditions logiques complexes afin qu’un solveur explore toutes les possibilités valides. D’abord, ils encodent comment les différences se propagent à travers les blocs de base d’un chiffrement fondé sur les opérations AND, rotation et XOR, une famille connue sous le nom de designs AndRX. Ensuite, ils modélisent quels bits de clé influencent chaque étape et combien de ces bits doivent réellement être devinés. Le solveur explore de nombreuses façons de découper le chiffrement en sections d’entrée, centrale et de sortie, choisissant la configuration qui minimise l’effort global d’une attaque.

Astuces supplémentaires pour réduire l’espace de clés

En complément du modèle de base, le cadre ajoute deux astuces d’optimisation adaptées aux chiffrements AndRX de type Feistel comme SIMON et Simeck. La première, appelée idée de sous-clé équivalente, déplace mathématiquement des parties des clés de tour en avant ou en arrière de sorte que plusieurs bits de clé différents se comportent comme s’ils étaient identiques. Cela réduit le nombre de bits indépendants que l’attaquant doit considérer. La seconde, le devinage sélectif de clés, étudie comment l’opération non linéaire AND utilise ses entrées et montre que, dans certaines conditions, un bit deviné peut remplacer deux. Les auteurs décrivent aussi, sans les automatiser complètement pour l’instant, deux améliorations supplémentaires : le partitionnement parallèle, qui peut ajouter un tour à l’attaque sans temps supplémentaire, et une astuce de réduction de données qui diminue le nombre de messages choisis nécessaires.

Ce que l’outil révèle sur des chiffrements réels

Pour tester leur approche, les chercheurs appliquent leur modèle automatisé à toutes les versions standard des chiffrements légers SIMON et Simeck, candidats à l’usage dans des dispositifs contraints comme des capteurs et des contrôleurs embarqués. Pour chaque variante, l’outil trouve une attaque différentielle meet-in-the-middle et estime ses coûts en données, temps et mémoire. Dans de nombreux cas, ces attaques couvrent plus de tours que les attaques meet-in-the-middle ou techniques apparentées précédentes, et surpassent souvent aussi les attaques différentielles impossibles et à corrélation nulle antérieures en nombre de tours couverts. Par exemple, l’outil produit des attaques allant jusqu’à 51 tours d’une version 128 bits de SIMON avec une clé de 256 bits, étendant la portée des méthodes antérieures tout en maintenant le travail en dessous d’une recherche exhaustive de toutes les clés.

Vue d’ensemble pour la cryptographie future

Pour les non-spécialistes, le message clé n’est pas que SIMON ou Simeck sont « cassés » en pratique, mais que les outils automatisés deviennent suffisamment puissants pour explorer des faiblesses subtiles qui seraient très difficiles à trouver manuellement. Le cadre présenté ici est générique au niveau des bits et peut en principe être adapté à d’autres familles de chiffrements. En aidant les concepteurs à tester rapidement la résistance des nouveaux algorithmes face à des attaques combinées avancées, de tels outils soutiennent l’objectif à long terme de construire un chiffrement qui reste robuste même lorsque les techniques d’analyse deviennent plus sophistiquées.

Citation: Chakraborty, D., Sahoo, S., Nguyen, P.H. et al. An automated model for differential meet in the middle attacks on AndRX ciphers. Sci Rep 16, 14773 (2026). https://doi.org/10.1038/s41598-026-41390-w

Mots-clés: cryptanalyse des chiffrements par blocs, différentiel meet-in-the-middle, chiffrement SIMON, chiffrement Simeck, programmation par contraintes