Il existe un chiffrement inviolable. Pas « très difficile à casser » : inviolable, au sens où aucun adversaire, quelle que soit sa puissance de calcul et quel que soit le temps dont il dispose, ne peut tirer du chiffré la moindre information sur le clair. Il a été breveté par Gilbert Vernam en 1919 et sa sécurité a été démontrée par Claude Shannon en 1949.

Ce chapitre explique pourquoi la discipline ne s'est pas arrêtée là — et pourquoi ce théorème d'impossibilité, loin d'être une curiosité historique, est ce qui justifie tout le reste du cours.

Le masque jetable

Le procédé tient en une ligne. Soit un message $m$ de $n$ bits et une clé $k$ de $n$ bits tirée uniformément au hasard :

Le déchiffrement est le même calcul, puisque le XOR est son propre inverse. Trois conditions sont exigées, et le nom du procédé les résume : la clé doit être aussi longue que le message, parfaitement aléatoire, et jetée après un seul usage.

Le secret parfait, défini

Shannon donne à l'intuition « le chiffré n'apprend rien » une forme mathématique. Un chiffrement est parfaitement sûr si, pour tout message $m$ et tout chiffré $c$ :

Observer le chiffré ne modifie donc en rien la distribution des messages possibles. Une formulation équivalente, plus commode à manipuler : pour tous messages $m$ et $m'$ de même longueur, $\Pr[C = c \mid M = m] = \Pr[C = c \mid M = m']$ — le chiffré est également probable quel que soit le clair.

Le masque jetable vérifie cette définition, et la preuve tient en une phrase. Fixons $c$. Pour chaque message $m$, il existe exactement une clé qui produit ce chiffré, à savoir $k = m \oplus c$. Comme la clé est uniforme sur $2^n$ valeurs, on a $\Pr[C = c \mid M = m] = 2^{-n}$, indépendamment de $m$. Tous les clairs sont exactement aussi plausibles après observation qu'avant.

C'est une propriété d'un autre ordre que celles du reste du cours. Elle ne suppose aucune limite sur l'adversaire, ne repose sur aucun problème réputé difficile, et ne vieillira pas : ni les progrès de la cryptanalyse ni un ordinateur quantique n'y peuvent rien.

Le théorème de Shannon

La contrepartie est un théorème d'impossibilité, et il est sans échappatoire.

Théorème. Si un chiffrement est parfaitement sûr, alors $|\mathcal{K}| \geq |\mathcal{M}|$ : l'espace des clés est au moins aussi grand que l'espace des messages.

La démonstration se fait par l'absurde et mérite d'être suivie, car elle explique pourquoi la borne est incontournable. Supposons $|\mathcal{K}| < |\mathcal{M}|$ et fixons un chiffré $c$ de probabilité non nulle. Considérons l'ensemble des déchiffrements possibles de $c$ :

Cet ensemble contient au plus $|\mathcal{K}|$ éléments, donc strictement moins que $|\mathcal{M}|$. Il existe donc un message $m'$ qui n'y figure pas — aucune clé ne le transforme en $c$. On a alors $\Pr[M = m' \mid C = c] = 0$, alors que $\Pr[M = m'] > 0$. La définition du secret parfait est violée : le chiffré a appris à l'adversaire que le message n'était pas $m'$.

Le raisonnement est purement combinatoire. Aucune ingéniosité de conception ne le contourne : une clé plus courte que le message laisse forcément des messages inatteignables, et un message inatteignable est une information.

Le prix, et pourquoi on le refuse

La borne de Shannon rend le masque jetable impraticable dans presque tous les cas, pour une raison de logistique plus que de mathématiques : il faut acheminer une clé aussi longue que le message, par un canal sûr, avant de communiquer. Si un tel canal existe, il aurait pu transporter le message.

Le procédé n'a donc de sens que lorsque le canal sûr existe à un moment et pas à un autre : on remet des carnets de clés à un ambassadeur avant son départ, il les consomme sur place. La ligne directe Moscou-Washington l'a employé, ainsi que plusieurs services diplomatiques. Toutes ces utilisations partagent le même profil — un volume faible, une valeur très élevée, et une distribution physique préalable.

S'y ajoutent deux exigences que la pratique respecte mal. L'aléa doit être vraiment uniforme, ce qui suppose une source physique et non un générateur logiciel — le chapitre 13 montrera ce que coûtent les défaillances de ce côté. Et la clé ne doit jamais resservir.

Ce que coûte un masque réutilisé

Cette dernière condition n'est pas un raffinement. Si deux messages sont chiffrés avec le même masque :

La clé s'annule. L'adversaire obtient le XOR des deux clairs, et la redondance de la langue suffit à les séparer : on fait glisser un mot probable le long du résultat, et toute position qui produit du texte lisible dans l'autre message est la bonne. La méthode porte un nom, le crib dragging, et elle est mécanique.

L'histoire a fourni le cas d'école. Pendant la Seconde Guerre mondiale, la production soviétique de carnets de clés a dupliqué certaines pages ; les services américains, dans le cadre du projet Venona, ont exploité ces répétitions pendant des décennies et déchiffré plusieurs milliers de messages. Le chiffrement était parfait, sa mise en œuvre ne l'était pas — et la sécurité est l'intersection des deux, jamais leur réunion.

// Deux messages, un seul masque. C'est l'erreur de Venona.
//
// c1 = m1 ⊕ k     c2 = m2 ⊕ k
// donc  c1 ⊕ c2 = m1 ⊕ m2 : la clé a disparu.
//
// Il ne reste plus qu'à séparer m1 de m2, et le français s'en charge.

const xor = (a, b) => a.map((x, i) => x ^ b[i]);
const enOctets = (s) => [...s].map((c) => c.charCodeAt(0));
const enTexte = (o) => o.map((c) => String.fromCharCode(c)).join("");

// Les deux clairs, que vous n'êtes pas censé connaître.
const M1 = "rendez-vous a minuit sous le pont neuf";
const M2 = "le convoi part demain a huit heures.";
const n = Math.min(M1.length, M2.length);

// Un masque aléatoire, uniforme, secret — et réutilisé.
const cle = Array.from({ length: n }, () => Math.floor(Math.random() * 256));
const c1 = xor(enOctets(M1.slice(0, n)), cle);
const c2 = xor(enOctets(M2.slice(0, n)), cle);

// ── À VOUS ────────────────────────────────────────────────────────────────
// Vous ne disposez que de c1 et c2.
//
// 1. Calculez d = c1 ⊕ c2. Vérifiez qu'il ne dépend plus de la clé.
// 2. Faites glisser un mot probable (« crib ») le long de d : à chaque
//    position, d ⊕ crib donne ce que l'AUTRE message contiendrait si le crib
//    était là. Si le résultat est du texte lisible, la position est la bonne.
// 3. Le mot " le " est un bon candidat en français.

const d = []; // à compléter

function essayer(crib, position) {
  // à compléter : renvoyer le fragment de l'autre message
  return "";
}

// Testez toutes les positions et affichez celles qui donnent du lisible.
const lisible = (s) => [...s].every((c) => /[a-z .,'-]/.test(c));

for (let p = 0; p + 4 <= n; p++) {
  const fragment = essayer(" le ", p);
  if (fragment && lisible(fragment)) console.log(p, JSON.stringify(fragment));
}

const d = xor(c1, c2); // = m1 ⊕ m2, la clé s'est annulée

function essayer(crib, position) {
  const bout = d.slice(position, position + crib.length);
  if (bout.length < crib.length) return "";
  return enTexte(xor(bout, enOctets(crib)));
}

// En position 15, " le " glissé sur d rend " a m" : le crib appartenait à M2
// (« ... part demain a huit heures ») et le fragment lu appartient à M1
// (« ... vous a minuit ... »). De proche en proche, chaque fragment lisible
// en révèle un peu plus des deux messages, jusqu'à les reconstituer tous les
// deux — sans jamais chercher la clé.
//
// Ce qu'il faut en retenir : le masque jetable n'est parfait que si « jetable »
// est respecté. Réutilisé une seule fois, il ne protège plus rien, et la
// perfection prouvée du chapitre s'évapore. C'est exactement ce qui est arrivé
// aux messages soviétiques du projet Venona.
//
// La même équation reviendra au chapitre 5 avec un nonce ChaCha20 réutilisé,
// et au chapitre 8 avec un nonce GCM réutilisé — où la conséquence est pire
// encore, puisque la clé d'authentification elle-même est compromise.

Ce qui survit

Renoncer au secret parfait, ce n'est pas renoncer au masque : c'est renoncer à ce que la suite masquante soit vraiment aléatoire. Un chiffrement par flot engendre, à partir d'une clé courte, une suite pseudo-aléatoire aussi longue qu'il faut, et l'applique par XOR exactement comme Vernam. La sécurité devient calculatoire — elle vaut ce que vaut le générateur — mais le problème logistique disparaît. C'est le chapitre 5.

L'équation $c_1 \oplus c_2 = m_1 \oplus m_2$, elle, ne disparaît pas. Elle se déplace. Sous le nom de « réutilisation de nonce », c'est aujourd'hui l'une des erreurs les plus coûteuses de la cryptographie appliquée : elle casse ChaCha20 au chapitre 5, et en mode GCM au chapitre 8 elle fait plus que révéler les clairs, puisqu'elle compromet aussi la clé d'authentification et permet de forger des messages.

À retenir

Un chiffrement par blocs est une famille de permutations : pour chaque clé, une bijection de $\{0,1\}^b$ sur lui-même. AES fixe $b = 128$. À lui seul il ne chiffre qu'un bloc — le gros du travail, et le gros des erreurs, est dans la manière de l'étendre à un message entier.

Ce chapitre suit ce fil, de la structure interne d'une primitive jusqu'au mode d'opération, et se termine par le TP le plus instructif du cours : casser un chiffrement CBC correct, sans en connaître la clé, à l'aide d'un serveur trop bavard.

Deux façons de construire une permutation

Historiquement, deux architectures dominent.

Un réseau de Feistel coupe le bloc en deux moitiés $(L, R)$ et itère $L_{i+1} = R_i$, $R_{i+1} = L_i \oplus F(R_i, k_i)$. Sa vertu tient dans un fait remarquable : le déchiffrement est le même circuit, parcouru en sens inverse, et $F$ n'a pas besoin d'être inversible. On peut donc y mettre n'importe quelle fonction de brouillage. DES, conçu chez IBM et normalisé en 1977, est un Feistel à 16 tours.

Un réseau de substitution-permutation (SPN) applique à chaque tour trois couches : une addition de clé, une substitution locale (la boîte S), une permutation globale qui diffuse. Ici la substitution doit être inversible, et le déchiffrement emploie les couches inverses. AES est un SPN.

DES est mort de sa clé : 56 bits, soit $2^{56}$ clés, épuisables par force brute — la machine Deep Crack de l'EFF l'a fait en 1998 en trois jours. 3DES a prolongé sa vie en chiffrant trois fois, $E_{k_1} \circ D_{k_2} \circ E_{k_3}$. Pourquoi trois et non deux ? La réponse est une attaque, celle du chapitre 6 : le double chiffrement n'offre pas 112 bits de sécurité mais environ 57, à cause de la rencontre au milieu. Retenez la question, le chapitre 6 y répond.

AES, couche par couche

AES-128 enchaîne 10 tours sur un état de 16 octets disposés en grille $4 \times 4$. Quatre opérations composent un tour.

• SubBytes — chaque octet passe dans la boîte S : inversion dans $\mathbb{F}_{2^8}$ (le corps du chapitre 2) suivie d'une application affine. C'est la seule couche non linéaire, et c'est elle qui résiste aux cryptanalyses du chapitre 6.
• ShiftRows — les lignes sont décalées, ce qui disperse les octets entre colonnes.
• MixColumns — chaque colonne est multipliée par une matrice fixe dans le corps ; un octet modifié en contamine quatre.
• AddRoundKey — l'état est XORé avec la sous-clé du tour, dérivée de la clé maîtresse.

Le duo confusion/diffusion, nommé par Shannon, y est explicite : SubBytes assure la confusion (le lien clé-chiffré est complexe), ShiftRows et MixColumns la diffusion (un bit d'entrée influence rapidement tous les bits de sortie). Après deux tours, changer un seul bit du clair modifie les 128 bits de l'état — c'est l'effet d'avalanche.

Un point pratique de première importance : la boîte S implémentée par table est une source de fuite par cache. AES-NI, le jeu d'instructions matériel présent sur les processeurs courants, calcule le tour en temps constant et doit être préféré à toute implémentation logicielle par tables. On retrouvera ce thème au chapitre 9.

Les modes : du bloc au message

Un mode d'opération étend la permutation à un message de longueur quelconque. Le choix du mode compte davantage que celui de la primitive.

ECB (Electronic Codebook) chiffre chaque bloc indépendamment. C'est le contre-exemple fondateur : deux blocs de clair identiques donnent deux blocs de chiffré identiques, et la structure du clair transparaît. Le pingouin Tux chiffré en ECB reste parfaitement reconnaissable. Vous avez vous-même distingué ECB au chapitre 1 — ne l'utilisez jamais.

CBC (Cipher Block Chaining) chaîne les blocs : $C_i = E_k(P_i \oplus C_{i-1})$, amorcé par un vecteur d'initialisation $C_0 = \text{IV}$. Deux blocs identiques donnent des chiffrés différents, à condition que l'IV soit imprévisible — un IV prévisible rouvre une attaque à clairs choisis, ce qui fut la faille BEAST sur TLS en 2011.

CTR (Counter) transforme le chiffrement par blocs en chiffrement par flot : on chiffre un compteur, $\text{flot}_i = E_k(\text{nonce} \Vert i)$, et on XOR. Parallélisable, sans padding, il ne demande jamais l'inverse de la primitive. Sa condition vitale est celle du chapitre 3 : le couple (clé, nonce) ne doit jamais se répéter, sous peine du masque réutilisé.

GCM (Galois/Counter Mode) ajoute à CTR une authentification. C'est un chiffrement authentifié, l'objet propre du chapitre 8 ; retenez pour l'instant qu'un mode moderne protège l'intégrité en même temps que la confidentialité, ce que ni CBC ni CTR ne font.

Le padding, et l'oracle qui le trahit

CBC exige des blocs pleins. Un message qui ne tombe pas juste est complété par un padding ; le schéma PKCS#7 ajoute $n$ octets valant chacun $n$. Pour compléter un bloc de 8 auquel il manque 3 octets : ... 03 03 03. Un message déjà aligné reçoit un bloc de padding entier, afin que le déchiffrement sache toujours combien d'octets retirer.

Au déchiffrement, on vérifie que le padding est bien formé. Et c'est là que tout se joue : si le serveur distingue un padding invalide des autres erreurs — par un message différent, un code de retour, ou seulement un délai — il devient un oracle. Un seul bit lui échappe à chaque requête : le padding est-il valide ? Ce bit suffit.

Le mécanisme repose sur l'équation de déchiffrement CBC, $P_i = D_k(C_i) \oplus C_{i-1}$. L'attaquant ne connaît pas $D_k(C_i)$, mais il contrôle $C_{i-1}$ : en l'envoyant modifié, il choisit ce que vaudra $P_i$. Il ajuste le dernier octet jusqu'à ce que l'oracle accepte le padding : le clair déchiffré se termine alors presque sûrement par 01, ce qui lui donne $D_k(C_i)$ sur ce dernier octet — et donc le vrai clair. Il vise ensuite 02 02, puis 03 03 03, et remonte le bloc entier. Environ 256 requêtes par octet, aucune connaissance de la clé.

Cette attaque, publiée par Serge Vaudenay en 2002, a frappé des systèmes déployés pendant plus d'une décennie : ASP.NET en 2010, et la variante Lucky Thirteen sur TLS en 2013, qui exploitait le seul délai d'exécution. Vous allez la monter vous-même.

À vous — casser CBC sans la clé

Le chiffrement ci-dessous est correct. La clé est secrète et le restera : vous ne la toucherez pas une seule fois. Votre seule prise est l'oracle, qui répond par oui ou par non à la question du padding. Reconstituez le clair.

// ── Un chiffre par blocs jouet (Feistel 4 tours, bloc de 8 octets) ────────
// La clé est secrète. Vous n'y toucherez jamais : l'attaque n'en a pas besoin.
const BLOC = 8;
const CLE = [0x2f, 0x9c, 0x41, 0xb7];

const xor = (a, b) => a.map((x, i) => x ^ b[i]);
const F = (demi, rk) =>
  demi.map((_, i) => (((demi[(i + 1) % 4] * 7 + demi[i] + rk) ^ (rk << 1)) & 0xff));

function dechiffrerBloc(b) {
  let L = b.slice(0, 4), R = b.slice(4, 8);
  for (let r = 3; r >= 0; r--) [L, R] = [xor(R, F(L, CLE[r])), L];
  return [...L, ...R];
}

// ── L'oracle : la seule chose que le serveur vous accorde ─────────────────
// Il déchiffre en CBC et répond UN SEUL bit : le padding est-il valide ?
// (padding PKCS#7 : n octets de valeur n.)
function paddingValide(o) {
  const n = o[o.length - 1];
  if (n < 1 || n > BLOC || n > o.length) return false;
  return o.slice(-n).every((x) => x === n);
}
function oracle(iv, chiffre) {
  let prec = iv, clair = [];
  for (let i = 0; i < chiffre.length; i += BLOC) {
    const bloc = chiffre.slice(i, i + BLOC);
    clair.push(...xor(dechiffrerBloc(bloc), prec));
    prec = bloc;
  }
  return paddingValide(clair);
}

// Le message intercepté (IV + un bloc chiffré). Contenu inconnu de l'attaquant.
const IV = [0x33, 0x71, 0x0a, 0xde, 0x5b, 0x62, 0x9f, 0x14];
const CHIFFRE = [0x1f, 0x60, 0x59, 0xd5, 0xc8, 0xfb, 0x31, 0x1d];

// ── À COMPLÉTER ───────────────────────────────────────────────────────────
// En CBC, le clair d'un bloc est  P = D(C) ⊕ Cprécédent.
// On note I = D(C) l'« intermédiaire », inconnu mais FIXE.
//
// En envoyant un IV forgé à la place de Cprécédent, on contrôle
//   P' = I ⊕ IVforgé.
// On cherche l'IVforgé qui rend le dernier octet de P' égal à 0x01 : le
// padding devient valide, et l'oracle le confirme. On en déduit I[7], puis
// P[7] = I[7] ⊕ Cprécédent[7]. On remonte octet par octet en visant des
// paddings 0x02 0x02, puis 0x03 0x03 0x03, etc.

function casserBloc(precedent, bloc) {
  const inter = new Array(BLOC).fill(0); // I = D(bloc), à découvrir

  for (let pos = BLOC - 1; pos >= 0; pos--) {
    const cible = BLOC - pos;            // valeur de padding visée à ce tour
    const forge = new Array(BLOC).fill(0);

    // Fixer les octets DÉJÀ trouvés pour qu'ils vaillent 'cible'.
    for (let j = pos + 1; j < BLOC; j++) forge[j] = inter[j] ^ cible;

    // Balayer les 256 valeurs de l'octet courant jusqu'à un padding valide.
    // Piège du dernier octet : 0x02 0x02 est aussi un padding valide. Quand
    // pos === BLOC-1, revérifiez en perturbant l'avant-dernier octet.
    let trouve = null;
    for (let g = 0; g < 256; g++) {
      // à compléter
    }

    if (trouve === null) throw new Error("échec en position " + pos);
    inter[pos] = trouve ^ cible;
  }
  return xor(inter, precedent);
}

const clair = casserBloc(IV, CHIFFRE);
console.log(clair.map((c) => String.fromCharCode(c)).join(""));

function casserBloc(precedent, bloc) {
  const inter = new Array(BLOC).fill(0);

  for (let pos = BLOC - 1; pos >= 0; pos--) {
    const cible = BLOC - pos;
    const forge = new Array(BLOC).fill(0);
    for (let j = pos + 1; j < BLOC; j++) forge[j] = inter[j] ^ cible;

    let trouve = null;
    for (let g = 0; g < 256; g++) {
      forge[pos] = g;
      if (!oracle(forge, bloc)) continue;

      if (pos === BLOC - 1) {
        // Désambiguïser : si le padding réel était 0x02 0x02 (ou plus long),
        // perturber l'avant-dernier octet le casse ; un vrai 0x01 y survit.
        const test = forge.slice();
        test[pos - 1] ^= 0xff;
        if (!oracle(test, bloc)) continue;
      }
      trouve = g;
      break;
    }

    if (trouve === null) throw new Error("échec en position " + pos);
    inter[pos] = trouve ^ cible; // P'[pos] = cible  ⇒  I[pos] = forge[pos] ⊕ cible
  }
  return xor(inter, precedent);
}

// Le clair sort en clair : "matin" suivi de son padding (0x03 0x03 0x03).
//
// Aucune clé n'a été touchée. On a fait environ 256 requêtes par octet, soit
// quelques milliers pour tout le bloc — négligeable. La faille n'est pas dans
// AES : elle est dans le fait que le serveur DISTINGUE « padding invalide »
// des autres erreurs. C'est une attaque CCA au sens du chapitre 1, et la
// parade est du chapitre 8 : Encrypt-then-MAC. On vérifie le MAC AVANT de
// déchiffrer, donc avant de regarder le padding — l'oracle disparaît.

Le fil du cours est ici tout entier : implémenter puis casser. Vous venez de retrouver un clair sans attaquer AES, en exploitant une décision d'ingénierie — le serveur qui en dit trop. La parade est du chapitre 8, et elle tient en une inversion d'ordre : vérifier l'authenticité avant de déchiffrer, pour qu'il n'y ait plus rien à interroger.

Ce que la suite en fait

Le chapitre 5 explore l'autre grande famille symétrique, le chiffrement par flot, où CTR trouve sa place naturelle et où la réutilisation de nonce refait surface. Le chapitre 6 attaque enfin les primitives elles-mêmes plutôt que leurs modes, et répond à la question laissée ouverte sur 3DES. Et le chapitre 8 referme l'oracle de padding en construisant le chiffrement authentifié qui aurait dû être employé dès le départ.

À retenir

Un chiffrement par flot réalise le rêve du chapitre 3 sous une forme atteignable : il engendre, à partir d'une clé courte, une suite pseudo-aléatoire aussi longue que le message, et l'applique par XOR comme le faisait Vernam. On échange la perfection prouvée contre une clé maniable — et l'on hérite, mot pour mot, de la fragilité du masque réutilisé.

Le principe, et sa condition unique

Le schéma est celui de Vernam, avec un générateur à la place du hasard :

Toute la sécurité se reporte sur $G$ : sa sortie doit être indistinguable d'une suite aléatoire pour tout adversaire en temps polynomial. Si elle l'est, le chiffré ne révèle rien de plus qu'un masque jetable — mais la garantie est désormais calculatoire, elle vaut ce que vaut $G$.

Le nonce mérite qu'on s'y arrête, car il est la raison d'être du chapitre. Une même clé sert à chiffrer des milliers de messages ; pour que la suite masquante diffère à chaque fois, on adjoint à la clé un nonce — un numéro utilisé une seule fois. La règle est absolue : à clé fixée, jamais deux fois le même nonce. On verra qu'elle est aussi facile à énoncer que difficile à tenir.

Les LFSR, et pourquoi la linéarité tue

Les premiers générateurs matériels furent des registres à décalage à rétroaction linéaire (LFSR). Un registre de bits se décale à chaque top d'horloge, et le bit entrant est un XOR de certaines positions. C'est rapide, compact, et le cauchemar du cryptographe : précisément parce que tout y est linéaire.

L'algorithme de Berlekamp-Massey reconstitue un LFSR de $L$ bits à partir de seulement $2L$ bits de sa sortie. Un LFSR seul n'offre donc aucune sécurité. Les chiffres réels qui en dérivent — A5/1 du GSM, E0 du Bluetooth, RC4 par un autre chemin — combinent plusieurs registres par une fonction non linéaire pour briser cette structure, et tous ont fini par tomber : la combinaison retardait l'attaque sans la supprimer. La leçon est générale, et elle revient au chapitre 6 : la linéarité est l'ennemi, et la non-linéarité de l'AES n'est pas un ornement.

ChaCha20, le flot moderne

La conception a changé de camp. ChaCha20, dessiné par Daniel Bernstein en 2008 et normalisé dans le RFC 8439, n'est pas un registre : c'est un chiffrement CTR bâti sur une fonction de brouillage. Une clé de 256 bits et un nonce de 96 bits amorcent un état de 512 bits ; vingt tours d'additions, de rotations et de XOR — la ronde « ARX », sans aucune table — produisent chaque bloc de flot, indexé par un compteur.

L'absence de table est un avantage de sécurité, pas seulement de vitesse : sans accès mémoire dépendant du secret, ChaCha20 est naturellement à temps constant, là où une boîte S tabulée expose l'implémentation aux attaques par cache. C'est pourquoi TLS 1.3 le retient comme alternative à AES-GCM, notamment sur les processeurs sans accélération AES matérielle.

Mais ChaCha20 reste un chiffrement par flot, et la règle du nonce s'y applique sans indulgence.

Le nonce rejoué, encore

Reprenons deux messages chiffrés sous la même clé et le même nonce. Le flot est identique, donc :

C'est l'équation du chapitre 3, au signe près de rien. La suite masquante s'annule, l'adversaire obtient le XOR des clairs, et un seul message connu — un en-tête, une formule convenue — dévoile l'autre par simple XOR. Aucune attaque sur ChaCha20 lui-même : la faute est dans l'usage.

Ce n'est pas une hypothèse d'école. Le WEP du Wi-Fi tirait un IV de 24 bits seulement, dont la répétition était garantie par le paradoxe des anniversaires après quelques heures de trafic. La faute s'est répétée sur des consoles, des messageries, des VPN. Elle est tellement récurrente qu'une famille entière de constructions — le chiffrement « résistant à la réutilisation de nonce », comme AES-GCM-SIV — existe pour en limiter les dégâts.

// ChaCha20 est un chiffrement par flot : flot = ChaCha(clé, nonce, compteur),
// puis chiffré = clair ⊕ flot. Ici un générateur jouet tient lieu de ChaCha —
// peu importe sa qualité, c'est la RÉUTILISATION qui casse tout.

function flot(cle, nonce, longueur) {
  // Générateur déterministe (xorshift ensemencé par clé+nonce). Non
  // cryptographique, mais reproductible : mêmes (clé, nonce) ⇒ même flot.
  let x = (cle ^ (nonce * 2654435761)) >>> 0 || 1;
  const out = [];
  for (let i = 0; i < longueur; i++) {
    x ^= x << 13; x >>>= 0;
    x ^= x >> 17;
    x ^= x << 5;  x >>>= 0;
    out.push(x & 0xff);
  }
  return out;
}

const enOctets = (s) => [...s].map((c) => c.charCodeAt(0));
const enTexte = (o) => o.map((c) => String.fromCharCode(c)).join("");
const xor = (a, b) => a.map((x, i) => x ^ b[i]);

const CLE = 0xC0FFEE;
const NONCE = 42; // LE MÊME pour les deux messages : c'est l'erreur.

// Message public, connu de l'attaquant (un en-tête, une formule de politesse).
const CONNU = "bonjour, voici le rapport : ";
// Message secret, que l'attaquant veut lire.
const SECRET = "le budget reel est de 4 millions";

const n = Math.min(CONNU.length, SECRET.length);
const cConnu = xor(enOctets(CONNU.slice(0, n)), flot(CLE, NONCE, n));
const cSecret = xor(enOctets(SECRET.slice(0, n)), flot(CLE, NONCE, n));

// ── À VOUS ────────────────────────────────────────────────────────────────
// Vous disposez de : cConnu, cSecret, et du clair CONNU. Pas de la clé, pas du
// flot. Retrouvez le début de SECRET.
//
// Indice : cConnu ⊕ cSecret élimine le flot. Il ne reste qu'à réintroduire ce
// que vous savez.

function retrouverSecret(cConnu, cSecret, connuClair) {
  // à compléter
  return "";
}

console.log(JSON.stringify(retrouverSecret(cConnu, cSecret, CONNU.slice(0, n))));

function retrouverSecret(cConnu, cSecret, connuClair) {
  // cConnu ⊕ cSecret = CONNU ⊕ SECRET  (le flot identique s'annule)
  const d = xor(cConnu, cSecret);
  // d ⊕ CONNU = SECRET
  return enTexte(xor(d, enOctets(connuClair)));
}

// Sortie : "le budget reel est de 4 millio" — le secret, en clair.
//
// Le flot n'a jamais été calculé, la clé jamais approchée. C'est exactement
// l'attaque du chapitre 3 sur le masque réutilisé : un chiffrement par flot
// N'EST qu'un masque dont la suite est engendrée. Réutiliser le nonce, c'est
// réutiliser le masque.
//
// C'est un incident réel : le WEP du Wi-Fi rejouait ses IV de 24 bits, la
// PlayStation 3 a signé avec un nonce ECDSA constant (chapitre 11), et
// l'implémentation de GCM (chapitre 8) transforme cette même faute en forge
// active. La règle tient en trois mots : un nonce, une fois.

Flot ou blocs ?

Le partage n'est pas celui qu'on croit. AES en mode CTR est un chiffrement par flot ; ChaCha20 est structuré comme CTR. La vraie ligne de fracture n'est pas flot contre blocs, mais avec ou sans authentification. Ni ChaCha20 brut ni AES-CTR ne protègent l'intégrité : un attaquant qui inverse un bit du chiffré inverse le bit correspondant du clair, sans être détecté — la malléabilité du chapitre 1.

C'est pourquoi on ne déploie jamais ces primitives nues. On les enveloppe : ChaCha20 devient ChaCha20-Poly1305, AES-CTR devient AES-GCM. Ces objets authentifiés sont le sujet du chapitre 8, et ils sont le seul niveau auquel un praticien devrait avoir affaire.

Ce que la suite en fait

Le chapitre 6 quitte les modes pour attaquer les primitives : il montre par quelles méthodes — différentielle, linéaire, rencontre au milieu — on évalue la solidité d'un AES ou d'un DES, et pourquoi la linéarité rencontrée ici chez les LFSR est le fil conducteur de toute la cryptanalyse symétrique. Le chapitre 8, lui, referme la malléabilité en ajoutant l'authentification qui manque à tout chiffrement de ce chapitre.

À retenir

Jusqu'ici, chaque attaque exploitait un usage : un nonce rejoué, un padding trahi. Ce chapitre s'en prend aux primitives elles-mêmes. On ne demande plus si le mode est correct, mais combien de tours d'AES ou de DES résistent, et pourquoi. C'est la cryptanalyse au sens strict, et son intérêt dépasse l'attaque : c'est elle qui dicte les choix de conception.

La force brute donne l'échelle

Toute clé de $b$ bits est vulnérable à la recherche exhaustive en $2^b$ chiffrements. Ce n'est pas une attaque, c'est l'étalon : une cryptanalyse n'a d'intérêt que si elle fait mieux. DES et ses 56 bits ont été épuisés par force brute — trois jours en 1998, quelques heures aujourd'hui. AES-128 y résiste par sa seule taille de clé.

Un mot sur la menace quantique, développée au chapitre 14 : l'algorithme de Grover accélère quadratiquement la recherche exhaustive, ramenant $2^b$ à $2^{b/2}$. AES-128 tomberait à 64 bits de sécurité quantique, AES-256 à 128 — la raison pour laquelle on recommande AES-256 dans une perspective post-quantique. Le symétrique est affaibli, pas effondré ; c'est l'asymétrique que Shor met à terre.

Cryptanalyse différentielle

L'idée, publiée par Biham et Shamir à la fin des années 1980, tient en une question : quand deux clairs diffèrent d'une valeur fixée $\Delta_{\text{in}}$, la différence des chiffrés est-elle uniformément répartie, comme elle devrait l'être, ou certaines différences $\Delta_{\text{out}}$ reviennent-elles trop souvent ?

Tout se joue dans la boîte S, seul étage non linéaire. Pour une boîte idéale, tout couple $(\Delta_{\text{in}}, \Delta_{\text{out}})$ est également probable. Une vraie boîte s'en écarte, et l'on dresse sa table des différences. Si un couple domine avec probabilité $p$, il se propage à travers les tours en une caractéristique différentielle dont la probabilité est le produit des probabilités par tour — d'où sa décroissance rapide, et d'où le nombre de tours choisi.

L'histoire réserve ici une anecdote qui n'en est pas une. Les boîtes S de DES, dont IBM n'avait jamais publié les critères de conception, se sont révélées quasi optimales contre l'attaque différentielle — que le public a découverte quinze ans après. IBM et la NSA la connaissaient et avaient durci DES en conséquence, tout en gardant le silence. AES a suivi la démarche inverse : ses boîtes sont justifiées publiquement par leur résistance différentielle et linéaire, et c'est ce qui fonde la confiance qu'on lui accorde.

Cryptanalyse linéaire

Découverte par Matsui en 1993 et appliquée à DES, elle cherche des approximations linéaires de la primitive : une relation du type

reliant certains bits du clair, du chiffré et de la clé, qui serait vraie avec probabilité exactement $1/2$ pour un chiffrement parfait. Si elle est vraie avec probabilité $1/2 + \varepsilon$, le biais $\varepsilon$ fuit de l'information : en accumulant assez de couples clair/chiffré, on décide le bit de clé du bon côté, et le nombre de couples nécessaires est de l'ordre de $\varepsilon^{-2}$.

Les deux attaques sont duales. La différentielle est à clairs choisis — il faut pouvoir demander le chiffrement de paires précises — tandis que la linéaire se contente de couples connus, ce qui la rend souvent plus réaliste. Ensemble, elles forment le socle de l'évaluation de tout chiffrement symétrique moderne : un candidat qui n'est pas argumenté contre elles n'est pas pris au sérieux.

Le compromis temps-mémoire

Certaines attaques n'exploitent aucune faiblesse : elles réorganisent la force brute. Le principe général est d'échanger du temps de calcul contre de la mémoire, en précalculant une fois ce qu'on interrogera ensuite rapidement.

Les tables arc-en-ciel, appliquées au cassage de mots de passe hachés, en sont l'exemple courant : au lieu de $2^b$ essais à chaque attaque, on précalcule une structure de taille $2^{2b/3}$ et l'on retrouve ensuite chaque préimage en $2^{2b/3}$ opérations. Le précalcul est amorti sur toutes les attaques suivantes. C'est précisément pourquoi le chapitre 8 imposera de saler les mots de passe : un sel distinct par utilisateur rend toute table précalculée inutilisable, puisqu'elle devrait être refaite pour chaque sel.

La rencontre au milieu

Le compromis le plus élégant frappe le double chiffrement. On pourrait croire qu'appliquer un chiffre deux fois avec deux clés, $C = E_{k_2}(E_{k_1}(P))$, double la sécurité : $2b$ bits de clé, donc $2^{2b}$ efforts. C'est faux.

L'attaquant écrit l'égalité au point du milieu :

Il calcule $E_{k_1}(P)$ pour les $2^b$ valeurs de $k_1$ et les range dans une table, puis essaie les $2^b$ valeurs de $k_2$ en cherchant $D_{k_2}(C)$ dans cette table. Une collision livre un couple candidat. Le coût tombe à $2^{b+1}$ opérations et $2^b$ mémoire, au lieu de $2^{2b}$ — la sécurité n'a gagné qu'un bit, pas $b$.

C'est la réponse à la question laissée ouverte au chapitre 4. Le double DES n'offre pas 112 bits mais environ 57, et c'est pourquoi le standard est le triple DES : trois étages échappent à une rencontre au milieu directe, qui n'y grignote qu'un tiers de la sécurité au lieu de la moitié.

Vous allez le monter. Le chiffre ci-dessous a un bloc plus large que sa clé — exactement la proportion du vrai DES, et ce qui rend la clé nette.

// Chiffre jouet : Feistel 4 tours, bloc 32 bits, clé 16 bits.
// La fonction de tour F n'a pas besoin d'être inversible (propriété Feistel).
const M16 = 0xffff;
const F = (demi, k) => {
  let x = (demi ^ k) & M16;
  x = (x * 40503) & M16;
  x = ((x << 7) | (x >>> 9)) & M16;
  x = (x ^ (x >>> 5)) & M16;
  return x;
};
function E(k, b) {
  let L = (b >>> 16) & M16, R = b & M16;
  for (let r = 0; r < 4; r++) {
    const nR = (L ^ F(R, (k + r * 0x9e37) & M16)) & M16;
    L = R; R = nR;
  }
  return (((L << 16) >>> 0) | R) >>> 0;
}
function D(k, b) {
  let L = (b >>> 16) & M16, R = b & M16;
  for (let r = 3; r >= 0; r--) {
    const pL = (R ^ F(L, (k + r * 0x9e37) & M16)) & M16;
    R = L; L = pL;
  }
  return (((L << 16) >>> 0) | R) >>> 0;
}
const dbl = (k1, k2, p) => E(k2, E(k1, p));

// DOUBLE chiffrement : C = E(k2, E(k1, P)), soit 32 bits de clé au total.
// On dispose de deux couples clair/chiffré connus (attaque à clair connu).
const P1 = 0x6789ab01 >>> 0, C1 = 0x96503ef0 >>> 0;
const P2 = 0x0f1e2d3c >>> 0, C2 = 0xab3240dd >>> 0;

// ── Force brute : les 2^32 couples (k1, k2) ───────────────────────────────
// C'est le coût qu'on veut BATTRE — 4 milliards d'essais.

// ── À COMPLÉTER : rencontre au milieu ─────────────────────────────────────
// E(k1, P1) = D(k2, C1) au point du milieu. On tabule le membre de gauche pour
// les 2^16 valeurs de k1, puis on parcourt les 2^16 valeurs de k2 en cherchant
// une valeur déjà vue, et on confirme sur le second couple.

function rencontreAuMilieu() {
  const table = new Map(); // E(k1, P1) -> k1

  for (let k1 = 0; k1 <= M16; k1++) {
    // à compléter : remplir la table
  }

  for (let k2 = 0; k2 <= M16; k2++) {
    // à compléter : chercher D(k2, C1) dans la table, confirmer sur (P2, C2)
  }
  return null;
}

const t0 = Date.now();
const sol = rencontreAuMilieu();
console.log("clés retrouvées :", sol ? { k1: sol.k1.toString(16), k2: sol.k2.toString(16) } : null,
  "en", Date.now() - t0, "ms");
console.log("essais : ~2·2^16 =", 2 * 65536, "au lieu de 2^32 =", 2 ** 32);

function rencontreAuMilieu() {
  const table = new Map();

  for (let k1 = 0; k1 <= M16; k1++) {
    table.set(E(k1, P1), k1);
  }

  for (let k2 = 0; k2 <= M16; k2++) {
    const milieu = D(k2, C1);
    if (!table.has(milieu)) continue;
    const k1 = table.get(milieu);
    // Confirmer sur le second couple élimine les rares collisions fortuites.
    if (dbl(k1, k2, P2) === C2) return { k1, k2 };
  }
  return null;
}

// Renvoie k1 = 0x1a2b, k2 = 0xc4d5, en quelques millisecondes.
//
// Deux balayages de 2^16 ont remplacé un balayage de 2^32 : le TEMPS chute de
// 2^32 à 2^17, au prix d'une MÉMOIRE de 2^16 entrées. C'est le compromis
// temps-mémoire, et c'est ce qui fait s'effondrer le double chiffrement.
//
// Transposé au vrai DES : le double DES a 2·56 = 112 bits de clé, mais la
// rencontre au milieu le casse en environ 2^57 opérations — à peine plus que
// le DES simple. DOUBLER NE DOUBLE PAS LA SÉCURITÉ. Voilà pourquoi le standard
// est le TRIPLE DES : trois étages placent la barrière hors de portée de la
// rencontre au milieu directe (elle n'y gagne qu'un tiers, pas la moitié).
//
// Le bloc plus large que la clé (ici 32 > 16, dans DES 64 > 56) est ce qui
// rend la table creuse et la clé nette : un seul couple suffit presque, le
// second ne sert qu'à écarter les coïncidences.

Ce que la cryptanalyse enseigne à la conception

Aucune de ces attaques ne brise AES en pratique, et c'est le but. La meilleure attaque publiée sur AES-128 demande environ $2^{126{,}1}$ opérations — une cassure au sens du chapitre 1, sans la moindre portée réelle. Ce qui compte est la marge : AES-128 tourne sur 10 tours quand 6 ou 7 suffiraient à résister aux attaques connues. Cette réserve est délibérée, car les attaques ne reculent jamais. La cryptanalyse ne sert donc pas seulement à casser : elle dit combien de tours mettre, quelles boîtes S choisir, et quelle marge garder pour les vingt ans qui viennent.

Ce que la suite en fait

Ce chapitre clôt le symétrique. Deux idées le traversent et resurgiront : la linéarité est l'ennemi — les LFSR du chapitre 5, les approximations linéaires ici — et le compromis temps-mémoire revient au chapitre 8 sous la forme du salage, et au chapitre 10 avec le rho de Pollard pour le logarithme discret. Le chapitre 7 ouvre un autre monde, celui des fonctions de hachage, où le paradoxe des anniversaires jouera le rôle qu'a joué ici la force brute : l'étalon que toute attaque doit battre.

À retenir

QCM de synthèse — Bloc I — Cryptographie symétrique

Le QCM ci-dessous porte sur l'ensemble du bloc : plusieurs questions relient les leçons entre elles. En cas d'erreur, le bilan indique le chapitre à revoir.