PICSI

Le schéma de Feistel

  Le schéma élémentaire

En 1977, le gouvernement américain adopta comme standard de chiffrement le DES (Data Encryption Standard) développé par IBM [7]. Le premier algorithme proposé, nommé Lucifer, rejeté à cause d'une faille de sécurité (voir par exemple [4]), avait été créé par Horst Feistel. Le DES utilise le même schéma qui a gardé le nom de son inventeur. Un chiffrement de Feistel est un chiffrement itéré qui utilise à chaque étage le même schéma, défini de la manière suivante : Soit f₁ une fonction de I_n={0,1 }ⁿ dans lui-même et x⁰, x¹, x², x³ quatre éléments de I_n. On définit le schéma de Feistel Ψ lié à f₁ sur I_2n = {0,1 }²ⁿ de la manière suivante :

∀(x0, x1) ∈ (In)2, Ψ(f1)[(x0, x1)] = (x2,x3) ⇔      x2 = x1 x3 = f1(x1) ⊕x0

Figure 1: Schéma de Feistel
Précisons quelques propriétés élémentaires de ce schéma [8] :

• Dans tous les cas et pour toute fonction f₁, Ψ(f₁) est une permutation de I_2n car on peut retrouver x⁰ et x¹ à partir de x² et x³ de façon unique :
  

  x2 = x1 et x3 = x0 ⊕f1(x1)   (1)

  donc on retrouve tout d'abord la valeur de x¹ puis celle de x³ grâce à la connaissance de x¹. Cette définition se généralise de la façon suivante : la fonction réciproque de Ψ(f₁) est très facile à calculer :
  

  Ψ(f1)−1 = σ°Ψ(f1) °σ

  où σ désigne la permutation de I²ⁿ qui inverse les parties droite et gauche d'un mot de I²ⁿ.

Ψ représente un schéma de Feistel sur un étage (voir figure 1). On peut alors généraliser la définition de Ψ à plusieurs étages comme cela est fait pour le DES : soit f₁, f₂,..., f_r, r fonctions de {0,1 }ⁿ vers {0,1 }ⁿ, on définit Ψ^r(f₁, …, f_r) de {0,1 }²ⁿ vers {0,1 }²ⁿ par :

Ψr(f1,...,fr) = Ψ(fr) °…°Ψ(f2) °Ψ(f1).

On définit ainsi un schéma de Feistel sur r étages. Précisons également que pour le DES, on a n=32 bits et que les blocs d'entrées sont donc de taille 64 bits.

  Des schémas modifiés

Nous venons de voir le schéma général de la fonction d'étage qui est utilisé dans le DES. Ce schéma possède plusieurs variantes tant dans la façon de placer la fonction f₁ que dans le nombre de blocs d'entrées. Dans le cas du DES, les blocs d'entrée sont découpés en deux afin de fournir x⁰ et x¹. On peut imaginer découper cette entrée en plus de blocs comme c'est le cas dans l'algorithme MARS [5] (figure 2) ou l'algorithme CAST-256 [3] (figure 3), deux candidats malheureux de la compétition AES qui s'est tenu entre 1997 et 2001 afin de choisir un nouvel algorithme de chiffrement symétrique américain pour le XXIème siècle.
Figure 2: Schéma de Feistel modifié pour l'algorithme MARS

Figure 3: Schéma de Feistel modifié pour l'algorithme CAST-256
On peut également citer ici le cas de MISTY [6] qui utilise une variante du schéma de Feistel, non pas en ce qui concerne le nombre de blocs d'entrée, mais pour la manière dont il fait agir la fonction f₁. Le schéma de MISTY est décrit à la figure 4. Cet algorithme a cependant révélé plusieurs faiblesses, plusieurs autres versions ont été proposé, notamment MISTY1, une version optimisée en hardware de ce chiffrement et nommée KASUMI qui est utilisé dans des modes particuliers (f8 pour la confidentialité et f9 pour l'intégrité [1]) pour les téléphones mobiles de troisième génération notamment dans la norme européenne UMTS [2].
Figure 4: Schéma de Feistel modifié pour les algorithmes MISTY et KASUMI
Nous venons donc de voir des schémas dérivés de celui de Feistel qui permettent de construire une fonction d'étage d'un algorithme de chiffrement par blocs itératifs. La question à se poser à présent est : de quoi doit être composée la fonction f₁ pour optimiser la confusion et la diffusion ? En général, cette fonction peut se décomposer en deux parties : une partie non linéaire qui va permettre une bonne confusion et une partie linéaire qui va permettre d'optimiser la diffusion et le mélange des bits d'entrée. La partie non linéaire est en général composée de "boîtes S", c'est à dire de permutations non linéaires qui agissent sur chaque sous-bloc de taille 4, 8 ou 16 bits et qui permettent de casser la structure linéaire du chiffrement. La deuxième fonction qui compose f₁ est une application linéaire chargée de maximiser la diffusion. Nous verrons des exemples pratiques de ces applications dans les sections suivantes.

 

Références

[1]

3rd Generation PartnerShip Project. "3gpp ts 35.201 - specification of the 3gpp confidentiality and integrity algorithms - document 1: f8 and f9 specification". http://www.3gpp.org/ftp/Specs/html-info/35201.htm, 2001.

[2]

3rd Generation PartnerShip Project. "3gpp ts 35.202 - specification of the 3gpp confidentiality and integrity algorithms - document 2: Kasumi specification". http://www.3gpp.org/ftp/Specs/html-info/35202.htm, 2001.

[3]

C. Adams and J. Gilchrist. "the cast-256 encryption algorithm". RFC 2612 - IETF, 1999.

[4]

I. Ben-Aroya and E. Biham. Differential cryptanalysis of lucifer. Journal of Cryptology, 9:21-34, 1996.

[5]

D. Coppersmith, C. Burwick, E. D'Avignon, R. Gennaro, S. Halevi, C. Jutla, S. Matyas Jr., L. O'Connor, M. Peyravian, D.Safford, and N. Zunic. Mars - a candidate ciphe for aes. In The First Advanced Encryption Standard Candidate Conference. N.I.S.T., 1998.

[6]

M. Matsui. New block encryption algorithm misty. In Fast Software Encryption'97, Haifa, Israël, pages 54-68. Lectures Notes in Computer Science 1267, Springer-Verlag, 1997.

[7]

National Bureau of Standards (États Unis). Data Encryption Standard. Federal Information Processing Standard, 1977. Publication 46.

[8]

J. Patarin. Etudes des Générateurs de Permutations Pseudo-aléatoires Basés sur le Schéma du DES. PhD thesis, Université Paris VI, 1991.