Cryptanalyse symétrique

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.