Cryptographie post-quantique · C3 Les autres familles · Chapitre 2 · 4 h

Signatures à base de hachage

Lamport, Winternitz et arbres de Merkle ; SLH-DSA sans état, XMSS et LMS avec état, et le danger de réutilisation d'index.

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.

Animation · 6 étapes

Prouver qu'une clé appartient à l'arbre sans montrer l'arbre

Construire l'arbre — Chaque feuille est le haché d'une clé à usage unique. Chaque nœud interne est le haché de la concaténation de ses deux enfants. La racine, en haut, résume les 8 feuilles en 32 octets — et c'est elle, et elle seule, qui sert de clé publique.
On veut prouver k2 — Le signataire publie la feuille k2 et affirme qu'elle appartient à l'arbre. Il ne peut pas envoyer les 8 feuilles : la preuve serait aussi grosse que l'arbre. Il envoie le chemin d'authentification.
Remontée, niveau 1 — Le vérificateur hache la feuille avec le frère fourni. Il obtient le parent — qu'il n'avait pas reçu, mais qu'il vient de recalculer.
Remontée, niveau 2 — Même opération un cran plus haut : le nœud recalculé et le frère fourni donnent le parent. Un frère par niveau, donc 3 au total pour 8 feuilles.
Remontée, niveau 3 — Même opération un cran plus haut : le nœud recalculé et le frère fourni donnent le parent. Un frère par niveau, donc 3 au total pour 8 feuilles.
Comparer à la racine — La valeur obtenue en haut est comparée à la clé publique. Si elles coïncident, la feuille appartenait bien à l'arbre. Coût de la preuve : 3 hachés au lieu de 8 — c'est le logarithme qui rend l'ensemble praticable.

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.

Quiz · 1 question

Que contient exactement le chemin d'authentification d'un arbre de Merkle ?

Tous les nœuds situés entre la feuille et la racine
Le FRÈRE de chaque nœud rencontré en remontant, soit log₂(n) valeurs
La racine et la feuille, signées ensemble

Réponse : Les nœuds situés SUR le chemin, le vérificateur les recalcule lui-même — c'est même tout l'intérêt. Ce qu'il ne peut pas recalculer, ce sont les frères, et il faut donc les lui fournir : un par niveau, soit log₂(n) valeurs. Pour un million de feuilles, vingt hachés suffisent à prouver l'appartenance.

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 :

	clé publique	signature
SLH-DSA-128s	32 o	7 856 o
SLH-DSA-128f	32 o	17 088 o
SLH-DSA-256s	64 o	29 792 o
ML-DSA-44 (comparaison)	1312 o	2 420 o
Ed25519 (comparaison)	32 o	64 o

Graphique

Taille des signatures, en octets

Ed25519 : 6464
ML-DSA-44 : 24202420
SLH-DSA-128s : 78567856
SLH-DSA-128f : 1708817088
SLH-DSA-256s : 2979229792

Les variantes « s » sont optimisées pour la petite taille, les « f » pour la rapidité de signature : 7856 contre 17088 octets au même niveau de sécurité. Face aux 64 octets d'Ed25519, l'écart va de 120 à 460 — c'est le prix de n'avoir aucune hypothèse algébrique à parier.

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.

Quiz · 1 question

Pourquoi SLH-DSA accepte-t-il des signatures dix fois plus grosses que ML-DSA ?

Parce que sa sécurité ne repose que sur la fonction de hachage, sans aucune hypothèse algébrique
Parce qu'il doit stocker son état dans la signature
Parce qu'il vise un niveau de sécurité supérieur

Réponse : SLH-DSA est justement SANS état — c'est ce qui le distingue de XMSS et LMS. Et il couvre les mêmes niveaux NIST que ML-DSA. Ce qu'on achète avec ces octets, c'est l'absence de pari : ni réseau, ni code, ni courbe, seulement une fonction de hachage, dont la résistance est l'hypothèse la mieux étudiée de la discipline. C'est le prix du filet de sécurité.

À vous

Exercice de code

Complétez la vérification du chemin d'authentification, puis regardez la seconde partie : deux signatures avec le même index suffisent à tout forger.

Point de départ

// 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");

Solution

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");

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

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;
}

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;
}

function verifier(feuille, preuve, racine) {
  let courant = feuille;
  for (const { valeur, aDroite } of preuve) {
    // L'ORDRE est la seule subtilité, et c'est une vraie faille quand on
    // l'oublie : un arbre où h(a:b) et h(b:a) seraient interchangeables
    // laisserait forger des preuves en permutant les frères.
    courant = aDroite ? h(courant + ":" + valeur) : h(valeur + ":" + 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));

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;

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");

// Les deux moitiés de l'exercice disent la même chose sous deux angles.
//
// PARTIE 1 — la preuve fait 3 hachés pour 8 feuilles, et ferait 20 hachés
// pour un million. C'est le logarithme, et c'est ce qui rend praticable une
// clé publique de 32 octets qui autorise des milliards de signatures.
// Notez que l'ordre de concaténation compte : un arbre où h(a:b) et h(b:a)
// seraient équivalents laisserait forger des preuves.
//
// PARTIE 2 — c'est la catastrophe. Signer DEUX messages complémentaires
// avec la même clé de Lamport révèle les 16 valeurs secrètes, et permet
// alors de signer N'IMPORTE QUEL message. Pas « affaiblit » : permet.
//
// Voilà pourquoi XMSS et LMS sont dits « à état » et pourquoi cet état est
// leur talon d'Achille opérationnel. Restaurer une sauvegarde, cloner une
// machine virtuelle, répliquer un service derrière un répartiteur de
// charge — toutes ces opérations parfaitement banales rejouent un index et
// détruisent la clé. SLH-DSA supprime l'état, au prix d'une signature dix
// fois plus grosse. Le prix se discute ; le risque, non.

À retenir

Flashcards · 3 cartes

Pourquoi les signatures à base de hachage servent-elles de filet de sécurité ?: Parce qu'elles ne reposent sur aucune structure algébrique — ni factorisation, ni réseau, ni code — mais seulement sur la résistance d'une fonction de hachage, l'hypothèse la mieux étudiée de la discipline. Grover ne fait que diviser par deux la sécurité en préimage. Si les réseaux tombaient, SLH-DSA resterait debout.
Quel est le danger opérationnel des schémas à état comme XMSS et LMS ?: Rejouer un index ne les affaiblit pas, il DÉTRUIT la clé : deux signatures au même index permettent de forger. Or restaurer une sauvegarde, cloner une machine virtuelle ou répliquer un service derrière un répartiteur de charge rejouent tous un état. La SP 800-208 les réserve aux contextes où l'état est garanti — typiquement la signature de firmware.
Comment SLH-DSA se passe-t-il d'état ?: En choisissant la feuille pseudo-aléatoirement à partir du message plutôt que séquentiellement. Comme des collisions restent possibles, les signatures à usage unique sont remplacées par des signatures à usages peu nombreux (FORS), tolérantes à quelques répétitions, et plusieurs arbres sont empilés en hypertree. Coût : une signature de 8 à 30 kio.