Signatures à base de hachage

Cette famille est à part, et il faut le dire dès l'ouverture. Les signatures à base de hachage ne reposent sur aucune structure algébrique : ni factorisation, ni logarithme discret, ni réseau, ni code. Leur seule hypothèse est qu'une fonction de hachage se comporte comme on l'attend. C'est l'hypothèse la mieux étudiée de toute la cryptographie, et la seule dont on soit à peu près certain qu'elle survivra à un ordinateur quantique — Grover ne fait que diviser par deux la sécurité en préimage.

D'où leur rôle : un filet de sécurité. Si les réseaux tombaient demain, SLH-DSA resterait debout.

Lamport : signer un bit

La construction de base est d'une simplicité désarmante, et date de 1979.

Pour signer un message de $n$ bits, on tire $2n$ valeurs secrètes aléatoires, deux par position : $x_{i,0}$ et $x_{i,1}$. La clé publique est la liste de leurs hachés, $y_{i,b} = H(x_{i,b})$.

Pour signer, on révèle $x_{i, m_i}$ pour chaque position $i$ — la valeur de gauche si le bit vaut 0, celle de droite s'il vaut 1. Pour vérifier, on hache ce qu'on a reçu et on compare à la clé publique.

La sécurité est immédiate : forger une signature exigerait d'inverser $H$ sur une valeur jamais révélée. Aucune structure, aucune réduction compliquée.

Le défaut l'est tout autant. La clé ne sert qu'une fois. Signer un second message avec la même clé révèle des valeurs supplémentaires, et l'exercice de fin de chapitre montre que deux messages bien choisis suffisent à tout révéler.

Winternitz : troquer du temps contre de la taille

Lamport produit des signatures énormes. Winternitz les réduit en traitant plusieurs bits à la fois, au moyen de chaînes de hachage.

Au lieu de deux valeurs par position, on part d'une valeur $x$ et on définit $H(x), H^2(x), \dots, H^{w-1}(x)$. Signer la valeur $v$ consiste à révéler $H^{v}(x)$ : le vérificateur applique $H$ encore $w-1-v$ fois et retombe sur la clé publique. On signe ainsi $\log_2 w$ bits par chaîne au lieu d'un seul.

Le compromis est explicite : augmenter $w$ raccourcit la signature et allonge le calcul, linéairement en $w$. Une somme de contrôle est ajoutée pour empêcher un attaquant d'« avancer » dans les chaînes et de forger une valeur plus grande. WOTS+ est la variante employée dans les schémas normalisés.

Merkle : d'une clé unique à un milliard

Reste le problème central : une clé à usage unique n'est pas utilisable. Merkle l'a résolu en 1979, la même année, et sa solution est aujourd'hui partout — de Git aux chaînes de blocs.

On engendre $2^H$ clés à usage unique, on hache chacune, et on construit un arbre binaire où chaque nœud est le haché de ses deux enfants. La racine devient la clé publique unique, 32 octets pour un nombre arbitraire de signatures.

Pour signer avec la $i$-ième clé, on fournit la signature à usage unique, plus le chemin d'authentification : les frères rencontrés en remontant à la racine. Le vérificateur recalcule la remontée et compare. Il ne fait pas confiance — il refait le calcul.

Le coût de la preuve est $\log_2$ du nombre de feuilles. Trois hachés pour huit clés, vingt pour un million. C'est cette croissance logarithmique qui rend toute la famille praticable.

Avec état : XMSS, LMS, et le piège opérationnel

XMSS (RFC 8391) et LMS (RFC 8554) mettent tout cela en œuvre. Ils sont normalisés, éprouvés, et produisent des signatures raisonnablement compactes.

Ils sont aussi à état. Le signataire doit mémoriser quel index il a déjà consommé, et cet état doit être mis à jour de façon durable et atomique avant l'émission de chaque signature.

Il faut insister, parce que l'énoncé paraît anodin et que ses conséquences ne le sont pas. Rejouer un index n'affaiblit pas la clé : il la détruit. Un attaquant qui observe deux signatures produites avec le même index peut forger. Et les opérations qui rejouent un état sont exactement celles que toute exploitation informatique pratique quotidiennement :

• restaurer une sauvegarde ;
• cloner ou reprendre l'instantané d'une machine virtuelle ;
• répliquer un service derrière un répartiteur de charge ;
• redémarrer après une panne, entre l'écriture de la signature et celle de l'état.

Le NIST, dans la SP 800-208, encadre ces schémas d'exigences strictes et les réserve explicitement à des contextes où l'état peut être garanti — typiquement la signature de firmware, opération rare, centralisée, sous contrôle matériel.

Sans état : SLH-DSA

SLH-DSA (FIPS 205), issu de SPHINCS+, supprime l'état. L'idée : au lieu de consommer les feuilles dans l'ordre, en choisir une pseudo-aléatoirement à partir du message. Comme une collision reste possible, on remplace les signatures à usage unique par des signatures à usages peu nombreux (FORS), qui tolèrent quelques répétitions, et on empile plusieurs arbres en hypertree pour maintenir la taille raisonnable.

Le résultat est un schéma sans état, sans structure algébrique, et dont la sécurité ne dépend que du haché. Le prix est franc :

La signature est cent fois plus grosse qu'Ed25519, et la signature est lente. En échange, on obtient la garantie la plus solide du paysage. Ce n'est pas un schéma à déployer partout ; c'est un schéma à déployer là où l'on ne peut pas se permettre d'avoir tort — racines de confiance, signature de firmware à très longue durée de vie, ancrage d'une PKI.

À vous

// Un haché JOUET — 32 bits, non cryptographique. Il suffit à faire tourner
// la mécanique ; ne l'utilisez jamais pour autre chose qu'un exercice.
function h(x) {
  let v = 0x811c9dc5;
  for (const car of String(x)) {
    v ^= car.charCodeAt(0);
    v = Math.imul(v, 0x01000193) >>> 0;
  }
  return v >>> 0;
}
const hex = (v) => v.toString(16).padStart(8, "0");

// ─────────── Partie 1 : l'arbre de Merkle ───────────

const FEUILLES = ["k0", "k1", "k2", "k3", "k4", "k5", "k6", "k7"].map(h);

// Construit tous les niveaux, des feuilles à la racine.
function construire(feuilles) {
  const niveaux = [feuilles];
  while (niveaux.at(-1).length > 1) {
    const bas = niveaux.at(-1);
    const haut = [];
    for (let i = 0; i < bas.length; i += 2) haut.push(h(bas[i] + ":" + bas[i + 1]));
    niveaux.push(haut);
  }
  return niveaux;
}

// Le chemin d'authentification : le FRÈRE rencontré à chaque niveau.
function chemin(niveaux, indice) {
  const preuve = [];
  let i = indice;
  for (let n = 0; n < niveaux.length - 1; n++) {
    preuve.push({ valeur: niveaux[n][i ^ 1], aDroite: (i & 1) === 0 });
    i >>= 1;
  }
  return preuve;
}

// Le vérificateur : il ne connaît QUE la feuille, la preuve et la racine.
function verifier(feuille, preuve, racine) {
  let courant = feuille;
  for (const { valeur, aDroite } of preuve) {
    // À COMPLÉTER — recombiner courant et valeur dans le BON ORDRE.
    courant = courant;
  }
  return courant === racine;
}

const niveaux = construire(FEUILLES);
const racine = niveaux.at(-1)[0];
const preuve = chemin(niveaux, 2);

console.log("racine (clé publique) :", hex(racine));
console.log("preuve pour k2        :", preuve.map((p) => hex(p.valeur)).join(" "));
console.log("taille de la preuve   :", preuve.length, "hachés pour", FEUILLES.length, "feuilles");
console.log("vérification k2       :", verifier(FEUILLES[2], preuve, racine));
console.log("vérification d'un faux:", verifier(h("intrus"), preuve, racine));

// ─────────── Partie 2 : ce que coûte un index rejoué ───────────
// Fourni. Signature de Lamport sur 8 bits, utilisée DEUX fois.

const bits = (n) => Array.from({ length: 8 }, (_, i) => (n >> (7 - i)) & 1);
const sk = Array.from({ length: 8 }, (_, i) => [h("s" + i + "a"), h("s" + i + "b")]);
const pk = sk.map(([a, b]) => [h(a), h(b)]);

const signer = (m) => bits(m).map((b, i) => sk[i][b]);
const verifierLamport = (m, sig) => bits(m).every((b, i) => h(sig[i]) === pk[i][b]);

const M1 = 0b10110010;
const M2 = 0b01001101;   // le complément : ensemble, ils révèlent TOUT

const connus = {};
for (const m of [M1, M2]) signer(m).forEach((v, i) => (connus[i + ":" + bits(m)[i]] = v));

const forger = (cible) => bits(cible).map((b, i) => connus[i + ":" + b]);
const CIBLE = 0b11111111;
const faux = forger(CIBLE);

console.log("\n── réutilisation d'index ──");
console.log("valeurs révélées      :", Object.keys(connus).length, "/ 16");
console.log("signature forgée sur", CIBLE.toString(2), ":", verifierLamport(CIBLE, faux) ? "ACCEPTÉE" : "refusée");

À retenir