Imprimer

Introduction

Le masque jetable est le seul système cryptographiquement sûr et prouvable, à la condition que la clé ne soit utilisée qu'une seule fois.  Les problèmes avec ce masque jetable est la longueur de la clé et le fait que la clé ne pourra être utilisé qu'une seule fois.  Il est possible que ces difficultés sont compensés par la certitude que le système est sûr, mais ce n'est pas pratique.  Les deux difficultés mentionnées viennent du fait que la clé est mélangée au message avec une fonction de mixage simple: la fonction XOR ("or exclusif").  En fait, le message et la clé sont interchangeables.  Ainsi, quand on connaît la clé, on connaît le message (c'est l'idée) ; mais quand on connaît le message, on connaît la clé !  Ça vient du fait que le XOR est une opération réversible (la fonction inverse est le XOR même).  L'effort de calcul pour trouver la clé si on connaît le message n'est pas plus grand (en fait, identique) que l'effort de calcul pour trouver le message quand on connaît la clé (l'utilisation normale).

En tout cas, il nous faut un algorithme qui mélange la clé et le texte en clair pour produire un texte chiffré.  Si on veut avoir un système avec une clé ré-utilisable, alors il faut trouver un moyen de mélanger la clé et le texte en clair d'une telle façon, qu'il est facile de retrouver le texte en clair si on a la clé et le texte chiffré, mais qu'il est essentiellement infaisable comme effort de calcul de retrouver la clé quand on a le texte chiffré et le texte en clair.  En d'autres termes, le traitement de la clé et du texte en clair dans le mixer doit être totalement asymétrique, avec une technique pour trouver l'inverse dans une direction (l'algorithme de déchiffrement), et une impossibilité pratique pour trouver l'inverse dans l'autre direction.

Bien sûr, il existe toujours une technique de principe dans cette autre direction: en essayant toute clé possible.  C'est l'attaque de force brute.   L'idée c'est d'avoir des algorithmes de mixer où la force brute est la seule technique connue pour faire l'inversion interdite.

Ainsi on vient à notre définition d'un chiffrement par bloc: c'est une paire d'algorithmes implémentant deux fonctions mathématiques f et g, tel que:

  1. nous avons des arguments K (clé) de k bits, C (texte en clair) de n bits, et X (texte chiffré) de n bits
  2. X = f(K,C)
  3. C = g(K, X)
  4. X' = f(K',C) est a peu près corrélé 50% avec X, pour a peu près toute clé K' différente de K, et a peu près tout texte clair C.  Ceci veut dire qu'à peu près chaque bit du texte chiffré est fortement dépendant d'à peu près chaque bit de la clé.
  5. il n'y a pas d'algorithme connu qui peut implémenter la fonction K = h(C, X) mieux que par force brute ; en plus, il n'y a pas d'algorithme connu qui peut implémenter hm: K = hm(C1, X1, C2, X2, ... Cm,Xm) pour tout m, mieux que par force brute.

La dernière condition nécessite une explication.  Il est bien possible qu'avec la connaissance d'un texte chiffré et le texte en clair associé, il n'est pas possible de retrouver la clé, mais il est bien possible que quand on connaît beaucoup de paires de texte chiffré et texte en clair associé, cela devient possible.  Comme nous voulons pouvoir réutiliser la clé, cette attaque ne doit idéalement pas être possible.  La plupart des algorithmes connus commencent à faillir sur cette condition quand m devient extrêmement large, mais tant que m est suffisamment large, l'algorithme peut être utilisé: il suffit de changer de clé avant que m ne soit atteint.

Notez que la condition 4 est aussi nécessaire.  Effectivement, le chiffre trivial C = f(K,C) satisferait toutes les conditions, comme la clé n'est pas utilisée, elle n'est pas récupérable d'une "paire" de textes en clair et texte chiffré (identique).

Le chiffrement en bloc sera un composant primitif essentiel dans beaucoup d'applications cryptographiques, et non seulement pour la messagerie secrète symétrique.  Sa fonction essentielle est de mélanger de façon irréversible la clé et le bloc de données dans un sens, de telle façon qu'on peut seulement retrouver le texte en clair avec la clé, mais jamais retrouver la clé.  C'est la propriété nécessaire pour pouvoir réutiliser la clé.

Il est nécessaire que le chiffrement par bloc est une fonction non-linéaire f(K,C).  Effectivement, si f était linéaire, (comme l'opération XOR dans le masque jetable) alors le système d'équations linéaire dans 4 peut toujours être résolu par de l'algèbre linéaire.  Mais un système d'équations non-linéaires peut parfois être résolu aussi, donc il n'est pas suffisant que la fonction f(K,C) ne soit pas linéaire.  En fait, il n'y a pas de façon garantie pour construire une fonction f(K,C) qui satisfait nos conditions ; il n'y a pas de problèmes impossibles à résoudre non plus.  Ainsi, tout chiffrement par bloc est une sorte de pari que personne ne trouvera une fonction inverse pour la clé.  D'un autre coté, les chiffrements par bloc ne sont pas liés non plus à un problème dur mathématique connu (ce sera le cas pour la cryptographie asymétrique).    La plupart des chiffrements par bloc sont des façons compliquées de mélanger les bits les uns avec les autres tel que le résultat est une fonction extrêmement compliquée de la clé et du bloc de texte en clair, tel qu'il y ait une façon de retracer le texte en clair avec l'aide de la clé.

La nécessité d'une fonction inverse g(K,X) est une faiblesse centrale dans les chiffrements par bloc et en fait, cette réversibilité n'est pas nécessaire pour beaucoup d'applications ; mais par définition un chiffrement par bloc est réversible dans le sens C = g(K,X).   

Beaucoup d'algorithmes de chiffrement par bloc sont grosso modo structuré ainsi: il y a un algorithme de base qui mélange un bloc d'entré avec une clé (exactement comme le chiffrement par bloc en son ensemble).  Cet algorithme de base est répété en N tours, tel que la sortie de données d'un tour est l'entré du tour suivant et les clés de chaque tour sont dérivés de la clé principale.  L'algorithme de dérivation des clés de chaque tour de la clé principale s'appelle le schéma de clés.  Il est important que le schéma de clés ne dépend pas des données.  Ainsi, du coté du déchiffrage, on peut aussi bien calculer les clés des tours que pendant le chiffrage.  Si chaque tour peut être inversé (à l'aide de la clé de tour) alors le système entier peut être inversé, mais la relation entre le texte original en clair et le texte final chiffré manque toutes les étapes intermédiaires pour pouvoir attaquer un seul tour.

Un tour a deux fonctions: la confusion et la diffusion.  La confusion est une opération non-linéaire qui essaie de rendre impossible la séparation de la clé des données (la condition 5).  Diffusion échange et mélange les bits de telle façon que l'influence de chaque bit (dans le texte en clair, et dans la clé) se propage de façon plus ou moins uniforme dans tous les bits de la sortie.  Diffusion peut être linéaire et implémente la condition 4.

A part des considérations théoriques, il est souvent important que l'algorithme qui implémente les fonctions f et g soit efficace.  Le chiffrement en bloc est souvent utilisé pour traiter de grands volumes ou de flux importants de données.  Un exemple est le chiffrement du disque dur d'un système.  On peut juger l'efficacité pour des implémentations en dur, et pour des implémentations en logiciel.  Certains chiffrements en bloc sont optimisés pour l'implémentation en dur, d'autres sont plus orientés pour une implémentation logicielle.  La distinction entre les deux n'est d'ailleurs pas toujours évident.  Ainsi, AES (un des chiffrements en bloc les plus utilisés aujourd'hui) est maintenant implémenté dans plusieurs processeurs Intel en dur.  Du logiciel qui tourne sur ces processeurs peut utiliser des instructions logicielles pour utiliser ces fonctions en dur.  Bien sûr, avant de se voir implémenté en dur dans un processeur Intel, il faut qu'un chiffrement en bloc ait déjà une base d'utilisateurs importante !  On peut espérer qu'un chiffrement important sera étudié beaucoup, et que des faiblesses évidentes ou des attaques réussies seront rendu publique par la communauté de recherche.  D'un autre coté, plus grand est la base d'utilisateurs, plus grand devient le bonus pour casser le chiffrement en gardant cela bien secret pour l'exploiter.  Ainsi, une trop grande uniformisation d'utilisation d'un chiffrement n'est peut-être pas une très bonne idée non plus.

DES

DES est un chiffrement en bloc avec une longueur de bloc de 64 bit et une clé de longueur de 56 bits.  C'est un chiffrement très célèbre qui est utilisé depuis les années 1970.  Maintenant, DES est essentiellement remplacé par AES.  Il n'y a pas de problème avec DES, a part sa clé trop courte.  Le chiffrement original dont DES a été dérivé est Lucifer, avec une (bonne) longueur de clé de 128 bits, mais l'implication de la NSA a fait que la longueur de clé a été réduite à 56 bits, ce qui est considéré, aujourd'hui, comme trop court pour être sûr.  Une attaque force brute avec la puissance de calcul d'aujourd'hui fait que une clé DES peut être trouvée en moins de 7 jours avec un budget de l'ordre de $ 10 000, comme démontré par le système COPACOBANA en 2006, qui avait ce prix et qui est construit exprès pour casser des chiffrements DES par force brute.  La faiblesse de DES vient donc de sa clé trop courte, et non de son algorithme car il faut toujours appliquer la force brute.  La structure de l'algorithme est donc de très bonne qualité.

La structure générale de DES est comme ceci:

  1. une permutation initiale des bits de données
  2. 16 tours, avec 16 clés de 48 bits
  3. une permutation finale des bits de données

La permutation dans 3 est l'inverse de celle de 1.  Cette permutation initiale est:

58, 50, 42, 34, 26, 18, 10,  2, 60, 52, 44, 36, 28, 20, 12,  4, 62, 54, 46, 38, 30, 22, 14,  6, 64, 56, 48, 40, 32, 24, 16,  8,
57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 31, 31, 23, 15, 7

Il faut lire cette liste ainsi: après la permutation, le premier bit du nouveau bloc est l'ancien bit qui se trouvait à la position 58.  Le deuxième bit du nouveau bloc est l'ancien qui se trouvait à la position 50.  Etc...

Chaque tour a la structure suivante:

  1. Le bloc de données de 64 bit est coupé en un demi bloc gauche et un demi bloc droit.  Le demi bloc droit deviendra le demi bloc gauche de la sortie.
  2. Le demi-bloc droit entre aussi la fonction f, ensemble avec la clé du tour de 48 bits (il y a 16 clés de tour car il y a 16 tours).
  3. De cette fonction f sort un mot de 32 bits, qui sera XORé avec le demi-bloc de gauche de départ.  Ce résultat deviendra le demi-bloc droit de sortie.

La structure ci-dessus est un principe général dans la construction de chiffrements en bloc et porte le nom de son inventeur: Horst Feistel: c'est un réseau Feistel.  Un réseau Feistel est réversible car chaque tour est réversible quand on connaît la clé: la clé de tour permet de ré-appliquer la fonction f, car les données utilisées sont intacts dans la sortie du tour, et l'opération XOR est aussi réversible, ce qui permet de reconstruire la partie gauche.  Notez qu'il n'est pas nécessaire (et d'ailleurs dangereux) d'inverser la fonction f.  C'est la fonction f qui protège la clé.  En échangeant la partie gauche et droite, on s'assure que les deux parties seront chiffrées.  Le fait que les données se mélangent entre eux (la moitié gauche se mélange avec la moitié droite modifiée) introduit de la non-linéarité vis-à-vis les données, et la fonction f qui est hautement non-linéaire introduit de la non-linéarité vis-à-vis la clé.  Bien sûr, toute l'ingénuité de DES se trouve dans la fonction f. 

La fonction f va ainsi:

  1. Les données (32 bit) sont élargies en 48 bits (avec répétitions)
  2. ces 48 bits sont XORés avec la clé de tour (aussi 48 bits)
  3. le résultat de 48 bit est coupé en 8 mots de 6 bits chacun
  4. Chaque mot de 6 bits passera dans une fonction 6 bits vers 4 bits, donné par des tableaux, appelés S-box.
  5. Les 8 mots de sortie de 4 bits sont recombinés en un mot de 32 bits: c'est la sortie.

L'expansion des 32 bit en 48 bit va selon la liste suivante:

32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17, 
18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1

avec la signification suivante: dans le mot de 48 bits, le premier bit est le 32-ième (le dernier) du mot de 32 bits d'entrée ; le deuxième bit du mot de 48 bits est le premier bit du mot d'entrée, etc.... le dernier bit du mot de 48 bit est de nouveau le premier bit d'entrée.

Il y a 8 S-box différent, un pour chacun des mots de 6 bits dans l'étape 4.  Ces S-box sont juste des tableaux et il n'y a pas de justification particulière, mais il se trouve qu'ils ont été construits spécialement pour résister à une attaque qui s'appelle "analyse différentielle".  Chaque S-box est un tableau avec 64 entrées, contenant un mot de 4 bits.

La façon standard de montrer ces tableaux est assez originale: les 4 bits du milieu du mot de 6 bits font le numéro de colonne (de 0 à 15, 4 bits non signés), le premier et le dernier bit ensemble font le numéro de colonne (de 0 à 3, 2 bits non signés).

S-box 1 est:

     14  4  13  1   2 15  11  8   3 10   6 12   5  9   0  7
      0 15   7  4  14  2  13  1  10  6  12 11   9  5   3  8
      4  1  14  8  13  6   2 11  15 12   9  7   3 10   5  0
     15 12   8  2   4  9   1  7   5 11   3 14  10  0   6 13 

S-box 2 est:

     15  1   8 14   6 11   3  4   9  7   2 13  12  0   5 10
      3 13   4  7  15  2   8 14  12  0   1 10   6  9  11  5
      0 14   7 11  10  4  13  1   5  8  12  6   9  3   2 15
     13  8  10  1   3 15   4  2  11  6   7 12   0  5  14  9

S-box 3 est:

     10  0   9 14   6  3  15  5   1 13  12  7  11  4   2  8
     13  7   0  9   3  4   6 10   2  8   5 14  12 11  15  1
     13  6   4  9   8 15   3  0  11  1   2 12   5 10  14  7
      1 10  13  0   6  9   8  7   4 15  14  3  11  5   2 12

S-box 4 est:

      7 13  14  3   0  6   9 10   1  2   8  5  11 12   4 15
     13  8  11  5   6 15   0  3   4  7   2 12   1 10  14  9
     10  6   9  0  12 11   7 13  15  1   3 14   5  2   8  4
      3 15   0  6  10  1  13  8   9  4   5 11  12  7   2 14

S-box 5 est:

      2 12   4  1   7 10  11  6   8  5   3 15  13  0  14  9
     14 11   2 12   4  7  13  1   5  0  15 10   3  9   8  6
      4  2   1 11  10 13   7  8  15  9  12  5   6  3   0 14
     11  8  12  7   1 14   2 13   6 15   0  9  10  4   5  3

S-box 6 est:

     12  1  10 15   9  2   6  8   0 13   3  4  14  7   5 11
     10 15   4  2   7 12   9  5   6  1  13 14   0 11   3  8
      9 14  15  5   2  8  12  3   7  0   4 10   1 13  11  6
      4  3   2 12   9  5  15 10  11 14   1  7   6  0   8 13

S-box 7 est:

      4 11   2 14  15  0   8 13   3 12   9  7   5 10   6  1
     13  0  11  7   4  9   1 10  14  3   5 12   2 15   8  6
      1  4  11 13  12  3   7 14  10 15   6  8   0  5   9  2
      6 11  13  8   1  4  10  7   9  5   0 15  14  2   3 12

S-box 8 est:

     13  2   8  4   6 15  11  1  10  9   3 14   5  0  12  7
      1 15  13  8  10  3   7  4  12  5   6 11   0 14   9  2
      7 11   4  1   9 12  14  2   0  6  10 13  15  3   5  8
      2  1  14  7   4 10   8 13  15 12   9  0   3  5   6 11

Pour illustrer comment ces S-box sont utilisés, supposez que le 5ième mot de 6 bits est 100110.  Les deux bits extrêmes sont 1 et 0, formant le mot 10, donc le numéro 2.  C'est la troisième rangée quand on commence à compter à partir de 1 de la 5ième S-box.  Les 4 bits du milieu sont 0011, donc le numéro 3.  C'est donc la 4ième colonne si on commence à compter à partir de 1.  Ainsi, l'entrée dans le tableau est: 11 (onze).  En binaire, cela s'écrit: 1011.  Ainsi, le résultat de la S-box sur le mot de 6 bits 100110 est 1011.

Ceci complète le descriptif de la transformation de données dans le chiffrement en bloc DES.  Nous devons encore décrire le schéma de clés: comment dériver les 16 clés de tour de 48 bits de la clé principale de 56 bits ?

Même si DES est un chiffrement avec une clé de 56 bits, il est défini comme utilisant une clé de 64 bits, donc de 8 octets, ou le dernier bit de chaque octet est le bit de parité (et ne contient donc pas d'entropie supplémentaire).  Le bit de parité lui-même ne participe pas dans la manipulation de la clé, mais il faut s'imaginer donc un mot de clé fait de 64 bits.  A ce mot de 64 bits, on applique une transformation des bits, appelée PC-1, qui extrait un mot de 56 bits (remarquez que les multiples de 8 n'apparaissent donc pas dans cette transformation):

57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18, 10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4

Ensuite, ce mot de 56 bits est coupé en deux mots de 28 bits.  Ces deux mots vont passer de façon indépendante dans 16 étages pour fabriquer les 16 clés de tour.

Chaque stage fait la chose suivante:

  1. Si nous sommes dans les stages 1, 2, 9 et 16, alors chaque mot de 28 bit est tourné un bit sur la gauche, sinon, il est tourné 2 bits sur la gauche.
  2. Les deux mots de 28 bits sont passés à l'étage suivante
  3. Les deux mots sont aussi combiné en un mot de 56 bits, et 48 bits en sont extrait avec la transformation PC-2 pour faire la clé du tour en question.

PC-2 va ainsi:

14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10, 23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2, 
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32

En d'autres termes, chaque clé de tour n'est rien d'autre qu'une sélection de 48 bits des 56 bits de la clé principale.  Il n'y a pas d'opérations logiques ou arithmétiques, seulement de la sélection.  En dur, ceci est bien sûr extrêmement rapide: ce ne sont que des fils !  La "rotation vers la gauche" n'est pas une opération réelle, c'est juste une façon pour décrire la sélection de bits.  Ainsi, les 16 clés de tour sont "disponible immédiatement avec des fils" quand la clé principale est donnée.

Étant donné le réseau Feistel, le déchiffrement fonctionne de la même façon que le chiffrement, mais dans l'ordre inverse.

Variantes 3-DES

DES étant un très bon chiffrement en bloc, son seul problème est la clé trop courte.  Il y a, cependant, des façons simples de changer un chiffrement en bloc avec une clé courte, en un chiffrement en bloc avec une clé bien plus longue.  Ces techniques sont assez universels, mais sont surtout intéressant pour DES, où le seul problème réside dans la longueur de clé et que l'algorithme est très sûr (toujours après 40 ans d'attaques).

Il y a de bonnes raisons pourquoi doubler un chiffrement en bloc ne marche pas bien: il y a une attaque générale sur le double chiffrement qui s'appelle "tableau arc-en-ciel" qui rend le double chiffrement presque identique à un chiffrement unique.  C'est pourquoi il est nécessaire de considérer au moins un chiffrement triple.

La première variante a une clé [ k0, k1, k2 ] de longueur 3 x 56 = 168 bit.  C'est une succession de 3 chiffrements DES:

X = DES (k3, DES (k2, DES (k1, C) ) )

Dans son ensemble, ceci fonctionne comme un chiffrement en block sur des données de 64 bit et une clé de 168 bits.

La deuxième variante ressemble à la première, mais le "chiffrement" du milieu est un DES en mode déchiffrement:

X = DES (k3, DES-1 (k2, DES(k1, C) ) )

Ce chiffrement est très semblable au premier, mais il a l'avantage particulier que quand k3 = k2 = k1 = k, le deuxième se réduit à un chiffrement DES standard.  C'est un (petit) avantage de pouvoir utiliser une implémentation identique pour deux chiffrements: un triple DES, ou un DES standard, selon le choix des clés.  Il peut être intéressant de basculer sur du DES standard dans des applications qui doivent pouvoir garder une compatibilité avec le passé.  Par contre, il faut toujours faire attention avec cette "compatibilité avec le passé", s'il s'agit de protocoles qui ne sont plus sûrs, car si un attaquant peut forcer le système dans ce mode, cela lui rend la vie plus facile.

Les deux variantes de triple-DES impliquent un triple calcul du chiffrement en bloc DES.  DES étant relativement efficace à implémenter, cela n'est pas une grande difficulté, mais il y a une variante bien plus rapide:

X = DES(k1, C XOR ka) XOR kb

Ici, la clé totale est [k1, ka, kb] où ka et kb ont une longueur de 64 bits chacune, nous avons donc un chiffrement en bloc avec un bloc de 64 bit, et une clé de 184 bit.

Triple DES souffre d'une attaque similaire que le double chiffrement, à savoir une attaque arc-en-ciel, mais avec le triple chiffrement, on peut sauver deux des trois clés.  Ainsi, la vraie sécurité de triple DES est plutôt 112 bits au lieu des 168 bits de la clé.  La troisième variante est plus rapide et robuste contre cette attaque.  C'est donc largement le chiffrement à préférer si on veut continuer à utiliser DES.  Il y a une attaque connue théoriquement, si on possède un nombre déraisonnable de paires (texte en clair, texte chiffré), mais comme cette attaque n'est pas réaliste, on peut considérer cette variante de DES comme toujours utilisable..

AES (ou Rijndael)

AES est le standard qui remplace DES.  Rijndael était le gagnant d'un concours ouvert organisé par NIST entre 1997 et 2001, pour trouver un remplacement de DES.  Il y avait d'autres finalistes dans cette compétition, de qualité comparable, comme Mars, Serpent et Twofish.  La prescription NIST était pour un chiffrement en bloc avec des longueurs de bloc de 128 bit et des clés de 128, 192 et 256 bits.  La proposition originale de Rijndael peut aussi recevoir des blocs de données de 192 et 256 bit, mais le concours du NIST ne considérait que 128 bits et les deux autres options n'ont pas été inclus dans le standard.  Ainsi, AES a 3 versions, correspondant aux trois longueurs de clé.

AES est, comme tous les autres chiffrements en bloc, une succession de tours, chaque tour ayant une clé de tour.  Le nombre de tours dépend de la version de longueur de clé: pour une clé de 128 bit, il y a 10 tours, pour une clé de 192, il y en a 12, et pour une clé de 256, il y en a 14.  Il y a une clé de tour en plus que le nombre de tours, car une clé est utilisé pour un pré-blanchiment: une clé qui sera XORé avec le texte en clair.

AES n'est pas un réseau Feistel.  Chaque tour a la structure générale suivante:

  1. le bloc de 128 bits est divisé en 16 octets (on peut dire que AES est plutôt orienté octet que orienté bit)
  2. L'unique S-box s'applique à chaque octet.  C'est une relation octet-octet
  3. Les 16 octets de sortie seront permutés en ce qui s'appelle l'opération Shift Row
  4. Les 16 octets résultants sont groupés en 4 groupes de 4 octets ; chaque groupe est multiplié par une matrice 4x4 pour donner 4 nouveaux octets.  Cette opération s'appelle opération Mix Column.
  5. Les groupes de 4 octets sont mis ensemble pour former un nouveau mot de 128 bits.  Ce mot est XORé avec la clé de tour de 128 bits.  Le résultat est la sortie du tour.

Le dernier tour n'a pas l'opération Mix Column.

Dans la mesure où DES était très ad hoc (ou au moins, le système derrière DES n'a jamais été rendu public ou découvert s'il existe), il y a beaucoup de mathématiques derrière les opérations de AES.  Beaucoup d'opérations en AES sont basées sur les opérations dans le champs Galois GF(28), ce qui explique l'orientation octet de AES.  La représentation de ce champs Galois est basé sur le polynôme irréductible:

P(x) = x8 + x4 + x3 + x + 1

En d'autres termes, un octet est représenté par les coefficients dans le champs binaire de polynômes du type a7 x7 + a6 x6 + ... + a1 x + a0 et les opérations sont des opérations formelles modulo P(x).

La S-box de AES c est faite des opérations suivantes:

En suite, on applique en GF(2), la fonction affine y = A u + B

où A est une matrice 8x8 et B est un vecteur de 8 bits.  On rappelle que l'algèbre est simplement en GF(2).  La matrice A est:

1 0 0 0 1 1 1 1 
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1

(on peut reconnaître un système...) et le vecteur B est:

1
1
0
0
0
1
1
0

La transformation affine est absolument nécessaire pour "casser" la simplicité mathématique de la S-box (une simple inversion dans le champs Galois), et pour faire en sorte que 0 ne reste pas 0.

La shift rows operation est simplement une permutation des 16 octets dans le bloc de données, avec le tableau de permutation (de 0 à 15) suivant:

0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11

En d'autres termes, l'octet numéro 0 dans la sortie est l'octet numéro 0 dans l'entrée ; l'octet numéro 1 dans la sortie est l'octet numéro 5 dans l'entrée ; etc...

 

La MixColumn operation fonctionne ainsi.  Les 16 octets de la sortie de l'opération shift rows sont combinés en 4 groupes de 4 octets.  On fait un vecteur de 4 octets de chaque groupe. On applique la multiplication par la matrice à ce vecteur, où il faut considérer que cette multiplication se fait dans GF(28).  En notation polynomiale, la matrice prend la forme:

 x   x+1   1   1
1 x x+1 1
1 1 x x+1
x+1 1 1 x

Il faut donc voir la multiplication comme une multiplication de polynômes formels, modulo le polynôme P(x) mentionné avant.

Ceci complète le descriptif de la transformation de données dans AES.  Il faut maintenant venir au schéma de clé.  En fait, les schéma de clé sont un peu différent pour la version 128 bit, 192 bit et 256 bit.  Nous allons nous limiter à la version 128 bit.  Il faut donc fabriquer 11 clés de 128 bit à partir de la clé d'origine de 128 bits.

La première clé de tour est en fait la clé principale elle-même.  Ensuite, il y a 10 tours du schéma de clés, qui vont transformer cette clé à chaque étape.  Les 10 tours ont la même structure:

  1. La clé de tour précédente est coupée en 4 mots de 32 bits
  2. Le dernier mot de 32 bits est envoyé dans une fonction "g" qui est une fonction 32-bit en 32-bit ; le résultat est XORé avec le premier mot
  3. le résultat est le nouveau premier mot de la nouvelle clé de tour
  4. Le même mot est XORé avec le deuxième mot de l'ancienne clé, pour former le deuxième mot de la nouvelle clé
  5. Le nouveau deuxième mot est XORé avec le troisième mot de l'ancienne clé, pour former le troisième mot de la nouvelle clé
  6. Ce troisième nouveau mot est XORé avec le quatrième mot de l'ancienne clé (déjà utilisé en 2) pour former le quatrième mot de la nouvelle clé.

La fonction g même dépend du numéro de tour, mais a la structure suivante:

  1. Le mot entrant de 32 bits est coupé en 4 octets
  2. Ces 4 mots sont tournés, de telle façon que si le mot entrant était B0 B1 B2 B3, alors le résultat est B1 B2 B3 B4
  3. Chacun de ces octets est passé par la même S-box que dans la transformation des données
  4. Le premier octet de ce mot est ensuite XORé avec le coefficient de tour, qui dépend du numéro de tour
  5. Le résultat (avec ce premier octet modifié) est le résultat de la fonction g.

Les 10 coefficients de tour sont à voir en GF(28) comme x0, x1, x2, ... x9 (donc en prenant cette expression modulo P(x) ).  En d'autres termes, le premier coefficient de tour est 0000 0001, le deuxième est 0000 0010, mais le dernier est 0011 0110 (car x9 n'est pas trivial dans GF(28) ).

Beaucoup de choix dans Rijndael ont un fond mathématique, comme on peut voir, et ceci est parfois vu comme une faiblesse potentielle avec ce chiffrement, car il est peut-être possible d'exploiter ces propriétés mathématiques.  D'un autre coté, des choix mathématiques sont plus "ouverts" que des tableaux choisis sur une base obscure dont on ne sait pas pourquoi ils ont été faits comme ça.  Il y avait des soupçons (finalement infondés) sur le choix des S-box de DES: est-ce qu'ils contiennent une porte dérobée ?  Il n'y a pas de porte dérobée dans un choix mathématique clairement affiché, car tout le monde pourrait alors potentiellement la trouver.  Des maths clairs ne contiennent pas une clé cachée qui ne serait pas accessible aux autres.

SERPENT

Serpent était le deuxième finaliste du concours AES.  Il est généralement accepté que Serpent est potentiellement plus sûr que Rijndael ; Serpent a perdu la compétition parce que son implémentation était plus lente, et que l'argument de sécurité est seulement intuitif, et non établi.  La critique essentielle de Rijndael est que sa structure mathématique est trop simple, même si en se moment, aucune attaque exploitant cela est connue publiquement ; on pense seulement que la structure mathématique de Rijndael, peut, un jour, inspirer une attaque.  Il est généralement accepté que Serpent a un bien meilleur score sur ce sentiment intuitif.

Serpent, étant aussi une soumission à la compétition AES, a une longueur de bloc de 128 bits, et une longueur de clé de 256 bits.  Si on veut utiliser des clés plus petites, il y a un schéma de complétion: on ajoute un bit "1" à gauche de la clé, et on ajoute autant de bit "0" à droite pour arriver à 256 bits.  Ainsi, toute longueur de clé plus petite que 256 est possible, et donc les trois cas demandés par le concours AES, à savoir 128, 192 et 256, aussi.  Nous allons considérer donc la clé de 256 bits.

La structure générale est:

  1. une permutation initiale du bloc de données
  2. 32 tours
  3. une permutation finale du bloc de données

Chaque tour est fait de:

  1. un étage de mélange avec la clé de tour
  2. une couche de substitution non-linéaire
  3. une couche de mélange linéaire (sauf dans la dernière couche: là, il y a un dernier étage de mélange avec une clé de tour)

L'étage de mélange de clé est classique: un XOR avec la clé de tour de 128 bits.

La couche de substitution consiste en l'application de S-box de 4 bit en 4 bit ; on coupe le mot de données de 128 bit en 32 mots de 4 bit, et on applique 32 fois la S-box.   Par tour, on applique la même S-box aux 32 mots, mais la S-box est dépendante du numéro de tour.  Il y a 8 S-box différents.  Si on compte les tours de 0 à 31, alors tour 0 utilisera la S-box 0, tour 1 utilisera S-box 1, ... tour 7 utilisera S-box 7, et tour 8 utilisera de nouveau S-box 0, et ainsi de suite.  Le numéro du tour, modulo 8, donnera le numéro de la S-box à utiliser et chaque S-box sera donc utilisé 4 fois sur les 32 tours.

Les auteurs de Serpent ont spécifié un algorithme assez complexe pour déduire les 8 S-box des S-box du chiffrement DES.  Ainsi, personne ne soupçonnerait que les S-box avaient un souci de porte dérobée, et on pouvait quand-même utiliser les très bonnes propriétés des S-box de DES.  Finalement, voici donc les S-box de Serpent:

S0:   3  8 15  1 10  6  5 11 14 13  4  2  7  0  9 12
S1:  15 12  2  7  9  0  5 10  1 11 14  8  6 13  3  4
S2:   8  6  7  9  3 12 10 15 13  1 14  4  0 11  5  2
S3:   0 15 11  8 12  9  6  3 13  1  2  4 10  7  5 14
S4:   1 15  8  3 12  0 11  6  2  5  4 10  9 14  7 13
S5:  15  5  2 11  4 10  9 12  0  3 14  8 13  6  7  1
S6:   7  2 12  5  8  4  6 11 14  9  1 15 13  3 10  0
S7:   1 13 15  0 14  8  2 11  7  4 12 10  9  3  5  6

La couche de mélange linéaire va ainsi.  Les 128 bit du bloc de données est coupé en 4 mots de 32 bits.  Nous allons décrire les transformations que ces mots subissent avec une forme de pseudo-code, où nous considérons 4 variables de mots de 32 bits: X0, X1, X2, X3.  Au départ, les 4 mots sont assignés aux 4 variables.  Ensuite:

  1. X0 est tourné à gauche de 13 bits
  2. X2 est tourné à gauche de 3 bits
  3. X1 devient le XOR de X1, X0 et X2
  4. X3 devient le XOR de X3, X2 et (X0 tourné à gauche de 3 bits)
  5. X1 est tournè 1 bit à gauche
  6. X3 est tourné 7 bits à gauche
  7. X0 est le XOR de X0, X1 et X3
  8. X2 devient le XOR de X2, X3 et (X1 tourné à gauche de 7 bits)
  9. X0 est tourné 5 bits à gauche
  10. X2 est tourné 22 bits à gauche

Le mot de sortie est bien sûr la concaténation du contenu de  X0, X1, X2 et X3.  La transformation linéaire est construite de telle façon que chaque bit de donnée aura influencé chaque bit de sortie après trois tours.

Finalement, la permutation initiale est:

0  32  64  96   1  33  65  97   2  34  66  98   3  35  67  99
4  36  68 100   5  37  69 101   6  38  70 102   7  39  71 103
8  40  72 104   9  41  73 105  10  42  74 106  11  43  75 107
12  44  76 108  13  45  77 109  14  46  78 110  15  47  79 111
16  48  80 112  17  49  81 113  18  50  82 114  19  51  83 115
20  52  84 116  21  53  85 117  22  54  86 118  23  55  87 119
24  56  88 120  25  57  89 121  26  58  90 122  27  59  91 123
28  60  92 124  29  61  93 125  30  62  94 126  31  63  95 127

et la permutation finale est:

0   4   8  12  16  20  24  28  32  36  40  44  48  52  56  60
64  68  72  76  80  84  88  92  96 100 104 108 112 116 120 124
1   5   9  13  17  21  25  29  33  37  41  45  49  53  57  61
65  69  73  77  81  85  89  93  97 101 105 109 113 117 121 125
2   6  10  14  18  22  26  30  34  38  42  46  50  54  58  62
66  70  74  78  82  86  90  94  98 102 106 110 114 118 122 126
3   7  11  15  19  23  27  31  35  39  43  47  51  55  59  63
67  71  75  79  83  87  91  95  99 103 107 111 115 119 123 127

Ceci finalise la description des transformations de donnée de Serpent.  Nous allons maintenant décrire le schéma de clés.  Ce schéma de clés doit produire 33 clés de tour de 128 bits (il y a 32 tours, et le dernier tour nécessite 2 clés).

La clé principale de 256 bit est coupée en 8 mots de 32 bits, qu'on appelle w-8, w-7 ... w-1.

Une formule d'itération produira 132 mots de 32 bits:

wi := (wi-8 XOR wi-5 XOR wi-3 XOR wi-1 XOR φ XOR i) tourné à gauche de 11 bits

φ est un mot constant qui est, en hexadécimal: 0x9E3779B9 et c'est la partie fractionnelle du nombre d'or. ; i est le numéro du tour en format non-signé 32 bits.   Quand nous avons nos 132 mots  wi avec i positif, nous les combinons 4 par 4, dans des mots de 128 bits, nous obtenons 33 mots de 128 bits.  A ces mots, nous appliquons les S-box.  Nous appliquons la même S-box au 32 différents morceaux de 4 bits d'un mot, de façon comparable à ce que nous faisions avec les données.  L'ordre dans lequel chacun des 33 mots utilise une S-box est particulière: S-box numéro 3 est appliquée au premier mot (fait de w0, w1, w2 and w3).  S-box numéro 2 est appliqué au deuxième mot (fait de w4, w5, w6, and w7).  S-box 1 au troisième mot et S-box 0 au quatrième mot.  En suite S-box 7 est appliquée au 5ième mot, S-box 6 au sixième etc.... 

Le résultat de l'application des S-box à chacun des 33 mots de 128 bits, produit 33 mots de 128 bits: les clés de tour.  Ceci complète la description du chiffrement en bloc Serpent.

Twofish

Twofish est une variante de Blowfish, et aussi un des finalistes du concours AES.  Twofish a une approche très conservatrice, avec un réseau Feistel.  Twofish est orienté mots de 32 bits.

La structure générale de Twofish est ainsi:

  1. Le bloc de données est considéré comme 4 mots de 32 bits et les 4 premiers mots de 32 bits du schéma de clés sont utilisés pour blanchir le texte en clair.
  2. 16 tours Feistel sont appliqués
  3. Un dernier swap des deux premiers, et des deux derniers mots de 32 bit défait le swap de sortie du 16ième et dernier tour
  4. Les 4 mots de 32 bits 5, 6, 7 et 8 du schéma de clés sont utilisés pour blanchir le texte chiffré

Un tour va ainsi:

  1. Comme c'est un réseau Feistel, les deux premiers mots de 32 bits deviennent les 2 derniers mots
  2. Le premier mot de 32 bits entre la fonction g
  3. Le deuxième mot de 32 bits est tourné de 8 bits sur la gauche, et entre aussi la fonction g
  4. Les sorties des étapes 2 et 3 subissent une pseudo-transformation Hadamard (PHT)
  5. Deux clés de tour de 32 bits sont sommés aux sorties de cette PHT (somme modulo 232)
  6. Le premier mot du résultat de 5 est XORé avec le troisième mot d'entrée et le résultat est tourné 1 bit sur la droite
  7. Le deuxième mot du résultat de 5 est XORé avec le quatrième mot d'entrée, qui est lui, tourné d'abord 1 bit sur la gauche
  8. Les sorties de 6 et 7 deviennent le premier et le deuxième mot de sortie

Le schéma de clés a besoin de 8 mots de 32 bit pour le blanchiment d'entrée et sortie, et il faut 2 clés de 32 bit par tour.  Il y a 16 tours.  Cela fait donc 40 clés de 32 bit à générer.

La pseudo-transformation de Hadamard va ainsi.  Si A et B sont deux mots de 32 bits, alors ils sont transformés en A', et B':

A' = A + B mod 232

B' = A + 2B mod 232

La fonction g transforme un mot de 32 bit en un autre mot de 32 bit.  Il en va ainsi:

  1. Le mot est coupé en 4 octets
  2. Il y a 4 S-box différents appliquées à chaque octet ; les S-box sont des fonctions de 8 bit en 8 bit
  3. Aux 4 octets sortants, on applique une transformation MDS

La transformation MDS est une multiplication d'un vecteur de 4 octets par une matrice 4 x 4 dans le champs Galois GF(28), similaire à ce qui est fait dans Rijndael.  Les octets sont vus comme des éléments de GF(28), donc avec des bits qui sont des coefficients de polynômes formels.  La différence avec Rijndael se trouve dans le polynôme irréductible:

P(x) = x8 + x6 + x5 + x3 + 1.

La matrice de transformation est la suivante:

01  EF  5B  5B
5B EF EF 01
EF 5B 01 EF
EF 01 EF 5B

Où il faut interpreter cette notation hexadécimale d'octets comme des coefficients de polynômes.  Ainsi, 5B devient x6 + x4 + x3 + x + 1 (car 5B est 0101 1011).

Les transformations de données de Twofish sont ainsi décrites.  Il faut venir maintenant au schéma de clé et les S-box.  La spécificité de Twofish est que les S-box sont dépendants de la clé, et font donc partie du schéma de clés.  Le fait d'avoir des S-box différents selon les clés implique qu'aucune propriété particulière des S-box ne pourra être exploitée, ce qui est considéré comme une résistance augmentée de Twofish contre certains types d'attaque (des attaques différentiels d'ordre supérieur).

Le schéma de clés de Twofish est compliqué.  En fait, l'idée est que ce schéma de clés ne doit être exécuté qu'une fois par clé, tandis que le chiffrement ou le déchiffrement de données sera fait plusieurs fois.  Ainsi, avoir une transformation simple de données et un schéma de clés compliqué est une façon efficace d'augmenter la sécurité, en transférant la difficulté de calcul dans le schéma de clés.

Les schémas de clés sont légèrement différents selon qu'on ait des clés de 128, 192 ou 256 bits.  Nous allons discuter le schéma avec la clé de 256 bits.

La clé d'origine contient donc 8 mots de 32 bits.  On déduit d'abord 3 vecteurs de 128 bits: M0, M1 et S.  M0 contiendra les mots pairs de 32 bits de la clé principale, et M1 contiendra les mots impairs de 32 bits de la clé principale.  M0 et M1, chacun long de 128 bits, serviront dans la génération des clés de tour.

La constitution du mot S sera bien plus compliqué.  Il faut voir ce mot d'un ensemble de 4 mots de 32 bits, et ces mots serviront dans la construction des S-box.

La clé principale est coupée en 4 blocs de 64 bits (donc 8 octets).  A chaque bloc de 8 octets, on applique la matrice suivante:

 
01   A4   55   87   5A   58   DB   9E
A4   56   82   F3   1E   C6   68   E5
02   A1   FC   C1   47   AE   3D   19
A4   55   87   5A   58   DB   9E   03

Cette multiplication se fait dans le champs Galois GF(28) avec le polynôme irréductible:

P(x) = x8 + x6 + x3 + x2 + 1

Notez que ce polynôme est différent du polynôme pour représenter le même champs Galois dans la transformation MDS.  Les octets dans le bloc de 64 bit doivent être interprétés comme des coefficients de polynômes dans le champs Galois, et les octets dans la matrice, aussi.

Comme la matrice n'est pas carré mais rectangulaire (et dérivée d'un code Reed-Solomon), le résultat de l'application de cette matrice à un mot de 64 bits (donc 8 octets) résultera en un mot de 4 octets, donc 32 bits.  Comme il y avait 4 mots de 64 bits au départ dans la clé principale, cela nous donne, en appliquant 4 fois cette matrice, les mots S0, S1, S2 et S3

Ces 4 mots serviront dans la définition implicite des 4 S-boxes.   Une fonction est définie qui, appliquée à un mot de 32 bits X, donne un mot de 32 bits Y, tel que elle est en fait octet par octet.  Cela veut dire que le deuxième octet de Y ne dépend que du deuxième octet de X, et pas du troisième, ni du premier.  La fonction de 32 bits est donc en fait quatre fonctions d'un octet: ces 4 fonctions sont, justement, les S-box dépendant de la clé.  La fonction de 32 bits vers 32 bits s'appellera la fonction h.  Elle va ainsi:

  1. X est coupé en 4 octets
  2. A ces 4 octets est appliqué respectivement 4 q-box: q1, q0, q0, et q1.
  3. Les 4 octets sont XORé avec S0
  4. On applique les 4 q-box à ces octets: q0, q0, q1, q1
  5. Les 4 octets sont XORé avec S1
  6. On applique les 4 q-box à ces octets: q1, q0, q1, q0
  7. Les octets sont XORé avec S2
  8. On applique les 4 q-box à ces octets: q1, q1, q0, q0
  9. Les octets sont XORé avec S3
  10. On applique les 4 q-box à ces octets: q0,q1,q0,q1
  11. Les 4 octets forment le résultat Y.

Nous voyons qu'à aucun moment un échange des octets, la fonction h définit bien 4 fonctions octet-octet.

Il y a deux q-box, q0 et q1.  Ce sont des fonctions d'un octet en un octet, qui sont orienté nibble (un mot de 4 bit).  Les fonctions q0 et q1 utiliseront à leur tour des t-box, qui sont des fonctions nibble vers nibble.  En fait, q0 et q1 sont identiques, à part les t-box. Ainsi, les deux q-box ont la structure suivante:

 

  1. coupez l'octet d'entrée en deux nibbles et mettez les dans les variables nibble a et b.
  2. a devient a XOR b, et b devient le XOR de (l'ancien) a, b tourné un bit à droite, et 8 a mod 16
  3. a devient le résultat du t-box t0 appliqué à a
  4. b devient le résultat du t-box  t1 appliqué à  b
  5. a devient a XOR b, et b devient le XOR de (l'ancien) a, b tourné un bit à droite, et 8 a mod 16
  6. a devient le résultat du t-box t2 appliqué à a
  7. b devient le résultat du t-box t3 appliqué à b
  8. a et b sont mis ensemble pour former l'octet de sortie

Pour q0, les t-box sont:

t0 = [  8  1  7  D 6 F 3  2  0  B  5  9 E C A  4  ]
t1 = [ E C B  8  1  2  3  5  F  4  A 6  7  0  9  D ]
t2 = [ B A  5  E 6 D 9  0  C  8  F 3  2  4  7  1  ]
t3 = [ D  7  F  4  1  2  6 E  9  B  3  0  8  5  C A ]

Pour q1, les t-boxes sont:

t0 = [  2  8  B D F  7  6  E 3  1  9  4  0  A C  5  ]
t1 = [  1  E  2  B  4  C  3  7  6 D A  5  F  9  0  8  ]
t2 = [  4  C  7  5  1  6  9  A 0 E D  8  2  B  3  F ]
t3 = [ B  9  5  1  C  3  D E 6  4  7  F  2  0  8  A ]

Ce sont des fonctions nibble vers nibble.

Ceci complète donc le descriptif des S-box dépendant de la clé, ce qui était la particularité de Twofish.

Finalement, il faut encore décrire le schéma classique des clés de tour: il faut dériver 40 clés de 32 bit de la clé d'origine avec M0 et M1.

Les clés tour sont générées en paires.   Il nous faut donc 20 paires.  Appelons i le numéro de la pair, de 0 à 19.  La pair numéro i est générée comme ceci:

  1. On répète la représentation octet du numéro (2i) 4 fois.  Par exemple, si i est 6 et donc 2i est 12, ce qui est représenté par l'octet 0x0c, alors le mot de 32 bit est 0x0c0c0c0c.
  2. Ce mot de 32 bit est entré comme X dans la fonction h mentionné ci-dessus pour la génération des S-box, excepté qu'au lieu d'utiliser (S0, S1, S2, S3), nous allons utiliser les 4 mots dans M0, mais dans l'ordre inverse.  C'est à dire, à la place de S0, nous utilisons le dernier mot de 32 bit de M0 ; au lieu de S1 on utilise le troisième mot de 32 bit de M0 etc....  Cette fonction h modifiée appliqué au mot de 1. nous donne un mot de 32 bits que nous allons appeler A.
  3. Nous répétons la représentation octet de (2i + 1) aussi 4 fois.  Dans notre exemple, 2i + 1 est 13, ce qui est représenté par 0x0d et le mot 32 bit devient donc 0x0d0d0d0d.
  4. Nous utilisons ce mot comme X dans la fonction h, mais cette fois, nous utilisons le mot M1 dont nous allons prendre les mots de 32 bits comme dans 2.  Nous appellerons ce mot: B.
  5. Nous allons appliquer la Transformation Pseudo Hadamard au couple (A,B) des étapes 2 et 4.  Le résultat est A' et B'.
  6. La première clé de tour de notre pair est A'.  La deuxième est B', tourné 4 bits à gauche.

Ainsi, la description de Twofish est complète.

PRESENT

Present est un chiffre par bloc très léger optimisé pour une implémentation matérielle dans des systèmes très petits.  Ce sont des blocs de 64 bits, et une clé de 80 bits.  La structure générale est:

  1. Un pré-blanchissement initial en appliquant un XOR du bloc de données avec la première clé de tour
  2. 31 tours.

Chaque tour consiste en 3 operations sur les blocks de données:

  1. L'application d'une S-box
  2. une couche de permutations
  3. Une operation XOR avec la clé de tour

La S-box est appliquée à chaque nibble de données ; la voici:

C 5 6 B 9 0 A D 3 E F 8 4 7 1 2

La permutation est:

P(i) = i . 16 mod 63 si i < 63

P(63) = 63

Le schema de clés va ainsi: la clé maître est copiée dans un registre et ce registre subira des transformations.  Après chaque tour, les 64 bit les plus à gauche (les plus significatifs) sont pris comme clé de tour.  La première clé de tour consiste donc des 64 bits de gauche de la clé maître.

En suite vient la transformation du registre de clé:

  1. Une rotation vers la droite sur 19 bits
  2. Une unique application de la S-box aux 4 bits les plus à gauche du registre
  3. Une application XOR avec le numéro de la tour (sur 5 bits car il y a 31 tours) sur les bits de 19 vers 15.

Il serait difficile de faire plus simple !

Conclusion

Nous avons parcouru quelques chiffrements en bloc modernes.  Il y en a beaucoup d'autres.  Même si les chiffrements que nous avons étudiés sont relativement différents les uns des autres, ils utilisent tous le même genre de techniques:

En alternant et en répétant ces opérations, on essaie d'obtenir que chaque bit du texte en clair et que chaque bit de la clé a statistiquement une influence égale sur chaque bit dans le texte chiffré.  Il y a en effet des attaques cryptanalytiques qui essayent d’exploiter toute différence statistique de l'influence de chaque bit du texte en clair, et plus encore, de chaque bit de la clé.  Beaucoup de chiffrements en bloc ont été craqués par cette analyse différentielle.  Ainsi, même si beaucoup d'opérations dans les chiffrements que nous avons étudiés ont l'air totalement arbitraire, en fait elles ont en réalité été choisies de façon minutieuse pour essayer d'égaliser au maximum les influences statistiques de chaque bit de clé ou de données sur le texte chiffré.  C'est une des raisons pour laquelle la construction d'un bon chiffrement est difficile même si cela donne l'air que suffisamment d'opérations complexes feraient bien l'affaire.

De l'autre coté, plusieurs schémas de chiffrement veulent éviter le soupçon qu'il pourrait y avoir une porte dérobée dans le système.  Effectivement, il pourrait très bien être le cas qu'il y ait des corrélations insoupçonnables qui permettent de découvrir la clé. Sans connaissance de ces corrélations d'ordre élevée, il est quasi impossible de détecter un schéma pareil.  Si un système de chiffrage était conçu spécialement pour induire une telle corrélation, cela pourrait être considéré comme une porte dérobée qu'aucune analyse postérieure pourrait déceler si elle ne savait pas ce qu'elle cherchait.  Pendant long temps cette suspicion a pesée sur le chiffrement DES. Les S-box de DES n'ont aucune "explication" et si jamais elles introduisaient des corrélations sophistiquées on ne saurait jamais.  Cette suspicion s'est avérée fausse, mais une fois la boîte de Pandore ouverte, tout future chiffrement doit montrer patte blanche et démontrer qu'il n'y ait pas d'intentions cachés dans le système.  La façon la plus simple de faire cela, est d'utiliser des maths relativement simples avec des techniques qui ne peuvent clairement pas contenir une porte dérobée, comme utiliser les chiffres du développement décimal (ou binaire ou...) du nombre Pi.  Mais cela pose un autre problème.  Dans la mesure où des systèmes complètement ad hoc peuvent prêter peu d'aide pour être inversés (sauf si leur auteur a mis expressément une porte dérobée dans le système), un système où tout a une base mathématique simple peut donner beaucoup plus de leviers pour inverser la fonction.  Ainsi, l'apparence de beaucoup de mathématiques (comme le champs Galois GF(28) est à double tranchant: d'un coté, cela prouve qu'il n'y ait pas d'intentions cachées par son auteur qui ne pourraient pas être découvertes par d'autres mathématiciens ; d'un autre coté il se peut que ces propriétés mathématiques peuvent être utilisés pour casser le système.  C'est une critique qui s'applique particulièrement à Rijndael (le gagnant du concours AES), à cause de sa structure mathématique simple.   En ce jour, aucune attaque mathématique sur Rijndael n'est connue, mais c'est une raison de s'intéresser à d'autres chiffrements en bloc que le gagnant AES. Cela dit, il faut éviter de vouloir inventer son propre chiffrement en bloc.  Cela a l'air simple, mais ça ne l'est pas, et beaucoup de chiffrements qui avaient l'air solide ont été cassés par des analyses cryptographiques sophistiquées.

Finalement, une considération est l'efficacité. On pourrait penser que plus qu'un chiffrement a des tours, plus qu'il sera incassable.  En réalité, cela n'est que partiellement vrai.  Si on a un tour mal fait, mais on le répète un très grand nombre de fois, on pourrait arriver à un chiffrement relativement solide (sans garantie!), mais ce chiffrement sera très inefficace.  En réalité, une fois que l'influence statistique de chaque bit du texte en clair et de la clé est suffisamment uniforme dans chaque bit du texte chiffré, et que le mélange entre clé et texte en clair est suffisamment mélangé, ajouter des tours n'a plus de sens.  Et si le chiffrement est assez mauvais que les derniers tours exposent les clés de tour, ajouter des tours ne résoudra pas ce défaut.   Ainsi, un bon chiffrement est efficace: il obtient un mélange irréversible entre clé et texte en clair, et une uniformité statistique dans un effort de calcul relativement faible.  Un bon chiffrement ajoute quelques tours de plus que strictement nécessaire pour obtenir de la marge si jamais une analyse peut "casser" partiellement un ou quelques tours.   Il est remarquable que SERPENT a été un peu plus conservateur sur ce plan que Rijndael, et a perdu le concours à cause de cela.  Le comité de AES a attaché plus d'importance à l'efficacité qu'a la marge de sécurité.  Twofish utilise un codage classique et même simple, mais il a un schéma de clé très complexe et intensif en calcul.  Cela rend une analyse statistique et donc une attaque différentielle sur twofish très improbable.

Si on a besoin de se protéger d'adversaires puissants, on peut envisager d'utiliser plusieurs chiffrements en bloc en série. Il est alors extrêmement important que les clés pour les deux systèmes sont différents (donc on a une clé effective plus longue).  C'est une bonne idée d'utiliser Rijndael dans la série, mais si on veut en utiliser d'autres, il faut préférer des chiffrements avec une technologie différente.

D'un autre coté, si on n'a besoin que d'une protection temporaire de grands volumes de données avec des adversaires avec des ressources limités, on peut être induit à utiliser des chiffrements légers comme PRESENT.  On peut aussi améliorer la sécurité d'un chiffrement "standard" en ajoutant un chiffrement léger.  Cela ne fait qu'augmenter un peu l'effort de calcul, et cela brouille les pistes d’attaque.