Les maths qui sécurisent le Web cachaient un mystère vieux de 25 ans, Anthropic l'a résolu

Pendant plus de 25 ans, les courbes elliptiques qui sécurisent une bonne partie du web ont reposé sur des nombres dont personne ne connaissait l'origine.

Ils sortent en fait tout bêtement d'un générateur aléatoire de la bibliothèque C, initialisé avec la date et l'heure du moment, quelque part entre mai 1997 et avril 1998.

La découverte revient à une équipe d'Anthropic, qui a décroché la semaine dernière la prime promise depuis trois ans à qui résoudrait l'énigme : 36 864 dollars, reversés à l'ISRG, l'association qui fait tourner Let's Encrypt.

Selon l'entreprise, c'est (sans trop de surprise) Claude qui a trouvé la solution, en moins d'une demi-heure.

Rien dans les mains, rien dans les poches

En cryptographie, une courbe elliptique est l'ensemble des points dont les coordonnées vérifient une équation, le plus souvent y² = x³ + ax + b (c'est simple, non ?), avec des calculs faits modulo un très grand nombre premier.

Ce nombre premier et les coefficients a et b suffisent à définir la courbe. Des algorithmes comme ECDSA s'appuient ensuite sur des calculs entre ses points pour produire des clés et des signatures.

Parmi les plus utilisées figurent celles que le NIST a publiées en 2000 dans la norme FIPS 186-2, de P-192 à P-521. P-256 et P-384 équipent notamment une bonne partie des certificats HTTPS du web.

Pour prouver qu'ils n'avaient pas choisi une courbe sur mesure, leurs concepteurs ont tiré l'un de ses paramètres de l'empreinte SHA-1 d'un nombre de départ, ce qu'on appelle la seed (la graine, pour les puristes).

Comme un hachage ne se remonte pas, impossible de partir d'une courbe voulue pour fabriquer la seed qui y mène.

La parade a toutefois une limite : rien n'empêche de tester des milliers de seeds et de garder celle qui donne la courbe qui vous arrange. Elle ne rassure donc que si l'on sait d'où vient la seed.

Or celles des courbes NIST avaient été fournies par la NSA (l'agence américaine chargée à la fois d'espionner les communications et de protéger celles de son gouvernement) sans la moindre explication.

Le scénario redouté était simple : si la NSA connaissait une faiblesse secrète qui ne touche qu'une partie des courbes, il lui suffisait d'essayer des seeds jusqu'à tomber sur une courbe concernée, puis de publier celle-là.

Vue de l'extérieur, cette seed aurait ressemblé à n'importe quel nombre tiré au hasard, et personne n'aurait pu prouver la manœuvre.

Et la NSA traîne une sacrée casserole : elle a selon toute vraisemblance piégé Dual_EC_DRBG, un générateur aléatoire normalisé par le NIST. Il repose lui aussi sur des courbes elliptiques, mais sa porte dérobée se cachait dans deux points fixés sans explication, pas dans la courbe.

Le seul indice venait de Jerry Solinas, mathématicien de longue date à la NSA, qui avait fourni les seeds en 1997. Il assurait les avoir tirées d'une phrase potache, quelque chose comme une demande d'augmentation pour lui et son collègue Bob, qu'il avait ensuite oubliée.

Si des archives existaient encore, plaisantait-il, elles dormaient sans doute sur un disque dur rangé dans le même entrepôt que l'Arche perdue d'Indiana Jones. Solinas est mort début 2023, et ses collègues de l'époque sont restés muets sur la question.

En octobre 2023, l'ingénieur en cryptographie Filippo Valsorda a lancé une prime de 12 288 dollars (un compte rond pour qui compte en octets : 12 × 1 024), triplée si le gagnant la reversait à une association.

Il comptait sur les casseurs de mots de passe pour retrouver les phrases. Trois ans de chasse n'ont rien donné, y compris chez Anthropic, où plusieurs employés s'y étaient eux-mêmes cassé les dents.

Le coupable était dans le manuel de C

Ce mois-ci, un employé curieux a soumis la question à un modèle de recherche interne, que le billet d'Anthropic appelle simplement "Claude" (👀), sans lui souffler la piste de la phrase.

Plutôt que de la chercher, le modèle s'est demandé comment un logiciel des années 90 avait pu fabriquer ces nombres.

Il a misé sur les générateurs pseudo-aléatoires livrés avec les bibliothèques C de l'époque, assez rudimentaires pour que leur sortie se reconnaisse, et a écrit un scanner pour traquer leur signature.

Il l'a trouvée sur quatre seeds de courbes dites binaires, beaucoup moins répandues : découpées en blocs de 32 bits, elles ont toutes un premier bit à zéro dans chaque bloc. Selon Anthropic, le hasard n'avait qu'environ une chance sur 5 810 de produire ça.

C'est la marque de fabrique de lrand48, le générateur de la bibliothèque C des systèmes Unix, qui ne renvoie que des nombres de 31 bits : rangés dans des mots de 32 bits, ils laissent toujours le premier bit à zéro.

Ce générateur garde en mémoire un nombre de 48 bits, qu'il fait évoluer à chaque tirage avec une multiplication et une addition, et n'en livre que le début. Initialisé par srand48 avec l'heure courante, c'est le proche cousin du duo srand(time(NULL)) puis rand(), que tout étudiant en informatique a tapé un jour en TP de C.

En cryptographie, un générateur aussi prévisible fait un peu tache. Mais la seed d'une courbe n'a besoin d'être ni secrète ni imprévisible, juste quelconque. Et c'est justement la prévisibilité de lrand48 qui a trahi l'origine des seeds.

Pour les cinq courbes au cœur de l'énigme, de P-192 à P-521, l'affaire était plus coriace. Leurs seeds ne gardent qu'un octet de chaque tirage, et la signature du bit à zéro s'y efface.

Il fallait donc retrouver le nombre de 48 bits du générateur à partir de ces seuls fragments. Le modèle a sorti pour ça l'algorithme LLL, un classique de la cryptanalyse pour ce genre de casse-tête.

Il ne restait plus qu'à faire tourner lrand48 à l'envers, ce qu'il permet sans broncher, jusqu'à son initialisation. Pour chacune des cinq courbes NIST, on tombe sur un horodatage Unix compris entre mai 1997 et avril 1998.

Le programme de l'époque tirait des seeds de 20 octets à la chaîne et ne gardait que celles qui donnaient une courbe valable. Celle de P-256 est par exemple le 1 842e de ces candidats, dans une série lancée le 16 août 1997.

Pas besoin de croire Anthropic sur parole

Dans l'extrait de raisonnement publié par Anthropic, le modèle s'étonne lui-même de sa trouvaille, au point de se demander s'il n'est pas dans un environnement de test (un petit air de Truman Show), avant que le calcul ne le convainque.

Toute cette histoire, chrono et états d'âme compris, est racontée par l'entreprise qui vend Claude. Le billet de Valsorda crédite quant à lui les dix membres de l'équipe, sans un mot sur l'IA ni sur cette fameuse demi-heure.

Heureusement, le résultat ne dépend pas de ce récit : Anthropic a partagé le code Python qui régénère les seeds, versé dans le domaine public, et Valsorda a réimplémenté l'algorithme en Go pour vérifier.

Après les plus de 700 papiers de maths publiés par OpenAI début octobre, c'est au tour d'Anthropic de mettre en vitrine un vieux problème résolu par son IA. Celui-là, au moins, peut être vérifié en lançant un script.

Des trous dans la raquette

Tout n'est pas élucidé pour autant. Le procédé produisait environ deux fois plus de seeds valides que celles publiées, sans que l'on sache sur quel critère certaines ont été écartées.

Pour P-256, le 876e candidat du même tirage donnait déjà une courbe tout aussi valable, ignorée au profit du 1 842e.

Valsorda avance deux pistes. Le programme se servait peut-être du même générateur pour tester les courbes, et chaque nombre tiré pour ces tests aurait décalé la série en faisant sauter des candidats.

À moins qu'un bug ne se soit glissé dans ces tests, au point de les faire se tromper une fois sur deux. En 1997, ces calculs relevaient encore de la recherche de pointe, alors qu'un logiciel courant les boucle aujourd'hui en quelques minutes.

La porte dérobée prend la porte

Ces candidats écartés ont de quoi faire tiquer les plus soupçonneux. Anthropic concède d'ailleurs qu'on aurait pu, en théorie, essayer plusieurs horodatages jusqu'à obtenir une courbe dotée d'une propriété bien précise.

En 2017, deux chercheurs, dont Daniel Bernstein (le concepteur de Curve25519, la grande rivale des courbes NIST), avaient décrit une technique pour cibler une catégorie hypothétique de courbes faibles en jouant sur le choix de la seed.

Encore fallait-il pouvoir piocher parmi environ mille milliards de milliards de seeds.

Pour Valsorda, ces découvertes excluent complètement ce scénario. Même si la NSA avait pu choisir n'importe quel horodatage de 1997-1998 et l'un des 16 premiers candidats valides, elle n'aurait eu le choix qu'entre un milliard de seeds environ, mille milliards de fois moins.

C'est bien trop peu pour viser délibérément des courbes faibles, et a fortiori pour y planquer une porte dérobée que seule la NSA saurait exploiter.

Ce n'est donc ni une attaque ni une faille, et rien ne change pour vos clés ou vos connexions TLS : Anthropic le dit d'emblée, la plupart des chercheurs faisaient déjà confiance à ces courbes.

Valsorda va même plus loin : la découverte achève la réhabilitation des courbes NIST, qu'il recommande désormais à titre personnel plutôt que Curve25519. Juste à temps, s'amuse-t-il, pour les voir partir à la retraite au profit des signatures post-quantiques.