Chiffrement symétrique

Une fois admis que le secret parfait est hors de portée pratique, on se tourne vers des chiffrements dont la clé est courte — de 128 à 256 bits, là où RSA réclame 2048 bits ou davantage — et le calcul rapide. C’est tout l’intérêt de la cryptographie symétrique : l’émetteur et le destinataire partagent une même clé, ce qui la rend efficace mais reporte toute la difficulté sur un point unique et névralgique, la distribution de ce secret commun.

Le talon d'Achille du symétrique

La clé étant commune aux deux parties, il faut l’acheminer par un canal sûr avant tout échange. C’est précisément ce problème que la cryptographie asymétrique viendra dénouer.

Les deux critères de Shannon

Dans son Communication Theory of Secrecy Systems (1949), Shannon dégage deux qualités attendues d’un bon algorithme¹ :

• la diffusion : une modification minime du clair doit se répercuter largement sur le chiffré, de sorte que les redondances du message soient réparties et noyées ;
• la confusion : la relation entre la clé, le clair et le chiffré doit être aussi enchevêtrée que possible.

En pratique, la diffusion s’obtient par des transformations essentiellement linéaires, tandis que la confusion repose sur des opérations non linéaires — typiquement les S-boxes. Tout l’art d’un chiffrement tient dans le mariage des deux.

Deux familles

On distingue deux grandes manières de chiffrer symétriquement :

• le chiffrement à flot, qui produit à partir de la clé une suite pseudo-aléatoire aussi longue que les données, ensuite combinée à celles-ci. On le retrouve dans RC4 (SSL/TLS, WEP, WPA), E0 (Bluetooth) ou A5 (GSM) ;
• le chiffrement par bloc, qui découpe les données en blocs de taille fixe (64 ou 128 bits), chiffrés séparément puis recombinés selon un mode opératoire. DES, IDEA, AES, Camellia en relèvent.

Le chiffrement à flot

Le principe est un héritier direct du chiffrement de Vernam : on génère un flux de clé (keystream) pseudo-aléatoire, que l’on combine par XOR aux données claires.

Là où le masque jetable exigeait un aléa vrai et incompressible, on se contente ici d’un aléa pseudo-aléatoire produit à partir d’une clé courte : c’est ce compromis qui rend le procédé praticable, au prix de sa perfection théorique. Très rapides, ces chiffrements conviennent au temps réel et à la protection des flux multimédia.

Leur sécurité, en revanche, est délicate. Chiffrer deux messages avec la même clé régénère le même aléa — d’où l’ajout d’un vecteur d’initialisation distinct à chaque usage. Surtout, le générateur pseudo-aléatoire doit être irréprochable : équiprobable, sans mémoire ni anticipation (chaque bit décorrélé de ses voisins), et de période longue.

WARNING

Ces trois conditions sont difficiles à réunir en pratique, et nombre de générateurs proposés ont été cassés. La sécurité des chiffrements à flot reste, pour cette raison, la plus fragile.

Le registre à décalage à rétroaction linéaire

Le Linear Feedback Shift Register (LFSR) est le générateur pseudo-aléatoire matériel par excellence.

Définition (LFSR)

Un LFSR est un système, électronique ou logiciel, produisant une suite récurrente linéaire sur le corps fini ${\mathbb{F}}_2=(\{0,1\},+,\times )$, où l’addition est le XOR et la multiplication le AND.

Un LFSR de taille $n$, dont l’état au temps $t$ est $(r_{n-1}^t,\dots ,r_0^t)$, se donne par un vecteur d’initialisation $r^0\in {\mathbb{F}}_2^n$ et un polynôme de rétroaction $P=1+c_{1}X+\cdots +c_n{X}^n$. L’état évolue par induction,

$r_i^{t+1}=r_{i+1}^t(0\le i\le n-1),r_{n-1}^{t+1}={\sum }_{i=1}^n{c}_i{r}_{n-i}^t,$

et la séquence chiffrante est la suite des bits de sortie $k=(r_0^t{)}_{t\ge 0}$.

Bien choisi, le polynôme confère à la suite une période maximale de $2^n-1$. Mais la linéarité même du procédé le condamne : l’algorithme de Berlekamp-Massey reconstruit le polynôme de rétroaction à partir de $2n$ bits seulement de la suite. Un LFSR nu n’est donc jamais sûr ; on ne l’emploie qu’assorti d’une couche non linéaire.

Le chiffrement par bloc

Un chiffrement par bloc transforme un bloc $m\in \{0,1{\}}^n$ sous une clé $k\in \{0,1{\}}^{\kappa }$ en un chiffré de même taille. Pour rester déchiffrable, la transformation doit être une permutation bijective.

Définition

Un chiffrement par bloc de taille $n$ et clé de taille $\kappa$ est une famille de permutations $E_k:\{0,1{\}}^n\to \{0,1{\}}^n$ indexée par les clés, avec $D_k=E_k^{-1}$ et $D_k(E_k(m))=m$, la clé $k$ restant secrète.

On lui demande trois vertus : la confusion et la diffusion déjà rencontrées, et l’indistinguabilité — pour un adversaire, $E_k$ doit être impossible à distinguer d’une permutation tirée au hasard².

Les réseaux de Feistel

Le réseau de Feistel est une élégante manière de construire une permutation réversible à partir d’une fonction interne qui, elle, ne l’est pas nécessairement. On scinde chaque bloc en deux moitiés $(L_0,R_0)$, et l’on itère

$L_{i+1}=R_i,R_{i+1}=L_i\oplus f(R_i,K_i),$

où $f$ est la fonction de ronde et $K_i$ la sous-clé dérivée de $k$. La beauté du procédé tient à ceci : le XOR étant involutif, le même circuit déchiffre en appliquant simplement les sous-clés à rebours, sans jamais requérir l’inverse de $f$³. La sécurité ne dépend plus alors que du choix de $f$ et du nombre de rondes.

DES

Le Data Encryption Standard est l’archétype du réseau de Feistel standardisé (NIST, 1977)⁴. Il opère sur des blocs de 64 bits avec une clé de 56 bits effectifs (64 saisis, dont 8 de parité), au fil de 16 rondes dont la fonction combine expansion, substitution par S-boxes, permutation et mélange à la sous-clé. Il illustre à merveille l’alliance confusion / diffusion — mais sa clé, trop courte, le rend aujourd’hui obsolète : la recherche exhaustive en vient à bout.

AES

L’Advanced Encryption Standard (2001) lui a succédé. Ce n’est pas un Feistel mais un réseau de substitution-permutation (SPN)⁵, décliné en trois variantes — AES-128, 192 et 256 — toutes sur des blocs de 128 bits. Chaque ronde applique en série :

• SubBytes — substitution non linéaire par S-boxes (la confusion) ;
• ShiftRows — décalage des lignes de l’état ;
• MixColumns — mélange au sein des colonnes (la diffusion) ;
• AddRoundKey — combinaison avec la clé de ronde.

Cette structure se prête aussi bien au logiciel qu’au matériel, et AES demeure réputé sûr contre les attaques classiques dès lors que la clé est adéquate⁶.

Les modes opératoires

Un chiffrement par bloc ne sait, par nature, traiter qu’un bloc. Pour un message plus long, un mode opératoire prescrit comment enchaîner les chiffrements⁷.

• ECB (Electronic Codebook) chiffre chaque bloc indépendamment, $C_i=E_k(P_i)$. Simple, mais dangereux : deux blocs clairs identiques donnent deux chiffrés identiques, et les motifs du message transparaissent dans le chiffré. À proscrire.
• CBC (Cipher Block Chaining) enchaîne les blocs par XOR, $C_i=E_k(P_i\oplus C_{i-1})$ avec $C_0=\text{IV}$ ; il gomme la répétition des motifs, au prix d’un traitement séquentiel.
• CTR (Counter) transforme le chiffrement par bloc en chiffrement à flot, en chiffrant les valeurs successives d’un compteur — parallélisable.
• OFB / CFB produisent de même un flux pseudo-aléatoire à partir de la primitive.

Le choix du mode n’est jamais neutre : il engage la parallélisation, la propagation des erreurs et la résistance à certaines attaques — l’oracle de padding sur CBC en est l’exemple canonique.

Footnotes

1. C. E. Shannon, « Communication Theory of Secrecy Systems », Bell System Technical Journal, 1949. ↩

2. M. Bombar, Cryptanalyse — Cours 4 : chiffrement par blocs, notes de cours. ↩

3. Sur la construction de Feistel, voir par exemple What Is a Feistel Cipher?. ↩

4. P. Gaborit, Notes de cryptographie, Université de Limoges. ↩

5. H. Ferradi, Chiffrement par bloc (AES), ENS. ↩

6. Block ciphers and modes of operation, notes de cours. ↩

7. Block cipher mode of operation, Wikipedia. ↩