- Im Kern steht die Kritik, dass NIST bei der Standardisierung von Kyber-512 als Post-Quanten-Kryptografie-Standard die Angriffskosten falsch berechnet und dadurch das Sicherheitsniveau künstlich aufgebläht habe
- Streitpunkt ist, dass die Rechenkosten und die Kosten für Speicherzugriffe pro Iteration addiert werden müssten, NIST sie jedoch so behandelt habe, als würden sie multipliziert, und damit Matzovs Schätzung von 2^137 um „40 zusätzliche Sicherheitsbits“ erhöht habe
- Kyber-512 wurde auf Basis von Core-SVP mit einem Niveau von 2^118 angegeben, und NIST versuchte, dies an AES-128 mit etwa 2^143 Bit-Operationen anzugleichen, wird jedoch dafür kritisiert, Zahlen mit unpassenden Einheiten und Bedeutungen kombiniert zu haben
- Während Kyber nur begrenzte Parameterauswahlen wie Kyber-512, Kyber-768 und Kyber-1024 bietet, werden NTRU und NTRU Prime als Systeme mit feineren Auswahlmöglichkeiten bei Größe und Sicherheitsniveau gegenübergestellt
- Die Standardisierung von Kyber-512 sei mit Unsicherheiten in der Angriffsanalyse, nicht quantifizierten Modellen für Speicherkosten und mangelnder öffentlicher Prüfung behaftet; der Autor fordert daher die Entfernung von Kyber-512 und die Offenlegung von NISTs Rechenfehler
Der Kern des Rechenfehlers
- Ausgangspunkt ist das einfache Beispiel: „2^40 + 2^40 ist nicht 2^80, sondern 2^41“
- Wenn man Zahlen verwechselt, die multipliziert werden müssen, mit Zahlen, die addiert werden müssen, kann das Sicherheitsniveau massiv aufgebläht werden
- Die problematische Struktur in der Debatte um das Sicherheitsniveau von Kyber-512 ist wie folgt
- Ein Angriff besteht aus vielen Iterationen
- Jede Iteration hat Rechenkosten und Kosten für Speicherzugriffe
- Die Gesamtkosten müssen als
Anzahl der Iterationen × Kosten pro Iterationberechnet werden - Innerhalb der Kosten pro Iteration müssen Rechenkosten und Kosten für Speicherzugriffe addiert werden
- Die zentrale Kritik ist, dass NIST Rechenkosten und Kosten für Speicherzugriffe nicht addiert, sondern effektiv multipliziert habe
- Beispielhaft müssen 2^25 Bit-Operationen/Iteration und 2^35 Bit-Operationen/Iteration addiert werden
- Würde man sie multiplizieren, entstünde die Einheit
bitops^2/iter^2, was keine Einheit für Angriffskosten ist - Eine solche Multiplikation kann die Angriffskosten um ein Vielfaches von Millionen oder mehr aufblähen
Hintergrund zu NISTPQC und Kyber-512
- NIST kündigte 2022 den Plan zur Standardisierung von Kyber-512 an und veröffentlichte 2023 einen Standardentwurf für Kyber-512
- Im Mittelpunkt der Kritik steht, dass NIST bei der Begründung des Sicherheitsniveaus von Kyber-512 einen gravierenden Rechenfehler gemacht habe
- Im März 2022 wurde ein FOIA-Antrag zu NSA, NIST, and post-quantum cryptography gestellt, und später wurden durch Klagen einige interne NIST-Dokumente veröffentlicht
- Aus dem Vergleich veröffentlichter und unveröffentlichter Dokumente wird geschlossen, dass die Beteiligung der NSA am NISTPQC-Prozess größer gewesen sei als von NIST öffentlich dargestellt
- Für 2016 wird angeführt, dass auf der Teamliste von
pqc@nist.govmehr Personen von der NSA als von NIST gestanden hätten - NIST hatte 2020 in öffentlichen Unterlagen erklärt, dass Feedback der NSA Entscheidungen nicht beeinflusse und nur NIST auf Basis öffentlicher Informationen entscheide
- Im Januar 2023 wurde ein weiterer FOIA-Antrag zu den Behauptungen über das Sicherheitsniveau von Kyber-512 gestellt; NIST habe die Antwort erneut verzögert, was zu einer weiteren Klage geführt habe
Kybers eingeschränkte Parameterauswahl
- Es wird kritisiert, dass sich das Sicherheitsniveau bei Kyber im Gegensatz zu RSA, ECC, McEliece oder NTRU nicht schrittweise auf beliebige Größen anheben lasse
- Ein Kyber-576 gibt es nicht; die nächststärkere Option nach Kyber-512 ist Kyber-768, was eine Erhöhung der Dimension um 50 % erfordert
- Die nächststärkere Option nach Kyber-768 ist Kyber-1024
- Über Kyber-1024 hinaus gibt es keine weitere Option
- Die offiziellen Kyber-Dokumente stellten als Vorteil heraus, dass alle Parametersätze mit einer „dimension-256 NTT“ verarbeitet werden können, doch in dieser Struktur erfordern Dimensionen, die keine Vielfachen von 256 sind, wesentliche Designänderungen
- In Anwendungen mit einer 1-KB-Beschränkung ist Kyber-768 schwer einsetzbar, sodass Kyber-512 zur stärksten praktikablen Kyber-Option wird
- Kyber-768 verwendet einen 1184-Byte-öffentlichen Schlüssel und einen 1088-Byte-Ciphertext
- Kyber-512 verwendet einen 800-Byte-Schlüssel und einen 768-Byte-Ciphertext
- Unter derselben 1-KB-Beschränkung werden NTRU-Systeme als Varianten mit höheren Core-SVP-Schätzungen gegenübergestellt
sntrup653: 994-Byte-Schlüssel, 897-Byte-Ciphertext, Core-SVP 2^129- NTRU-677 (
ntruhps2048677): 931-Byte-Schlüssel, 931-Byte-Ciphertext, Core-SVP 2^145 - Die Round-3-Version von Kyber-512 wurde mit Core-SVP 2^118 angegeben
- Core-SVP ist der Mechanismus, den das Kyber-Team in den Einreichungen der Round 1 und Round 2 zur Schätzung des Sicherheitsniveaus verwendete; auch NISTs Round-2-Bericht von 2020 nutzte Core-SVP für Vergleiche
NIST-Bewertungskriterien und Vergleich mit NTRU
- NISTs offizieller Call for Proposals von 2016 enthielt Flexibilität als Bewertungskriterium
- Unter der Voraussetzung „guter Gesamtsicherheit und Leistung“ wurde angenommen, dass flexiblere Verfahren mehr Nutzeranforderungen erfüllen
- Es wurde ausdrücklich erwähnt, dass auch innerhalb derselben Kategorie mehrere Parametersätze angeboten werden können, um Leistung oder Sicherheitsreserve anzupassen
- Als NIST 2020 NewHope ausschied, nannte es unter anderem als Grund, dass Kyber auf natürliche Weise einen Parametersatz für Kategorie 3 unterstütze
- Falls Kyber-512 das minimale Sicherheitsniveau nicht erfüllt, bleiben bei Kyber nur Kyber-768 und Kyber-1024 übrig, wodurch das Problem geringerer Flexibilität gegenüber NTRU größer wird
- NISTs Selection Report von 2022 erklärte, man habe Vertrauen in die Sicherheit sowohl von Kyber als auch von NTRU, und bewertete auch die Leistung von KEMs insgesamt als für allgemeine Anwendungen akzeptabel
- Unter diesen Bedingungen lautet das Argument: Fällt Kyber-512 weg, bietet NTRU kleinere Optionen, höhere Sicherheitsoptionen und feinere Abwägungen zwischen Größe und Sicherheitsniveau und ist damit Kyber überlegen
Vier Kritikpunkte daran, dass NIST den Wettbewerb verzerrt habe
-
1. Ignorieren der zusätzlichen Flexibilität von NTRU
- Laut dem Text zeigt die NTRU-Literatur seit Langem, dass mehrere Sicherheits- und Größenoptionen angeboten werden können
- NIST erklärte 2020, dass „zu viele parameter sets“ die Bewertung und Analyse erschwerten
- Obwohl Flexibilität in den offiziellen Kriterien positiv dargestellt wurde, sei später plötzlich die Kritik „too many“ aufgetaucht, ohne dass NIST dieses Kriterium klar erläutert habe
-
2. Übertreibung der Kosten der Schlüsselerzeugung
- In Benchmarks auf Basis von Golden Cove erreicht Kyber-512 25829 Zyklen für Encapsulation und 20847 Zyklen für Decapsulation
- Für NTRU-509 werden 15759 Zyklen für Encapsulation und 25134 Zyklen für Decapsulation genannt; die Gesamtsumme für die Verarbeitung von Ciphertexts liege damit 13 % unter Kyber-512
- Dagegen liegt die Schlüsselerzeugung bei NTRU-509 mit 112866 Zyklen über Kyber-512 mit 17777 Zyklen
- Es wird jedoch argumentiert, dass KEM-Schlüssel für viele Ciphertexts wiederverwendet werden können, dass Kosten für das Senden und Empfangen von Bytes weit wichtiger seien als Zyklen und dass sich die Schlüsselerzeugung bei NTRU mit dem Montgomery-Trick beschleunigen lasse
-
3. Verschleierung des höheren Sicherheitsniveaus von NTRU
- NIST begann im Round-2-Bericht von 2020, Parametersätze der Kategorie 5 stark zu empfehlen
- NTRU präsentierte NTRU-1229 und NTRU-HRSS-1373, jeweils mit Core-SVP 2^301 bzw. 2^310 und damit höher als Kyber-1024 mit 2^254
- Auch NTRU Prime bot mit
sntrup1277,ntrulpr1277usw. Optionen mit Core-SVP 2^270 bzw. 2^271 - Kritisiert wird, dass NIST-Grafiken diese hochsicheren NTRU-Optionen nicht ausreichend sichtbar gemacht hätten
-
4. Ausschluss von NTRU-509 als leistungsstärkster Option
- Es wird beanstandet, dass NIST NTRU-509 aus großen Diagrammen und später aus Abbildungen und Tabellen im Selection Report ausgeschlossen habe
- NTRU-509 bietet kleinere Schlüssel und Ciphertexts als Kyber-512, was laut Text nicht zu NISTs Aussage passe, NTRU habe „somewhat larger“ öffentliche Schlüssel und Ciphertexts als Kyber
- Um NTRU-509 auszuschließen, müsse man behaupten, es erreiche das minimale Sicherheitsniveau von AES-128 nicht; Kyber-512 nach demselben Maßstab zu behalten, sei jedoch eine äußerst schwache Unterscheidung
Unsicherheit jenseits von Core-SVP
- Für Kyber-512 wird Core-SVP mit 2^118 angegeben, während die Angriffskosten auf AES-128 mit etwas mehr als 2^140 Bit-Operationen veranschlagt werden
- Die Kyber-Einreichungen von 2017 und 2019 behaupteten, mindestens 30 Bit sicherer als Core-SVP zu sein, doch ein Teil der Begründung wird als falsch oder unzureichend kritisiert
- Rounding Noise gelte nicht für Schlüsselangriffe und sei daher keine Grundlage für einen Sicherheitsgewinn
- Die Behauptung subexponentiell wachsender Kosten beim Sieving sei unbegründet; tatsächlich könnten die Asymptotiken schneller als Core-SVP sein
- Die Anzahl der SVP-Oracle-Aufrufe und die Gate Count mögen teilweise plausibel sein, reichten aber offenbar nicht aus, um Kyber-512 zu retten
- Kosten für Speicherzugriffe könnten für reale Angriffskosten wichtig sein, doch da NIST offiziell 2^143 „classical gates“ verlangte, lasse sich dies nicht direkt als Rettungsargument für Kyber-512 verwenden
- Die Round-3-Einreichung von Kyber änderte Kyber-512 und veränderte auch die Definition von Core-SVP, um statt 2^112 nun 2^118 zu erhalten
- Diese Einreichung gab die Sicherheit von Kyber-512 mit 151 Bits ±16 an und argumentierte, selbst ein Abfall auf 135 sei wegen des Speicherbedarfs nicht „catastrophic“
- Später machten mehrere Analysen von Gitterangriffen, darunter Matzov, die Schätzung des Sicherheitsniveaus von Kyber-512 noch komplexer und instabiler
NISTs Rettungslogik für Kyber-512
- NISTs offizieller Call erklärt, dass jede Sicherheitskategorie primitive Referenzwerte wie AES-128 in verschiedenen potenziell relevanten Metriken als Untergrenze verwendet
- Das heißt, jeder Angriff muss nach allen Metriken, die NIST als potenziell relevant für praktische Sicherheit ansieht, mindestens Ressourcen auf dem Referenzniveau erfordern
- NIST wich lange der Bitte aus, „classical gates“ klar zu definieren, und erläuterte erst im Selection Report von 2022, dass ein Ein-Bit-Speicherlesen oder -schreiben als Gate mit Kosten 1 zugelassen wurde
- Es wird kritisiert, dass NIST beim Ausschluss von NTRU-509 ein „non-local cost model“ verwendet habe, also ein Modell, das Kosten für Speicherzugriffe faktisch als kostenlos behandelt
- Umgekehrt sei bei der Einstufung von Kyber-512 in Kategorie 1 argumentiert worden, dass unter Berücksichtigung „realistic memory access costs“ die Anforderungen von Kategorie 1 erfüllt seien
- Das führe dazu, dass auf NTRU-509 eine Free-Memory-Metrik angewandt worden sei, auf Kyber-512 dagegen eine speicherkostenintensive Metrik
NISTBS: Widerlegung der Erklärung vom 7. Dezember 2022
- Am 7. Dezember 2022 erklärte NIST, warum Kyber-512 aus seiner Sicht NIST Category I erfülle; der Text bezeichnet dies als „NISTBS“
- NISTBS beginnt mit der Annahme, dass der Matzov-Bericht die Angriffskosten auf Kyber-512 auf 2^137 Bit-Operationen schätze
- Die Kosten eines klassischen Angriffs auf AES-128 werden mit etwa 2^143 Bit-Operationen angesetzt
- Es fehlen also 6 Bit
- NISTBS erklärt weiter, dass Gitter-Sieving-Angriffe unstrukturierte Zugriffe auf großen Speicher erfordern und das RAM-Modell diese Kosten ignoriere
- Anschließend wird unter Bezug auf Bewertungen in den Einreichungen von NTRU und NTRU Prime berechnet, dass bei Sieving-Angriffen der Kategorie 1 unter Berücksichtigung von Speicherzugriffskosten der Wert um „20–40 bits“ höher liegen könne als im RAM-Modell
- Das Problem sei, dass NIST Matzovs 2^137 offenbar um die 40 Bit aus NTRU Prime erhöht und damit als Niveau von 2^177 interpretiert habe
- Die 40 Bit aus NTRU Prime scheinen aus der Differenz zwischen „real“ 2^169 und „free“ 2^129 bei
sntrup653abgeleitet zu sein - 2^129 sei jedoch Core-SVP, also ungefähr die Anzahl der Iterationen, und nicht die von NIST gemeinte Gate Count im RAM-Modell
- Kosten für Speicherzugriffe müssen zu den Kosten pro Iteration addiert werden; sie können nicht mit bereits in Bit-Operationen erfassten Gesamtrechenkosten multipliziert oder als Exponent hinzuaddiert werden
- Die 40 Bit aus NTRU Prime scheinen aus der Differenz zwischen „real“ 2^169 und „free“ 2^129 bei
Die Bedeutung der tatsächlichen Zahlen
- Das NTRU-Prime-Dokument meldet für
sntrup653einen Core-SVP-Wert von 2^129- Das ist eine grobe Schätzung der Anzahl der Iterationen
- Dasselbe Dokument schätzt die gesamten Kosten der Speicherzugriffe auf ein Äquivalent von 2^169 Bit-Operationen
- Für Kyber-512 wird Core-SVP mit 2^118 angegeben
- Mit derselben Methode werden die Kosten der Speicherzugriffe grob auf ein Äquivalent von 2^154 Bit-Operationen geschätzt
- Die Schätzung von 2^151 „gates“ im Kyber-Dokument ist keine Schätzung der Speicherzugriffskosten
- Sie schätzt die Zahl der Bit-Operationen innerhalb der Angriffsberechnung
- Unter Berücksichtigung von „known unknowns“ wird ein Bereich von 2^135 bis 2^167 angegeben
- Deshalb sind die Schätzung der Rechenkosten von 2^151 und die Schätzung der Speicherzugriffskosten keine Faktoren, die miteinander multipliziert werden dürfen, sondern Terme, die auf Ebene der Kosten pro Iteration addiert werden müssen
Warum der Fehler als leicht erkennbar gilt
- Eine einfache Plausibilitätsprüfung sieht so aus
- Das Kyber-Dokument schätzt die Rechenkosten eines Angriffs auf Kyber-512 auf 2^135 bis 2^167 Bit-Operationen
- NTRU Prime schätzt die Kosten der Speicherzugriffe für
sntrup653, das schwerer als Kyber-512 aussieht, auf ein Äquivalent von 2^169 Bit-Operationen - Wenn sich der Angriff um 2^14 verbessert hat, wirkt es seltsam, dass NIST die Angriffskosten für Kyber-512 mit 2^177 berechnet
- NISTBS schrieb, das NTRU-Prime-Dokument schätze „40 bits additional security over the RAM model“, doch in Abschnitt 6.11 dieses Dokuments stünden weder „40“ noch „RAM model“ ausdrücklich
- Für eine klare Überprüfung hätte NIST laut Kritik offenlegen müssen, woher die 40 genau stammen und auf welchen Wert welcher Metrik sie sich beziehen
- Nach Dezember 2022 wurde zu dem konkreten Szenario X die Rückfrage gestellt, ob wirklich „137+40=177“ gerechnet worden sei; NIST habe darauf nicht geantwortet
- Später habe NIST lediglich erklärt, die betreffende E-Mail „speaks for itself“, ohne die konkrete Interpretation der Rechnung zu bestätigen oder eine alternative Deutung vorzulegen
Forschung, die für eine korrekte Berechnung nötig ist
- Eine korrekte Berechnung muss zwei Effekte unterscheiden
- Ein Teil der Erhöhung gegenüber Core-SVP stammt aus den Kosten der Bit-Operationen innerhalb einer Iteration
- Ein anderer Teil stammt aus einer größeren Anzahl von Iterationen in der äußeren Schleife
- Ein Effekt, der die Iterationszahl erhöht, kann mit den Kosten der Speicherzugriffe multipliziert werden
- Dagegen müssen die internen Rechenkosten pro Iteration und die internen Speicherzugriffskosten pro Iteration addiert werden; genau deren Multiplikation ist der zentrale Fehler
- Für eine präzise Berechnung müsste der gesamte Stack aktueller Gitterangriffe über Hunderte Seiten Fachliteratur hinweg unter Einbeziehung der Speicherzugriffskosten neu optimiert werden
- Beispielsweise müsste innerhalb von BKZ neu bewertet werden, ob Low-Memory-Enumeration oder High-Memory-Sieving vorteilhafter ist, wenn Kosten für Speicherzugriffe eingerechnet werden
Standardentwurf und Verantwortungsfrage
- Im August 2023 veröffentlichte NIST den Entwurf des Kyber-Standards ML-KEM
- ML-KEM-512 ist Sicherheitskategorie 1
- ML-KEM-768 ist Kategorie 3
- Für ML-KEM-1024 steht, dass Kategorie 5 „claimed“ wird
- Das Problem sei, dass unklar bleibt, wer das „claimed“ beansprucht
- Es sei nicht klar, ob NIST dies behaupte, die Designer oder jemand anderes
- Appendix A des Entwurfs wiederholt das Kriterium, dass die Kategorien AES-128, AES-192 und AES-256 in allen potenziell relevanten Metriken übertreffen müssen
- Die neueste Analyse in den Kyber-Dokumenten legt nahe, dass die Angriffskosten auf Kyber-512 bis auf 2^135 „classical gates“ sinken könnten, was unter NISTs Schätzung von 2^143 Gates für AES-128 liegt
- Deshalb sei eine öffentliche Analyse nötig, wie NIST die Behauptung rechtfertigt, Kyber-512 liege in allen relevanten Metriken mindestens auf dem Niveau von AES-128
Fazit und Vorschlag
- Da die Angriffsoberfläche von Gitterverfahren instabil und nicht hinreichend verstanden sei, komme der Text zu dem Schluss, dass die Standardisierung von Kyber-512 leichtfertig sei
- Es könne sein, dass Kyber-512 selbst unter Berücksichtigung bereits veröffentlichter Angriffe und der Kosten für Speicherzugriffe deutlich leichter zu brechen ist als AES-128; das Gegenteil sei ebenfalls möglich, und zur Klärung des tatsächlichen Zustands sei aufwendige Forschung nötig
- Auch AES-128 selbst könne bei Multi-Target-Angriffen auf etwa 2^88 Berechnungen sinken, wenn eines aus einer Billion Schlüsseln gebrochen werden soll; ein Verlust von 10 bis 30 Bit sei daher nicht vernachlässigbar
- Wenn Kyber-512 als Standardoption erhalten bleibt, ist laut Text wahrscheinlich, dass selbst Anwendungen, die Kyber-1024 oder NTRU-1229 verkraften könnten, aus Geschwindigkeitsgründen die schnellere Option wählen
- Die abschließende Empfehlung lautet, Kyber-512 zu entfernen und dass NIST den Fehler in der Berechnung des Sicherheitsniveaus von Kyber-512 sowie die intransparente Auswahl von Daten im Vergleich mit NTRU öffentlich anerkennt
1 Kommentare
Hacker-News-Kommentare
Was man vor dem Lesen dieses Beitrags unbedingt wissen sollte: Nicht NIST und NSA haben diesen Algorithmus entwickelt, sondern sie haben den Wettbewerb bewertet.
Der Großteil der Analyse wurde von den Wettbewerbern und der Wissenschaft durchgeführt, und zum Kyber-Team gehörten Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé sowie Peter Schwabe, ein Mitarbeiter von Bernstein.
Historisch wird oft nur der Gewinner übernommen. Man denke nur an den AES-Wettbewerb und daran, wie selten Serpent erwähnt wird, obwohl ihm ein größerer Sicherheitsspielraum als Rijndael zugeschrieben wird.
Es sieht nicht so aus, als würde NIST seine Empfehlungen auf irgendeine geheime Analyse stützen.
Die bedauerliche Realität ist: Bernstein könnte recht haben, aber es ist schwer zu unterscheiden, ob man die Antwort – oder ausbleibende Antwort – von NIST als Täuschung werten sollte oder ob man dort einfach nicht mit jemandem zu tun haben wollte, der mit sehr aggressivem Ton auftritt.
Auch bei NIST arbeiten normale Menschen, und es ist gut möglich, dass sie scharfe Forderungen nach Erklärungen ähnlich aufgenommen haben, wie die meisten von uns aggressive Bug-Reports aufnehmen.
Überzogene Vorwürfe wie „Man hat ab 2024 empfohlen, Kyber zu verwenden, wenn die Patentlizenz aktiv wird, und damit drei Jahre an Nutzerdaten Angreifern ausgesetzt, statt seit 2021 NTRU zu empfehlen“ helfen nicht. Es wird wohl ohnehin noch eine Weile kaum jemand eigenständige Post-Quantum-Kryptografie sofort ausrollen, und 2021 hätte NIST mehrere Alternativen vorschlagen können. SIKE sah ziemlich gut aus, bis es letztes Jahr gebrochen wurde.
NIST hat in diesem Bereich keinen makellosen Ruf, aber wenn man Algorithmen und Verfahren kritisieren will, wären eine knappe Zusammenfassung des Warum und ein oder zwei entscheidende Belege wünschenswert. Zahlreiche E-Mail-Analysen, der Vergleich nur mit einer einzigen Einreichung und Vorwürfe, alle würden auf Zeit spielen, um Daten abzugreifen, machen es schwer, die Sache ernst zu nehmen. Wenn Kyber-512 tatsächlich so gefährlich ist, sollte das klarer vermittelt werden.
Dass die Seite 17.000 Wörter umfasst, ist ebenfalls ein großer Punkt. Selbst nach Harry-Potter-Maßstäben bräuchte ein durchschnittlicher Leser dafür 70 Minuten, und dieser Text ist kein Roman, sondern voll mit Zahlen, Abwägungen und Sätzen wie NIST-Zitaten, bei denen man jedes Wort genau prüfen muss. Selbst wenn man genug Hintergrund hat, um Post-Quantum-Kryptografie zu verstehen, lässt sich das nicht so schnell lesen wie ein normales Buch.
Am Anfang klickte ich auf „That lawsuit has been gradually secret NIST documents, shedding some light on what was actually going on behind the scenes“ und wurde in einen anderen Text hineingezogen; die verlinkte Seite hatte wiederum 54.000 Wörter. Auf dem Handy gab es keine Scrollbar, sodass ich den Umfang nicht sah und linear weiterlas, bis ich irgendwann das Gefühl hatte, mich für ein Promotionsforschungsprojekt eingeschrieben zu haben. Dann schloss ich den Tab und kehrte zum ursprünglichen Text zurück.
HN-Leser sind oft klug und technisch versiert, kommen aber aus unterschiedlichen Bereichen, sodass es schwierig ist, fachjargonlastige Belege, die „NIST=böse“ stützen sollen, vernünftig zu bewerten. Ich bin in einem angrenzenden Feld und denke, dass ich mehr verstehe als der durchschnittliche Leser, aber ohne gründliche Lektüre fühle ich mich nicht urteilsberechtigt. Der Text erklärt zwar Kontext und Abkürzungen, aber es ist so viel, dass ich nicht weiß, ob jemand, der es nicht schon kennt, ihn überhaupt lesen möchte. Nicht jede Einreichung muss für alle verständlich sein, aber weil hier Anschuldigungen erhoben werden, frage ich mich, ob das für HN der passende Beitrag ist.
Deshalb nehme ich manches, was ich unten gesagt habe, vielleicht etwas zurück, oder zumindest kann ich den aggressiven Ton besser nachvollziehen, wenn man die Vorgeschichte von djb mit NIST-Empfehlungen bedenkt. Relevante Informationen gibt es unter https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptograp....
Ich mag es nicht, Form über Inhalt zu stellen, aber in diesem Fall war die Form des Blogposts so schlecht, dass es schwer war zu beurteilen, ob der Inhalt wertvoll ist. Da ich kein Kryptograf bin, kann ich die Sache inhaltlich nicht bewerten, aber die unnötige Häme und Herabsetzung machten die Botschaft sehr verdächtig. Selbst wenn gute Punkte getroffen werden, ähnelt der Gesamttenor einem YouTube-Video der Art „WhaT ThE ElITe DoN'T WanT YoU TO KnoW!!“, und selbst wenn er recht hat, klingt der Autor ziemlich unangenehm.
Ich frage mich auch, ob das tatsächlich jemand bis zum Ende gelesen hat. Vielleicht stimmt es, dass das Internet unsere Aufmerksamkeitsspanne zerstört hat; andererseits gibt es heute so viele Informationen, dass man sehr streng auswählt, wofür man Zeit aufwendet. Bei einem Blogpost sollten relevante Details und eine Zusammenfassung in die ersten paar Absätze, und das lange mäandernde Tagebuch nach hinten. Wenn die wichtigen Teile wie bei Where's Waldo in einem ausschweifenden Protokoll versteckt sind, kann man kaum erwarten, dass Leute es vollständig lesen.
Der Kern seiner wiederholten Fragen ist, warum die Bewertungskriterien nachträglich immer wieder geändert wurden, warum die Ergebnisse irreführend dargestellt wurden und warum grundlegende Rechenfehler gemacht wurden. Diese Leute sind Experten, und all diese Dinge wirkten zugunsten eines einzigen Algorithmus.
Für mich sieht das nach einem Signal aus, dass man diesen Algorithmus zum Standard machen wollte. Nimmt man hinzu, dass die Beteiligung der NSA offenbar viel größer war als bekannt und man dies zu verbergen versuchte, macht mich das gegenüber diesem Standard extrem misstrauisch.
Das ist ein Problem, weil diese Algorithmen bald in Hardware eingebaut werden sollen.
Sobald die zu standardisierende Implementierung feststeht, dürften Hardwarehersteller beginnen, Blöcke zu entwerfen, die den FIPS-203-Standard effizienter berechnen. Vielleicht haben sie bereits einige entworfen.
Angesichts der erwarteten Veröffentlichung des Standards im Jahr 2024 und der Tatsache, dass die NIST-CMVP-Prüfung von FIPS-Modulen ein bis zwei Jahre dauert, wäre es nicht überraschend, wenn etwa Mitte 2026 FIPS-140-3-Hardwaremodule mit ML-KEM (Kyber usw.) erscheinen.
Der Kern scheint der Satz aus [1] zu sein: „NIST hat jedoch keine klare End-to-End-Aussage gemacht, dass Kyber-512 für ein klar spezifiziertes (N,X) im Szenario X eine Sicherheitsmarge von N Bit hat.“
djb hat in [2] sein „Szenario X“ knapp zusammengefasst und sagt, dass nur eine Ja/Nein-Antwort nötig sei. Er fragt tatsächlich die Leute, die dieses Problem kennen müssen und den technischen Hintergrund haben, um es zu diskutieren. Weil er keine Antwort bekommen hat, hat er [1] veröffentlicht.
Die NIST-Antwort in [3] weist [1] zurück, ohne die Sicherheit selbst zu diskutieren. Besonders der zweite Absatz war frustrierend. „Die zitierte E-Mail (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...) spricht für sich. NIST ist weiterhin an den Meinungen der Leute dazu interessiert, ob der aktuelle Plan zur Standardisierung von Kyber512 gut ist. Reviewer können gern versuchen, zum Spaß das zu widerlegen, was NIST offenbar über Sicherheitsmargen behauptet, aber das Ergebnis wird für den Standardisierungsprozess nicht besonders nützlich sein. Frühere Aussagen von NIST und deren Interpretation sind dafür, ob Menschen glauben, dass die Standardisierung von Kyber512 eine gute Idee ist, nicht relevant.“
Wenn NIST sicherheitsbezogene Argumente von Reviewern als „für den Standardisierungsprozess nicht besonders nützlich“ ansieht, warum sollte die Öffentlichkeit diesem Standard dann vertrauen, wenn man bedenkt, dass diese Reviewer Kryptografen sind?
Entscheidende Beweise kann es zwangsläufig nicht geben. Denn der aktuelle Streitpunkt ist gerade das Fehlen einer klaren Erklärung. Wenn man erklären könnte, wie die Sicherheitsstärke von Kyber-512 berechnet wurde, wäre es eine andere Sache.
Nach derzeitigen Schätzungen Dritter liegt der etwas vage Wert der Sicherheitsstärke von Kyber-512 unter den ursprünglichen Anforderungen, daher scheint eine Erklärung oder Rechtfertigung nötig.
[1]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[2]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[3]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
Wenn dieser Beitrag von einer unbekannten Person stammte, hätte ich vielleicht zugestimmt, aber die Autoren sind DJB oder Tanja Lange, und beide sind keineswegs unbekannt.
Solche Dinge sind bis zu einem gewissen Grad zwangsläufig antagonistisch. Bei der Kryptoanalyse ist eine solche Haltung teils notwendig, und zudem gab es in der Vergangenheit mehrere verdächtige Vorgänge. Das ist Teil des Fachgebiets und der Politik und lässt sich kaum vermeiden.
Das ist weniger ein Artikel als vielmehr ein Tagebuch. Viele Fachbegriffe, unstrukturiert, es dreht sich ständig um dieselben Punkte, und es ist sehr schwer, ihm zu folgen
Trotzdem könnten die Informationen an sich wichtig sein. Es gibt eine starke Andeutung, dass NIST mit Hilfe der NSA absichtlich einen schwachen Algorithmus standardisiert hat
Dass so etwas möglich ist, wissen wir alle
Allerdings: Wenn jemand das Feld genauer verfolgt, würde ich mir wünschen, dass er erklärt, worin hier der Vorteil besteht. Ich habe es immer für eine riskante Wette gehalten, Public-Key-Kryptografie auf diese Weise zu schwächen, weil man nicht garantieren kann, dass ein Angreifer dieselbe Erkenntnis nicht unabhängig entdeckt. Einen geheimen Backdoor-Schlüssel kann man verstecken. So lautete der Verdacht bei Dual_EC_DRBG. Mathematische Ergebnisse hingegen sind wirklich schwer zu verbergen
Warum sollte man hier dieses Risiko eingehen wollen?
Ich weiß inzwischen nicht einmal mehr, warum diese Diskussion nötig ist. Wir brauchen sie nicht mehr. Exportbeschränkungen sind ebenfalls verschwunden
Was wir brauchen, ist ein Konsortium, das die Aufmerksamkeit der Hardwarehersteller gewinnt und NIST und NSA auf den Status bloßer Teilnehmer beschränkt. Dann würden, selbst wenn die Regierung einen Standard mit Backdoor übernimmt, nur sie selbst ihn verwenden
Warum sollte sie das interessieren?
Die aktuelle Vermutung dazu, was bei den NIST-Elliptic-Curves passiert sein könnte, geht in diese Richtung
Dann könnte es sehr lange faktisch eine nur den USA vorbehaltene Backdoor bleiben
Die Überlegung war, dass sie bei Angriffen einen Vorsprung behalten könnten und DES etwa zu dem Zeitpunkt durch etwas anderes ersetzt würde, wenn 56-Bit-Schlüssel allgemein zu schwach würden. War das riskant? Ja. Aber in gewissem Sinne war es „erfolgreich“. Deshalb würde ich nicht annehmen, dass so etwas nie wieder passiert
Die Theorie dahinter heißt Kleptografie (kleptography). Das bedeutet auch, dass die NSA wahnhaft genug ist zu glauben, sie könne Informationen „sicher“ stehlen
Letztes Jahr gab es einen verwandten Thread mit 443 Kommentaren
https://news.ycombinator.com/item?id=32360533 ("NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)")
„Herausfinden, wie NISTPQC im Verborgenen funktioniert. Im März 2022 habe ich einen FOIA-Antrag mit dem Titel ‘NSA, NIST, and post-quantum cryptography’ gestellt. NIST hat rechtswidrig auf Zeit gespielt. Die Bürgerrechtskanzlei Loevy & Loevy hat in meinem Namen Klage eingereicht“
Persönlich mag ich djb im Großen und Ganzen nicht, aber beruflich hat er die Bundesregierung vor Gericht konsequent unter Druck gesetzt, daher unterstütze ich ihn immer. Ich freue mich sehr zu sehen, dass er immer noch weitermacht
Unabhängig davon, dass DJB eine wichtige Figur in der Kryptografie ist und ich viele Details hier nicht kenne, gab es eine Stelle, an der seine Glaubwürdigkeit stark gelitten hat
Insbesondere sagt er im Abschnitt zu den Diagrammen: „NIST entschied sich dafür, in den Bandbreitendiagrammen dünnere rote Balken zu verwenden, um sie weniger hervorzuheben“, aber das wird durch die Belege überhaupt nicht nachgewiesen. Es gibt eine viel plausiblere Erklärung. Das Diagramm mit den dünneren Balken ist ein Balkendiagramm mit mehr Datenpunkten als die anderen. Öffnet man irgendein Chart-Tool und vergleicht ein Diagramm mit 12 Datenpunkten mit einem mit 9 Datenpunkten, ist es selbstverständlich, dass die Balken bei den 12 dünner werden. An dieser Stelle hatte ich stark das Gefühl, dass er jede Handlung so böswillig wie möglich auslegen wollte
Im nächsten Punkt beschwert er sich darüber, dass keine logarithmische Achse verwendet wurde, obwohl die Werte in derselben Größenordnung liegen. Das klingt nicht nach einem guten Anwendungsfall für eine logarithmische Achse, und ich sehe nicht recht, warum sie hier gerechtfertigt wäre
Wenn man weiß, dass DJB an NTRU beteiligt war, ist es schwer, den Eindruck abzuschütteln, dass ein erheblicher Teil davon eine verbitterte Reaktion auf die Niederlage im Wettbewerb ist
Jede andere Annahme wirkt zumindest auf mich ziemlich naiv
Es gibt genügend Grund für Misstrauen
Dass Konkurrenten in diesem Bereich gegenseitig ihre Arbeit prüfen, ist selbstverständlich
Was ich daraus gelernt habe, beruflich die hitzigen Kämpfe unter Kryptografen zu verfolgen: Wette nicht gegen Bernstein, und vertraue NIST nicht
NIST hat geantwortet: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO...
Ich bin mir nicht sicher, ob noch Vertrauen in N(IST)SA übrig ist
Dass curve25519 weiter verbreitet ist als ihre P-Kurven, ist ermutigend, und ich hoffe, dass die Community diese Richtung beibehält und sie künftig weitgehend ignoriert
Die Regierung sollte das nicht anführen oder entscheiden. Bei FIPS, Regulierung usw. wäre es besser, wenn ihre Rolle vor allem darin bestünde, den aktuellen Konsens zu sammeln und ihm zu folgen