NIST-Bounty für elliptische-Kurven-Seeds
(words.filippo.io)- Die Seeds von fünf NIST-Elliptic-Curves, die in der modernen Kryptografie weit verbreitet sind, stammen aus Werten, die die NSA in den 1990er-Jahren geliefert hat; auf das Auffinden des $12,288-Bountys für den ursprünglichen Wortlaut ist eine Belohnung ausgesetzt
- Betroffen sind in FIPS 186-2 die Kurven P-192, P-224, P-256, P-384, P-521; wenn die erfolgreiche Person statt einer Barauszahlung eine Spende an eine US-amerikanische 501(c)(3)-Wohltätigkeitsorganisation wählt, wird der Betrag auf $36,864 verdreifacht
- Die Seeds sollen 1997 von Jerry Solinas erstellt worden sein; vermutlich wurde ein englischer Satz mit SHA-1 gehasht, aber die tatsächliche Formulierung ist nach Geräteaustausch oder Upgrades verloren gegangen
- Das Format des Satzes ist unklar, einschließlich Punkt, Zeilenumbruch, Position und Format eines Zählers sowie der Frage, ob der Kurvenname enthalten war; daher wird zunächst eine Liste mit etwa 12k Hashes als Angriffsziel vorgeschlagen
- Wer zuerst mindestens einen pre-seed einreicht, erhält $6,144; wer als Erste:r alle fünf einreicht, erhält die restlichen $6,144; die Reihenfolge wird anhand der
Received-Header des Mailservers bestimmt
Ziel des Bountys und Auszahlungshöhe
- Ziel des öffentlichen Bountys ist es, die Hash-Eingabewerte (pre-seeds) zu finden, aus denen die Seeds der fünf NIST-Elliptic-Curves erzeugt wurden
- Das gesamte Bounty beträgt $12,288, also 12 Ki$
- Wenn die erfolgreiche Person statt Bargeld eine Spende an eine US-amerikanische 501(c)(3)-Wohltätigkeitsorganisation wählt, steigt der Gesamtbetrag auf $36,864
- Die Ziel-Hashes sind die folgenden fünf Werte
3045AE6FC8422F64ED579528D38120EAE12196D5BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5C49D360886E704936A6678E1139D26B7819F7E90A335926AA319A27A1D00896A6773A4827ACDAC73D09E8800291CB85396CC6717393284AAA0DA64BA
Warum die NIST-Kurven-Seeds Misstrauen geweckt haben
- Die NIST-Kurven P-192, P-224, P-256, P-384, P-521 wurden 2000 in FIPS 186-2 veröffentlicht; nach dem Verfahren aus ANSI X9.62 werden einige Parameter aus der SHA-1-Ausgabe eines zufälligen Seeds abgeleitet
- Viele kryptografische Systeme verwenden NIST-Kurven, insbesondere P-256 und P-384
- Beide Kurven sind Teil der Commercial National Security Algorithm Suite
- Sie werden auch in ECDSA-X.509-Zertifikaten verwendet, die große Teile des Webs schützen
- Steve Weis’ NIST curve seed origins fasst zusammen, was über die zufälligen Seeds in der FIPS-186-Spezifikation bekannt ist
- Die Seeds scheinen von der NSA geliefert worden zu sein
- Sie sollen 1997 von Jerry Solinas erzeugt worden sein
- Möglicherweise wurden sie erzeugt, indem ein englischer Satz mit SHA-1 gehasht wurde
- Jerry Solinas erwähnte einmal als Beispiel Seeds der Form
SHA1("Jerry deserves a raise."); die tatsächliche Formulierung ist jedoch verloren, und ähnliche Sätze stimmten nicht mit den Hashes überein
Wie ein pre-seed-Fund Misstrauen verringern könnte
- In jüngeren Bewertungen erscheinen die NIST-Kurven in mancher Hinsicht positiver
- complete addition formulas entschärfen wichtige footguns
- Es sind bessere Methoden für das Design sicherer Schnittstellen bekannt
- Der Wert von Kurven mit Primordnungsgruppe, die gegen Cofactor-Angriffe immun sind, ist ebenfalls klarer geworden
- Unter manchen Nicht-Praktikern besteht weiterhin die Sorge, die NSA könnte die Seeds absichtlich gewählt haben, um schwache Kurven zu erhalten
- Koblitz und Menezes argumentieren in A riddle wrapped in an enigma, dass ein solcher Angriff selbst bei vollständiger Seed-Kontrolle durch die NSA wenig überzeugend wäre
- Dafür wäre eine große Klasse schwacher Kurven nötig, die Wissenschaft und Industrie 25 Jahre lang nicht entdeckt hätten
- Diese Sorge wirkt zwar nicht besonders gut begründet, aber das Auffinden der pre-seeds könnte helfen, FUD rund um die NIST-Kurven zu verringern
- Das Finden des englischen preimage garantiert rigidity nicht vollständig, würde aber ein fehlendes Stück Kryptografiegeschichte ergänzen
Bekannte Hinweise zu den Hash-Eingabewerten
- Die Eingabewerte sind wahrscheinlich englische Formulierungen, die Jerry Solinas erwähnen; möglicherweise kamen auch andere Namen und ein Zähler vor
- Ein Zähler war wahrscheinlich nötig, weil je nach Kurven-Bitgröße nur ungefähr einer von 192 bis 521 Hashes für die Kurvenerzeugung geeignet ist
- Für die größte Kurve liegt die Wahrscheinlichkeit bei 99%, dass der Zähler unter 2400 liegt
- Für P-256 gibt es eine entsprechende Wahrscheinlichkeit, dass der Zähler unter 1175 liegt
- Die Seeds von P-192 und P-256 erschienen bereits als Beispiele im früheren ANSI-X9.62-Standard, die übrigen wurden erst in FIPS 186-2 neu eingeführt; daher kann die Satzstruktur unterschiedlich gewesen sein
- Ziel des Bountys sind nur die fünf NIST-Kurven mit Primordnungsgruppe, aber wenn die Testkosten niedrig sind, können auch andere Beispiele aus ANSI X9.62 und Seeds der binären Kurven aus FIPS 186-2 ausprobiert werden
- ANSI prime192v2, prime192v3, prime239v1, prime239v2, prime239v3 sind nicht Teil des Bountys
- NIST B-163, B-233, B-283, B-409, B-571 sind ebenfalls nicht Teil des Bountys
Mögliche String-Formate und Angriffsliste
- Das Format des Strings selbst bleibt ein Rätsel
- Der Satz könnte mit einem Punkt enden oder nicht
- Es könnte einen Zeilenumbruch geben oder keinen
- Der Zähler könnte dezimal sein, führende Nullen enthalten oder als 16-Bit- oder 32-Bit-Binärwert vorliegen
- Der Zähler könnte nach einem Punkt folgen oder auf andere Weise angehängt worden sein
- Es könnte derselbe Satz mit unterschiedlichen Zählern verwendet worden sein, um alle Seeds zu erzeugen, oder für jeden Seed ein anderer Satz
- Der Kurvenname oder die Kurvengröße könnte in der Formulierung enthalten gewesen sein
- Da menschliche Erinnerung fehleranfällig ist, ist es möglich, dass einige Details aus indirekten Aussagen falsch sind
- Statt eines Zählers könnte auch wiederholtes Hashing wie
SHA-1(s)oderSHA-1(SHA-1(s))verwendet worden sein - Ein weiterer Kandidat ist, bei
SHA-1(s)zu starten und den Hash-Wert dann wie in ANSI X9.62 Section A.3.3.1 zu inkrementieren - Als Angriffsziel wird eine Liste mit etwa 12k Hashes in nist-and-ansi-prime-order-seeds-increments-99-percent.txt bereitgestellt
- Die Liste deckt für jeden Prime-Order-Curve-Seed aus FIPS 186-2 und ANSI X9.62 einen Wahrscheinlichkeitsraum von 99% ab
- Wenn das Prüfen vieler Hashes billig ist, wird empfohlen, diese Liste anzugreifen
- Wenn möglich, reicht auch ein Vergleich der ersten 16 Bytes des Hashes für dasselbe Ergebnis
- SHA-1 lässt sich sehr schnell brute-forcen; das Problem eignet sich daher für Personen mit Erfahrung in Passphrase-Cracking und Brainwallet-Bruteforce
Einreichung und Auszahlungsbedingungen
- Die Person, die als Erste die pre-seeds der fünf NIST-Kurven mit Primordnungsgruppe per E-Mail an
seeds@filippo.ioeinreicht, erhält das Bounty - Die Auszahlungsstruktur besteht aus zwei Stufen
- Wer zuerst mindestens einen pre-seed einreicht, erhält die Hälfte, also $6,144
- Wer zuerst alle fünf pre-seeds einreicht, erhält die restlichen $6,144
- Eine Person kann beide Auszahlungen erhalten; man muss also nicht warten, bis alle fünf gefunden sind
- Es kann zwischen Barauszahlung und Spende an eine US-amerikanische 501(c)(3)-Wohltätigkeitsorganisation gewählt werden
- Bei Wahl der Wohltätigkeitsspende wird der Betrag verdreifacht
- Die Wahl einer Wohltätigkeitsorganisation kann abgelehnt werden, wenn sie den eigenen Werten drastisch widerspricht
- Wer als US-Amerikaner:in oder italienische Staatsangehörige:r rechtlich kein Geld überwiesen bekommen darf, muss die Wohltätigkeitsoption wählen
- Steuern auf das Bargeld-Bounty sind Sache der Empfängerin oder des Empfängers
- Der Betreff der Einreichungs-E-Mail muss
ANTISPAMenthalten, um die Allowlisting-Regeln zu passieren - Die Reihenfolge der Einreichungen wird endgültig anhand des Received-Headers des Mailhosts bestimmt
- Das Bounty verfällt, sobald die Seeds öffentlich bekannt werden; andernfalls bleibt es gültig, bis auf dieser Seite etwas anderes angekündigt wird
- Eine Absage oder Kürzung des Bountys wird 6 Monate im Voraus angekündigt
- Es gibt keine Einschränkungen für die Methode, mit der die Seeds gefunden werden
- Brute-Force, clevere Vermutungen, Recherchen, Wiederherstellung alter NIST-Backups oder jede andere Methode sind erlaubt
- Es gilt die Zusage, auf Wunsch nicht nach der Methode zu fragen
1 Kommentare
Meinungen auf Hacker News
Der Hintergrund hier ist ziemlich amüsant: In letzter Zeit kursiert die Geschichte, dass der „zufällige“ Seed der NIST-P-Curves, die Jerry Solinas von der NSA in den 1990er-Jahren erstellt hat, in Wirklichkeit der SHA1-Hash einer abgewandelten Zeichenkette von
"Give Jerry a raise"gewesen sei.Damals galt es als vertrauensbildende Maßnahme, eine Zeichenkette durch SHA1 zu schicken, weil dadurch die Struktur des Seeds verschwinde und die NSA nicht gezielt einen schwachen Seed auswählen könne.
Nachdem NIST/NSA in den 2000er-Jahren ihren Ruf aber selbst beschädigt hatten, reichte diese Erklärung allein nicht mehr aus, um Verschwörungstheorien zu beruhigen. Als NIST später zeigen wollte, dass der Seed harmlos war, und Jerry Solinas ihn zu rekonstruieren versuchte, soll er ausgerechnet die von ihm verwendete Zeichenkette vergessen haben.
Echte Verschwörungstheoretiker würden wohl annehmen, dass niemand die Zeichenkette finden wird, die diesen Seed erzeugt. Falls sie aber jemand findet, könnte das der Theorie, die NIST-P-Curves seien böswillig erzeugt worden, ziemlich zusetzen – eine interessante Bounty also.
"Give Jerry a raise of $100000 dollars now!!!"zum Seed passt, sehe ich das nicht als Beweis dafür, dass keine böse Absicht dahintersteckte.Wenn man die besonderen Eigenschaften kannte, die eine schwache Kurve haben müsste, hätte man sehr viele ähnliche Zeichenketten-Varianten hashen und so lange auswählen können, bis eine Konstante mit den gewünschten Eigenschaften herauskam.
SSLv2 und SSLv3 sind gute Beispiele dafür, und auch wenn die Ausgabegröße zu SHA1 passt, wäre es nicht allzu überraschend, wenn es eine Pipeline wie
echo "$string" | md5sum | sha1sumgewesen wäre.https://eprint.iacr.org/2015/1018
https://eprint.iacr.org/2015/1018.pdf
Ähnliche Backdoor-Verdächtigungen gab es auch bei (EC)DSA; RSA-Befürworter behaupteten, die NSA treibe DSA voran, weil sie dort eine Backdoor eingebaut habe. Belege gab es jedoch keine, und in 20 Jahren wurde offenbar auch keine Methode gefunden, eine Backdoor in DSA oder ECDSA einzubauen.
Es gibt außerdem die Anekdote, dass ein NSA-Vertreter bei einer Standardisierungssitzung nach einem Telefonat zurückkam und sagte, die NSA halte ECC für ausreichend für sichere Kommunikation aller US-Regierungsstellen einschließlich der Federal Reserve – was alle überraschte.
So wie sich die Anpassungen an DES später als Schutz gegen differentielle Kryptoanalyse herausstellten und die Schwächen des ursprünglichen SHA, also SHA-0, im finalen SHA-1 nicht mehr vorhanden waren, wurden auch andere Handlungen der NSA mit Misstrauen betrachtet.
Bei beiden Kurven ist die Wahl von G das Doppelte eines Punkts mit einer x-Koordinate von verdächtig passender Größe, und dieses Merkmal ist bei beiden Kurven gleich.
Bei diesen Kurven ist die Wahl von G der einzige Input mit viel Entropie, sie ist aber nachweislich praktisch irrelevant; die Person, die ihn ausgewählt hat, kennt dadurch höchstens einen bestimmten zufälligen diskreten Logarithmus.
In einem gekünstelten Protokoll könnte das vielleicht eine Backdoor sein, wäre aber sehr konstruiert. Trotzdem war es den Versuch wert, danach zu suchen, weil es der einzige unbekannte Parameter ist.
Wenn man den Seed der P-Curves findet, könnte er den Seeds ähneln, die für die Generatorpunkte anderer Kurven verwendet wurden, und damit auch dieses kleine Rätsel lösen.
Eine Formulierung kann theoretisch so gewählt werden, dass der gewünschte Hash herauskommt.
Der britische GCHQ beschäftigt mehr Mathematiker als jedes Forschungsinstitut oder jede Universität im Land. Bei den entsprechenden US-Behörden dürfte es ähnlich sein.
Auch den Diffie-Hellman-Schlüsselaustausch kannten GCHQ und NSA schon, bevor Diffie und Hellman ihn wiederentdeckten.
Über die grundlegenden Fähigkeiten von Nachrichtendiensten lässt sich schwer ein abschließendes Urteil fällen, und ich sage nicht, dass sie tatsächlich von solchen schwachen Kurvenfamilien wissen, aber unmöglich erscheint es auch nicht. Dieses Gebiet ist ihr Kerngeschäft.
Üblicherweise heißt es, die Wissenschaft sei so gut, dass sie es bereits entdeckt hätte, wenn die NSA etwas getan hätte; wer nicht zustimmt, wird als jemand behandelt, der sich nicht auskennt und FUD verbreitet. Dieser Text wiederholt diese Linie, aber es ist gut, dass das Problem durch ein organisiertes Bounty ernster genommen wird.
Ich habe früher an Kryptografie gearbeitet, über mehrere Jahre beruflich regelmäßig Kryptografie-Paper begutachtet, Konferenzen besucht, mit Forschern gesprochen und mehrere „ungewöhnliche“ Implementierungen elliptischer Kurvenkryptografie gebaut. Aus der Perspektive von jemandem, der kein vollständiger Insider, aber auch kein kompletter Außenseiter ist, wirkt diese herrschende Meinung gefährlich.
Die Kernargumente sind zwei: Erstens, dass Wissenschaft oder Industrie es bereits gefunden hätten, wenn bei der Standardisierung der NIST-Kurven ein Kleptografie-Angriff möglich gewesen wäre; zweitens, dass Dual_EC_DRBG sofort verdächtigt wurde und die offene Kryptografie-Community daher Backdoors gut erkennt.
Das erste überzeugt wenig. In der Wissenschaft gibt es das File-Drawer-Problem und den Anreiz „publish or perish“. Für junge Forscher ist offensichtlich vorteilhafter, einen neuen Zero-Knowledge-Proof-Algorithmus zu entwickeln und ein zitierbares Paper zu veröffentlichen, als einen Algorithmus anzugreifen, den alle für stark halten, und am Ende nichts vorweisen zu können.
Die Grundlage ist ein Expertenkonsens nach dem Motto: „Viele kluge Leute haben das gründlich untersucht, aber nichts gefunden.“ Da Nullergebnisse in der Wissenschaft schwer zu publizieren sind, gibt es aber keine Möglichkeit zu wissen, wie viel Aufwand tatsächlich investiert wurde.
Kleptografie – also die Kunst, Backdoors in Standards einzubauen – ist zudem außerhalb der NSA kaum nützlich und daher kein guter Karriereweg; sie hilft weder beim Wechsel in die Industrie noch bei Zitierungen.
Die NSA dagegen kann besser zahlen als die Wissenschaft, mehr Forscher beschäftigen als die gesamte akademische Welt und sie auf Forschung ansetzen, die mit hoher Wahrscheinlichkeit scheitert oder nur für Standard-Backdoors nützlich ist. Außerdem konnte sie dank Hardware-Budgets über Jahrzehnte interdisziplinäre Forschung betreiben, die akademische Kryptografieforschung nicht leisten kann.
Wenn ich darauf wetten müsste, wer ECC besser versteht, NSA oder Wissenschaft, läge die Feuerkraft auf Regierungsseite; der Vergleich ist kaum fair. Die Zahl der promovierten Mathematiker, die der Staat beschäftigt, kann man grob abschätzen, aber wir wissen nicht, wie viel Feuerkraft die Wissenschaft tatsächlich in diesen Problemraum gesteckt hat.
Auch das zweite Argument ist nicht ideal. Nicht nur bei Dual_EC_DRBG, auch bei den NIST-Kurven äußerten Leute sofort Bedenken. Der Unterschied war nur, dass es im ersten Fall einen bekannten Algorithmus gab, um den nötigen Angriff durchzuführen, im zweiten Fall aber nicht.
Die Methode, solche Debatten von vornherein unnötig zu machen, ist seit Jahrzehnten bekannt, und genau deshalb wurden die NIST-Kurven aus SHA1-Ausgaben erzeugt. Der beste Zeitpunkt, die NIST-Kurven schrittweise abzuschaffen, war vor Jahrzehnten; der zweitbeste ist jetzt.
Der Grund, zu diesem Bounty beizutragen, ist: Falls es sich wirklich um eine per Passwort-Cracking auffindbare Phrase handelt, wäre es historisch von großer Bedeutung, sie herauszufinden.
Dass die NIST-Elliptic-Curves durch Hashing von Seeds erzeugt wurden, die die NSA bereitgestellt hat, ist ziemlich beunruhigend.
Es klingt wie: „Keine Sorge, wir haben nur irgendeinen harmlosen Satz gehasht. Wir haben ihn inzwischen vergessen, aber Jerry hat nur einen Witz über eine Gehaltserhöhung gemacht.“
Es ist schwer zu glauben, warum das nicht früher einer strengen Überprüfung unterzogen wurde – und warum man keine vernünftigere Seed-Auswahl getroffen hat, etwa durch Mischen zufälliger Seeds mehrerer Parteien mit unterschiedlichen Interessen und Hardware-Zufallszahlengeneratoren.
Diese Methode wäre gut gewesen, aber damals dürften nicht viele die Notwendigkeit dafür gesehen haben.
https://en.wikipedia.org/wiki/Utah_Data_Center
Es gibt ein Video, in dem Professor Dan Boneh den Hintergrund erklärt: https://youtu.be/8WDOpzxpnTE?t=892
Wenn ich das richtig verstehe, hat die Community verdächtige Strings unbekannter Herkunft akzeptiert, obwohl es sehr einfach gewesen wäre, durch Einspeisen anderer bekannter Inputs in den Hash daraus Strings mit klarer Herkunft zu machen?
Leider ist das meines Wissens der einzige Fall, in dem im Zusammenhang mit NSA und Kryptostandards Inkompetenz ins Spiel gebracht wird; normalerweise gehen die Geschichten in die entgegengesetzte Richtung.
Noch problematischer ist, dass NIST bereits früher eine Backdoor in einen Standard im Umfeld elliptischer Kurven eingebaut hatte und dass sofort darauf hingewiesen wurde, dass dieser Mechanismus kein Vertrauen schafft – trotzdem unternahmen weder NIST noch NSA etwas. Genau wie bei Dual_EC_DRBG.
Noch problematischer ist, dass die NSA 2015 ausdrücklich sagte, man solle nicht von den NIST-Kurven auf andere spätere Kurven upgraden. Begründet wurde das damit, dass Quantencomputer bald gut genug sein würden, um ECC insgesamt zu brechen, und daher alle auf Post-Quantum-Kryptografie umsteigen müssten.
Wenn ECC gut funktioniert, Quantencomputer noch weit entfernt sind und man die Leute möglichst lange an die NIST-Kurven binden möchte, wäre genau das die Aussage gewesen.
Die Kryptografie-Community kommt in dieser Situation nicht besonders ehrenhaft weg. Fast 25 Jahre sind vergangen, und es gibt neuere Kurven ohne dieses Problem – warum werden die NIST-Kurven immer noch verwendet? Wo sind die Bemühungen, sie wie SHA1 schrittweise aus dem Verkehr zu ziehen? Dieser Text wirkt eher so, als würde er diese Kurven bewerben.
Wenn ihr euch glücklich fühlt, könnt ihr hier versuchen, den SHA1-Hash zu erraten: https://wending.dev/hash_guessing/
Wenn der Seed-Generator der NSA auch nur ein bisschen Ahnung von Kryptografie und Computern gehabt hätte, hätte er sicher nicht 500 verschiedene Phrasen von Hand eingegeben, bis eine gute Kurve herauskam.
Selbst wenn doch, sind die möglichen Varianten endlos: einen Punkt ans Ende setzen, Groß-/Kleinschreibung ändern, in Title Case schreiben usw.
Eine Liste plausibler Varianten, die man ausprobieren müsste, wird sich kaum je vollständig machen lassen. Aber wenn man wie auf dieser Seite nur SHA1-Hashes erzeugt, ist es praktisch unmöglich, den tatsächlichen Hash zu finden, selbst wenn man die Zeichenkette inklusive Zeichensetzung und Groß-/Kleinschreibung richtig errät.
Zumindest müsste man prüfen können, ob der Ergebnis-Hash ein inkrementierter Wert ist, etwa indem man verifiziert, ob die vorderen oder hinteren 10 Byte passen. Trotzdem würde das die meisten nur Zeit verschwenden lassen, und der Autor weiß vermutlich auch, dass das nirgendwohin führt.
Auf der Seite sollte stehen, dass es nur ein Demo-Spielzeug ist und dass man damit selbst bei korrektem Raten nicht den tatsächlichen Seed findet.
Was ich nach langem Zuschauen bei den hitzigen Debatten der Kryptografen gelernt habe, war: „Setz nicht auf Bernstein, und vertraue NIST nicht.“
Das muss ich jetzt wohl ändern in: „Setz weder auf Bernstein noch auf Filippo, und vertraue NIST nicht. Wenn diese beiden Regeln kollidieren, vertraue trotzdem NIST nicht.“
Es stimmt, dass SHA-1 gebrochen ist, aber ich dachte, dabei gehe es vor allem um Probleme wie Kollisionen über Length-Extension-Angriffe oder Known-Plaintext-Angriffe.
Wenn nur der Hash gegeben ist, hielt ich es weiterhin für praktisch schwierig, die Passphrase zu finden.
Wenn die Hypothese zur Seed-Struktur stimmt, ist Preimage-Resistenz hier aber nicht so wichtig. SHA-1 ist sehr schnell und leicht zu parallelisieren, daher besteht eine recht gute Chance, dass jemand, der den Variantenraum von
"Jerry needs a raise"hartnäckig durchsucht, die ursprüngliche Eingabe findet.Mit SHA1 selbst hat das wenig zu tun.