Cryptographie post-quantique · C3 Les autres familles · Chapitre 3 · 3 h
Isogénies et multivarié
La cassure de SIKE en 2022 et ce qu'elle enseigne, CSIDH et SQIsign, l'échec de Rainbow : la valeur pédagogique des candidats brisés.
Ce chapitre est le plus court du cours et le plus important pour la formation du jugement. Il porte sur deux familles qui ont échoué en public, devant témoins, après avoir passé plusieurs tours d'un processus de normalisation international. Ce n'est pas un chapitre d'histoire : c'est un chapitre de méthode.
Isogénies : l'idée
Une isogénie est une application entre deux courbes elliptiques qui préserve la structure de groupe. On peut la voir comme un morphisme reliant une courbe à une autre.
L'objet cryptographique n'est plus la courbe, mais le graphe dont les sommets sont des courbes elliptiques supersingulières et les arêtes des isogénies de petit degré. Ce graphe a une propriété remarquable : il est expandeur. En s'y promenant au hasard quelques dizaines de pas, on aboutit à un sommet impossible à relier à son point de départ — trouver le chemin entre deux courbes données est le problème difficile.
L'attrait était considérable : les clés étaient les plus petites de tout le paysage post-quantique, quelques centaines d'octets seulement, là où les réseaux en demandent plusieurs milliers.
SIKE, et l'après-midi du 30 juillet 2022
SIDH, proposé en 2011, était le protocole d'échange de clés fondé sur ces graphes. SIKE en était la version encapsulation, candidate au processus NIST, arrivée jusqu'au quatrième tour. Onze ans d'examen public.
Le 30 juillet 2022, Wouter Castryck et Thomas Decru publient une attaque qui récupère la clé secrète. Elle s'exécute en une heure environ sur un seul cœur de processeur ordinaire pour les paramètres du premier niveau de sécurité. Des optimisations publiées dans les semaines suivantes ramèneront ce temps à quelques minutes, et Damien Robert généralisera l'attaque en temps polynomial pour toute courbe de départ.
Le mécanisme mérite d'être compris, parce qu'il change complètement la leçon à en tirer. SIDH ne publiait pas seulement une courbe d'arrivée : pour permettre aux deux parties de calculer la même valeur commune, il publiait aussi l'image de points de torsion auxiliaires par l'isogénie secrète. C'est cette information supplémentaire que l'attaque exploite, en s'appuyant sur un théorème de Kani datant de 1997 — un résultat de géométrie algébrique qui n'avait jamais été rapproché de SIDH.
Autrement dit : le problème général des isogénies n'a pas été cassé. C'est la manière dont SIDH en révélait un morceau qui l'a été. La distinction est essentielle, et c'est elle qui explique que CSIDH et SQIsign, qui ne publient pas ces points de torsion, restent debout.
Quiz · 1 question
Qu'a exactement cassé l'attaque de Castryck et Decru ?
- Le problème général de recherche d'isogénies entre courbes supersingulières
- La publication par SIDH des images de points de torsion auxiliaires
- L'implémentation de référence de SIKE, par un canal auxiliaire
Réponse : Le problème d'isogénie général reste ouvert, et c'est pourquoi CSIDH et SQIsign survivent. Ce qui est tombé, c'est l'information supplémentaire que SIDH devait publier pour que le protocole fonctionne : l'image de points de torsion par l'isogénie secrète. Un théorème de Kani de 1997, jamais rapproché de SIDH en onze ans, permet de la transformer en attaque. Ce n'était pas non plus un défaut d'implémentation — le schéma lui-même était cassé.
Ce que SIKE enseigne
Trois leçons, et elles valent pour tout le reste du cours.
L'examen public ne prouve pas l'absence d'attaque. SIDH a été scruté onze ans par une communauté active. Le résultat qui l'a tué existait depuis 1997, dans une branche voisine des mathématiques. Personne n'avait fait le rapprochement. « Personne n'a trouvé d'attaque » est une observation, pas une garantie.
Une cassure peut être totale et instantanée. Il n'y a pas eu d'érosion progressive des paramètres, pas de signal d'alerte, pas de fenêtre pour réagir. Le passage d'« il tient » à « une heure sur un portable » a été immédiat.
D'où l'hybridation. Un déploiement qui combinait X25519 et SIKE n'a rien perdu le 30 juillet 2022 : il lui restait la sécurité classique de X25519. Un déploiement SIKE seul était nu. C'est l'argument décisif en faveur de l'approche que l'ANSSI impose et que le chapitre 13 détaille — et sans SIKE, cet argument passerait pour une précaution excessive.
CSIDH et SQIsign
La famille n'est pas morte, et il serait injuste de la présenter ainsi.
CSIDH utilise une action de groupe commutative sur les courbes supersingulières définies sur . Sa commutativité est un atout — elle rend possibles des primitives que les réseaux ne fournissent pas facilement — et une faiblesse : l'algorithme quantique de Kuperberg pour le problème du décalage caché s'y applique, avec un coût sous-exponentiel. Le dimensionnement de CSIDH reste discuté pour cette raison.
Graphique
Clé publique + signature, en octets
- Ed25519 : 9696
- SQIsign : 241241
- Falcon-512 : 15631563
- ML-DSA-44 : 37323732
- SLH-DSA-128s : 78887888
SQIsign est une signature dont les objets sont d'une compacité sans rivale — une clé publique de quelques dizaines d'octets, une signature de moins de deux cents. Comparez aux 2420 octets de ML-DSA-44. Son défaut est la vitesse : signer et vérifier coûtent des ordres de grandeur de plus que ML-DSA. Elle est candidate au processus additionnel de signatures du NIST, et représente le meilleur espoir de la famille.
Le multivarié, et Rainbow
L'autre famille de ce chapitre repose sur la difficulté de résoudre un système d'équations quadratiques à plusieurs variables sur un corps fini — problème NP-difficile dans le cas général.
La trappe s'appelle huile et vinaigre. On construit un système central où les variables sont séparées en deux groupes, et où l'on s'interdit tout produit huile × huile. Fixer les variables de vinaigre au hasard rend alors le système linéaire en les variables d'huile : il se résout par élimination de Gauss. La clé publique est ce système composé avec un mélange linéaire secret, qui cache quelles combinaisons de variables forment l'espace d'huile.
Rainbow empilait plusieurs couches de cette construction pour réduire la taille des clés. Il était finaliste du troisième tour du NIST, à un cheveu de la normalisation.
En février 2022, Ward Beullens publie un article au titre sans équivoque : Breaking Rainbow Takes a Weekend on a Laptop. Les paramètres du premier niveau de sécurité tombent en une cinquantaine d'heures sur un ordinateur portable. L'attaque exploite précisément la structure en couches ajoutée pour gagner en taille : elle offrait une prise supplémentaire pour localiser l'espace d'huile.
Le point qui doit rester : la sécurité d'un schéma multivarié ne se lit pas dans la taille de l'espace de recherche. Elle se lit dans la difficulté de retrouver la structure cachée, et cette difficulté-là est bien plus délicate à estimer. Le schéma UOV originel, sans les couches de Rainbow, survit et reste candidat — avec des clés publiques de plusieurs dizaines de kilooctets, mais des signatures d'une centaine d'octets.
Quiz · 1 question
Rainbow a été cassé alors que l'espace de recherche brut se comptait en 2^400. Pourquoi ?
- Parce que le corps fini choisi était trop petit
- Parce que l'attaque ne cherche pas une solution par force brute mais RETROUVE la structure cachée — l'espace d'huile
- Parce que l'implémentation de référence contenait une erreur
Réponse : La taille de l'espace de recherche ne dit rien quand une structure y est cachée : casser un schéma multivarié consiste à localiser le sous-espace d'huile, pas à énumérer des solutions. La structure en couches de Rainbow — ajoutée pour réduire les clés — offrait justement une prise pour cela. C'est la même leçon qu'avec Ring-LWE au chapitre 5 : toute structure ajoutée pour gagner en taille est aussi une prise potentielle.
À vous
Exercice de code
Implémentez l'inversion par la trappe, puis comparez à la force brute — et lisez pourquoi la taille de l'espace de recherche n'a pas protégé Rainbow.
Point de départ
// La trappe « huile et vinaigre », celle de Rainbow et de UOV.
//
// n = 4 variables sur F_7 : deux VINAIGRE (x0, x1) et deux HUILE (x2, x3).
// Règle unique du système central : jamais de produit huile × huile.
// C'est cette absence qui rend le système inversible — et c'est elle que
// l'attaque de Beullens a fini par retrouver dans Rainbow.
const q = 7;
const V = [0, 1]; // indices vinaigre
const O = [2, 3]; // indices huile
const mod = (x) => ((x % q) + q) % q;
const inv = (a) => { for (let i = 1; i < q; i++) if (mod(a * i) === 1) return i; return null; };
// Deux polynômes quadratiques SANS terme huile × huile.
// coefQuad[k][i][j] = coefficient de x_i·x_j dans l'équation k.
const coefQuad = [
[[3, 1, 2, 5], [0, 4, 6, 1], [0, 0, 0, 0], [0, 0, 0, 0]],
[[2, 6, 1, 3], [0, 5, 2, 4], [0, 0, 0, 0], [0, 0, 0, 0]],
];
// Les deux dernières LIGNES sont nulles : aucun terme ne commence par une
// variable d'huile, donc aucun produit huile × huile n'existe.
function evaluer(k, x) {
let t = 0;
for (let i = 0; i < 4; i++) for (let j = 0; j < 4; j++) t += coefQuad[k][i][j] * x[i] * x[j];
return mod(t);
}
// INVERSION AVEC LA TRAPPE : on fixe le vinaigre, le système devient LINÉAIRE
// en l'huile, et deux équations à deux inconnues se résolvent.
function inverserAvecTrappe(cible, vinaigre) {
// À COMPLÉTER — pour chaque équation k, construire la ligne linéaire
// [a_k2, a_k3 | b_k] obtenue en fixant x0 et x1, puis résoudre.
//
// Indication : le coefficient de x_h (h dans O) vaut
// somme sur i dans V de ( coefQuad[k][i][h] + coefQuad[k][h][i] ) * x_i
// et le terme constant est l'évaluation avec l'huile mise à zéro.
return null;
}
// INVERSION SANS LA TRAPPE : force brute sur toutes les variables.
let essais = 0;
function inverserSansTrappe(cible) {
essais = 0;
for (let a = 0; a < q; a++) for (let b = 0; b < q; b++)
for (let c = 0; c < q; c++) for (let d = 0; d < q; d++) {
essais++;
const x = [a, b, c, d];
if (evaluer(0, x) === cible[0] && evaluer(1, x) === cible[1]) return x;
}
return null;
}
const CIBLE = [4, 2];
const VINAIGRE = [3, 5];
const avec = inverserAvecTrappe(CIBLE, VINAIGRE);
console.log("avec trappe :", JSON.stringify(avec),
avec ? "→ " + JSON.stringify([evaluer(0, avec), evaluer(1, avec)]) : "");
const sans = inverserSansTrappe(CIBLE);
console.log("force brute :", JSON.stringify(sans), `(${essais} essais)`);
console.log("\ncoût de la force brute selon la taille :");
for (const [corps, n] of [[7, 4], [16, 40], [16, 100], [256, 112]]) {
console.log(` F_${String(corps).padStart(3)}, n = ${String(n).padStart(3)} → 2^${(n * Math.log2(corps)).toFixed(0)}`);
}
Solution
const q = 7;
const V = [0, 1];
const O = [2, 3];
const mod = (x) => ((x % q) + q) % q;
const inv = (a) => { for (let i = 1; i < q; i++) if (mod(a * i) === 1) return i; return null; };
const coefQuad = [
[[3, 1, 2, 5], [0, 4, 6, 1], [0, 0, 0, 0], [0, 0, 0, 0]],
[[2, 6, 1, 3], [0, 5, 2, 4], [0, 0, 0, 0], [0, 0, 0, 0]],
];
function evaluer(k, x) {
let t = 0;
for (let i = 0; i < 4; i++) for (let j = 0; j < 4; j++) t += coefQuad[k][i][j] * x[i] * x[j];
return mod(t);
}
function inverserAvecTrappe(cible, vinaigre) {
// Le vinaigre étant fixé, tout terme x_i·x_h avec i vinaigre et h huile
// devient un coefficient CONSTANT devant x_h. Et comme il n'y a aucun
// terme huile × huile, il ne reste rien de quadratique : le système est
// linéaire. Voilà toute la trappe.
const lignes = [0, 1].map((k) => {
const coef = O.map((h) =>
mod(V.reduce((t, i) => t + (coefQuad[k][i][h] + coefQuad[k][h][i]) * vinaigre[i], 0)),
);
const constante = evaluer(k, [vinaigre[0], vinaigre[1], 0, 0]);
return [...coef, mod(cible[k] - constante)];
});
// Élimination de Gauss sur 2 × 2 dans F_7.
let [L0, L1] = lignes;
if (L0[0] === 0) [L0, L1] = [L1, L0];
if (L0[0] === 0) return null;
const p = inv(L0[0]);
L0 = L0.map((v) => mod(v * p));
L1 = L1.map((v, i) => mod(v - L1[0] * L0[i]));
if (L1[1] === 0) return null;
const x3 = mod(L1[2] * inv(L1[1]));
const x2 = mod(L0[2] - L0[1] * x3);
return [vinaigre[0], vinaigre[1], x2, x3];
}
let essais = 0;
function inverserSansTrappe(cible) {
essais = 0;
for (let a = 0; a < q; a++) for (let b = 0; b < q; b++)
for (let c = 0; c < q; c++) for (let d = 0; d < q; d++) {
essais++;
const x = [a, b, c, d];
if (evaluer(0, x) === cible[0] && evaluer(1, x) === cible[1]) return x;
}
return null;
}
const CIBLE = [4, 2];
const VINAIGRE = [3, 5];
const avec = inverserAvecTrappe(CIBLE, VINAIGRE);
console.log("avec trappe :", JSON.stringify(avec),
avec ? "→ " + JSON.stringify([evaluer(0, avec), evaluer(1, avec)]) : "");
const sans = inverserSansTrappe(CIBLE);
console.log("force brute :", JSON.stringify(sans), `(${essais} essais)`);
console.log("\ncoût de la force brute selon la taille :");
for (const [corps, n] of [[7, 4], [16, 40], [16, 100], [256, 112]]) {
console.log(` F_${String(corps).padStart(3)}, n = ${String(n).padStart(3)} → 2^${(n * Math.log2(corps)).toFixed(0)}`);
}
// Ce que l'exercice met à nu.
//
// La trappe n'est pas une clé secrète au sens habituel : c'est la
// CONNAISSANCE D'UN SOUS-ESPACE — celui des variables d'huile, sur lequel le
// système est linéaire. Fixez le vinaigre, et deux équations quadratiques
// deviennent deux équations linéaires.
//
// La clé publique d'un schéma multivarié n'est pas ce système-ci : c'est sa
// composition avec un mélange linéaire secret T, qui cache QUELLES
// combinaisons de variables forment l'espace d'huile. Casser le schéma, ce
// n'est donc pas résoudre un système quadratique aléatoire — c'est
// RETROUVER CE SOUS-ESPACE.
//
// Et c'est exactement ce qu'a fait Ward Beullens contre Rainbow en 2022. La
// structure en couches de Rainbow, ajoutée pour réduire la taille des clés,
// offrait une prise supplémentaire pour localiser l'espace d'huile. Les
// paramètres du premier niveau de sécurité sont tombés en une cinquantaine
// d'heures sur un ordinateur portable, alors que la dernière colonne
// ci-dessus prédisait 2^400 pour une attaque par force brute.
//
// Morale : la sécurité d'un schéma multivarié ne se lit PAS dans la taille
// de l'espace de recherche. Elle se lit dans la difficulté de retrouver la
// structure cachée — et cette difficulté-là est bien plus dure à estimer.
À retenir
Flashcards · 3 cartes
- Que faut-il retenir de la cassure de SIKE en 2022 ?
- Trois choses. L'examen public ne prouve rien : onze ans de scrutin n'ont pas révélé un théorème de 1997. Une cassure peut être totale et instantanée, sans érosion progressive ni fenêtre pour réagir. Et un déploiement hybride X25519 + SIKE n'aurait rien perdu ce jour-là — c'est l'argument décisif en faveur de l'hybridation.
- Le problème des isogénies est-il cassé ?
- Non. Ce qui est cassé, c'est la publication par SIDH des images de points de torsion auxiliaires, nécessaire à son protocole. Le problème général de recherche d'isogénies reste ouvert, et CSIDH comme SQIsign — qui ne publient pas ces points — restent debout. SQIsign offre les objets les plus compacts du paysage, au prix d'une lenteur considérable.
- Où se trouve la trappe d'un schéma multivarié, et comment Rainbow est-il tombé ?
- La trappe est la connaissance de l'espace d'HUILE, le sous-espace sur lequel le système central est linéaire une fois le vinaigre fixé. La clé publique le cache par un mélange linéaire. Beullens (2022) a montré que la structure en couches de Rainbow — ajoutée pour réduire les clés — permettait de localiser cet espace : niveau 1 cassé en 53 heures sur un portable.
QCM du bloc II — Les autres familles
Neuf questions sur les codes, le hachage, les isogénies et le multivarié. Plusieurs demandent de CHOISIR une famille pour un usage donné : c'est la compétence que ce bloc vise réellement.
QCM de bloc · 9 questions
Les autres familles
1. Le syndrome H·yᵀ d'un mot reçu y = c + e :
- dépend à la fois du message et de l'erreur
- ne dépend que du message émis
- ne dépend que de l'erreur
Réponse : H·cᵀ = 0 pour tout mot de code, par définition de la matrice de contrôle. Il reste H·yᵀ = H·eᵀ : le message s'annule intégralement. C'est ce qui permet de reformuler le décodage comme « retrouver un vecteur de petit poids à partir de son syndrome », le problème NP-difficile sur lequel toute la famille repose.
2. On vous propose Classic McEliece pour le handshake TLS d'un site grand public. Que répondez-vous ?
- Mauvais choix : chaque connexion retransmettrait une clé publique de 261 kio à 1 Mio
- Excellent choix : ses chiffrés ne font que 96 octets
- Impossible : McEliece n'est pas un mécanisme d'encapsulation
Réponse : Les chiffrés de 96 octets sont bien les plus courts du paysage post-quantique, et McEliece est bien un KEM — les deux autres options contiennent chacune une affirmation vraie. Mais en TLS, c'est la CLÉ qui circule à chaque connexion, et le mégaoctet est rédhibitoire. Le même schéma est excellent pour un tunnel durable où la clé est provisionnée une fois à l'installation.
3. Pourquoi le NIST a-t-il retenu HQC en secours de ML-KEM plutôt qu'un second schéma à réseaux ?
- Parce que HQC est plus rapide que ML-KEM
- Parce qu'un secours ne vaut que s'il repose sur une hypothèse de difficulté différente
- Parce que HQC a des clés publiques plus petites
Réponse : HQC est plus lent que ML-KEM et ses objets sont plus gros — 2249 octets de clé contre 1184, et 4433 de chiffré contre 1088. Il n'est donc supérieur sur aucun critère de performance. Son intérêt est ailleurs : il repose sur le décodage de codes quasi-cycliques. Si les réseaux tombaient, deux schémas à réseaux tomberaient ensemble ; HQC resterait debout.
4. Combien de hachés compte le chemin d'authentification d'un arbre de Merkle à 1 048 576 feuilles ?
- 1 048 576
- 20
- 2
Réponse : Un frère par niveau, et il y a log₂(2²⁰) = 20 niveaux. Les nœuds situés SUR le chemin, le vérificateur les recalcule lui-même — c'est tout l'intérêt. Cette croissance logarithmique est ce qui rend praticable une clé publique de 32 octets autorisant un million de signatures.
5. Une machine virtuelle qui signe avec XMSS est restaurée depuis un instantané pris la veille. Conséquence ?
- Aucune : l'état se resynchronise au premier démarrage
- Les signatures émises la veille deviennent invalides
- Des index vont être rejoués : la clé doit être considérée comme compromise
Réponse : Rien ne resynchronise un état local, et les signatures déjà émises restent parfaitement vérifiables — c'est même le problème. La machine va réutiliser des index déjà consommés, et deux signatures au même index suffisent à forger. Restaurer une sauvegarde, cloner une VM ou répliquer derrière un répartiteur de charge sont des opérations banales qui détruisent une clé XMSS.
6. Comment SLH-DSA se passe-t-il d'état ?
- En choisissant la feuille pseudo-aléatoirement d'après le message, avec des signatures à usages peu nombreux (FORS) tolérantes aux répétitions
- En stockant l'index consommé dans la signature elle-même
- En n'employant qu'une seule clé à usage unique, renouvelée à chaque signature
Réponse : Stocker l'index dans la signature ne servirait à rien : le signataire devrait toujours savoir lesquels il a déjà utilisés. La solution est de ne plus consommer les feuilles dans l'ordre mais d'en tirer une d'après le message. Comme des collisions redeviennent possibles, les signatures à usage unique cèdent la place à FORS, qui tolère quelques répétitions — au prix d'une signature de 8 à 30 kio.
7. Qu'a exactement cassé l'attaque de Castryck et Decru en 2022 ?
- La publication par SIDH des images de points de torsion auxiliaires
- Le problème général de recherche d'isogénies entre courbes supersingulières
- L'implémentation de référence de SIKE, par un canal auxiliaire
Réponse : Ce n'était pas un défaut d'implémentation — le schéma lui-même est tombé. Mais le problème général d'isogénie reste ouvert, et c'est pourquoi CSIDH et SQIsign survivent : ils ne publient pas ces points de torsion. SIDH devait le faire pour que les deux parties convergent, et c'est cette information supplémentaire qu'un théorème de Kani de 1997 permet de retourner en attaque.
8. Rainbow disposait d'un espace de recherche de l'ordre de 2^400 et est tombé en 53 heures sur un ordinateur portable. Pourquoi ?
- Le corps fini retenu était trop petit
- L'implémentation de référence contenait une erreur
- L'attaque n'énumère pas : elle retrouve la structure cachée, l'espace d'huile
Réponse : La taille de l'espace de recherche ne dit rien quand une structure y est cachée. Casser un schéma multivarié consiste à localiser le sous-espace sur lequel le système central est linéaire — pas à énumérer des solutions. La structure en couches de Rainbow, ajoutée pour réduire la taille des clés, offrait justement une prise pour cela.
9. Quelle conclusion opérationnelle tirer de SIKE et Rainbow pris ensemble ?
- Il faut renoncer aux familles proposées après 2000
- L'examen public ne prouve pas l'absence d'attaque, et l'hybridation est la seule protection contre une cassure surprise
- Le processus de normalisation du NIST a échoué
Réponse : Le processus a fait son travail : les deux schémas sont tombés PENDANT l'évaluation, pas après normalisation. Et renoncer aux familles récentes reviendrait à renoncer aux réseaux, donc à tout. Ce que ces deux cassures établissent, c'est qu'onze ans de scrutin public ne garantissent rien et qu'une cassure peut être totale et instantanée — d'où l'hybridation, qui aurait laissé intacte la sécurité classique le 30 juillet 2022.