filippo.io/mlkem768: Quantenresistente Kryptografie für das Go-Ökosystem

 (words.filippo.io)
1 Punkte von GN⁺ 2024-02-02 | 1 Kommentare | Auf WhatsApp teilen
  • filippo.io/mlkem768 ist eine reine Go-Implementierung von ML-KEM-768, das sich im NIST-Standardisierungsprozess befindet, und ermöglicht es, quantenresistenten Schlüsselaustausch im Go-Ökosystem zu evaluieren
  • Das Paket besteht aus etwa 500 Zeilen Code, 200 Zeilen Kommentaren und 650 Zeilen Tests und hat außer golang.org/x/crypto/sha3 keine Abhängigkeiten, wodurch es sich leicht als internes Paket in die Go-Standardbibliothek übernehmen lässt
  • Statt die Referenzimplementierung von pq-crystals zu portieren, wurde es direkt anhand der FIPS-203-Spezifikation geschrieben, um zu prüfen, ob allein aus der Spezifikation eine interoperable Implementierung möglich ist
  • Die schwierigsten Bereiche sind Kompression/Dekompression und Constant-Time-Operationen; durch den Einsatz von Barrett-Reduktion vermeidet es das Risiko variabler Laufzeiten durch DIV-Instruktionen, das bei Referenzimplementierungen auftreten konnte
  • Performance-Optimierung war nicht das primäre Ziel, aber der Bob-Pfad ist vergleichbar mit Go-Implementierungen von X25519 und P-256, und auch der Alice-Pfad bleibt unter dem Doppelten, was in der Praxis ausreichend schnell ist

Reine Go-Implementierung von ML-KEM-768

  • filippo.io/mlkem768 ist eine reine Go-Implementierung von ML-KEM-768, bei der Korrektheit und Lesbarkeit Vorrang haben
  • ML-KEM war früher als Kyber bekannt und ist ein quantenresistenter Schlüsselaustauschmechanismus, der sich im NIST-Standardisierungsprozess befindet
  • Das Paket besteht aus rund 500 Zeilen Code, 200 Zeilen Kommentaren und 650 Zeilen Tests
  • Die einzige Abhängigkeit ist golang.org/x/crypto/sha3
  • Ziel ist das Upstreaming in die Go-Standardbibliothek; zunächst ist es als internes Paket für ein opt-in-crypto/tls-Experiment vorgesehen

Implementierungsansatz nach FIPS 203

  • Diese Implementierung wurde von Grund auf neu geschrieben, ohne die pq-crystals-Referenzbibliothek zu portieren oder andere Codebasen im Detail zu studieren
  • Das zentrale Ziel war zu prüfen, ob sich allein aus der Spezifikation eine interoperable Implementierung erstellen lässt
  • Das FIPS-203-Dokument bot dafür detaillierten Pseudocode, vollständige Definitionen und konsistente Typinformationen
  • Funktionsnamen, Variablennamen und die Reihenfolge der Operationen orientieren sich so eng wie möglich an der FIPS-Spezifikation, um Review und Lernen zu erleichtern
  • Der für die ML-KEM-Implementierung nötige mathematische Hintergrund wird separat in Enough Polynomials and Linear Algebra to Implement Kyber erläutert

Kompression/Dekompression und Constant-Time-Implementierung

  • Es blieben drei zentrale Implementierungsaufgaben
    • Implementierung modularer Arithmetik für die Primzahl 3329
    • Implementierung der Kompressions- und Dekompressionsfunktionen, die Werte aus [0, 3329) nach [0, 2ᵈ) abbilden und zurück
    • Gewährleistung von Constant-Time-Operationen
  • Die modulare Arithmetik war dank umfangreicher Erfahrung mit RSA- und Elliptic-Curve-Implementierungen vergleichsweise einfach, und die kleine Primzahl vereinfachte die Implementierung zusätzlich
  • Kompression und Dekompression waren der schwierigste Teil
    • Die Spezifikation definiert sie abstrakt über Brüche und Rundungsregeln
    • Die konkrete Implementierung muss sie mit Constant-Time-Arithmetik und Bitoperationen umsetzen
  • Viele Referenzimplementierungen und deren Portierungen verwendeten Divisionen, die je nach Compiler-Optimierung und Plattform zu DIV-Instruktionen mit variabler Laufzeit werden konnten
  • Dieses Paket nutzte von Anfang an Barrett-Reduktion und war daher nicht betroffen; BoringSSL verwendet denselben Ansatz

Warum nur ML-KEM-768

  • Die Implementierung beschränkt sich von den drei ML-KEM-Sicherheitsstufen -512, -768 und -1024 auf ML-KEM-768
  • Das Kyber-Team empfiehlt -768 statt -512, um konservativere Sicherheitsreserven gegenüber neuer Kryptanalyse zu haben
  • -1024 wird als Option für 256-Bit-Sicherheitsniveau genannt, also vor allem für Compliance und Strength Matching
  • Da sich die meisten experimentellen oder standardisierten Protokolle auf ML-KEM-768 konzentrieren, erhöht die Fokussierung auf eine einzelne Stufe die Kosten kaum
  • Diese Fokussierung reduziert die Komplexität und ist vorteilhaft für Lesbarkeit, Sicherheit und Performance
    • So werden 1-, 4-, 10- und 12-Bit-Ganzzahlserialisierung nicht mit einem generischen Encoder behandelt, sondern mit dedizierten Encodern und Decodern
    • Weil nur ML-KEM-768 unterstützt wird, mussten 5-Bit- und 11-Bit-Encoding nicht implementiert werden

Teststrategie und öffentliche Testvektoren

  • Tests sind nach der Lesbarkeit die zweitwichtigste Säule der Sicherheitsstrategie dieses Pakets
  • Die Basistests umfassen Roundtrips für Schlüsselgenerierung, Kapselung und Entkapselung sowie mehr als 95 % Testabdeckung
  • Weitere Tests decken unter anderem ab
    • Interoperabilität mit Testvektoren von NIST und anderen Implementierungen
    • Vergleich aller Eingabekombinationen für Addition, Subtraktion und Multiplikation modulo 3329 mit erwarteten Werten aus variabler Laufzeitberechnung
    • Vollständige Tests von Kompression und Dekompression gegen math/big.Rat
    • Verifikation, dass vorkalkulierte Konstanten mit ihren Definitionen übereinstimmen
    • Prüfung, dass alle Funktionen bei zu langen oder zu kurzen Eingaben die richtigen Fehler liefern
    • Ausführung von Testvektoren, die von Sophie Schmieg bereitgestellt wurden und künftig in Wycheproof aufgenommen werden sollen
  • Eigene Testvektoren werden als Teil des CCTV-Projekts veröffentlicht, damit auch andere Implementierungen sie wiederverwenden können
  • Die CCTV-Vektoren enthalten Zwischenwerte, mit denen sich einzelne Zwischenschritte und Teilalgorithmen testen und debuggen lassen

Welche Fehler spezielle Testvektoren finden

  • Negative test vectors liefern fehlerhafte Kapselungsschlüssel mit Koeffizienten größer als 3329
    • Die Vektoren von Kyber und dem NIST-Team konzentrieren sich auf gültige Eingaben, daher wurden solche Vektoren häufig nachgefragt
    • Alle Werte von 3329 bis 2¹²-1 und jede Koeffizientenposition werden einzeln getestet
    • Durch das Teilen der übrigen Koeffizienten werden 1–3 MiB Daten auf 12–28 KiB komprimiert
  • „Unlucky“ vectors testen Fälle, in denen ungewöhnlich viele XOF-Lesevorgänge nötig sind
    • Es handelt sich um öffentliche Schlüssel, bei denen SampleNTT mehr als 575 Byte aus dem SHAKE-128-XOF lesen muss; normalerweise tritt das nur mit Wahrscheinlichkeit 2⁻³⁸ auf
    • Sophies Vektoren wurden weiter bruteforced und benötigen im Maximum 591 Byte
  • strcmp vectors bringen Implementierungen zu Fall, die in ML-KEM.Decaps strcmp() verwenden
    • Beim Vergleich des Ciphertexts mit der Ausgabe von K-PKE.Encrypt während der Entkapselung kann ein Nullbyte strcmp() dazu bringen, den Vergleich vorzeitig zu beenden
  • Accumulated vectors stammen aus der pq-crystals-Referenzimplementierung
    • Statt 300 MB an zufälliger Vektorausgabe zu speichern, werden sie während des Tests mit einem deterministischen RNG reproduziert und dann gegen erwartete Hashes geprüft
    • So lassen sich nicht nur die 10k Tests der Referenzimplementierung, sondern auch Hashes aus 1 Million Zufallstests erzeugen
  • Auch in später hinzugefügten weiteren Tests wurden keine Probleme in filippo.io/mlkem768 gefunden, und es gibt mindestens einen dokumentierten Fall, in dem negative Vektoren Fehler in wichtigen Implementierungen aufgedeckt haben

Performance-Ergebnisse

  • Performance ist weder für dieses Paket noch für Go-Kryptopakete das primäre Ziel, aber sie muss ausreichend hoch für praktischen Nutzen sein
  • ML-KEM ist schnell genug, und selbst diese einfache Implementierung erreicht ein Niveau, das mit den assembleroptimierten Go-Implementierungen von P-256 und X25519 konkurrieren kann
  • Vergleiche sollten sich an der gesamten Arbeit orientieren, die beide Seiten beim Key Setup leisten müssen
    • ECDH führt zwei Skalarmultiplikationen aus, einschließlich einer mit festem Basispunkt
    • Ein KEM führt auf einer Seite Schlüsselgenerierung und Entkapselung aus, auf der anderen Kapselung
    • ECDH ist symmetrisch, ML-KEM-Key-Setup dagegen asymmetrisch
  • Im Benchmark führt „Alice“ Schlüsselgenerierung und Entkapselung aus, „Bob“ übernimmt die Kapselung
    • Die Entkapselung enthält eine vollständige Verschlüsselung, um zu prüfen, ob Eingabe-Ciphertext und Ergebnis zusammenpassen
    • Alice führt Verschlüsselung, Entschlüsselung und Schlüsselgenerierung aus und braucht daher länger als Bob
  • Im Ergebnis ist Bob so schnell wie X25519 oder P-256, und Alice bleibt unter dem Doppelten davon
  • Im Vergleich zu schnellen ML-KEM-Implementierungen wie BoringSSL und libcrux benötigt dieses Paket ungefähr doppelt so viel Zeit

Benchmark-Zahlen und Optimierungsspielraum

  • Die gemessenen Werte lauten
    • Auf macOS arm64 beträgt ECDH/P256-8 49.43µs und ECDH/X25519-8 77.46µs
    • In derselben Umgebung liegt RoundTrip/Alice-8 bei 109.4µs und RoundTrip/Bob-8 bei 56.19µs
    • Unter Linux amd64 beträgt ECDH/P256-4 78.88µs und ECDH/X25519-4 115.6µs
    • In derselben Umgebung liegt RoundTrip/Alice-4 bei 223.8µs und RoundTrip/Bob-4 bei 114.7µs
  • Die Implementierung folgt performancetauglichen Go-Mustern, etwa zur Reduzierung von Heap-Allokationen
  • x/crypto/sha3 wurde überarbeitet, damit es ohne Heap-Allokationen genutzt werden kann, aber auf Apple M2 zeigte sich ein negativer Effekt; daher wurde die Änderung noch nicht gemergt und ist auch nicht in den obigen Benchmarks enthalten
  • Weiteres Optimierungspotenzial ist klar erkennbar
    • Da Schlüsselgenerierung und Entkapselung dieselbe Matrix aus denselben Werten sampeln, ließen sich auf der Alice-Seite etwa 10 % Zeit sparen, wenn die Matrix bei unmittelbar aufeinanderfolgenden Operationen zwischengespeichert würde
    • Im sha3-Lesepfad könnte sich das Kopieren weiter reduzieren lassen
    • Danach wäre Optimierung der Feldimplementierung nötig

Unterstützung von Kyber v3 mit einer ML-KEM-Implementierung

  • NIST hat gegenüber dem Kyber-Round-3-Submission einige kleine Änderungen vorgenommen, die in Abschnitt 1.3 des FIPS-Entwurfs zusammengefasst sind
  • Es gibt einige experimentelle Protokolle auf Basis von Kyber v3 oder „draft00“, darunter auch wichtige ausgerollte PQ-TLS-Schlüsselaustausche
  • Kyber v3 lässt sich ohne separates Paket mit einer ML-KEM-Implementierung unterstützen
  • Eine der Änderungen fügt Validierung für den Sonderfall nichtkanonischer Koeffizientencodierung in öffentlichen Schlüsseln hinzu
    • Korrekte Implementierungen erzeugen solche Schlüssel nicht, daher können sie gemäß FIPS-Entwurf abgelehnt werden
    • Dieses Verhalten macht eine Kyber-on-ML-KEM-Implementierung erkennbar, ist darüber hinaus aber nicht schädlich
  • Eine weitere Änderung entfernt den zuvor auf CSPRNG-Eingaben angewandten Hashing-Schritt
    • Da die Eingabebytes zufällig sind, kann keine Partei den Unterschied erkennen
  • Die größte Änderung betrifft das Hashing des Ciphertexts in das Shared Secret
    • Dieser Unterschied kann die Interoperabilität verhindern
    • Erzeugt man mit ML-KEM zunächst das Shared Secret K und wendet dann SHAKE-256(K || SHA3-256(c))[:32] an, erhält man das Kyber-Shared-Secret
    • Dafür muss die ML-KEM-Abstraktion nicht aufgebrochen werden
  • Sowohl Kyber als auch ML-KEM hashen bei der Entkapselung Secret und Ciphertext für Implicit Rejection
    • Wendet man die obige Schlüsselableitung auf ML-KEM an, wird der Ciphertext bei Implicit Rejection zweimal gehasht
    • Die Ausgabe der Implicit Rejection ist per Design nicht vorhersagbar und kein Interoperabilitätsziel, daher ist das unproblematisch

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-02-02
Hacker-News-Kommentare

  • Grüße von Kudelski Security. Sehr zeitgemäß, da wir kürzlich eine der nahezu einzigen anderen post-quantenkryptografischen Bibliotheken für Go einstellen mussten
    Die ganze Geschichte steht unter https://research.kudelskisecurity.com/2024/02/01/the-kybersl...

    • War Kyber-512 nicht von NSA-nahen Mitgliedern des NIST absichtlich geschwächt worden?

  • Ich frage mich, wie weit Quantencomputing tatsächlich schon ist, dass so etwas nötig wird
    Ist das wie bei AI, wo nicht wirklich etwas Neues aufgetaucht ist, sondern nur die Definition geändert wird, um neue Produkte unter einem bestehenden Namen herauszubringen?

    • Kryptografie geht mit der Bedrohung durch Quantencomputer auf besondere Weise um. Denn ein Teil der heute verschlüsselten Daten und Verbindungen darf auch in 30 oder 50 Jahren nicht entschlüsselbar werden
      Die Frage lautet also nicht: „Kommen Quantencomputer bald?“, sondern: „Können Quantencomputer innerhalb des nächsten halben Jahrhunderts plausibel auftauchen?“ Es gibt keinen präzisen Konsens, aber die Antwort ist nicht „nein“, daher entsteht jetzt diese Bewegung
      Deshalb sieht man mehr Fortschritte bei PQC-Schlüsselaustausch als bei Signaturen. Die Verifikation heutiger Signaturen wird von einem Quantencomputer in 50 Jahren nicht beeinflusst, Verschlüsselung dagegen schon
    • Es geht nicht darum, heutige Quantencomputer abzuwehren
      Die Gefahr ist, dass ein Angreifer heutige Chiffretexte speichert und sie in Zukunft entschlüsseln kann. Je früher man auf quantensichere Kryptografie umstellt, desto weniger „aufgestaute Chiffretexte“ hinterlässt man, die für künftige Angriffe anfällig sind
    • Wenn die Antwort lautet: „Die NSA betreibt bereits Quanten-Kryptoanalyse in Production, und ECDH muss als vollständig gebrochen gelten“, dann würde die Person, die das weiß und es sagt, in enorme Schwierigkeiten geraten
      Tatsächlich wirkt das eher unwahrscheinlich, aber diese Frage ist in gewissem Maß schwer zu beantworten. Derzeit ist es keine bekannte Bedrohung, aber wie paranoid man gegenüber diesem Potenzial ist, ist subjektiv
    • In den letzten etwa zwei Jahren hat NIST einige Post-Quantum-Kryptografie-Algorithmen festgelegt, und seither gibt es immer mehr Implementierungen. Quantencomputing ist noch weit entfernt, aber die Haltung scheint zu sein: „Was spricht dagegen, jetzt anzufangen?“
      Sicher weiß ich es nicht, aber ich vermute, dass auch Elliptic-Curve-Kryptografie schon lange vor ihrer breiten Nutzung ziemlich viele Implementierungen hatte. Wer diese Zeit miterlebt hat, möge mich korrigieren, falls das falsch ist
    • Damit ein Quantencomputer RSA-2048 knacken kann, müssten Qualität der heutigen physischen Qubits ungefähr um den Faktor 10 und ihre Anzahl um den Faktor 10.000 steigen. Das sind sehr grobe Zahlen
      Der nächste wichtige Meilenstein, auf den man achten sollte, ist ein logisches Qubit, dessen Fidelity 1000-mal besser ist als die der physischen Qubits, aus denen es besteht. Wenn das erreicht ist, wäre das ein Signal, dass die Qualität physischer Qubits ausreicht und man nur noch mit der Skalierung der Anzahl beginnen muss

  • Für die Diskussion könnte John Arundels Einführung in die Implementierung kryptografischer Systeme auf Basis der neuesten Go-Version hilfreich sein. Im letzten Abschnitt wird Post-Quantum-Kryptografie kurz erwähnt; wenn NIST PQ standardisiert ist, könnte John das Buch später vielleicht mit dieser Bibliothek aktualisieren
    Explore Go: Cryptography (Go 1.22 edition):
    https://bitfieldconsulting.com/books/crypto

  • Korrigiert mich, wenn ich falschliege, aber wenn das in reinem Go geschrieben ist, ist es dann nicht anfällig für Timing-/Power-Side-Channel-Angriffe?

    • Go ist schwerlich anfälliger als C, und vielleicht sogar weniger. Der Unterschied ist, dass Go einen maßgeblichen Compiler hat und normalerweise nicht übermäßig optimiert, während man in C immer kompliziertere Tricks anwenden muss, damit der Compiler nicht die Absicht erkennt und sie in effizientere Branches mit variabler Laufzeit umwandelt
      Diese Implementierung wurde so geschrieben, dass Codepfade vermieden werden, die von geheimen Werten abhängen. Power-Side-Channels, die physischen Zugriff erfordern, liegen außerhalb des Bedrohungsmodells von Go
    • Dort steht: „Alle Kernoperationen werden in konstanter Zeit ausgeführt“
      Ich hätte wohl den Links bis zur Projektdokumentation folgen sollen; offenbar wird das berücksichtigt
    • Gibt es irgendeine Sprache, die gegen Power-Side-Channel-Angriffe immun ist? Schon die Idee scheint mir unsinnig
      Und bei Timing-Angriffen sehe ich nicht, warum Go anfälliger für Timing-Side-Channels sein sollte als andere Sprachen

  • Kennt jemand Implementierungen für andere Sprachen wie Java oder C#?

  • Cool, dass es auch mit draft00/kyber v3 funktionieren kann
    Wie schwierig wäre es, den schnellen Kyber-90’s-Modus ohne SHA-3 zu unterstützen? Vermutlich müsste man dafür die Abstraktion aufbrechen

    • Um den Hash zu wechseln, wäre ein Fork nötig. Diese Implementierung verbringt nur etwa 20% der CPU-Zeit in SHA-3, der Gewinn wäre also nicht groß
      Wenn die Feldimplementierung optimiert wird, würde dieser Anteil steigen, aber wohl kaum genug, um einen nicht standardisierten und weniger getesteten Modus zu rechtfertigen

  • Nicht damit verwandt, aber Filo, die 32-Bit-System-Call-Tabelle ist immer noch „coming soon“ :')

    • Haha, stimmt. Jedes Mal, wenn ich mir vornehme, diese Seite anzupassen, wird der Scope immer größer, etwa in Richtung „automatisch per CI aus den Kernel-Quellen generieren“ :)

  • Ich kann die Qualität dieses Algorithmus oder dieser Implementierung nicht beurteilen, aber dass bei Variablennamen Unicode verwendet wird, gefällt mir sehr
    ρ, σ := G[:32], G[32:]
    Irgendwie ist das viel besser als "rho", "sigma"

    • Da fällt es mir schwer zuzustimmen. Sieht zwar cool aus, aber in echtem Code möchte ich das eher nicht sehen
      Erstens wüsste ich nicht, wie ich das auf der Tastatur eingeben soll. Und die meisten werden nicht einmal die Namen dieser Symbole kennen. Natürlich ist die Wahrscheinlichkeit höher, dass Leute, die diesen Code lesen, sie kennen, aber freundlich geschriebener Code ist das meiner Ansicht nach nicht
      Klarheit ist entscheidend, und "rho" oder "sigma" sind ziemlich klar. Außerdem lädt es geradezu zu Verwechslungen ein, wenn es daneben auch noch die Konstante "n" und die Konstante "η" gibt
    • Gefällt mir überhaupt nicht. Zeichen, die nicht auf meiner Tastatur sind, bedeuten zusätzliche Eingabeschritte und erzeugen zu viel Reibung. Außerdem würde ich ρ vermutlich als p fehllesen und dann auf seltsame Compilerfehler stoßen
      Wie wäre es mit Akzenten oder Cedillen auf Buchstaben? Das erhöht nur die Komplexität. Besser ist es, sich am kleinsten gemeinsamen Nenner zu orientieren
    • Erlaubt Go Unicode-Subskripte in Variablennamen?
      Von den Sprachen, die ich geprüft habe, haben Perl, Python und JavaScript das in Chrome und Firefox nicht erlaubt, PHP dagegen schon

  • Die Person, die das gemacht hat, ist dieselbe, die auch https://github.com/FiloSottile/age gemacht hat
    Dieses Tool gefällt mir wirklich gut

    • Schade, dass keine plausible Abstreitbarkeit eingebaut ist. Gemeint ist: Man sollte mindestens zwei Dateien verschlüsseln und je nachdem, welchen Schlüssel man angibt, eine davon entschlüsseln können
      Das scheint eine Sicherheitsschwäche der meisten Tools dieser Art zu sein. Wenn es nur einen möglichen Schlüssel gibt, kann jemand mit einem Hammer einen dazu bringen, diesen Schlüssel preiszugeben. Wenn aber die Anzahl der Schlüssel unbekannt ist, könnte man ein paar herausgeben, die eigentlich geschützte Datei verstecken und hoffen, dass der Angreifer abzieht
    • Ich würde dieses Tool gern mögen, aber es fehlt an Handbüchern oder Tutorials, die typische Nutzungsszenarien erklären. Ich meine nicht die Kommandozeilen-Nutzung, sondern wie man Schlüssel verwalten und verteilen soll und worauf man achten muss
      Die gesamte soziale Schicht, die auf der Technik aufsitzt, ist mir unklar. Eine Beispielgeschichte mit Alice und Bob wäre schön
    • Age ist okay, wirkt aber etwas stagnierend. Das letzte Release war 2022, und es verwendet keine moderneren passwortbasierten Schlüsselableitungsfunktionen wie Argon
      Wenn man etwas sucht, das für das Speichern/Teilen von Geheimnissen gedacht ist, kann man sich rot ansehen: https://github.com/candiddev/rot

  • Spezifikation: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf ist auch im Artikel verlinkt