Wie Google kernelCTF-PoW mit AVX512 geschlagen wurde

 (anemato.de)
2 Punkte von GN⁺ 2025-05-31 | 1 Kommentare | Auf WhatsApp teilen
  • Das Team Crusaders of Rust wollte einen Exploit für den Linux-Paket-Scheduler CVE-2025-38001 einreichen, aber wegen der First-Come-First-Served-Struktur von kernelCTF wurde nicht der Bug selbst, sondern die Verkürzung des PoW zum entscheidenden Faktor
  • Der Einreichungsablauf bestand aus Verbindungsaufbau um 12:00 UTC, etwa 4 Sekunden PoW, etwa 2,5 Sekunden VM-Start, Exploit-Ausführung und Einreichung über Google Forms; der Rekord von 4,5 Sekunden aus der vorherigen Runde zeigte den Flaschenhals
  • Das Ziel-PoW war die „sloth“-VDF, eine serielle Berechnung mit wiederholtem modularen Quadrieren modulo 2^1279 - 1 auf 1280-Bit-Ganzzahlen, die sich nicht einfach durch mehr CPU- oder GPU-Kerne beschleunigen ließ
  • Mit GMP/C++ und Mersenne-Modularreduktion wurde die Zeit auf 1,9 Sekunden gesenkt, mit statischem Linken und -march=native auf etwa 1,4 Sekunden, und mit dem 52-Bit-Integer-Fused-Multiply-Add von AVX512IFMA auf einem Ryzen 9950X schließlich auf etwa 0,21 Sekunden
  • Am 16. Mai 2025 reichte das Team mit einem Zen-5-Google-Cloud-Server und einem optimierten POST-Pfad die Flag in nur 3,6 Sekunden ein; am 28. Mai kündigte kernelCTF die Entfernung des PoW an

Wettlauf: Nicht der Bug, sondern die schnellere Einreichung war das Problem

  • Im Mai 2025 entdeckten William Liu und Savy Dicanosa vom Team Crusaders of Rust den Use-after-free-Bug CVE-2025-38001 im Linux-Paket-Scheduler und entwickelten einen Exploit
    • William fand den Bug beim Fuzzing von Linux für seine Masterarbeit
    • Savy reduzierte die Laufzeit des Exploits auf etwa 0,55 Sekunden
  • Google kernelCTF öffnete alle zwei Wochen um 12 Uhr UTC das Einreichungsfenster; nur das Team, das den Server ausnutzte und als erstes die Flag über ein Google-Formular einreichte, erhielt die Belohnung
  • Die Einreichung lief immer in derselben Reihenfolge ab
    • Verbindung zum kernelCTF-Server um 12:00:00 UTC
    • Proof of Work lösen, ungefähr 4 Sekunden
    • Auf den Start der Instanz warten, ungefähr 2,5 Sekunden
    • Exploit hochladen und ausführen
    • Die Flag über Google Forms einreichen
  • Die erwartete Bounty lag bei 51.000 $
    • Grundprämie 21.337 $
    • Bonus für Ausführungsstabilität 10.000 $
    • Bonus für einen 0-Day-Bug 20.000 $

Frühere Einreichungszeiten machten den PoW-Flaschenhals sichtbar

  • Im Einreichungsfenster vom 2. Mai 2025 ging die erste Einsendung 4,5 Sekunden nach Mittag ein
  • Schon PoW mit etwa 4 Sekunden und VM-Start mit etwa 2,5 Sekunden ergaben zusammen 6,5 Sekunden, also passte der Wert von 4,5 Sekunden nicht zu einer naiven Rechnung
  • Wegen des Rundungsverhaltens im kernelCTF-Servercode wurde die VM-Instanz tatsächlich schon um 11:59:59 gestartet, womit der zeitliche Widerspruch verschwand
  • Trotzdem zeigte der Zeitstempel der Flag-Erzeugung, dass das Siegerteam den PoW in unter 1 Sekunde gelöst hatte
  • Falls das konkurrierende Team ein FPGA verwendet hatte, wäre ein PoW unter 1 Sekunde möglich gewesen
    • Ein FPGA ist maßgeschneiderte Hardware, die bestimmte Aufgaben sehr schnell ausführen kann
    • Für allgemeine Aufgaben ist es ungeeignet, zudem teuer und schwierig zu programmieren

sloth VDF: Ein PoW, das sich kaum parallelisieren lässt

  • Das kernelCTF-PoW war eine verifizierbare Verzögerungsfunktion (VDF) namens „sloth“
  • Eine VDF ist ein kryptografischer Baustein, der durch eine lange serielle Berechnung belegt, dass Zeit vergangen ist, während sich der Nachweis vergleichsweise schnell verifizieren lässt
  • Da die Berechnung selbst seriell ist, lässt sich die Laufzeit kaum durch zusätzliche CPU- oder GPU-Kerne reduzieren
  • Die zu optimierende Kernschleife hatte folgende Struktur
    • difficulty=7337
    • Für jede Difficulty-Iteration wurde 1277-mal x = (x * x) % (2 ** 1279 - 1) ausgeführt
    • Danach wurde das niederwertigste Bit von x invertiert
  • Googles Referenzimplementierung nutzte in Python gmpy; gmpy ist ein Python-Binding für GMP
    • GMP ist eine Bibliothek für Ganzzahlen mit beliebiger Präzision, deren plattformspezifische Additions- und Multiplikations-Kernel in Assembler implementiert sind

Erste Optimierung auf Basis von GMP

  • Die erste Optimierung nutzte aus, dass 2^1279 - 1 eine Mersenne-Zahl ist
    • Das 2560-Bit-Zwischenprodukt wurde in die unteren 1279 Bit und die oberen Bits aufgeteilt und anschließend addiert
    • Wenn das Ergebnis mindestens so groß wie der Modulus war, wurde einmal subtrahiert und so die %-Operation ersetzt
  • Um den Python-FFI-Overhead zu reduzieren, wurde die Implementierung nach C++ portiert; diese Version lief auf einem M1 MacBook Pro in 1,9 Sekunden
  • William kompilierte libgmp lokal mit -march=native und linkte statisch, wodurch die Zeit auf einem Intel-Ice-Lake-Laptop auf etwa 1,4 Sekunden sank
  • Ein ähnlich optimierter Solver in Rust nutzte dieselbe Mersenne-Technik, benötigte aber etwa 2,4 Sekunden
  • Danach wurde auch FLINT ausprobiert, war aber fast genauso schnell wie GMP

Neuschreiben des Big-Integer-Quadrierens mit AVX512IFMA

  • AVX512 ist eine Erweiterung der Intel-x86-ISA, die Zahl und Breite der Vektorregister erhöht sowie Masking und verschiedene neue Instruktionen hinzufügt
    • Intel deaktivierte AVX512-Unterstützung auf Client-CPUs ab Alder Lake
    • Im Serverbereich blieb die Unterstützung erhalten, und AMD implementierte AVX512 in Zen 4 und Zen 5 sowohl in Consumer- als auch in Server-CPUs
  • Entscheidend war AVX512IFMA
    • vpmadd52luq: addiert die untere Hälfte eines 52-Bit-Produkts in einen 64-Bit-Akkumulator
    • vpmadd52huq: addiert die obere Hälfte eines 52-Bit-Produkts in einen 64-Bit-Akkumulator
  • Diese Instruktionen berechnen die unteren und oberen Teile eines 52×52→104-Bit-Produkts und akkumulieren sie in Vektorregistern
  • Zen 5 verfügt über einen 512-Bit-Datenpfad und konnte diese Instruktionen mit zwei Starts pro Takt ausgeben
  • Die natürliche Basis war 2^52, und die 1280-Bit-Ganzzahl wurde als 25 52-Bit-Limbs dargestellt
    • Ein 512-Bit-zmm-Register kann 8 Limbs aufnehmen
    • Der gesamte Wert passt in 4 zmm-Register

Multiplikationsanordnung und Mersenne-Reduktion

  • Das 1280-Bit-Quadrieren wurde umgesetzt, indem 25 52-Bit-Limbs quadriert wurden, um ein Zwischenresultat mit 50 Limbs zu erzeugen
  • Durch Ausnutzung der Symmetrie des Quadrierens ließ sich die Zahl der nötigen Multiplikationen fast halbieren
    • Diagonalterme ai^2
    • Kreuzterme 2 * ai * aj für i < j
  • Bei der Berechnung der Kreuzterme wurde ein Sliding Window aus 8 aufeinanderfolgenden Limbs mit einem einzelnen Multiplier-Limb multipliziert, um Shuffle-Operationen zu reduzieren
  • Mit dem Merge Masking von AVX512 wurde verhindert, dass Multiplikationen akkumuliert werden, die nicht in die Endsumme eingehen
  • Die Modularreduktion erfolgte, indem die oberen 1279 Bit zu den unteren 1279 Bit addiert wurden
    • Da Akkumulatorelemente größer als 2^52 - 1 sein konnten, wurde die Carry-Propagation bis nach der Addition verschoben
    • Ob das Ergebnis mindestens 2^1279 - 1 war, wurde daran erkannt, ob das 1280. Bit auf 1 stand
    • Das Subtrahieren von 2^1279 - 1 entsprach dem Löschen des 1280. Bits und dem Addieren von 1 zum niederwertigsten Limb
  • Im letzten Schritt blieb eine sehr kleine Überlaufwahrscheinlichkeit bestehen
    • Wenn das letzte Limb exakt 2^52 - 1 war, musste ein Carry weitergereicht werden
    • Für zufällige PoWs wurde die Wahrscheinlichkeit mit etwa 2 zu 2 Milliarden pro Ausführung als vernachlässigbar betrachtet

Mikrooptimierungen von 0,45 auf 0,21 Sekunden

  • Die erste AVX512IFMA-Version verarbeitete den PoW auf einem gemieteten Ryzen 9950X in etwa 0,45 Sekunden
  • Die Multiply-Add-Instruktionen hatten eine Latenz von 4 Zyklen und konnten mit 2 Starts pro Takt ausgegeben werden; um die Multiplikationseinheiten auszulasten, wurden mindestens 8 Akkumulatoren benötigt
    • Zuvor gab es nur 7 Akkumulatoren
    • Daher wurde auf 7 Akkumulatoren für die untere Hälfte und 7 für die obere Hälfte umgestellt, insgesamt also 14, die am Ende zusammengeführt wurden
    • Diese Änderung senkte die Zeit auf etwa 0,32 Sekunden
  • GCC und clang erzeugten beim Unrolling der Schleife vbroadcastsd zmm, m64; durch Registerallokation fehlten dadurch Vektorregister, was zu Stack-Spills und Reloads führte
    • Mit Inline-Assembler wurde erzwungen, dass vpmadd52luq/vpmadd52huq einen Memory-Broadcast-Operand verwenden
    • Das Multiplier-Limb wurde nicht in ein separates Vektorregister geladen, sondern aus dem Speicher gelesen und auf alle Vektorelemente repliziert
    • Dieser Broadcast-Load verbrauchte keine Vektor-ALU-Ressourcen, sondern lief über die Load-Unit
    • Damit sank die Zeit auf etwa 0,23 Sekunden
  • Das Speichern der Ganzzahlen ausgerichtet im Speicher und anschließendes unaligned Laden zur Bildung des Fensters verursachte Store-Forwarding-Stalls
    • Mit valignq wurde ein unaligned Load innerhalb der zmm-Register emuliert und so die Zahl der Speicherzugriffe reduziert
    • Die endgültige PoW-Zeit lag bei etwa 0,21 Sekunden

Ergebnis der Einreichung vom 16. Mai 2025

  • Das Team bereitete die finale Einreichung am 16. Mai 2025 um 4:30 Uhr PST vor
  • Um die Latenz zu senken, wurde ein Zen-5-Google-Cloud-Server in den Niederlanden genutzt, geografisch nahe am Google-Forms-Server
  • Einige Minuten vor der Einreichung wurde eine Google-Forms-POST-Anfrage mit einer Dummy-Flag abgefangen und protokolliert
    • Bryce Casaje und Larry Yuan entwarfen und optimierten das Programm zum Absenden des Formulars
    • Max Cai half ebenfalls bei Entwicklung und Einreichung
  • Um 5:00 Uhr verband sich der Server mit dem kernelCTF-Server, löste den PoW, führte Savys optimierten Exploit aus und fügte anschließend die Flag in die POST-Anfrage ein und sendete sie ab
  • Das Ergebnis war eine Einreichung in 3,6 Sekunden, damals die schnellste in der Geschichte von kernelCTF
  • Noch am selben Tag bestätigten die kernelCTF-Betreiber die Bounty-Berechtigung

Entfernung des PoW und Veröffentlichung des finalen Solvers

  • Am 28. Mai 2025 kündigte kernelCTF-Betreiber koczkatamas die Entfernung des PoW an
  • Ohne PoW verlagerte sich der Slot-Wettbewerb auf Exploit-Laufzeit und Netzwerklatenz
  • Dadurch können nun auch Teams ohne FPGA oder Kenntnisse in Inline-Assembler unter denselben Bedingungen wie Spezialistenteams antreten
  • Der finale Solver-Code war das Ergebnis von etwa 12 Stunden Arbeit am 14. und 15. Mai 2025 und wurde unter GNU AGPL 3.0 veröffentlicht
  • Ein Build-Beispiel war gcc main.c -O3 -march=znver5 -masm=intel -lgmp

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-05-31
Meinungen auf Hacker News

  • Toller Inhalt. Dieser Ansatz ist auch Implementierungen von AVX-512-optimiertem RSA sehr ähnlich, weil RSA ebenfalls Exponentiationen mit sehr großen Exponenten durchführen muss.
    Dieses Paper[1] behandelt, wie RSA Windowing nutzt, und enthält auch eine Formel, die zeigt, dass die Fenstergröße beliebig sein kann. AVX-512-RSA-Implementierungen speichern zusätzlich die Multiplikationsergebnisse im Bereich [0..2^{window-size}) in einer Tabelle; für jedes Fenster wird das Ergebnis dann aus Tabelle[2] geholt, danach werden nur noch Shifts/Umordnungen ausgeführt.

    1. https://dpitt.me/files/sime.pdf (stammt aus einem Journal, daher auf meiner Domain gehostet)

    2. https://github.com/aws/aws-lc/blob/9c8bd6d7b8adccdd8af4242e0...

    • Interessant. Das hätte ich mir bei der Entwicklung ansehen sollen. Für diesen Code wäre zum Beispiel eine zusätzliche Version für Zen 5 gut; mit zmm-Registern scheint sich der Multiplikationsdurchsatz verdoppeln zu lassen.
      Außerdem werden Maskenregister wegen arithmetischer Operationen in General-Purpose-Register verschoben, was auf Zen 4/5 nicht optimal ist. Unabhängig davon frage ich mich auch, ob der Übertrag wirklich in einem Durchgang propagiert werden muss. In meinem Code gehe ich davon aus, dass ein Übertrag nur einmal auftritt, und gehe bei Bedarf in eine Schleife zurück, um die Latenz im Normalfall zu senken. Mit Branches könnte es allerdings Probleme mit Timing-Angriffen geben.
    • dpitt.me/files/sime.pdf kann man auch auf archive.org hochladen: https://archive.org/download/sime_20250531/sime.pdf

  • Die Formulierung „obwohl [AVX512] über mehrere Generationen hinweg auf Consumer-CPUs unterstützt wurde“ wirkt etwas merkwürdig.
    Vor Rocket Lake (11. Generation) gab es AVX-512 nur in High-End-Hobby-CPUs, Xeon-CPUs und einigen mobilen Prozessoren; mobile Prozessoren als Consumer-CPUs zu bezeichnen, ist etwas fragwürdig. In der 12. Generation wurde es wegen der Performance-/Efficiency-Core-Struktur einige Monate später auf diesen Cores deaktiviert und tauchte danach nicht wieder auf. Wenn AMD mit AVX-512 aber einigermaßen Erfolg hat, halte ich es für wahrscheinlich, dass Intel es wieder einführt. Nebenbei: Ich nutze immer noch einen Intel i9-11900.

    • Das ist die richtige Tendenz. Das vor einigen Monaten aktualisierte AVX10-Whitepaper[1] von Intel scheint das ebenfalls zu bestätigen. Darin steht ausdrücklich, dass 512-Bit-AVX zum Standard sowohl für P-Cores als auch für E-Cores werden soll und man sich von reinen 256-Bit-Konfigurationen entfernt.
      Das wirkt wie ein starkes Signal, dass AVX-512 nicht nur auf Servern, sondern auch auf künftigen Consumer-CPUs mit E-Cores richtig zurückkommt. Vermutlich will Intel AMDs breitere AVX-512-Adoption einholen.

      [1] - https://cdrdv2.intel.com/v1/dl/getContent/784343 (PDF)

    • CPUs der 12. Generation mit Performance-Cores haben AVX512-Unterstützung von Anfang an weder ausgewiesen noch standardmäßig aktiviert.
      Weil die Efficiency-Cores aus Flächengründen kein AVX512 enthielten, galt die gesamte CPU als ohne AVX512-Unterstützung. Man konnte lediglich ein eigenartiges Verhalten einiger BIOS-Optionen ausnutzen, die Efficiency-Cores abschalten und auf der verbleibenden CPU AVX512 aktivieren – um den Preis, auf die E-Cores zu verzichten.

  • Die Siegerzeit lag bei 3,6 Sekunden, aber Platz zwei bei 3,73 Sekunden, gerundet auf dieselbe Stellenzahl wie die Siegerzeit also 3,74 Sekunden. Muss man dann davon ausgehen, dass auch Platz zwei den Proof of Work optimiert oder ein FPGA verwendet hat?
    Der Autor beschrieb frühere Einreichungen als teure FPGA-basierte Lösungen, die trotzdem über 4 Sekunden lagen. Dann hätte der zweite Platz dieser Woche möglicherweise die zweitschnellste Einreichung aller Zeiten sein können; dazu hätte man doch wohl etwas erwähnt.

    • Auf dem Bild steht dupe. Vermutlich hat das Team des Originalposts versucht, parallel über mehrere Accounts einzureichen.

  • Beeindruckend, aber es wirkt, als würde hier das Falsche optimiert. Ein CTF sollte nicht zu einem Kampf um den Einreichungsbetrieb werden.
    Wäre es nicht für alle besser, wenn alle Teams, die das Flag innerhalb des Einreichungsfensters senden, sich das Preisgeld teilen?

    • Eine solche Struktur kann auch dazu führen, dass man Exploits nicht sofort meldet, sondern zurückhält. Wenn man diesmal nichts bekommt, kann man auf die nächste Einreichung zielen; selbst ohne Spielchen beim Timing gibt es einen Anreiz zum Zurückhalten.
      In der Praxis könnte das also aktiv zu „falschem“ Verhalten ermutigen.
    • Das würde zu einem anderen Metagame werden. Ich habe nicht tief darüber nachgedacht, aber am Ende scheint es sehr wahrscheinlich, dass Leute die Motivation verlieren und kernelCTF-Einreichungen gar nicht mehr in Betracht ziehen.
    • Stimmt, aber faktisch gibt es solche Elemente in fast jedem CTF.

  • Wenn ich es richtig verstanden habe, gibt es einen 4-Sekunden-Proof-of-Work, und das Preisgeld wird einmal im Monat ausgezahlt.
    Gibt es wirklich so viele Exploits, dass jeden Monat Leute darum konkurrieren?

    • Der Server wurde alle zwei Wochen geöffnet. Der Proof of Work war eine Maßnahme, um Verbindungen etwas zu verlangsamen und den Anreiz zu reduzieren, möglichst viele Verbindungsanfragen zu spammen.
      Öffentliche CTFs sind schwierig. Am Ende verhalten sich manche Teams auf dem Weg zur Ziellinie ähnlich wie bei einem DDoS. Später hat Google den Proof-of-Work-Schritt entfernt.
    • Das ist keine Remote Code Execution, sondern ein lokaler Privilege-Escalation-Exploit, also die Art, bei der man vom normalen Nutzer zu root wird. Privilege-Escalation-Bugs gibt es wie Sand am Meer.
    • Der Mythos der Linux-Kernel-Sicherheit ist eben genau das: ein Mythos.

  • Großartige Sache, aber wenn man sich die Hürden ansieht, die man überwinden muss, um diese Challenge zu gewinnen, liest es sich wie eine Komödie. Wirklich wie eine Rube-Goldberg-Maschine.

  • Wer mehr über die in diesem Artikel erwähnte Darstellung zur Basis 52 wissen möchte, sollte sich auch einen anderen heutigen Frontpage-Beitrag ansehen: https://news.ycombinator.com/item?id=44132673

  • Kleine Korrektur: statisches Linken sorgt nicht für Inlining, sondern entfernt nur den PLT-Overhead. LTO ist das, was zusätzliche Inlining-Möglichkeiten schafft.

  • Ich verstehe nicht, warum man daraus einen Wettbewerb macht. Warum nicht einfach jede einzigartige Exploit belohnen?

    • Weil der Chef für den Betrieb eines so coolen Programms ein strikt festes Budget will. Die Begründung für solche Programme besteht zumindest teilweise nicht im Kauf von Bugs, sondern darin, Trends bei Exploits und Mitigation-Techniken zu messen.
      Und Linux hat so viele Bugs, dass es außer Kontrolle gerät, wenn man anfängt, für jeden 0-day zu zahlen. Google hatte früher einmal eine zeitlich begrenzte Promotion ohne Wettbewerb, um von Leuten gehortete Bugs freizusetzen; als alle 0-days anerkannt wurden, explodierte die Zahl der Einreichungen. Gleichzeitig will man die Community nicht verärgern, also ist diese Struktur entstanden.

  • Es ist etwas deprimierend, dass Fachleute nach all den Jahren eine Linux-Maschine in nur 3 Sekunden übernehmen können.