Réseau de Feistel

Un réseau de Feistel est une construction utilisée dans les algorithmes de chiffrement par bloc, nommée d'après le cryptologue d'IBM, Horst Feistel. Elle a été utilisée pour la première fois dans Lucifer et DES. Cette structure offre plusieurs avantages, le chiffrement et le déchiffrement ont une architecture similaire voire identique dans certains cas. L'implémentation matérielle est aussi plus facile avec un tel système même si les choses ont passablement changé depuis la fin des années 1970. Un réseau de Feistel repose sur des principes simples dont des permutations, des substitutions, des échanges de blocs de données et une fonction prenant en entrée une clé intermédiaire à chaque étage.

Il est vraisemblable que Feistel ne soit pas le seul inventeur de cette architecture. Durant une conférence, Don Coppersmith a laissé entendre que Bill Notz et Lynn Smith (de l'équipe d'IBM travaillant sur DES) avaient été en grande partie à l'origine du réseau de Feistel tel que nous le connaissons.

Structure

Réseau de Feistel à n tours utilisant l'opérateur XOR

Un réseau de Feistel est subdivisé en plusieurs tours ou étages. Dans sa version équilibrée, le réseau traite les données en deux parties de taille identique. À chaque tour, les deux blocs sont échangés puis un des blocs est combiné avec une version transformée de l'autre bloc. Pour simplifier, la moitié des données sont encodées avec la clef, puis le résultat de cette opération est ajouté grâce à un xor (ou exclusif) à l'autre moitié des données. Puis au tour suivant, on inverse : c'est au tour de la dernière moitié d'être chiffrée puis d'être ajoutée avec un xor à la première moitié, sauf qu'on utilise les données chiffrées précédemment (sinon ça ne servirait à rien de faire plus de deux tours). Le schéma ci-contre montre le cheminement des données (le "plus" entouré représente le xor). Chaque tour utilise une clé intermédiaire, en général tirée de la clé principale via une génération appelée key schedule. Les opérations effectuées pendant l'encryptage avec ces clefs intermédiaires sont spécifiques à chaque algorithme.

Dans le cas de DES, le réseau de Feistel possède 16 tours, chacun avec une sous-clé. Ces différentes clés permettent d'améliorer la robustesse d'un algorithme face à la cryptanalyse.

Une variante, le réseau de Feistel non-équilibré coupe les données en deux parties de tailles différentes. Cette variante a été utilisée dans MacGuffin de Bruce Schneier, ou encore Skipjack, candidat pour AES.

Définition formelle

Une définition formelle d'un réseau de Feistel peut être donnée sous plusieurs formes. Nous reprenons ici la notation utilisée par Knudsen dans Partial and Higher Order Differentials and Applications to DES.

$C_0^L = P^L~$ et $C_0^R = P^R~$

$C_i = (C_i^L, C_i^R) = (C_{i-1}^R, f(C_{i-1}^R, K_i) + C_{i-1}^L)~$

$C^L = C_r^L~$ et $C^R = C_r^R~$

• l'exposant représente la sous-partie du bloc considérée (L à gauche, R à droite).
• $P~$ correspond au bloc de texte clair, $P_i^L$ correspond au bloc de gauche à l'entrée du tour $i~$
• $C~$ correspond au bloc de texte chiffré, $C_i^R$ correspond au bloc de droite à la sortie du tour $i~$
• $K_i~$ est la clé du tour $i~$, elle est calculée grâce à un key schedule de la clé principale
• $r~$ est le nombre de tours dans l'algorithme
• $+~$ est une opération dans un groupe commutatif (souvent un XOR ou une addition)

Composition des tours

Chaque tour applique plusieurs transformations sur les données provenant du tour précédent :

• permutation des bits via des P-Boxes
• fonction non-linéaire (substitution) avec des S-Boxes
• mixage linéaire en utilisant la fonction XOR
• application de la clé du tour (intégrée dans une fonction ou via un XOR)

On utilise les termes de confusion et diffusion pour décrire la propagation des informations dans la structure (termes utilisés par Claude Shannon). En effet, une modification d'un bit en entrée produira des variations très importantes dans les stages intermédiaires et en sortie. Un terme plus récent pour décrire ce phénomène est l'effet avalanche. L'utilisation des permutations permet d'améliorer la diffusion alors que les substitutions ont pour effet d'augmenter la confusion.

Cryptanalyse

Les schémas de Feistel ont été largement analysés et examinés par les experts. Plusieurs attaques sont possibles mais les deux principales sont :

• la cryptanalyse linéaire;
• la cryptanalyse différentielle.

Ces méthodes ont fait leur preuve sur DES et sur d'autres algorithmes similaires. Mais cela ne signifie pas que l'utilisation d'un réseau de Feistel va obligatoirement entraîner des vulnérabilités significatives. Grâce à l'ajout de différentes techniques et avec une conception bien menée, on peut considérablement améliorer la résistance d'un algorithme basé sur Feistel. C'est le cas pour Blowfish qui est cryptographiquement sûr en date de décembre 2008.

En général, les cryptanalystes s'attaquent en premier à des versions amoindries des chiffrements, c’est-à-dire comportant moins de tours.

Algorithmes

Un grand nombre d'algorithmes utilise des réseaux de Feistel, avec des variantes. Voici une liste non-exhaustive :

• DES
• Blowfish
• Twofish
• Camellia
• SEED
• RC5
• OAEP