Graines NIST d'ECDSA résolues : 5 mythes démontés

Pendant vingt-cinq ans, les graines des courbes ECDSA du NIST ont été ce que la cryptographie appliquée avait de plus proche d'une affaire non résolue. Cinq valeurs de 160 bits en apparence aléatoires, remises au NIST par la NSA sans la moindre explication, sous-tendent les signatures de tout, des connexions TLS aux transactions Bitcoin. Cette semaine, l'affaire est close, et la réponse est presque embarrassante : les graines étaient la sortie du générateur lrand48() de la bibliothèque C, initialisé avec des horodatages Unix de 1997 et 1998. C'est tout. Pas de hash d'une phrase de passe secrète, aucune machinerie exotique : srand48(time(NULL)), exactement le motif que tous les cours de sécurité vous disent de ne jamais utiliser.

La découverte vient d'un modèle de recherche d'Anthropic, mis sur le problème par un employé curieux, qui a reconnu la signature statistique d'un générateur congruentiel linéaire des années 1990 dans les constantes publiées, et a remonté l'état à l'envers jusqu'à tomber sur des dates de calendrier. J'ai passé assez d'années à auditer des systèmes cryptographiques pour savoir que ça compte, non pas parce que les courbes sont cassées (elles ne le sont pas), mais parce que ça ruine plusieurs choses que notre secteur croyait avec assurance. Prenons les mythes un par un.

Mythe 1 : des constantes inexpliquées signifient un backdoor caché

Le soupçon n'avait rien de délirant. Quand le NIST a publié les courbes FIPS 186-2 en 2000, chacune était accompagnée d'une graine dont le hash détermine le coefficient b de la courbe. Le NIST affirmait que les graines garantissaient que les courbes étaient « vérifiablement aléatoires », mais ne pouvait ou ne voulait pas dire comment les graines elles-mêmes avaient été générées. Koblitz et Menezes ont écrit tout un article sur la controverse, au titre malicieux : « A Riddle Wrapped in an Enigma ». La meilleure piste de la communauté était Jerry Solinas, à la NSA, qui se rappelait en 2015 que l'entrée était le hash d'une phrase humoristique, quelque chose comme « Give Bob and Jerry a raise ». Il est décédé en 2023 sans que personne n'ait retrouvé les détails.

La vérité inconfortable pour les adeptes de la théorie du complot, moi y compris à l'occasion : « inexpliqué » veut généralement dire « non documenté », pas malveillant. Le processus de génération réel, c'était un développeur qui lançait un petit programme C, laissait le PRNG par défaut s'initialiser à partir de l'horloge murale, et prenait le premier candidat qui produisait une courbe utilisable. La graine publiée pour P-256 était le candidat numéro 1 842, issu d'une exécution démarrée à 1 h 52 du matin le 16 août 1997. Ce n'est pas le fonctionnement d'une agence qui glisse un piège mathématique. C'est un ingénieur à une heure du matin qui fait tourner une boucle jusqu'à ce qu'elle affiche quelque chose de valide.

J'ai vu ce schéma dans des revues d'incidents plus de fois que je ne peux en compter. Une valeur de configuration mystérieuse, une constante magique non documentée, une étape de déploiement que personne ne sait expliquer, et le postmortem révèle que c'était un raccourci raisonnable sur le moment, d'un ingénieur épuisé, jamais écrit nulle part. Le vrai péché de la NSA ici n'était pas d'avoir glissé un backdoor dans les courbes. C'était d'avoir livré des constantes cryptographiques au monde entier sans README.

Mythe 2 : la méthode de génération prouve que la sélection était honnête

Maintenant, la correction excessive. Beaucoup de commentaires cette semaine présentent « ce ne sont que des horodatages » comme une disculpation totale. Ce n'est pas le cas, et les chercheurs derrière ces travaux prennent soin de le dire. Savoir comment les candidats ont été générés ne dit rien sur la manière dont les courbes finales ont été sélectionnées, et cette sélection s'est étalée sur des mois, de mai 1997 à avril 1998.

Les indices vont dans les deux sens. Dans l'exécution de P-256, le candidat 876 produisait aussi une courbe d'ordre premier de la bonne taille, construite avec les mêmes conventions de paramètres, et il a été écarté. La courbe publiée était le candidat 1 842. L'exécution de P-224 a laissé de côté trois courbes viables ; les exécutions ANSI X9.62 en ont écarté sept de plus. Nous ne voyons pas l'historique complet des candidats rejetés, seulement ceux qui sont accessibles dans les exécutions enregistrées. Si quelqu'un voulait une courbe avec une propriété rare précise, il aurait pu, en principe, chercher parmi les horodatages jusqu'à en trouver une, puis rester discret sur l'horodatage lui-même. « Le faire et ne rien dire » a toujours été une option.

Mon avis, après des années à suivre la recherche sur les courbes faibles : l'hypothèse du backdoor est sérieusement blessée, mais pas formellement morte. Les candidats écartés sont trop peu nombreux pour que la sélection sur mesure implique que les courbes faibles soient courantes et faciles à trouver, ce que deux décennies de cryptanalyse publique disent précisément ne pas être le cas. Personne n'a jamais publié de distingueur capable de séparer ces courbes de courbes aléatoires. Mais « aucune faiblesse connue » et « aucune faiblesse prouvée » sont deux affirmations différentes, et la position honnête est la première. C'est exactement le décalage entre spécification et implémentation qui se joue au niveau des standards : la spec disait « vérifiablement aléatoire », et l'implémentation était « ce que disait l'horloge ».

Les graines ont été générées comme le ferait un doctorant : un PRNG standard et l'horloge système. Le scandale n'a jamais été les mathématiques. C'était l'absence de documentation.

Mythe 3 : les vieux PRNG faibles sont inoffensifs si on ne les utilise qu'une fois

C'est le mythe qui devrait faire sursauter tout ingénieur ayant déjà tapé srand(time(NULL)). Tout le voile de mystère de vingt-cinq ans existait à cause d'une propriété de conception de lrand48() : il laisse fuiter sa propre structure. Le générateur ne renvoie que les 31 bits de poids fort d'un état de 48 bits, si bien que ses mots de sortie ont toujours un bit de poids fort nul. Écrites en mots de 32 bits, quatre des dix graines de courbes binaires montrent des bits de poids fort tous nuls sur vingt mots consécutifs, un événement de probabilité environ un sur 58 000 sous une distribution uniforme. La signature était visible à l'œil nu pour quiconque pensait à regarder.

À partir de là, l'attaque est d'une simplicité embarrassante. Pour retrouver les états des courbes binaires, on prend le premier mot de sortie, on force brutalement les 2^17 bits de poids faible cachés, et on vérifie si les quatre mots suivants en découlent. Quelques millisecondes de calcul. Pour les courbes premières, les graines conservaient moins de bits par sortie, donc récupérer l'état exigeait l'attaque classique sur LCG tronqué : la modéliser comme un problème de réseau euclidien et la traiter avec la réduction de base LLL. Du grand classique, littéralement. Une fois l'état obtenu, un LCG se remonte aussi facilement qu'il se parcourt : on le fait reculer jusqu'à obtenir la forme d'initialisation de srand48, avec des bits de poids faible égaux à 0x330E, et on lit l'horodatage utilisé comme graine.

# The whole mystery, reproduced
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

La leçon dépasse les organismes de normalisation. Toute valeur « d'apparence aléatoire » que vous émettez (jetons de session, identifiants de requête, sels, noms de fichiers) porte l'empreinte du générateur qui l'a produite. Si ce générateur est un moteur congruentiel linéaire ou un Mersenne Twister, quelques sorties suffisent à reconstruire l'état interne, et tout ce que vous avez généré avant et après devient prévisible. Une seule utilisation, il y a vingt-cinq ans, dans un fichier conçu pour ressembler à du bruit, a été entièrement inversée. Quand je relis du code qui utilise des RNG non cryptographiques pour quoi que ce soit qu'un attaquant peut observer, c'est désormais l'anecdote que je cite.

Mythe 4 : les nombres « rien dans la manche » n'ont jamais été la vraie protection

L'idée « nothing-up-my-sleeve », qui consiste à dériver les constantes de quelque chose d'évidemment innocent comme les décimales de pi, sert à limiter la marge de manœuvre du concepteur. Si je peux vous montrer que ma constante découle d'une procédure publique et rigide, je n'avais aucune latitude pour glisser un backdoor. Les graines du NIST ont échoué à ce test sur le plan procédural : la procédure était secrète, donc la limite de la marge de manœuvre était inconnue. Mais ce que cet épisode révèle vraiment, c'est que le test de la manche est plus faible qu'on le prétendait, même quand il fonctionne.

Considérez ce que « vérifiablement aléatoire à partir d'un horodatage » vous apporte réellement. Un horodatage représente environ 31 bits d'entropie pour une fenêtre plausible. N'importe qui, y compris l'auteur original, peut parcourir des millions d'horodatages, générer des millions de courbes candidates, et ne publier que celle qu'il veut, accompagnée de sa graine d'apparence innocente. Si des courbes à faiblesse secrète existaient à raison d'une sur un million, le criblage d'horodatages en trouve une en un après-midi. La graine prouve d'où vient le nombre, et dit presque rien de la raison pour laquelle celui-là a été choisi. Il en va de même pour les schémas basés sur le hash d'une phrase de passe, et c'est pourquoi la rumeur sur la blague de Solinas n'a jamais été totalement rassurante non plus.

La pratique moderne la plus solide est la construction rigide des courbes : choisir le plus petit coefficient satisfaisant une liste publique de critères de sécurité, les règles de sélection étant figées avant le début de la recherche. C'est la philosophie derrière Curve25519, et c'est pourquoi les arguments de rigidité de Dan Bernstein ont remodelé la façon dont la communauté évalue les courbes. La vraie protection contre les constantes malveillantes n'a jamais été une jolie histoire de dérivation. Elle consiste à réduire l'espace de recherche, à publier les critères à l'avance, et à avoir assez d'yeux indépendants sur les mathématiques pour qu'une propriété cachée ne puisse pas rester cachée. Auditer des constantes, c'est auditer le processus qui les a filtrées. C'est pourquoi les questions restées sans réponse ici (les candidats écartés, les points de base inexpliqués pour P-256 et consorts, la graine toujours non identifiée de B-163) méritent de rester ouvertes au dossier plutôt que d'être effacées par la célébration.

Mythe 5 : les LLM se contentent de régurgiter, ils ne peuvent pas faire de cryptanalyse originale

C'est le mythe qui pique le plus, parce que j'y ai cru sous une forme ou une autre. Le problème ouvert est resté non résolu pendant un quart de siècle malgré une prime publique de 36 864 dollars et l'attention sérieuse d'amateurs compétents. Plusieurs chercheurs d'Anthropic l'avaient eux-mêmes poursuivi, en suivant la piste du « hash d'une phrase drôle », et étaient revenus bredouilles. Puis un modèle de recherche interne, interrogé sans qu'on lui fournisse la rumeur, a essayé un angle différent en moins d'une demi-heure : au lieu de deviner l'entrée d'un hash, il s'est demandé quel logiciel aurait généré les graines, a émis l'hypothèse d'un PRNG de bibliothèque C des années 1990, a écrit un scanner glissant sur chaque graine en testant 34 combinaisons de générateur et de tranche de sortie, a repéré le motif de bits de poids fort nuls, a appliqué l'attaque par réseau sur les sorties tronquées, et a remonté les états jusqu'à des dates de calendrier.

Remarquez ce qu'est ce processus. Ce n'est pas de la récitation : aucun document d'entraînement ne contenait la réponse, parce que la réponse n'existait nulle part. C'est de la génération d'hypothèses, combinée à l'usage d'outils et à la vérification, ce qui est précisément la forme réelle du travail de cryptanalyse. Le modèle a même vérifié sa propre cohérence en cours de route : est-ce un environnement de test simulé, un élément aussi évident pourrait-il vraiment passer inaperçu pendant 25 ans, une correspondance de 160 bits à partir d'une graine de 32 bits exclut-elle la coïncidence ? Cette autocritique est ce que j'attendrais d'un analyste humain, et franchement, certains analystes humains la sautent. Nous avons déjà testé les mythes sur ce que font réellement ces modèles sur ce site, et voici un point de donnée net : les LLM peuvent désormais mener un raisonnement forensique en plusieurs étapes sur des artefacts réels, et pas seulement sur des benchmarks.

L'objection raisonnable des praticiens porte sur la provenance. Le modèle n'a pas inventé la récupération d'état LCG ni LLL : il s'appuie sur des décennies de cryptanalyse publiée par des chercheurs nommés et anonymes, et il ne peut pas vous dire dont les articles ont façonné son approche. Cela me dérange moins que certains. Le scanner, le code de vérification et le script de reproduction sont publics ; les humains de l'équipe ont dirigé la question et validé le résultat. Reconnaissons honnêtement la répartition des rôles : la machine a fourni une recherche d'hypothèses infatigable, les humains ont apporté le jugement et la responsabilité. Le fait que la prime de 36 864 dollars soit revenue à l'Internet Security Research Group était une façon élégante de conclure.

Ce que cela change pour les audits de sécurité

Alors, où cela laisse-t-il un ingénieur en activité ? Quelques évolutions concrètes dans ma façon d'aborder les audits. D'abord, traitez chaque constante magique d'un protocole ou d'une base de code comme un artefact forensique, et non comme un fait de la nature. Demandez quel générateur a pu la produire, cherchez les empreintes structurelles (bits de poids fort biaisés, mots successifs corrélés par LCG, récupérations d'état plausibles en termes d'horodatage) avant d'accepter « c'est aléatoire » comme réponse. L'outillage pour cela est désormais trivialement accessible.

Ensuite, si vous publiez des constantes, publiez le générateur. Code source, entrées exactes, environnement exact. « Vérifiablement aléatoire » sans recette reproductible vous vaut vingt-cinq ans de soupçons et une prime sur votre héritage. Enfin, continuez à utiliser P-256 : la découverte renforce la confiance dans les courbes plutôt que de l'affaiblir, et la vraie menace pour les courbes elliptiques vient du matériel quantique, pas de l'horloge d'une station de travail de 1997. Mais lisez honnêtement les questions ouvertes : les points de base inexpliqués et les candidats écartés sont des fils qui pendent, et un travail de sécurité mature consiste à les garder inscrits au registre.

L'enseignement le plus profond concerne la mémoire institutionnelle. Jerry Solinas se souvenait d'une blague sur des augmentations salariales, qui s'est avérée fausse. Les archives, selon ses propres mots, se trouvaient probablement sur un disque dur près de l'Arche d'Alliance. Si nous connaissons la vérité aujourd'hui, c'est uniquement parce que la sortie elle-même a conservé assez de structure pour se confesser. Vos systèmes écrivent leurs propres confessions en ce moment même, dans chaque identifiant, chaque jeton et chaque constante que vous livrez. Assurez-vous qu'elles avouent quelque chose dont vous êtes fier.