L'essentiel
La provenance des graines utilisées pour définir les courbes elliptiques standard du NIST n'avait jamais été expliquée depuis leur publication en 2000 dans le FIPS 186-2. La NSA les avait fournies sans justification, ce qui alimentait depuis des années les soupçons d'une possible porte dérobée. Un employé d'Anthropic a posé la question à un modèle de recherche interne en octobre 2026 et Claude a retrouvé l'origine des graines de P-192, P-224, P-256, P-384 et P-521 en moins d'une demi-heure.
Le résultat est prosaïque. Les graines ne sortent d'aucune fonction de hachage, contrairement à une rumeur tenace. Elles proviennent du générateur pseudo-aléatoire lrand48 des bibliothèques C, amorcé par un horodatage Unix.
Les détails
Comment Claude a procédé
Les recherches menées à partir de la rumeur d'une phrase humoristique hachée n'avaient rien donné. Claude a changé d'angle en raisonnant sur le logiciel qui avait dû produire les courbes. Il a supposé l'usage d'un générateur pseudo-aléatoire livré avec les bibliothèques C des années 1990, assez faible pour que sa sortie soit reconnaissable.
Claude a écrit un scanner qui parcourt chaque graine publiée bit par bit et teste si des blocs adjacents sont des sorties consécutives d'un générateur de cette époque. Le balayage a couvert 34 combinaisons de générateur et de découpe. Un motif est alors apparu sur les bits de poids fort de certaines graines, tous à zéro. Écrites en cinq mots de 32 bits, quatre des dix graines ont un 0 en tête pour leurs 20 mots, ce qui n'arriverait par hasard qu'avec une probabilité de 1/5810. C'est la signature de lrand48, qui ne renvoie que les 31 bits de poids fort d'un état de 48 bits.
Pour retrouver l'état, Claude a essayé les 2¹⁷ valeurs possibles des 17 bits cachés du premier mot et vérifié que les quatre suivants suivaient. La méthode a fonctionné pour les quatre graines concernées. Les graines des courbes premières venaient du même générateur mais conservaient moins de bits par sortie. Claude a ramené le problème à une réduction de base par l'algorithme Lenstra–Lenstra–Lovász (LLL), en testant toutes les fenêtres de bits possibles. Les cinq graines NIST et cinq autres issues du standard ANSI X9.62 présentaient le même motif, lrand48() >> 23.
Le générateur se remonte aussi facilement qu'il descend. Claude a reculé chaque état jusqu'à la forme produite par srand48, avec les 16 bits de poids faible à 0x330E. Pour les dix graines de courbes premières, chaque initialisation correspondait à un horodatage Unix entre mai 1997 et avril 1998. Les quatre initialisations des courbes binaires lues comme des dates donnaient février 1984. En doublant ces horodatages, on retombe sur le 17 avril 1998, deux semaines après le calcul de P-224. Le programme a peut-être divisé l'horloge par deux.
Les points de base
Claude a aussi retrouvé l'origine de certains points de base G. Ceux des six courbes générées en mai 1997 (P-192 et les cinq courbes d'exemple ANSI X9.62 prime192v2, prime192v3 et prime239v1 à v3) viennent du générateur de FreeLIP, la bibliothèque d'arithmétique sur grands entiers d'Arjen Lenstra. Les premières versions de la bibliothèque NTL de Victor Shoup embarquent le même code. Les graines du générateur sont 20000 pour P-192, 20420, 20507 et 20509 pour prime239v1 à v3, et 20512 et 20517 pour prime192v2 et v3.
Les points de base de P-224, P-256, P-384 et P-521 ne suivent pas cette recette et restent inexpliqués, tout comme ceux des courbes binaires du NIST. La graine de B-163 résiste aussi à toutes les tentatives.
Ce qui reste ouvert
Certains candidats viables ont été écartés lors de la génération. Pour P-256, la graine publiée est le candidat 1842, mais le candidat 876 de la même exécution donne aussi une courbe d'ordre premier de la bonne taille. Le calcul de P-224 a sauté trois courbes de ce type et les deux exécutions derrière les courbes ANSI X9.62 en ont sauté sept de plus. Les auteurs ne savent pas quels critères ont été appliqués, ni s'il s'agit d'un artefact involontaire.
La prime de 36 864 dollars pour la découverte des graines sera versée à l'Internet Security Research Group. Les travaux ont été menés chez Anthropic par John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini et Steve Weis.
Pourquoi c'est important
Il ne s'agit ni d'une attaque ni d'une faiblesse des courbes ECDSA. Les auteurs estiment au contraire que ces résultats renforcent la confiance dans les paramètres, puisqu'une génération aussi simple laisse peu de place à une subversion délibérée. Mon hypothèse est que le précédent le plus intéressant n'est pas cryptographique mais méthodologique : un modèle a résolu en trente minutes un problème ouvert depuis vingt-cinq ans en raisonnant sur le logiciel de l'époque plutôt qu'en cherchant la bonne phrase. Cela suggère que les modèles peuvent être utiles pour l'archéologie logicielle, quand les archives ont disparu et que seuls les artefacts subsistent. Le fait que les points de base de plusieurs courbes restent inexpliqués montre aussi que le travail n'est pas terminé.
Source
- Claude reveals ECDSA curve origins · anthropic.com (via Hacker News)