« Prouvé sûr » est l'expression la plus mal comprise de la cryptographie. Elle ne signifie jamais « incassable ». Elle signifie : si telle hypothèse tient, et si le modèle décrit correctement l'attaquant, alors casser le schéma est au moins aussi difficile que résoudre tel problème. Trois conditions, trois endroits où la preuve peut ne rien garantir.

Ce chapitre précise ce que les preuves post-quantiques disent, et surtout où elles s'arrêtent.

Un jeu de sécurité, c'est une définition opérationnelle

On ne définit pas la sécurité par une propriété abstraite mais par un jeu entre un challenger et un adversaire. Trois jeux couvrent presque tout le cours.

IND-CPA. L'adversaire reçoit la clé publique, soumet deux messages de même longueur, et reçoit le chiffré de l'un des deux tiré au hasard. Il gagne s'il devine lequel avec un avantage non négligeable sur le hasard. C'est le minimum : il modélise un attaquant passif, qui observe.

IND-CCA2. Même jeu, mais l'adversaire dispose en plus d'un oracle de déchiffrement qu'il peut interroger sur n'importe quel chiffré, sauf celui du défi. C'est un attaquant actif, et c'est le modèle réaliste : dans un protocole, votre serveur déchiffre volontiers tout ce qu'on lui envoie et son comportement se lit dans sa réponse.

EUF-CMA. Pour les signatures : l'adversaire obtient des signatures sur les messages de son choix, et gagne s'il produit une signature valide sur un message jamais soumis.

L'écart entre IND-CPA et IND-CCA2 n'est pas académique. Le chiffrement du chapitre 6 est IND-CPA et parfaitement malléable : ajouter $q/2$ à un coefficient du chiffré inverse un bit du message, sans connaître la clé. L'exercice de ce chapitre vous le fait faire en trois lignes.

ROM : l'oracle aléatoire

Beaucoup de preuves, dont celle de Fujisaki-Okamoto, se placent dans le modèle de l'oracle aléatoire. On y suppose que la fonction de hachage se comporte comme une fonction véritablement aléatoire, à laquelle tout le monde — y compris le réducteur de la preuve — n'accède que par requêtes.

C'est une idéalisation, et une idéalisation fausse : SHA-3 est un algorithme public de quelques centaines de lignes, pas une fonction aléatoire. Canetti, Goldreich et Halevi ont même construit des schémas prouvés sûrs dans le ROM et cassés pour toute instanciation concrète du hachage.

Ces contre-exemples sont artificiels, et aucun schéma déployé n'en a jamais souffert. Le ROM reste donc largement accepté, mais comme un argument de conception plutôt que comme une garantie mathématique. Il faut le formuler ainsi devant des étudiants : une preuve ROM dit qu'il n'existe pas d'attaque générique, pas qu'il n'existe pas d'attaque.

QROM : ce que change un attaquant quantique

Voici le point spécifiquement post-quantique du chapitre, et il est plus subtil qu'il n'en a l'air.

Un attaquant quantique qui dispose du code de SHA-3 peut l'implémenter en circuit quantique et l'interroger en superposition : une seule requête sur une superposition de toutes les entrées possibles. Le modèle qui capture cela s'appelle le QROM, l'oracle aléatoire quantique.

Ce n'est pas seulement un attaquant plus fort. C'est un modèle où les techniques de preuve classiques cessent de fonctionner :

• l'échantillonnage paresseux disparaît. En ROM, le réducteur note les requêtes et choisit les réponses au fur et à mesure. En QROM, observer une requête en superposition la perturbe : on ne peut plus tenir de registre sans être détecté.
• l'extraction devient problématique. Beaucoup de preuves reposent sur le fait que l'adversaire a forcément interrogé l'oracle sur une valeur précise, qu'on lit dans le registre. En superposition, cette lecture n'a plus de sens direct.
• le rembobinage — rejouer l'adversaire avec des réponses différentes — se heurte au fait qu'on ne peut pas cloner un état quantique.

Il a fallu reconstruire l'outillage. Le lemme central s'appelle one-way to hiding (O2H), et les preuves QROM de Fujisaki-Okamoto ont été établies à partir de 2017, plusieurs années après les preuves ROM correspondantes. Certaines restent moins serrées que leurs analogues classiques.

Une preuve ROM ne vaut pas automatiquement en QROM. C'est la phrase à retenir de cette section, et c'est ce qui distingue un schéma « post-quantique » sérieux d'un schéma qui se contente d'une hypothèse résistante.

Fujisaki-Okamoto, déroulée

La transformation fait passer d'un PKE IND-CPA à un KEM IND-CCA2 en rendant le chiffrement vérifiable : on dérive l'aléa du message, ce qui rend le chiffrement déterministe, et le déchiffreur refait le chiffrement pour comparer.

L'argument de sécurité tient en une observation. Pour qu'un chiffré passe le test, il faut qu'il ait été produit par la procédure d'encapsulation à partir d'un message $m$ — donc que l'attaquant connaisse $m$. Or s'il connaît $m$, il connaît déjà la clé $K = G(m)$ : l'oracle de déchiffrement ne lui apprend rien. L'oracle devient simulable sans la clé secrète, et c'est exactement ce dont la réduction a besoin.

La branche « sinon » est le détail qui compte. Le rejet implicite renvoie une clé pseudo-aléatoire dérivée d'un secret interne et du chiffré, plutôt qu'une erreur. Deux raisons : l'erreur serait un oracle de validité, et la clé bidon est déterministe, donc un attaquant qui rejoue le même chiffré obtient la même réponse — il n'apprend rien non plus en répétant.

Les niveaux de sécurité du NIST

Le NIST n'exprime pas la sécurité en bits, ce qui serait ambigu entre modèles de coût, mais par équivalence avec des primitives symétriques bien comprises.

Le choix de cette échelle est habile. Il évite d'avoir à trancher entre les modèles de coût du chapitre 4, et il transporte automatiquement les hypothèses sur le matériel quantique : si Grover se révèle plus cher que prévu à cause de contraintes de profondeur de circuit, tous les niveaux se décalent ensemble, sans qu'aucune spécification n'ait à être réécrite.

En pratique, le niveau 3 — ML-KEM-768 et ML-DSA-65 — est la recommandation par défaut, et c'est ce que les navigateurs déploient.

Où la preuve s'arrête

Trois honnêtetés, à énoncer explicitement en cours.

Le serrage. Une réduction qui perd un facteur $2^{40}$ n'interdit pas les attaques en $2^{88}$ contre un schéma annoncé à 128 bits. En pratique, on dimensionne d'après l'estimation d'attaque du chapitre 4 et l'on ignore la perte de la réduction. C'est un choix raisonné, pas une conséquence de la preuve.

Le modèle décrit un attaquant, pas le monde. Aucun jeu de sécurité de ce chapitre ne donne à l'adversaire le temps d'exécution, la consommation électrique ou la possibilité d'injecter une faute. Un schéma peut être IND-CCA2 dans le QROM et tomber en quelques minutes sur une carte à puce. C'est le chapitre 12, et c'est là que se produisent la plupart des attaques réelles.

L'hypothèse peut être fausse. Toute la construction repose sur la difficulté de Module-LWE. SIKE était prouvé sûr sous son hypothèse ; l'hypothèse a cédé.

À vous

// Un mini K-PKE, réduit à n = 4 coefficients mais structurellement exact :
// Module-LWE de rang 1, arithmétique négacyclique, message encodé en q/2.
// Assez pour monter une attaque à chiffré choisi, et voir FO l'arrêter.

const q = 3329, n = 4;
const mod = (x) => ((x % q) + q) % q;
const centre = (x) => (mod(x) > q / 2 ? mod(x) - q : mod(x));

const mul = (f, g) => {
  const r = new Array(n).fill(0);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) {
      const d = i + j;
      r[d % n] = mod(r[d % n] + (d >= n ? -1 : 1) * f[i] * g[j]);
    }
  return r;
};
const add = (f, g) => f.map((x, i) => mod(x + g[i]));
const sub = (f, g) => f.map((x, i) => mod(x - g[i]));

// Générateur pseudo-aléatoire déterministe : FO exige de pouvoir REFAIRE
// exactement le même chiffrement à partir de la même graine.
function prng(graine) {
  let v = 0x811c9dc5;
  for (const c of String(graine)) { v ^= c.charCodeAt(0); v = Math.imul(v, 0x01000193) >>> 0; }
  return () => { v ^= v << 13; v ^= v >>> 17; v ^= v << 5; v >>>= 0; return v; };
}
const petit = (suivant) => Array.from({ length: n }, () => (suivant() % 3) - 1);

const A = [2571, 913, 3200, 47];
const cleSecrete = petit(prng("secret"));
const t = add(mul(A, cleSecrete), petit(prng("erreur")));

const encoder = (bits) => bits.map((b) => b * Math.round(q / 2));
const decoder = (p) => p.map((c) => (Math.abs(centre(c)) > q / 4 ? 1 : 0));

function chiffrer(bits, graine) {
  const g = prng(graine);
  const r = petit(g), e1 = petit(g), e2 = petit(g);
  return { u: add(mul(A, r), e1), v: add(add(mul(t, r), e2), encoder(bits)) };
}
const dechiffrer = (c) => decoder(sub(c.v, mul(cleSecrete, c.u)));

const M = [1, 0, 1, 1];
const c = chiffrer(M, "aléa-honnête");
console.log("message           :", M.join(""));
console.log("déchiffré          :", dechiffrer(c).join(""));

// ── L'attaque : le schéma est MALLÉABLE ──
// Ajouter q/2 à un coefficient de v inverse le bit correspondant, sans
// jamais connaître la clé secrète.
function trafiquer(c, position) {
  const v = c.v.slice();
  // À COMPLÉTER — ajouter Math.round(q / 2) au coefficient d'indice position.
  return { u: c.u, v };
}

const cTrafique = trafiquer(c, 1);
console.log("\ntrafiqué (bit 1)   :", dechiffrer(cTrafique).join(""), " ← attendu 1111");

// ── La parade : Fujisaki-Okamoto ──
// L'aléa est dérivé du message lui-même, donc le chiffrement devient
// déterministe et le déchiffreur peut REFAIRE le chiffrement et comparer.
const memeChiffre = (a, b) => a.u.every((x, i) => x === b.u[i]) && a.v.every((x, i) => x === b.v[i]);

function decapsulerFO(chiffre) {
  const m = dechiffrer(chiffre);
  const c2 = chiffrer(m, "G:" + m.join(""));   // ré-encapsulation
  return memeChiffre(c2, chiffre) ? { ok: true, cle: m.join("") } : { ok: false, cle: "clé bidon" };
}

const cFO = chiffrer(M, "G:" + M.join(""));
console.log("\nFO, chiffré honnête :", JSON.stringify(decapsulerFO(cFO)));
console.log("FO, chiffré trafiqué:", JSON.stringify(decapsulerFO(trafiquer(cFO, 1))));

const q = 3329, n = 4;
const mod = (x) => ((x % q) + q) % q;
const centre = (x) => (mod(x) > q / 2 ? mod(x) - q : mod(x));

const mul = (f, g) => {
  const r = new Array(n).fill(0);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) {
      const d = i + j;
      r[d % n] = mod(r[d % n] + (d >= n ? -1 : 1) * f[i] * g[j]);
    }
  return r;
};
const add = (f, g) => f.map((x, i) => mod(x + g[i]));
const sub = (f, g) => f.map((x, i) => mod(x - g[i]));

function prng(graine) {
  let v = 0x811c9dc5;
  for (const c of String(graine)) { v ^= c.charCodeAt(0); v = Math.imul(v, 0x01000193) >>> 0; }
  return () => { v ^= v << 13; v ^= v >>> 17; v ^= v << 5; v >>>= 0; return v; };
}
const petit = (suivant) => Array.from({ length: n }, () => (suivant() % 3) - 1);

const A = [2571, 913, 3200, 47];
const cleSecrete = petit(prng("secret"));
const t = add(mul(A, cleSecrete), petit(prng("erreur")));

const encoder = (bits) => bits.map((b) => b * Math.round(q / 2));
const decoder = (p) => p.map((c) => (Math.abs(centre(c)) > q / 4 ? 1 : 0));

function chiffrer(bits, graine) {
  const g = prng(graine);
  const r = petit(g), e1 = petit(g), e2 = petit(g);
  return { u: add(mul(A, r), e1), v: add(add(mul(t, r), e2), encoder(bits)) };
}
const dechiffrer = (c) => decoder(sub(c.v, mul(cleSecrete, c.u)));

const M = [1, 0, 1, 1];
const c = chiffrer(M, "aléa-honnête");
console.log("message           :", M.join(""));
console.log("déchiffré          :", dechiffrer(c).join(""));

function trafiquer(c, position) {
  const v = c.v.slice();
  // Le message est encodé en plaçant chaque bit près de 0 ou près de q/2.
  // Ajouter q/2 déplace donc le coefficient de l'un vers l'autre : le bit
  // s'inverse. Aucune connaissance de la clé n'est requise — c'est la
  // définition même de la malléabilité.
  v[position] = mod(v[position] + Math.round(q / 2));
  return { u: c.u, v };
}

const cTrafique = trafiquer(c, 1);
console.log("\ntrafiqué (bit 1)   :", dechiffrer(cTrafique).join(""), " ← attendu 1111");

const memeChiffre = (a, b) => a.u.every((x, i) => x === b.u[i]) && a.v.every((x, i) => x === b.v[i]);

function decapsulerFO(chiffre) {
  const m = dechiffrer(chiffre);
  const c2 = chiffrer(m, "G:" + m.join(""));
  return memeChiffre(c2, chiffre) ? { ok: true, cle: m.join("") } : { ok: false, cle: "clé bidon" };
}

const cFO = chiffrer(M, "G:" + M.join(""));
console.log("\nFO, chiffré honnête :", JSON.stringify(decapsulerFO(cFO)));
console.log("FO, chiffré trafiqué:", JSON.stringify(decapsulerFO(trafiquer(cFO, 1))));

// Ce que l'exercice démontre, dans l'ordre.
//
// 1. LE SCHÉMA CPA EST MALLÉABLE. Ajouter q/2 à un coefficient inverse le
//    bit correspondant, sans clé, sans calcul, sans rien. Le déchiffrement
//    ne proteste pas : il rend un message différent, parfaitement formé.
//    IND-CPA n'a jamais prétendu l'empêcher — il ne parle que d'un
//    attaquant PASSIF.
//
// 2. FO L'ARRÊTE, et le mécanisme est visible ici. L'aléa étant dérivé du
//    message, le chiffrement devient déterministe : le déchiffreur refait
//    le chiffrement et compare. Le chiffré trafiqué déchiffre en un autre
//    message, dont le rechiffrement ne redonne pas le chiffré soumis.
//
// 3. LA LIGNE À REGARDER est le "clé bidon". On ne renvoie PAS d'erreur.
//    Une erreur dirait à l'attaquant que sa modification a été détectée,
//    et il pourrait alors faire varier sa modification pour apprendre le
//    secret coefficient par coefficient. Le rejet implicite lui refuse ce
//    signal — à condition que l'implémentation mette exactement le même
//    temps dans les deux branches. C'est le chapitre suivant.

À retenir

Le chapitre précédent s'est terminé sur une limite : aucun jeu de sécurité ne donne à l'adversaire un chronomètre, une sonde de courant ou un laser. C'est pourtant par là que passent la majorité des attaques réelles. Un schéma parfaitement prouvé peut tomber en quelques minutes sur une carte à puce, et cela n'invalide en rien la preuve — cela montre qu'elle parlait d'autre chose.

Ce chapitre est le plus long du cours. Ce n'est pas un hasard : c'est là que se joue la sécurité effective des déploiements.

Le modèle change

Les modèles du chapitre 11 traitent l'implémentation comme une boîte noire : l'adversaire soumet des entrées et lit des sorties. Un circuit réel n'est pas une boîte noire. Il met un certain temps, consomme un certain courant, émet un certain rayonnement, et peut être perturbé.

Chacune de ces grandeurs est une sortie supplémentaire, non prévue par la spécification, et souvent corrélée aux valeurs secrètes manipulées. C'est tout le domaine des canaux auxiliaires, ouvert par Kocher en 1996 avec les attaques temporelles, puis en 1999 avec l'analyse différentielle de consommation.

L'animation compare deux fonctions qui font la même chose et donnent le même résultat. La première sort dès qu'elle trouve une différence ; la seconde lit tout. Cette différence d'écriture, qui paraîtrait un détail d'optimisation à toute relecture ordinaire, sépare $2^{64}$ essais de 2048.

Le temps d'exécution

C'est le canal le plus accessible — il se mesure à distance, à travers un réseau — et le plus fréquent en pratique.

La règle est simple à énoncer et exigeante à respecter : aucun branchement, aucun accès mémoire indexé et aucune borne de boucle ne doivent dépendre d'une valeur secrète.

Les trois cas se valent en gravité. Un branchement fait varier le nombre d'instructions. Un accès mémoire indexé par un secret — une table de substitution, par exemple — fait varier l'état du cache, et un attaquant qui partage le processeur peut l'observer. Une borne de boucle secrète est le cas de l'animation.

Le point le plus contre-intuitif est qu'une division peut fuir. Sur beaucoup de processeurs, le temps de la division entière dépend des opérandes. C'est exactement ce qui s'est produit avec KyberSlash, signalée fin 2023 : l'implémentation de référence de ML-KEM contenait une division par $q$ dont le temps dépendait d'une valeur secrète, ce qui permettait de reconstruire la clé. Le schéma était prouvé, la spécification correcte, l'implémentation officielle. Le code fuyait.

Pire encore : écrire du code sans branchement ne suffit pas si le compilateur en réintroduit. Des cas documentés montrent un optimiseur transformant une expression écrite sans branchement — précisément pour éviter la fuite — en un saut conditionnel, parce que c'est plus rapide. La vérification doit donc porter sur le binaire produit, pas seulement sur la source. C'est une exigence que peu d'équipes appliquent.

Consommation, rayonnement, fautes

Sur un composant auquel l'attaquant a un accès physique — carte à puce, module de sécurité, objet connecté — trois autres canaux s'ouvrent.

L'analyse simple de consommation (SPA) lit le déroulement de l'algorithme sur une seule trace de courant. Les motifs sont souvent visibles à l'œil nu sur l'oscilloscope.

L'analyse différentielle (DPA) est bien plus puissante. Elle corrèle des milliers de traces avec une hypothèse sur un fragment de clé : la bonne hypothèse fait apparaître un pic de corrélation. Elle fonctionne même quand le signal est très inférieur au bruit, parce que la statistique accumule.

Les attaques par faute perturbent le calcul — variation de tension, impulsion laser, horloge dégradée — et exploitent le résultat erroné. Sur une signature déterministe, comparer une exécution correcte et une exécution fautée du même message livre le secret : c'est la raison pour laquelle la FIPS 204 fait de la signature aléatoire le mode par défaut, comme vu au chapitre 7.

Ce qui est propre à la cryptographie post-quantique

Un cours qui se contenterait des généralités ci-dessus manquerait l'essentiel. Les schémas à réseaux offrent des prises que RSA et les courbes elliptiques n'avaient pas.

L'échantillonnage. Tirer du bruit est une opération secrète, et elle est bien plus complexe qu'un simple random(). L'échantillonneur gaussien de Falcon a été attaqué à plusieurs reprises, et des attaques par cache visant l'échantillonnage gaussien de schémas antérieurs sont documentées depuis 2016. C'est précisément pour cela que ML-KEM emploie une binomiale centrée, qui se calcule en comptant des bits.

Le rejet d'échantillonnage. Le nombre de tours de ML-DSA est aléatoire et corrélé au secret : c'est justement parce que $z$ dépasse le seuil qu'on rejette. Un signataire dont le temps total laisse voir ce nombre rend une information exploitable. L'implémentation doit donc masquer le nombre de tours, ce qui n'est pas trivial quand il est intrinsèquement variable.

L'oracle d'échec de déchiffrement. Le rejet implicite du chapitre 6 ne ferme l'oracle que si les deux branches — succès et échec — sont indiscernables en temps comme en consommation. Une implémentation qui court-circuite le calcul de la clé bidon quand la ré-encapsulation réussit rouvre exactement le canal qu'on croyait fermé.

Le masquage coûte plus cher qu'ailleurs. La contre-mesure de référence consiste à partager chaque valeur secrète en plusieurs parts aléatoires, de sorte qu'aucune part seule ne corrèle au secret. Le problème est que les schémas à réseaux alternent de l'arithmétique modulaire — la NTT — et des opérations booléennes — hachage, compression, encodage. Or le masquage arithmétique et le masquage booléen ne sont pas compatibles : il faut convertir de l'un à l'autre, et ces conversions sont coûteuses. Un ML-KEM masqué à l'ordre 2 ou 3 est plusieurs fois plus lent que sa version nue.

Que faire, concrètement

Quatre recommandations, dans l'ordre où elles doivent être appliquées.

Ne réimplémentez pas. Utilisez les implémentations éprouvées — celles qui sont auditées, testées en temps constant et maintenues. Écrire soi-même un ML-KEM correct est un projet de plusieurs mois-personnes, et l'exercice de ce chapitre montre à quel point la faute est facile.

Vérifiez le binaire. Des outils d'analyse dynamique détectent les branchements et accès mémoire dépendant d'entrées marquées comme secrètes. Intégrez-les à l'intégration continue, pas à une revue ponctuelle : une mise à jour de compilateur peut réintroduire une fuite dans un code inchangé.

Dimensionnez les contre-mesures selon le modèle de menace. Le masquage et la redondance contre les fautes ne se justifient que si l'attaquant a un accès physique. Pour un serveur en centre de données, le temps constant suffit et le reste est du gaspillage.

Testez les fautes si le matériel est exposé. Une carte à puce ou un objet connecté déployé sur le terrain doit être évalué en injection, pas seulement en analyse statique.

À vous

L'exercice remplace le chronomètre par un compteur d'octets lus — l'horloge d'un navigateur est trop grossière pour une mesure fiable, mais le principe est identique. Le rapport entre les deux colonnes est la totalité du chapitre.

// Forger une étiquette d'authentification de 8 octets sans connaître le
// secret, uniquement en observant le TEMPS de vérification.
//
// Mesurer des nanosecondes dans un navigateur n'est pas fiable : l'horloge
// y est volontairement grossière. On remplace donc le chronomètre par un
// COMPTEUR d'octets lus, qui est ce que le chronomètre mesurerait. Le
// principe de l'attaque est identique ; seule la métrologie est simplifiée.

const ETIQUETTE_SECRETE = [0x8f, 0x2a, 0xc7, 0x10, 0x55, 0xe3, 0x9b, 0x04];

let octetsLus = 0;

// La victime : comparaison naïve, avec sortie anticipée.
function verifierNaif(soumise) {
  for (let i = 0; i < ETIQUETTE_SECRETE.length; i++) {
    octetsLus++;
    if (soumise[i] !== ETIQUETTE_SECRETE[i]) return false;
  }
  return true;
}

// La même, en temps constant.
function verifierConstant(soumise) {
  let diff = 0;
  for (let i = 0; i < ETIQUETTE_SECRETE.length; i++) {
    octetsLus++;
    diff |= soumise[i] ^ ETIQUETTE_SECRETE[i];
  }
  return diff === 0;
}

// L'oracle : combien d'octets la victime a-t-elle lus ?
function mesurer(verifier, soumise) {
  octetsLus = 0;
  const ok = verifier(soumise);
  return { ok, cout: octetsLus };
}

let requetes = 0;

function forger(verifier) {
  requetes = 0;
  const trouvee = new Array(8).fill(0);
  for (let position = 0; position < 8; position++) {
    // À COMPLÉTER — pour chaque valeur d'octet de 0 à 255, mesurer le coût
    // et retenir celle qui en provoque le PLUS : c'est la bonne, puisque
    // la boucle est allée un cran plus loin.
    trouvee[position] = 0;
  }
  return trouvee;
}

const hex = (t) => t.map((b) => b.toString(16).padStart(2, "0")).join(" ");

console.log("secret réel        :", hex(ETIQUETTE_SECRETE));

const contreNaif = forger(verifierNaif);
console.log("contre le naïf     :", hex(contreNaif),
  verifierNaif(contreNaif) ? "→ ACCEPTÉE" : "→ refusée", `(${requetes} requêtes)`);

const contreConstant = forger(verifierConstant);
console.log("contre le constant :", hex(contreConstant),
  verifierConstant(contreConstant) ? "→ ACCEPTÉE" : "→ refusée", `(${requetes} requêtes)`);

console.log("\nforce brute nécessaire : 2^" + (8 * 8));

const ETIQUETTE_SECRETE = [0x8f, 0x2a, 0xc7, 0x10, 0x55, 0xe3, 0x9b, 0x04];

let octetsLus = 0;

function verifierNaif(soumise) {
  for (let i = 0; i < ETIQUETTE_SECRETE.length; i++) {
    octetsLus++;
    if (soumise[i] !== ETIQUETTE_SECRETE[i]) return false;
  }
  return true;
}

function verifierConstant(soumise) {
  let diff = 0;
  for (let i = 0; i < ETIQUETTE_SECRETE.length; i++) {
    octetsLus++;
    diff |= soumise[i] ^ ETIQUETTE_SECRETE[i];
  }
  return diff === 0;
}

function mesurer(verifier, soumise) {
  octetsLus = 0;
  const ok = verifier(soumise);
  return { ok, cout: octetsLus };
}

let requetes = 0;

function forger(verifier) {
  requetes = 0;
  const trouvee = new Array(8).fill(0);
  for (let position = 0; position < 8; position++) {
    let meilleur = -1, meilleurCout = -1;
    for (let valeur = 0; valeur < 256; valeur++) {
      requetes++;
      const essai = trouvee.slice();
      essai[position] = valeur;
      // Les positions au-delà de la position courante restent à zéro : peu importe,
      // la boucle de la victime s'arrêtera avant si l'octet courant est
      // faux, et exactement un cran plus loin s'il est juste.
      const { cout } = mesurer(verifier, essai);
      if (cout > meilleurCout) { meilleurCout = cout; meilleur = valeur; }
    }
    trouvee[position] = meilleur;
  }
  return trouvee;
}

const hex = (t) => t.map((b) => b.toString(16).padStart(2, "0")).join(" ");

console.log("secret réel        :", hex(ETIQUETTE_SECRETE));

const contreNaif = forger(verifierNaif);
console.log("contre le naïf     :", hex(contreNaif),
  verifierNaif(contreNaif) ? "→ ACCEPTÉE" : "→ refusée", `(${requetes} requêtes)`);

const contreConstant = forger(verifierConstant);
console.log("contre le constant :", hex(contreConstant),
  verifierConstant(contreConstant) ? "→ ACCEPTÉE" : "→ refusée", `(${requetes} requêtes)`);

console.log("\nforce brute nécessaire : 2^" + (8 * 8));

// Trois chiffres résument le chapitre.
//
// 2048 requêtes contre la version naïve — 256 valeurs × 8 positions — et
// l'étiquette est retrouvée EXACTEMENT. Pas approchée : retrouvée.
//
// 2^64 requêtes sans le canal auxiliaire. Le rapport est de l'ordre de
// 10^16.
//
// 0 information contre la version en temps constant : le coût est de 8
// octets lus quelle que soit l'entrée, la boucle de forge retient donc la
// première valeur essayée, et l'étiquette produite est fausse.
//
// La différence entre les deux fonctions tient en une ligne : un « return »
// anticipé contre un OU cumulé. C'est la totalité de la contre-mesure, et
// c'est la totalité de la faille.
//
// Deux remarques pour la pratique.
//
// D'abord, cette faille existe encore. KyberSlash, signalée fin 2023, était
// une division par q non constante en temps dans l'implémentation de
// référence de ML-KEM. Le schéma était prouvé sûr ; le code fuyait.
//
// Ensuite, écrire du code en temps constant ne suffit pas : il faut que le
// COMPILATEUR le préserve. Des cas documentés montrent un compilateur
// reconstituant un branchement conditionnel à partir d'une expression
// écrite sans branchement, au nom de l'optimisation. La vérification doit
// donc porter sur le binaire produit, pas seulement sur la source.

À retenir

QCM du bloc III — Sécurité et implémentation

Huit questions sur ce qu'une preuve garantit et sur ce qu'elle laisse ouvert. Les distracteurs y sont plus retors qu'ailleurs, parce que les erreurs de ce bloc sont des erreurs de raisonnement, pas de mémoire.