PICSI

Fonctionnement d'un algorithme de chiffrement par bloc

De façon générique, on décrit un algorithme de chiffrement par blocs E comme une application de l'espace des messages M et de l'espace des clés K vers l'espace des textes chiffrés C où la relation E_K(m)=c est vérifiée pour l'ensemble des éléments des différents ensembles. Donc E_K doit être une permutation pour toutes les clés possibles K. De plus, l'algorithme de déchiffrement correspondant D_K qui permet de déchiffrer c avec la même clé K doit vérifier : D_K(c)=m c'est à dire ∀m,   D_K(E_K(m))=m autrement dit D_K = E⁻¹_K pour toute clé K dans K. Donc la permutation de chiffrement E_K paramétrée par la clé K doit également être facile à inverser. De plus, la clé K doit être prise dans un espace suffisamment grand pour se prémunir contre la recherche exhaustive (essayer toutes les clés). Par exemple dans le cas de l'AES, K est de taille 128, 192 ou 256 bits, ce qui fait que la recherche exhaustive nécessite 2¹²⁸, 2¹⁹² ou 2²⁵⁶ essais, cette dernière borne étant très proche du nombre d'atomes présents dans l'univers. Nous allons nous intéresser ici à la construction de la fonction E_K. Pour répondre aux exigences de la cryptographie symétrique, un algorithme de chiffrement par blocs E_K doit satisfaire plusieurs propriétés. Rappelons les plus importantes : l'algorithme doit être facilement calculable et inversible pour n'importe quelle valeur de la clé, tout en offrant une bonne sécurité pratique.
Les méthodes de construction restent très empiriques mais la plus usitée est l'utilisation d'algorithmes itératifs. Ces algorithmes sont composés de r étages et à chaque étage, ils font agir la même fonction f paramétrée par une sous-clé K_i. Les sous-clés K₁,..., K_r sont différentes à chaque étage et générées à partir de la clé secrète K et d'un algorithme de génération de sous-clés (voir figure 1).
Figure 1: Structure Générale d'un Chiffrement par Blocs Itératif
Notons que, mis à part quelques cas pathologiques, plus le nombre d'étages est grand, plus on augmente la diffusion (faire en sorte que chaque bit de sortie soit influencé par le plus grand nombre possible de bits d'entrée) et la confusion (faire disparaître les structures tant linéaires qu'algébriques du chiffrement) selon les principes décrits par Shannon dans [1]. Dans ce cas, le principal défi reste la construction de la fonction d'étage f. C'est à cette étape que nous allons à présent nous intéresser en présentant les fonctions de tour les plus usitées.

 

Références

[1]

C.E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28:656-715, 1949.

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.

Les réseaux de substitution-permutation

Un réseau de substitutions-permutations est également un système de chiffrement itératif. A chaque étage, on applique au bloc d'entrée une substitution non linéaire puis une fonction généralement linéaire appelée abusivement permutation. Ces réseaux prennent au mot les deux concepts définis par Shannon. La substitution, en général représentée par une boîte S, garantit, si elle est bien choisie, une bonne confusion (faire disparaître les structures tant linéaires qu'algébriques du chiffrement) et la permutation garantit une bonne diffusion de l'information (faire en sorte que chaque bit de sortie soit influencé par le plus grand nombre possible de bits d'entrée). Précisons également que l'usage des mots substitution et permutation est abusif. On peut effectivement parler de substitution en ce qui concerne les boîtes S même si il peut y avoir confusion avec le terme de permutation mais le terme de permutation est beaucoup trop approximatif pour désigner l'application linéaire qui suit. Cependant, l'emploi de ces termes restent classique en cryptographie, nous continuerons donc à les utiliser dans la suite de ce paragraphe.

Ce réseau doit également vérifier ce qu'on appelle l'effet avalanche : les modifications du texte clair doivent être de plus en plus importantes au fur et à mesure que les données se propagent dans la structure de l'algorithme. De ce fait, en perturbant un seul bit en entrée, on obtient idéalement une sortie totalement différente, d'où le nom de ce phénomène. Si la diffusion des modifications des entrées sur les sorties n'est pas suffisamment grande, il sera possible d'établir des prédictions sur les entrées à partir de l'observation des sorties et donc d'obtenir un biais statistique. Le critère d'avalanche stricte a été introduit en cryptographie par Webster et Tavares en 1985 [1] comme une propriété des fonctions booléennes utilisées qui doit être vérifiée. Une fonction qui satisfait ce critère est telle que tout changement d'un bit d'entrée a une chance sur deux de modifier un bit de sortie ce qui permet d'uniformiser les sorties.
Deux exemples d'algorithmes de chiffrement utilisant des réseaux de substitutions-permutations sont la famille SAFER et l'AES.

 

Références

[1]

A. F. Webster and Stafford E. Tavares. On the design of s-boxes. In CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 523-534, 1985.

Génération de sous-clés

Intéressons nous à présent à l'autre partie importante d'un algorithme de chiffrement par blocs : la génération des sous-clés à partir de la clé secrète. Généralement, celle-ci peut se décomposer en deux étapes : l'expansion de la clé et la génération des sous-clés à partir de la clé étendue. Ces opérations sont en général très simples; on étend la clé secrète par des opérations élémentaires (permutation, décalage, addition de constante,...) en une clé étendue de longueur égale à la somme de celles de toutes les sous-clés. Puis, on "découpe" la clé étendue (de manière plus ou moins simple) en sous-clés.

Des exemples correspondants à ces cas de figures sont donnés dans la description du DES et de l'AES.