Réseau de Feistel

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.

Sommaire

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 :

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 :

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 :


v · Chiffrement par bloc
Algorithmes 3-Way • AES • Akelarre • Blowfish • C2 • Camellia • CAST-128 • CAST-256 • CMEA • CS-Cipher • DEAL • DES • DES-X • Double DES • E2 • FEAL • FOX • FROG • G-DES • GOST • ICE • IDEA • KASUMI • KHAZAD • Khufu et Khafre • LOKI89/91 • LOKI97 • Lucifer • MacGuffin • Madryga • MAGENTA • MARS • MISTY1 • MMB • MULTI2 • NewDES • RC2 • RC5 • RC6 • REDOC • Red Pike • S-1 • SAFER • SC2000 • SEED • Serpent • SHACAL • SHARK • Skipjack • Square • TEA • Triple DES • Twofish • XTEA
Architecture Réseau de Feistel • Key schedule • Chiffrement par produit • S-box • Réseau de substitution permutation
Attaques Cryptanalyse • Attaque par force brute • Linéaire / Différentielle • Modulo n • XSL
Standardisation Concours AES • CRYPTREC • NESSIE
Divers Effet avalanche • Taille de bloc • Vecteur d’initialisation • Taille de clé • Mode d’opération • Lemme Piling-Up • Clé faible


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Réseau de Feistel de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Reseau de Feistel — 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Reseau de substitution-permutation — Réseau de substitution permutation En cryptographie, un réseau de permutation substitution (SPN en anglais) est une architecture utilisée dans les chiffrements par bloc comme AES. Elle consiste en une série de transformations mathématiques sur le …   Wikipédia en Français

  • Réseau de substitution permutation — En cryptographie, un réseau de permutation substitution (SPN en anglais) est une architecture utilisée dans les chiffrements par bloc comme AES. Elle consiste en une série de transformations mathématiques sur le bloc en clair en entrée pour… …   Wikipédia en Français

  • Réseau de substitution-permutation — En cryptographie, un réseau de permutation substitution (SPN en anglais) est une architecture utilisée dans les chiffrements par bloc comme AES. Elle consiste en une série de transformations mathématiques sur le bloc en clair en entrée pour… …   Wikipédia en Français

  • Schéma de Feistel — 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… …   Wikipédia en Français

  • Horst Feistel — Horst Feistel, né le 30 janvier 1915 à Berlin, mort le 14 novembre 1990, était un cryptographe américain d origine allemande. Feistel fut l un des premiers cryptographes universitaires. Il est l inventeur du réseau de Feistel… …   Wikipédia en Français

  • SPN — Réseau de substitution permutation En cryptographie, un réseau de permutation substitution (SPN en anglais) est une architecture utilisée dans les chiffrements par bloc comme AES. Elle consiste en une série de transformations mathématiques sur le …   Wikipédia en Français

  • Lucifer (cryptographie) — Pour les articles homonymes, voir Lucifer (homonymie). Lucifer Résumé Concepteur(s) Horst Feistel, IBM Première publication 1971 Dérivé de …   Wikipédia en Français

  • Lucifer (cryptographie)) — Lucifer (cryptographie) Pour les articles homonymes, voir Lucifer (homonymie). Lucifer …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”