Anthropic rapporte que Claude, un modèle de recherche interne, a déterminé en moins d'une demi-heure comment avaient été générées les valeurs de « graine » derrière les courbes elliptiques du NIST, une question restée ouverte depuis l'adoption d'ECDSA dans la norme FIPS 186-2 en 2000. Aucune des graines ne provient d'un hachage. Ce sont des sorties du générateur de nombres aléatoires lrand48 de la bibliothèque C, initialisé avec un horodatage Unix. Anthropic y voit « un joli chapitre de clôture », sans aucune mesure à prendre pour quiconque : il ne s'agit ni d'une cassure cryptographique, ni d'une nouvelle attaque, ni d'une faiblesse.
Le mystère
Pour les courbes sur corps premiers et sur corps binaires, la norme publie une graine dont le hachage définit le coefficient b. La NSA a fourni ces graines sans explication, par exemple pour P-256 C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, ce qui a alimenté les soupçons de porte dérobée. La meilleure histoire, racontée en 2015 par Jerry Solinas, employé de longue date de la NSA, évoquait le hachage d'une phrase de passe humoristique du genre « Give Bob and Jerry a raise ». Solinas est mort en 2023, et plusieurs employés d'Anthropic qui avaient suivi cette piste n'ont rien trouvé. Une prime pour qui retrouverait les graines restait ouverte, organisée par Filippo Valsorda, et « A Riddle Wrapped in an Enigma » de Koblitz et Menezes résume la controverse.
Comment Claude l'a trouvé
Un employé d'Anthropic a demandé à un modèle de recherche interne de déterminer l'origine des graines sans l'indice de la phrase de passe. Claude a supposé que le logiciel utilisait un générateur faible de bibliothèque C des années 1990, dont la sortie est reconnaissable, et a écrit un scanner testant chaque graine, décalée d'un bit à la fois, à la recherche de sorties consécutives de tels générateurs, sur 34 combinaisons de générateur et de tranche de sortie.
- L'indice décisif : dans quatre des dix graines, le bit de poids fort des 20 mots de 32 bits valait zéro, ce qui se produit par hasard avec une probabilité de 1 sur 5 810. Cela correspond à
lrand48, qui ne renvoie que les 31 bits de poids fort d'un état de 48 bits. Essayer les 2^17 valeurs possibles des bits cachés du premier mot et vérifier que les quatre suivants concordaient a permis de retrouver l'état. - Les courbes premières : elles conservent moins de bits de chaque sortie (
lrand48() >> 23). Retrouver l'état d'un générateur congruentiel linéaire tronqué est un problème de réseaux euclidiens classique, résolu par la réduction de base LLL. Claude l'a appliquée à chaque fenêtre de bits, et les cinq graines des courbes premières du NIST, ainsi que cinq de l'ANSI X9.62, ont correspondu. Chaque état retrouvé régénère l'intégralité des 160 bits de sa graine. - Les horodatages : en remontant chaque état jusqu'à la forme définie par
srand48(16 bits de poids faible égaux à0x330E), on obtient des horodatages Unix compris entre mai 1997 et avril 1998, par exemple le 16 août 1997 à 01:52:34 UTC pour P-256. Les états des courbes binaires se lisent comme février 1984, mais doublés, ils tombent au 17 avril 1998, deux semaines après l'exécution de P-224, de sorte que le programme a peut-être divisé l'horloge par deux. - Les itérations : chaque itération tire 20 octets comme graine candidate. La graine publiée de P-256 est la candidate 1 842 de son exécution.
Le code de reproduction fourni dans l'article affiche les 14 graines ; la valeur de P-256 coïncide exactement avec la graine publiée. Le journal de raisonnement de Claude comporte un moment de doute, où le modèle se demande s'il se trouve dans un environnement de test, avant de conclure que les concordances sur 160 bits à travers dix graines ne pouvaient pas être une coïncidence.
Les points de base
La graine ne fixe pas le point de base G de chaque courbe. Claude a aussi relié les six courbes générées en mai 1997 (P-192 et les prime192v2, prime192v3, prime239v1, v2 et v3 de l'ANSI) au générateur de nombres aléatoires du paquet FreeLIP d'Arjen Lenstra, également livré dans les premières versions de NTL de Victor Shoup. La recette : initialiser avec un petit entier (20000 pour P-192, 20420, 20507 et 20509 pour les courbes de 239 bits, 20512 et 20517 pour les autres courbes de 192 bits), écarter sept sorties, construire des abscisses candidates à partir de sorties de 26 bits réduites modulo p, et recommencer jusqu'à ce que x se trouve sur la courbe. Le code publié reproduit les six, en un à cinq essais. Ce sont les premiers points de base liés au NIST à être expliqués.
Ce que cela signifie
Anthropic soutient que cela renforce la confiance dans les courbes : les graines proviennent d'un générateur simple et reproductible, initialisé par l'horloge, ce qui laisse peu de place à une subversion. Elle note aussi que rien dans les chiffres ne montre combien d'exécutions la NSA a effectuées, et que certaines courbes viables ont été écartées : l'exécution de P-256 a aussi sauté la candidate 876, celle de P-224 trois candidates, et les deux exécutions de l'ANSI sept de plus. Les critères, ou le caractère accidentel de ces sauts, restent inconnus. Comme peu de candidates ont été écartées, Anthropic ne juge pas plausible l'existence de courbes affaiblies, car cela supposerait qu'elles soient courantes et faciles à trouver.
Reste inexpliqué : la graine de B-163 ne correspond à rien de ce que Claude a essayé, et les points de base de P-224, P-256, P-384, P-521 et des courbes binaires du NIST demeurent inexpliqués.
La prime de 36 864 $ sera reversée à l'Internet Security Research Group. Le travail est attribué à John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini et Steve Weis, avec un clin d'œil à Solinas, qui avait pris avec bonne humeur le fait d'être qualifié de « mème Internet maléfique ». Cet article s'ajoute à la couverture de Claude en sciences sur ce blog, comme le calcul d'amplitude à neuf boucles et la découverte d'enzymes de type CRISPR.