Prime pour retrouver les seeds des courbes elliptiques NIST

 (words.filippo.io)
1 points par GN⁺ 2023-10-06 | 1 commentaires | Partager sur WhatsApp
  • Les seeds de 5 courbes elliptiques NIST largement utilisées en cryptographie moderne proviennent de valeurs fournies par la NSA dans les années 1990, et une prime de 12 288 $ est offerte pour retrouver le texte source d’origine
  • Les courbes visées sont celles de la norme FIPS 186-2 : P-192, P-224, P-256, P-384, P-521 ; si la personne gagnante choisit un don à une organisation caritative américaine 501(c)(3), le montant est triplé à 36 864 $
  • Le seed aurait été créé par Jerry Solinas en 1997 ; il pourrait provenir du hachage SHA-1 d’une phrase en anglais, mais la formulation exacte a disparu après un remplacement ou une mise à niveau du matériel
  • Le format de la phrase reste incertain — point final, saut de ligne, position et format d’un compteur, présence éventuelle du nom de la courbe — si bien qu’une liste d’environ 12k hachages est proposée comme première cible d’attaque
  • La première personne à soumettre au moins un pre-seed reçoit 6 144 $ ; si elle soumet les cinq, elle reçoit les 6 144 $ restants ; l’ordre de soumission sera déterminé à partir des en-têtes Received du serveur mail

Les cibles de la prime et les montants

  • L’objectif de cette prime publique est de retrouver la valeur d’entrée du hachage (pre-seed) ayant servi à générer les seeds de cinq courbes elliptiques NIST
  • Le montant total de la prime est fixé à 12 288 $, soit 12 Ki$
    • Si la personne gagnante choisit un don à une organisation caritative américaine 501(c)(3) au lieu d’un paiement en espèces, le total passe à 36 864 $
  • Les hachages à casser sont les cinq suivants
    • 3045AE6FC8422F64ED579528D38120EAE12196D5
    • BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
    • C49D360886E704936A6678E1139D26B7819F7E90
    • A335926AA319A27A1D00896A6773A4827ACDAC73
    • D09E8800291CB85396CC6717393284AAA0DA64BA

Pourquoi les seeds des courbes NIST ont suscité des soupçons

  • Les courbes NIST P-192, P-224, P-256, P-384, P-521 ont été publiées en 2000 dans FIPS 186-2 et, selon la méthode ANSI X9.62, certains paramètres sont dérivés de la sortie obtenue en appliquant SHA-1 à un seed arbitraire
  • De nombreux systèmes cryptographiques utilisent les courbes NIST, en particulier P-256 et P-384
    • Ces deux courbes figurent dans la Commercial National Security Algorithm Suite
    • Elles sont aussi utilisées dans les certificats ECDSA X.509 qui protègent une grande partie du Web
  • Le billet de Steve Weis, NIST curve seed origins, récapitule ce que l’on sait des seeds arbitraires inclus dans la spécification FIPS 186
    • Les seeds semblent avoir été fournis par la NSA
    • Ils auraient été générés par Jerry Solinas en 1997
    • Ils pourraient avoir été obtenus en hachant en SHA-1 une phrase en anglais
  • Jerry Solinas a déjà indiqué avoir utilisé, à titre d’exemple, des seeds du type SHA1("Jerry deserves a raise."), mais la phrase réelle a disparu et des formulations proches ne correspondent pas aux hachages connus

En quoi retrouver le pre-seed pourrait réduire la méfiance

  • Les courbes NIST sont vues plus favorablement dans les évaluations récentes
    • Les complete addition formulas atténuent un important footgun
    • On connaît désormais de meilleures façons de concevoir des interfaces plus sûres
    • La valeur des courbes d’ordre premier immunisées contre les attaques par cofacteur est aussi mieux comprise
  • Chez certains non-praticiens subsiste l’idée que la NSA aurait pu choisir les seeds de façon à sélectionner délibérément des courbes faibles
  • Dans A riddle wrapped in an enigma, Koblitz et Menezes estiment qu’une telle attaque resterait peu convaincante même si la NSA avait eu un contrôle total sur les seeds
    • Elle supposerait l’existence d’une vaste classe de courbes faibles que ni le monde académique ni l’industrie n’auraient détectée en 25 ans
  • Même si ces inquiétudes ne paraissent pas très fondées, retrouver le pre-seed pourrait aider à réduire le FUD autour des courbes NIST
  • Trouver une preimage anglaise ne garantirait pas totalement la rigidity, mais permettrait de combler une pièce manquante de l’histoire de la cryptographie

Ce que l’on sait sur la valeur d’entrée du hachage

  • Il s’agit vraisemblablement d’une phrase en anglais mentionnant Jerry Solinas, avec éventuellement le nom d’une autre personne et un compteur
  • La présence probable d’un compteur s’explique par le fait que, selon la taille en bits de la courbe, seul environ un hachage sur 192 à 521 convient à la génération de la courbe
    • Pour la plus grande courbe, la probabilité que le compteur soit inférieur à 2400 est de 99 %
    • Pour P-256, il y a une probabilité que le compteur soit inférieur à 1175
  • Les seeds de P-192 et P-256 apparaissaient déjà comme exemples dans une version antérieure de la norme ANSI X9.62, tandis que les autres sont apparus avec FIPS 186-2 ; la structure des phrases peut donc différer
  • La prime ne concerne que les cinq courbes NIST d’ordre premier, mais si le coût de test est faible, il peut aussi être utile d’essayer d’autres exemples de l’ANSI X9.62 ainsi que les seeds des binary curves de FIPS 186-2
    • ANSI prime192v2, prime192v3, prime239v1, prime239v2, prime239v3 ne sont pas couverts par la prime
    • NIST B-163, B-233, B-283, B-409, B-571 ne sont pas couverts par la prime

Formats de chaîne possibles et liste d’attaque

  • Le format exact de la chaîne reste mystérieux
    • La phrase peut se terminer par un point, ou non
    • Il peut y avoir un saut de ligne, ou non
    • Le compteur peut être en décimal, avec des zéros initiaux, ou en binaire 16 ou 32 bits
    • Le compteur peut venir après le point ou être rattaché d’une autre manière
    • Tous les seeds ont pu être produits à partir d’une même phrase avec des compteurs différents, ou chaque seed peut avoir eu sa propre phrase
    • Le nom ou la taille de la courbe a pu être inclus dans la phrase
  • La mémoire humaine étant faillible, certains détails des témoignages indirects peuvent aussi être erronés
  • Au lieu d’un compteur, il est aussi possible qu’un hachage répété ait été utilisé, comme SHA-1(s) ou SHA-1(SHA-1(s))
  • Une autre possibilité consiste à partir de SHA-1(s) puis à incrémenter la valeur du hachage comme dans l’ANSI X9.62 Section A.3.3.1
  • Une liste d’attaque d’environ 12k hachages, nist-and-ansi-prime-order-seeds-increments-99-percent.txt, est fournie
    • Cette liste couvre un espace de probabilité de 99 % pour chaque seed de courbe d’ordre premier de FIPS 186-2 et de l’ANSI X9.62
    • Si le coût de vérification d’un grand nombre de hachages est faible, il est recommandé de l’utiliser comme cible d’attaque
    • Si possible, comparer seulement les 16 premiers octets du hachage donne le même résultat
  • SHA-1 se brute-force très rapidement, ce qui en fait un problème bien adapté aux personnes expérimentées dans le cassage de passphrases et le brute-force de brainwallets

Modalités de soumission et conditions de paiement

  • La première personne à envoyer par email les pre-seeds des cinq courbes NIST d’ordre premier à seeds@filippo.io remporte la prime
  • La structure du paiement se fait en deux étapes
    • La première personne à soumettre au moins 1 pre-seed reçoit la moitié, soit 6 144 $
    • La première à soumettre les 5 pre-seeds reçoit les 6 144 $ restants
    • Une même personne peut recevoir les deux paiements ; il n’est donc pas nécessaire d’attendre d’avoir trouvé les cinq
  • Il est possible de choisir entre un paiement en espèces et un don à une organisation caritative américaine 501(c)(3)
    • En choisissant l’option caritative, le montant est triplé
    • Le choix d’une organisation caritative en contradiction flagrante avec les valeurs du donateur peut être refusé
    • Si la personne est américaine ou de nationalité italienne et qu’un paiement direct lui est légalement impossible, elle devra choisir l’option caritative
    • Les taxes liées à la prime en espèces relèvent de la responsabilité du bénéficiaire
  • L’objet de l’email doit contenir ANTISPAM afin de passer les règles d’allowlisting
  • L’ordre de soumission sera tranché définitivement à partir des en-têtes Received de l’hébergeur mail
  • La prime expirera si les seeds deviennent publics ; sinon, elle reste valide jusqu’à annonce contraire sur cette page
    • En cas d’annulation ou de baisse du montant, un préavis de 6 mois sera donné
  • Aucune restriction n’est imposée quant à la méthode employée pour retrouver les seeds
    • Brute-force, intuition, enquête, récupération d’anciennes sauvegardes NIST : toutes les approches sont permises
    • Il est précisé qu’aucune question ne sera posée sur la méthode si la personne préfère ne pas la révéler

À lire aussi

1 commentaires

 
GN⁺ 2023-10-06
Avis sur Hacker News

  • Le contexte est assez amusant : une rumeur circule récemment selon laquelle les graines « aléatoires » des NIST P-curves, créées dans les années 1990 par Jerry Solinas de la NSA, seraient en réalité des valeurs obtenues en hachant avec SHA1 une variante de la chaîne "Give Jerry a raise"
    À l’époque, faire passer une chaîne dans SHA1 était considéré comme un mécanisme de confiance : la structure de la graine disparaissait, ce qui empêchait la NSA de choisir délibérément une graine faible
    Mais dans les années 2000, le NIST et la NSA ont eux-mêmes abîmé leur réputation, si bien que cette explication ne suffisait plus à faire taire les théories du complot ; plus tard, lorsque le NIST a voulu montrer que la graine était bénigne et que Jerry Solinas a tenté de la reconstituer, il aurait tout simplement oublié la chaîne qu’il avait utilisée
    Un vrai complotiste pensera que personne ne trouvera jamais la chaîne ayant généré cette graine, mais si quelqu’un la trouve, cela pourrait porter un coup assez sérieux à la théorie selon laquelle les NIST P-curves ont été générées de manière malveillante : c’est donc un bounty amusant

    • Même si quelqu’un trouvait une chaîne comme "Give Jerry a raise of $100000 dollars now!!!" dont le hash correspond à la graine, je ne pense pas que cela prouverait l’absence de malveillance
      Si l’on connaissait les propriétés particulières qu’une courbe faible devait avoir, on aurait pu hacher un très grand nombre de variantes de chaînes similaires jusqu’à obtenir une constante possédant les propriétés voulues
    • À la fin des années 1990, il était aussi courant d’utiliser MD5 et SHA1 ensemble pour apporter une « robustesse supplémentaire » à des constructions arbitraires
      SSLv2 et SSLv3 en sont de bons exemples, et même si la taille de sortie correspond à SHA1, il ne serait pas très surprenant qu’il se soit agi d’un pipeline du type echo "$string" | md5sum | sha1sum
    • Pour une histoire plus complète, on peut lire l’article de Koblitz et Menezes mentionné dans le texte, « A Riddle Wrapped in an Enigma ». Il traite aussi de la raison pour laquelle la NSA a déclaré en 2015 qu’il fallait passer à un monde post-quantique
      https://eprint.iacr.org/2015/1018
      https://eprint.iacr.org/2015/1018.pdf
      Les mêmes soupçons de backdoor ont aussi existé autour de (EC)DSA, et les partisans de RSA affirmaient que la NSA poussait DSA parce qu’elle y avait placé une backdoor, mais il n’y avait pas de preuve, et il semble qu’en vingt ans personne n’ait découvert de méthode pour introduire une backdoor dans DSA ou ECDSA
      Il existe aussi une anecdote selon laquelle, lors d’une réunion de normalisation, un représentant de la NSA serait revenu après un appel téléphonique et aurait déclaré que la NSA considérait l’ECC comme suffisamment sûre pour les communications sécurisées de toutes les agences du gouvernement américain, y compris la Federal Reserve, ce qui avait surpris tout le monde
      Comme les ajustements de DES se sont révélés plus tard être une défense contre la cryptanalyse différentielle, et comme la faiblesse du SHA original, SHA-0, n’était plus présente dans le SHA-1 final, d’autres actions de la NSA ont également été perçues avec suspicion
    • J’ai brûlé beaucoup trop de CPU à essayer de trouver l’entrée ayant produit la valeur « aléatoire » d’environ 166 bits utilisée pour construire G dans secp256k1 et secp224k1, sans succès
      Dans les deux courbes, le choix de G est le double d’un point dont la coordonnée x a une taille suspectement adéquate, et cette caractéristique est la même pour les deux courbes
      Dans ces courbes, le choix de G est le seul paramètre d’entrée ayant une forte entropie, mais on peut démontrer qu’il est en pratique presque sans importance, et que la personne qui l’a choisi ne connaît qu’un logarithme discret arbitraire particulier
      Dans un protocole forcé, cela pourrait servir de backdoor, mais ce serait très artificiel ; malgré tout, comme c’est le seul paramètre inconnu, cela valait la peine de chercher
      Si la graine des P-curves est retrouvée, elle pourrait ressembler aux graines utilisées pour les points générateurs d’autres courbes, ce qui pourrait aussi résoudre ce petit mystère
    • Pour ce genre d’objectif, la méthode standard consiste généralement à utiliser des constantes transcendantes comme π ou e, parce qu’elles ne peuvent pas être choisies
      Une phrase peut, en théorie, être choisie de façon à produire le hash voulu

  • Le GCHQ britannique emploie plus de mathématiciens que n’importe quel laboratoire ou université du pays. L’agence américaine équivalente doit probablement être dans une situation similaire.
    L’échange de clés Diffie-Hellman était également connu du GCHQ et de la NSA avant que Diffie et Hellman ne le redécouvrent.
    Il est difficile d’être catégorique sur les capacités de base des agences de renseignement, et je ne dis pas qu’elles connaissent effectivement une telle famille de courbes faibles, mais il est difficile de dire que c’est impossible. C’est leur cœur de métier.

    • Je pense qu’il est juste d’être méfiant. Surtout parce que l’argument présenté pour dire que c’est impossible a l’air mathématique, alors qu’en réalité il relève plutôt d’un argument social.
      En général, on dit que le monde académique est si brillant que si la NSA avait fait quelque chose, il l’aurait déjà découvert ; et si l’on n’est pas d’accord, on est traité comme quelqu’un qui répand du FUD sans bien comprendre. Cet article reprend aussi cette ligne, mais c’est une bonne chose que le problème soit pris plus au sérieux au moyen d’un bounty organisé.
      J’ai travaillé par le passé sur la cryptographie et, pendant plusieurs années, j’ai régulièrement examiné des articles de crypto dans le cadre de mon travail ; j’ai aussi assisté à des conférences, discuté avec des chercheurs et implémenté plusieurs chiffrements sur courbes elliptiques « atypiques ». Sans être totalement de l’intérieur, mais sans être non plus complètement extérieur, ce consensus me paraît dangereux.
      Les deux arguments centraux sont les suivants : si une attaque kleptographique avait été possible lors de la normalisation des courbes du NIST, le monde académique ou l’industrie l’auraient déjà trouvée ; et Dual_EC_DRBG ayant été immédiatement suspecté, la communauté ouverte de la cryptographie saurait bien détecter les portes dérobées.
      Le premier est peu convaincant. Dans le monde académique, il y a le problème du tiroir à fichiers et l’incitation « publier ou périr » ; pour un jeune chercheur, il est évident qu’il vaut mieux inventer un nouvel algorithme de preuve à divulgation nulle de connaissance et publier un article qui sera cité, plutôt que d’attaquer un algorithme que tout le monde croit robuste pour ne rien obtenir.
      L’argument repose sur un consensus d’experts selon lequel « beaucoup de gens intelligents l’ont étudié en profondeur sans rien trouver », mais comme il est difficile de publier des résultats négatifs dans le monde académique, il n’y a aucun moyen de savoir combien d’efforts y ont réellement été consacrés.
      La kleptographie, c’est-à-dire la manière d’insérer une porte dérobée dans une norme, n’a quasiment aucun intérêt à moins d’être la NSA ; ce n’est donc pas une bonne trajectoire de carrière, et ce n’est favorable ni pour passer dans l’industrie ni pour obtenir des citations.
      À l’inverse, la NSA peut payer davantage que le monde académique, employer plus de chercheurs que l’ensemble du milieu universitaire pour les affecter à des recherches à forte probabilité d’échec ou utiles uniquement à des portes dérobées dans des standards, et mener depuis des décennies des recherches pluridisciplinaires que la recherche académique en cryptographie ne peut pas se permettre faute de budget matériel.
      S’il fallait parier sur qui, de la NSA ou du monde académique, comprend le mieux l’ECC, la puissance de feu est du côté du gouvernement et il n’y a pas de comparaison possible. On peut estimer approximativement le nombre de docteurs en mathématiques employés par le gouvernement, mais on ne sait pas quelle puissance de feu le monde académique a réellement consacrée à cet espace de problèmes.
      Le second argument n’est pas idéal non plus. Les gens ont immédiatement exprimé des inquiétudes non seulement au sujet de Dual_EC_DRBG, mais aussi des courbes du NIST. La seule différence est que, dans le premier cas, il existait un algorithme connu permettant de mener l’attaque nécessaire, et pas dans le second.
      La manière d’éviter d’emblée ce genre de débat était connue depuis des décennies, et c’est aussi pour cela que les courbes du NIST ont été générées à partir de sorties SHA1. Le meilleur moment pour abandonner progressivement les courbes du NIST était il y a plusieurs décennies ; le deuxième meilleur moment, c’est maintenant.
    • La NSA emploie aussi des professeurs de mathématiques spécialisés en théorie des nombres américains.

  • La raison de contribuer à ce bounty, c’est que s’il s’agit vraiment d’une phrase que l’on peut retrouver par cassage de mot de passe, la découvrir aurait une grande portée historique.

  • Le fait que les courbes elliptiques du NIST aient été générées en hachant des seeds fournies par la NSA est assez inquiétant.
    Cela sonne comme : « Ne vous inquiétez pas, on les a créées en hachant une phrase sans importance. On l’a oubliée depuis, mais c’était juste Jerry qui plaisantait sur une augmentation de salaire. »
    Il est difficile de croire qu’elles n’aient pas été soumises plus tôt à une vérification solide, et qu’on n’ait pas choisi des seeds de façon plus raisonnable, par exemple en mélangeant des seeds aléatoires de plusieurs parties aux intérêts différents avec des générateurs matériels de nombres aléatoires.

    • C’est parce que tu vis en 2023 et que tu regardes cela en sachant ce qui s’est passé depuis les années 1990 jusqu’à aujourd’hui.
      Cette méthode aurait été préférable, mais à l’époque, peu de gens ont dû en voir la nécessité.
    • Si la majeure partie du trafic Internet est aujourd’hui chiffrée, on peut se demander à quoi servent d’immenses datacenters comme Bluffdale.
      https://en.wikipedia.org/wiki/Utah_Data_Center

  • Il existe une vidéo où le professeur Dan Boneh explique le contexte : https://youtu.be/8WDOpzxpnTE?t=892

  • Si j’ai bien compris, cela signifie que la communauté a accepté des chaînes suspectes dont l’origine était inconnue, alors qu’il aurait été très facile d’injecter dans le hash d’autres entrées connues pour les remplacer par des chaînes à l’origine claire ?

    • Tu as bien compris, et c’est assez catastrophique. Cela fait penser à « on y était presque » et à « tu n’avais qu’une seule chose à faire ».
      Malheureusement, à ma connaissance, c’est le seul cas où l’incompétence est invoquée à propos de la NSA et des standards cryptographiques ; en général, les récits vont dans le sens inverse.
      Ce qui est encore plus problématique, c’est que le NIST avait déjà un précédent d’insertion de porte dérobée dans un standard lié aux courbes elliptiques, que le fait que ce mécanisme ne crée pas de confiance avait été immédiatement signalé, et que ni le NIST ni la NSA n’ont rien fait. Comme avec Dual_EC_DRBG.
      Plus problématique encore, la NSA a explicitement dit en 2015 de ne pas migrer vers d’autres courbes postérieures aux courbes du NIST. La raison avancée était que les ordinateurs quantiques deviendraient bientôt assez performants pour casser toute l’ECC, et que tout le monde devait donc passer à la cryptographie post-quantique.
      Si l’ECC fonctionne bien, que les ordinateurs quantiques sont encore loin et que l’on veut maintenir les gens le plus longtemps possible sur les courbes du NIST, c’est exactement ce qu’on aurait dit.
      La communauté cryptographique ne sort pas vraiment grandie de cette situation. Près de 25 ans se sont écoulés, et il existe des courbes plus récentes qui n’ont pas ce problème : pourquoi les courbes du NIST sont-elles encore utilisées ? Où sont les efforts pour les retirer progressivement, comme SHA1 ? Cet article donne plutôt l’impression de promouvoir ces courbes.

  • Si vous vous sentez chanceux, vous pouvez essayer de deviner le hash SHA1 ici : https://wending.dev/hash_guessing/

    • Ça ne fait que générer le SHA1 de la chaîne saisie, non ? Comme le dit l’article, il devrait y avoir une forme de compteur incluse.
      Si le générateur de seeds de la NSA avait eu ne serait-ce qu’une vague notion de cryptographie et d’informatique, il ne serait pas resté à entrer à la main 500 phrases différentes jusqu’à obtenir une bonne courbe.
      Et même s’il l’avait fait, les variantes possibles sont infinies : ajouter un point à la fin, changer la casse, mettre en capitales façon titre, etc.
      Une liste de variantes plausibles à essayer ne pourra jamais vraiment être exhaustive, mais si, comme cette page, on ne fait que générer des hashes SHA1, même en devinant la bonne chaîne avec la ponctuation et la casse exactes, il est pratiquement impossible de trouver le hash réel.
      Au minimum, pour vérifier si le hash résultant est une valeur incrémentée, il faudrait pouvoir vérifier si les 10 octets au début ou à la fin correspondent. Malgré tout, cela fera surtout perdre du temps, et l’auteur sait probablement que ça ne mènera nulle part.
      La page devrait indiquer que ce n’est qu’un jouet de démonstration, et que même une bonne supposition ne permettrait pas de retrouver le seed réel.

  • Ce que j’ai appris en regardant longtemps les débats enflammés entre cryptographes, c’est : « ne pariez pas contre Bernstein, et ne faites pas confiance au NIST ».
    Je crois qu’il faut maintenant corriger en : « ne pariez pas contre Bernstein ni contre Filippo, et ne faites pas confiance au NIST. Si ces deux règles entrent en conflit, ne faites quand même pas confiance au NIST ».

  • SHA-1 est bien cassé, mais je pensais que les problèmes concernaient surtout les collisions via des attaques par extension de longueur ou les attaques à texte clair connu.
    Quand on ne dispose que du hash, retrouver en pratique la phrase de passe me semblait encore difficile.

    • Exact. On considère toujours que SHA-1 conserve une résistance à la préimage.
      Mais si l’hypothèse sur la structure du seed est correcte, la résistance à la préimage n’est pas si importante ici. SHA-1 est très rapide et facile à paralléliser, donc quelqu’un qui fouille obstinément l’espace des variantes de "Jerry needs a raise" a de bonnes chances de découvrir l’entrée d’origine.
    • C’est une simple attaque par dictionnaire, et c’est ainsi que la plupart des hashes de mots de passe sont cassés.
      Ça n’a pas grand-chose à voir avec SHA1 lui-même.