Réseaux de Feistel : éléments fondamentaux des chiffrements modernes

Au début des années 1970, Horst Feistel travaillait chez IBM Research sur le chiffre Lucifer lorsqu'il a développé une intuition fondamentale : il est possible de construire un chiffre inversible à l'aide d'une fonction de ronde non inversible.

Cette idée était révolutionnaire, car il est difficile de concevoir des fonctions qui soient à la fois inversibles et sûres. La construction de Feistel contourne entièrement cette exigence et permet d'utiliser des fonctions de ronde à sens unique d'une complexité arbitraire.

Dans un chiffre de Feistel, le bloc d'entrée est divisé en deux moitiés égales : L (gauche) et R (droite). À chaque ronde, la fonction de ronde F est appliquée à R, le résultat est combiné par XOR avec L, puis les deux moitiés sont échangées.

Après n rondes, les deux moitiés sont recombinées pour produire le texte chiffré. L'échange garantit que les deux moitiés sont traitées à tour de rôle et mélangées en profondeur.

Dans un réseau de Feistel, la fonction de ronde F reçoit la moitié droite et la sous-clé de ronde en entrée, puis produit une sortie combinée par XOR avec la moitié gauche. Point crucial, F n'a pas besoin d'être inversible.

F peut être d'une complexité arbitraire : elle peut combiner des substitutions, des permutations, des XOR et de l'arithmétique modulaire. Plus F est complexe et non linéaire, plus le chiffre est robuste, car le déchiffrement n'a jamais besoin d'inverser F.

Le déchiffrement d'un chiffre de Feistel utilise exactement la même structure que le chiffrement, mais applique les sous-clés de ronde dans l'ordre inverse. Cela est possible parce que XOR est son propre inverse : si A XOR B = C, alors C XOR B = A.

Puisque le déchiffrement n'appelle jamais F^-1 (l'inverse de F), la fonction de ronde peut être un hachage irréversible, une table de correspondance ou n'importe quelle opération complexe sans compromettre l'inversibilité du chiffre.

L'élégance mathématique des réseaux de Feistel tient au fait que leur structure fondée sur XOR garantit l'inversibilité, quelle que soit l'action de F. Même si F est une fonction à sens unique comme SHA-256, l'ensemble du chiffre de Feistel reste inversible.

Les chiffres de Feistel sont ainsi extrêmement flexibles. Les cryptographes peuvent se concentrer entièrement sur le fait de rendre F aussi déroutante et diffusante que possible, sachant que l'inversibilité est assurée par la structure du réseau elle-même.

La norme de chiffrement des données (DES), publiée en 1977, est un chiffre de Feistel à 16 rondes qui traite des blocs de 64 bits avec une clé de 56 bits. Chaque ronde utilise une sous-clé différente de 48 bits dérivée de la clé principale.

La fonction de ronde de DES comprend une permutation d'expansion, un XOR avec la sous-clé, huit boîtes S fournissant la non-linéarité et une permutation P. Cette combinaison assure à la fois la confusion et la diffusion requises par les principes de conception des chiffres de Shannon.

Blowfish, conçu par Bruce Schneier en 1993, est un chiffre de Feistel à longueur de clé variable (32 à 448 bits) comportant 16 rondes. Il utilise des boîtes S dépendantes de la clé, ce qui rend les attaques précalculées irréalisables.

Twofish, finaliste de la compétition AES, prolonge les idées de Blowfish avec des blocs de 128 bits et 16 rondes. Tous deux restent inviolés et sont utilisés dans des applications comme le hachage de mots de passe bcrypt, qui utilise une version modifiée de Blowfish.

Un chiffre de Feistel équilibré divise le bloc en deux moitiés égales. Un Feistel déséquilibré utilise des moitiés de tailles différentes, par exemple une division en 3/4 et 1/4.

Les réseaux de Feistel déséquilibrés peuvent offrir des avantages de sécurité dans certains contextes et sont utilisés dans certains chiffres spécialisés. La famille de chiffres CAST utilise une structure de Feistel équilibrée sur 64 bits.

En 1988, Michael Luby et Charles Rackoff ont démontré qu'un réseau de Feistel à 3 rondes utilisant des fonctions de ronde pseudo-aléatoires est une permutation pseudo-aléatoire sûre (PRP), et qu'une version à 4 rondes est une PRP forte.

Ce résultat théorique a donné aux réseaux de Feistel un fondement solide de sécurité démontrable, et pas seulement une confiance empirique. Il a confirmé que la structure de Feistel elle-même contribue à la sécurité, au-delà de la seule fonction de ronde.

Le réseau de substitution-permutation (SPN) utilisé par AES applique simultanément une substitution et une permutation à l'ensemble du bloc, plutôt qu'à la moitié du bloc à chaque ronde. Cela assure une diffusion plus rapide.

AES atteint une diffusion complète en seulement 4 rondes, tandis que la structure de Feistel de DES nécessite davantage de rondes pour obtenir une diffusion comparable. Le SPN d'AES s'adapte également mieux aux architectures modernes de processeurs dotées d'instructions SIMD.

Le théorème de Luby-Rackoff considère la fonction de ronde F comme une fonction véritablement aléatoire. En pratique, F est une fonction pseudo-aléatoire, c'est-à-dire un chiffre à clé ou une fonction de hachage, et non un véritable oracle aléatoire.

Cette différence entre les démonstrations théoriques et les implémentations pratiques est un thème récurrent en cryptographie. Les démonstrations apportent une certaine confiance, mais reposent sur des modèles idéalisés. La sécurité dans le monde réel dépend également d'implémentations sûres, exemptes de vulnérabilités par canal auxiliaire.

Évaluez votre compréhension de la conception des réseaux de Feistel.

Les réseaux de Feistel sont des structures de chiffres par blocs qui utilisent une fonction de ronde n'ayant pas besoin d'être inversible. Le déchiffrement s'effectue en exécutant la même structure en sens inverse, avec les sous-clés dans l'ordre inversé.

DES, Blowfish et Twofish sont tous des chiffres de Feistel. Le théorème de Luby-Rackoff fournit des garanties de sécurité théoriques. AES utilise à la place une structure SPN, qui offre une meilleure diffusion à chaque ronde.