Fonctions de hachage

Une fonction de hachage comprime un message de taille quelconque en une empreinte de taille fixe — 256 bits pour SHA-256. Elle n'a pas de clé, elle est publique, et pourtant elle est partout : signatures, mots de passe, intégrité des fichiers, blockchains, identifiants Git. Sa sécurité ne tient pas au secret mais à trois propriétés de résistance, qu'il faut distinguer avec soin car les attaques et les seuils ne sont pas les mêmes.

Trois résistances, trois seuils

Notons $H$ la fonction et $n$ la taille de l'empreinte.

Résistance à la préimage. Étant donné une empreinte $y$, il doit être infaisable de trouver un message $m$ tel que $H(m) = y$. C'est l'irréversibilité : d'une empreinte, on ne remonte pas au message. Coût de l'attaque générique : $2^n$.

Résistance à la seconde préimage. Étant donné un message $m$, il doit être infaisable d'en trouver un autre $m' \neq m$ avec $H(m') = H(m)$. Coût générique : $2^n$.

Résistance aux collisions. Il doit être infaisable de trouver un couple $m \neq m'$ tel que $H(m) = H(m')$. Ici l'attaquant choisit les deux messages, et cette liberté change tout : coût générique $2^{n/2}$ seulement.

Ce facteur deux dans l'exposant est le cœur du chapitre. La collision est quadratiquement plus facile que la préimage, et c'est ce qui fixe la taille des empreintes.

Le paradoxe des anniversaires

Dans un groupe de 23 personnes, la probabilité que deux partagent un anniversaire dépasse 50 %. L'intuition proteste — il faudrait sûrement approcher 183, la moitié de 365 — et l'intuition a tort. On ne compare pas une personne aux autres, mais toutes les paires : il y en a $\binom{23}{2} = 253$, assez pour qu'une coïncidence devienne probable.

Le même calcul vaut pour les empreintes. Après environ $\sqrt{N}$ tirages dans un espace de $N$ valeurs, une collision devient probable. Pour $N = 2^n$, cela fait $2^{n/2}$ — pas $2^n$. Une empreinte de $n$ bits n'offre donc que $n/2$ bits de résistance aux collisions, tout en gardant $n$ bits contre la préimage.

Cette asymétrie décide tout. SHA-256 rend 256 bits pour offrir 128 bits contre les collisions : le seuil de sécurité usuel. Un haché de 128 bits ne résisterait qu'à $2^{64}$, aujourd'hui atteignable — c'est ce qui a condamné MD5 (128 bits) et SHA-1 (160 bits, dont la première collision publique, SHAttered, a coûté environ $2^{63}$ calculs en 2017).

Vous allez voir la première collision arriver de vos yeux, très en dessous de la taille de l'espace.

// Un haché jouet de n bits, pour observer où tombe la PREMIÈRE collision.
// On tire des messages au hasard, on hache, et on s'arrête à la première
// valeur déjà vue.

function hache(x, bits) {
  // Mélange déterministe, tronqué à 'bits' bits. La qualité importe peu :
  // seule compte la taille de sortie.
  let h = (x * 2654435761) >>> 0;
  h ^= h >>> 15; h = (h * 0x85ebca6b) >>> 0;
  h ^= h >>> 13;
  return h & ((1 << bits) - 1);
}

function premiereCollision(bits) {
  const vus = new Map();
  let essais = 0;
  while (true) {
    const m = (Math.random() * 1e9) | 0;
    const h = hache(m, bits);
    essais++;
    if (vus.has(h)) return essais;
    vus.set(h, m);
  }
}

// ── Observation ───────────────────────────────────────────────────────────
// Pour chaque taille de sortie, moyennez le nombre de tirages avant collision
// sur plusieurs répétitions, et comparez à 2^(bits/2).

console.log("bits | espace 2^bits | collision observée | ~1,25·2^(bits/2)");
for (const bits of [8, 12, 16, 20]) {
  let total = 0;
  const repet = 40;
  for (let i = 0; i < repet; i++) total += premiereCollision(bits);
  const moyenne = Math.round(total / repet);
  const attendu = Math.round(1.25 * Math.sqrt(2 ** bits));
  console.log(
    String(bits).padStart(4),
    String(2 ** bits).padStart(13),
    String(moyenne).padStart(18),
    String(attendu).padStart(17)
  );
}

// ── À COMPLÉTER ───────────────────────────────────────────────────────────
// La collision tombe vers √(espace), pas vers l'espace entier. Écrivez la
// taille de sortie MINIMALE (en bits) pour qu'une attaque par anniversaire
// coûte au moins 2^128, le seuil de sécurité usuel.

const bitsPourResister128 = 0; // à compléter
console.log("Pour 128 bits de résistance aux collisions, il faut une sortie de",
  bitsPourResister128, "bits.");

// Le nombre de tirages avant collision suit environ 1,25·2^(bits/2) : chaque
// fois qu'on ajoute 2 bits de sortie, il double. C'est le paradoxe des
// anniversaires — √N essais pour N valeurs possibles, pas N.

// Donc pour qu'une attaque coûte 2^128, il faut 2^(bits/2) = 2^128, soit :
const bitsPourResister128 = 256;
console.log("Pour 128 bits de résistance aux collisions, il faut une sortie de",
  bitsPourResister128, "bits.");

// C'est LA raison pour laquelle SHA-256 existe et pourquoi on ne se contente
// pas de SHA-128 : la résistance aux collisions d'un haché de n bits n'est que
// de n/2 bits. Un haché de 128 bits ne résiste qu'à 2^64 — atteignable — ce
// qui a scellé le sort de MD5 (128 bits) et de SHA-1 (160 bits, cassé à 2^63).
//
// Nuance importante : ce n/2 ne vaut QUE pour les collisions. La résistance à
// la préimage et à la seconde préimage reste, elle, de n bits complets — car
// on n'y a pas la liberté de choisir les DEUX messages. D'où l'asymétrie du
// chapitre : SHA-256 offre 128 bits contre les collisions mais 256 contre la
// préimage.

Merkle-Damgård : construire long à partir de court

Comment hacher un message de gigaoctets ? On part d'une fonction de compression $f$ qui mélange un bloc de message et un état interne, et on l'itère : l'empreinte d'un bloc devient l'état d'entrée du suivant, amorcé par une valeur initiale fixe.

C'est la construction Merkle-Damgård, celle de MD5, SHA-1 et SHA-2. Son théorème fondateur est rassurant : si la fonction de compression $f$ résiste aux collisions, alors la fonction itérée $H$ y résiste aussi. On ramène la sécurité du tout à celle d'une brique petite et analysable.

Le message est d'abord complété par un rembourrage qui encode sa longueur (le « Merkle-Damgård strengthening ») — détail qui va se révéler à double tranchant.

La faille : l'extension de longueur

Merkle-Damgård a un défaut structurel qui n'est pas une faiblesse de collision mais une fuite d'usage. L'empreinte $H(m)$ est l'état interne final. Quiconque la connaît peut reprendre le calcul là où il s'est arrêté et calculer $H(m \Vert \text{padding} \Vert m')$ pour un suffixe $m'$ de son choix — sans connaître $m$.

La conséquence est concrète et a été exploitée en production. On croit parfois authentifier un message en publiant $H(\text{clé} \Vert \text{message})$ — un « MAC préfixe ». C'est cassé : l'extension de longueur permet de forger l'empreinte d'un message rallongé sans jamais connaître la clé. La leçon vaut d'être retenue avant le chapitre 8 : un haché n'est pas un MAC, et bricoler l'un pour obtenir l'autre échoue. Le chapitre 8 montrera la construction correcte, HMAC, dont la double application ferme précisément cette porte.

L'éponge : SHA-3, une autre architecture

Après les chutes de MD5 et SHA-1, toutes deux Merkle-Damgård, le NIST a voulu une construction de structure différente pour ne pas mettre tous ses œufs dans le même panier. SHA-3, issu de la fonction Keccak et normalisé en 2015, adopte la construction éponge.

Un grand état interne est divisé en deux parties : le débit $r$, par lequel entre et sort le message, et la capacité $c$, jamais exposée directement, qui porte la sécurité. On procède en deux temps : la phase d'absorption injecte les blocs du message dans le débit en permutant l'état à chaque fois ; la phase d'essorage en extrait l'empreinte. La sécurité aux collisions vaut $c/2$.

Le gain est double. D'abord SHA-3 est immunisé contre l'extension de longueur : la capacité n'apparaît jamais dans la sortie, il n'y a donc pas d'état final à prolonger. Ensuite l'éponge est polyvalente — la même permutation produit des empreintes de taille variable (les fonctions extensibles SHAKE), des générateurs pseudo-aléatoires, et des schémas d'authentification.

Un point que la pratique dément souvent : SHA-3 n'a pas rendu SHA-2 obsolète. SHA-2 reste sûr, largement déployé, et souvent plus rapide en logiciel. SHA-3 est une alternative de secours d'architecture indépendante, pas un remplaçant imposé — la même logique d'agilité que le chapitre 14 généralisera.

Ce que la suite en fait

Les trois résistances de ce chapitre sont les hypothèses des chapitres suivants. Le chapitre 8 construit HMAC sur une fonction de hachage et referme l'extension de longueur ; la signature RSA-PSS au chapitre 9 et ECDSA au chapitre 11 hachent le message avant de le signer, et leur sécurité repose directement sur la résistance aux collisions — une collision sur le haché est une signature forgée. Le paradoxe des anniversaires, enfin, reviendra au chapitre 10 sous les traits du rho de Pollard, qui l'exploite pour le logarithme discret.

À retenir