Sécurité prouvée

Onze chapitres durant, « sûr » a été employé au fil de l'eau — IND-CPA au chapitre 4, EUF-CMA au chapitre 8, IND-CCA2 pour OAEP au chapitre 9. Il est temps de donner à ces sigles leur sens exact. C'est l'objet de la sécurité prouvée : définir précisément ce qu'on démontre, et par quel mécanisme — la réduction — on le rattache à un problème réputé difficile.

Ce chapitre arrive délibérément après les constructions asymétriques. Une réduction reste un exercice formel creux tant qu'on n'a pas RSA et ElGamal en tête comme objets concrets à réduire. Placé au début d'un cours, ce chapitre fait fuir ; placé ici, il range enfin ce qu'on a déjà manipulé.

Prouver, mais prouver quoi ?

La cryptographie ne prouve presque jamais qu'un schéma est sûr dans l'absolu — une telle preuve impliquerait $P \neq NP$, hors de portée. Elle prouve des énoncés conditionnels : si tel problème est difficile, alors tel schéma est sûr. Toute la valeur est dans la qualité de l'implication et dans la solidité de l'hypothèse.

Trois ingrédients composent un énoncé de sécurité, et il faut les nommer séparément :

• Un objectif — que veut-on empêcher l'adversaire d'obtenir ? (distinguer deux chiffrés, forger une signature.)
• Un modèle d'attaque — de quels moyens l'adversaire dispose-t-il ? (les modèles COA à CCA2 du chapitre 1.)
• Une hypothèse — quel problème suppose-t-on difficile ? (factorisation, logarithme discret, DDH.)

Un schéma n'est jamais « sûr » tout court : il est sûr pour tel objectif, dans tel modèle, sous telle hypothèse.

Les jeux de sécurité

On formalise l'objectif comme un jeu entre un défieur et un adversaire. La sécurité est l'affirmation que l'avantage de l'adversaire — l'écart entre son taux de succès et celui du pur hasard — reste négligeable pour tout adversaire polynomial (le vocabulaire du chapitre 1).

IND-CPA (indistinguabilité sous clairs choisis). L'adversaire soumet deux messages $m_0, m_1$ de même longueur. Le défieur tire un bit $b$, chiffre $m_b$, rend le chiffré. L'adversaire annonce $b'$. Son avantage est $|\Pr[b' = b] - 1/2|$. Que gagner ce jeu soit infaisable est la définition du secret : le chiffré ne dit rien du clair. On retrouve pourquoi un chiffrement déterministe échoue (chapitre 1) — l'adversaire y soumet deux fois le même message et distingue.

IND-CCA2 (sous chiffrés choisis, adaptatif). Même jeu, mais l'adversaire dispose en plus d'un oracle de déchiffrement qu'il peut interroger avant et après avoir reçu le défi — sur tout chiffré sauf le défi lui-même. C'est le modèle le plus fort, et le bon défaut dès qu'un serveur déchiffre : l'oracle de padding du chapitre 4 était précisément une attaque CCA. OAEP vise ce niveau ; le chiffrement authentifié du chapitre 8 l'atteint.

EUF-CMA (inforgeabilité existentielle sous messages choisis). Le jeu des signatures. L'adversaire obtient les signatures de messages de son choix, et gagne s'il produit une signature valide pour un message nouveau. C'est ce que garantissent RSA-PSS (chapitre 9) et ECDSA (chapitre 11).

La réduction, mécanique centrale

Comment démontre-t-on qu'un schéma gagne un jeu ? Par réduction — l'outil que le chapitre 2 a esquissé avec les classes de complexité, ici mis au travail.

On raisonne par contraposée. On suppose qu'existe un adversaire $\mathcal{A}$ qui gagne le jeu, et l'on construit avec lui un algorithme $\mathcal{B}$ qui résout le problème réputé difficile. Comme ce dernier est infaisable, un tel $\mathcal{A}$ ne peut exister. La forme est toujours la même :

C'est l'exact analogue des réductions de complexité — on ramène la sécurité d'un objet compliqué à la difficulté d'un problème simple et étudié. On l'a déjà croisée sans la nommer : Merkle-Damgård (chapitre 7) réduit la résistance du haché à celle de sa compression ; la sécurité de RSA (chapitre 9) se raccroche à la factorisation.

Rien ne vaut de l'exécuter une fois. L'exercice transforme un adversaire IND-CPA contre un chiffrement à flot en un distingueur du générateur pseudo-aléatoire sous-jacent, et mesure l'avantage qui se transfère de l'un à l'autre.

// Chiffrement : c = m ⊕ PRG(clé, nonce). S'il existe un adversaire A qui gagne
// le jeu IND-CPA, on FABRIQUE avec lui un distingueur du PRG. Donc : PRG sûr ⇒
// chiffrement IND-CPA. On code la réduction et on la mesure.

// Une suite FRAÎCHE à chaque appel (nouveau nonce). Deux mondes :
//   pseudo = true  : pseudo-aléatoire, avec une FAILLE volontaire — le bit de
//                    poids faible du premier octet est toujours 0 ;
//   pseudo = false : vraiment aléatoire, aucune structure à exploiter.
let compteurNonce = 1;
function suiteFraiche(pseudo, longueur) {
  if (!pseudo) {
    return Array.from({ length: longueur }, () => (Math.random() * 256) | 0);
  }
  let x = (compteurNonce++ * 2654435761) >>> 0 || 1;
  const out = [];
  for (let i = 0; i < longueur; i++) {
    x ^= x << 13; x >>>= 0; x ^= x >> 17; x ^= x << 5; x >>>= 0;
    out.push(i === 0 ? (x & 0xfe) : (x & 0xff)); // biais sur l'octet 0
  }
  return out;
}
const xor = (a, b) => a.map((v, i) => v ^ b[i]);

// ── L'adversaire IND-CPA ──────────────────────────────────────────────────
// Il soumet m0 et m1 (de bits 0 différents sur l'octet 0), reçoit le chiffré de
// l'un, et devine lequel en exploitant le biais : l'octet 0 de la suite ayant
// son bit 0 à 0, l'octet 0 du clair a le même bit 0 que celui du chiffré.
function adversaire(chiffre, m0) {
  const bit0Clair = chiffre[0] & 1;
  return bit0Clair === (m0[0] & 1) ? 0 : 1;
}

// ── À COMPLÉTER : la réduction ────────────────────────────────────────────
// Le distingueur joue le jeu IND-CPA en masquant avec le PRG testé, sur de
// NOMBREUX défis indépendants (un masque frais par défi). Si l'adversaire gagne
// bien plus qu'une fois sur deux, le PRG était pseudo-aléatoire : le biais l'a
// trahi. Sinon, il était vrai aléa.
function tauxDeSucces(pseudo) {
  const m0 = [0, 0, 0, 0]; // bit 0 de l'octet 0 = 0
  const m1 = [1, 0, 0, 0]; // bit 0 de l'octet 0 = 1
  let succes = 0, tours = 2000;
  for (let t = 0; t < tours; t++) {
    const b = Math.random() < 0.5 ? 0 : 1;
    const s = suiteFraiche(pseudo, 4); // masque FRAIS à chaque défi
    // à compléter : chiffrer m_b avec s, interroger l'adversaire, compter succès
  }
  return succes / tours;
}

// ── Mesure : la réduction sépare-t-elle les deux mondes ? ──────────────────
const tauxPseudo = tauxDeSucces(true);
const tauxVrai = tauxDeSucces(false);
console.log("succès de l'adversaire, PRG PSEUDO-aléatoire :", (tauxPseudo * 100).toFixed(0) + " %");
console.log("succès de l'adversaire, vrai aléa         :", (tauxVrai * 100).toFixed(0) + " %");
console.log("avantage transféré au PRG :", ((tauxPseudo - tauxVrai) * 100).toFixed(0), "points");

function tauxDeSucces(pseudo) {
  const m0 = [0, 0, 0, 0];
  const m1 = [1, 0, 0, 0];
  let succes = 0, tours = 2000;
  for (let t = 0; t < tours; t++) {
    const b = Math.random() < 0.5 ? 0 : 1;
    const s = suiteFraiche(pseudo, 4);
    const chiffre = xor(b === 0 ? m0 : m1, s);
    if (adversaire(chiffre, m0) === b) succes++;
  }
  return succes / tours;
}

// Résultat : ~100 % sous le PRG pseudo-aléatoire (le biais de l'octet 0 laisse
// tout passer), ~50 % sous le vrai aléa (rien à exploiter). L'écart d'environ
// 50 points EST l'avantage que la réduction transfère du chiffrement au PRG.
//
// C'est cela, une RÉDUCTION. On ne prouve pas directement que le chiffrement
// est sûr : on établit une IMPLICATION. « Si un adversaire gagne le jeu
// IND-CPA avec un avantage ε, alors on distingue le PRG avec un avantage ε. »
// Par contraposée : PRG indistinguable ⇒ chiffrement IND-CPA. La sécurité du
// schéma est RÉDUITE à celle d'une brique — même mouvement que Merkle-Damgård
// ramenant la résistance du haché à celle de sa compression (chapitre 7).
//
// Le jeu IND-CPA : le défieur tire b, chiffre m_b, l'adversaire rend b' ;
// l'avantage est |Pr[b' = b] − 1/2|, qui doit être négligeable pour tout
// adversaire polynomial (chapitre 1). IND-CCA2 ajoute un oracle de
// déchiffrement même après le défi ; EUF-CMA est le jeu des signatures. Une
// même mécanique partout : un jeu, un avantage, une réduction.

La qualité d'une réduction se mesure. Une réduction est serrée (tight) si $\mathcal{B}$ réussit avec à peu près le même avantage et le même temps que $\mathcal{A}$. Elle est lâche si $\mathcal{B}$ perd un facteur — disons le nombre de requêtes de l'adversaire. Ce n'est pas un détail théorique : une réduction lâche oblige à augmenter la taille des clés pour compenser la perte, avec un coût de performance bien réel. La finesse de la preuve a un prix en octets.

Le modèle de l'oracle aléatoire, et sa controverse

Beaucoup de schémas efficaces — OAEP, PSS, la plupart des signatures — ne se prouvent que dans le modèle de l'oracle aléatoire (ROM). On y fait une idéalisation : la fonction de hachage est traitée comme une fonction parfaitement aléatoire, une boîte noire que tout le monde interroge et qui répond de façon uniforme et cohérente.

Cette idéalisation rend les preuves possibles, et donne à la réduction un pouvoir supplémentaire : elle peut « programmer » l'oracle, choisir ses réponses pour piéger l'adversaire. C'est puissant, et c'est précisément là qu'est la critique.

Car aucune fonction réelle — ni SHA-256, ni SHA-3 — n'est un oracle aléatoire : ce sont des algorithmes publics, déterministes, courts à décrire. Canetti, Goldreich et Halevi ont même construit, en 1998, des schémas prouvés sûrs dans le ROM et cassés dès qu'on remplace l'oracle par n'importe quelle fonction réelle. La preuve ROM n'est donc pas une garantie au sens strict ; c'est une heuristique — un argument de bonne conception, un filtre qui élimine les schémas manifestement faibles, sans certifier les survivants.

La position raisonnable, et celle qu'adopte la pratique : une preuve dans le modèle standard (sans oracle idéalisé) est préférable ; une preuve ROM vaut mieux qu'aucune preuve ; et aucune de l'une ni de l'autre ne protège contre ce qu'aucun modèle ne capture — un canal auxiliaire, un générateur aléatoire défaillant, une clé lue en mémoire. Les preuves cadrent la primitive ; elles ne couvrent pas l'implémentation, qui est le sujet du chapitre 13.

Ce que la suite en fait

Ce chapitre a donné aux mots leur sens exact. Le chapitre 13 quitte les primitives isolées pour les protocoles : TLS 1.3, où un échange de clés authentifié doit atteindre des objectifs de sécurité composés, et où l'on verra que prouver un protocole entier est bien plus dur que prouver une brique. Il montrera aussi combien les hypothèses de ce chapitre sont fragiles face à la réalité — un générateur pseudo-aléatoire biaisé fait s'effondrer des schémas parfaitement prouvés.

À retenir