Chiffrement par blocs

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