Wie Google kernelCTFs PoW mit AVX512 geschlagen wurde

• Das Team Crusaders of Rust entdeckte einen Use-after-free-Bug im Linux-Paket-Scheduler und entwickelte einen Exploit dafür
• Für den Google-kernelCTF-Wettbewerb war wegen der Notwendigkeit einer schnellen PoW-(Proof-of-Work)-Lösung ein Versuch mit leistungsstarker Optimierung erforderlich
• Mit eigener Assembly sowie SIMD-Optimierung auf Basis von AVX512IFMA-Befehlen wurde gegenüber bestehenden Implementierungen in Python/GMP und Rust eine fast 7-fache Geschwindigkeitssteigerung erreicht
• Durch Feintuning bis hin zu Funktionsprinzip, modularer Arithmetik, Speicherverwaltung und Registereinsatz wurde die PoW-Verarbeitungszeit auf 0,21 Sekunden reduziert
• Am Ende gelang eine erfolgreiche Einreichung bei kernelCTF in der bis dahin kürzesten Zeit von 3,6 Sekunden, woraufhin die PoW-Richtlinie offiziell abgeschafft wurde

---

Überblick und Zielsetzung

• Im Mai 2025 fanden William Liu und Savy Dicanosa aus dem Team Crusaders of Rust eine Use-after-free-Schwachstelle in Linux und nahmen am Google-Wettbewerb kernelCTF teil
• Dieser Beitrag behandelt den Optimierungsprozess, mit dem die PoW-(Proof-of-Work)-Prüfung schneller gelöst wurde, um in einem zeitlich stark begrenzten Bounty-Wettbewerb schneller als andere globale Teams einzureichen

Einreichungsablauf bei kernelCTF und Wettbewerbshintergrund

• kernelCTF ist wegen der hohen Preisgelder ein Wettbewerb, an dem professionelle Security-Teams aus aller Welt teilnehmen und bei dem sie alles auf Automatisierung der Einreichung und PoW-Optimierung setzen
• In jedem Einreichungsfenster, das alle zwei Wochen geöffnet wird, erhält nur das schnellste Team das Preisgeld
• Einreichungsablauf:
  • Punktgenaue Verbindung zum Server
  • Lösung des PoW, was einige Sekunden dauert
  • Warten auf den Start der VM
  • Ausführen des Exploit-Codes und Erhalt der Flag
  • Einreichung über ein Google-Formular
• Kürzlich gab es zwar bereits einen erfolgreichen Flag-Submit nach 4,5 Sekunden, doch allein PoW und VM-Start dauerten schon 6,5 Sekunden, weshalb eine schnellere PoW-Lösung zwingend erforderlich war

Analyse des PoW-(VDF-Sloth)-Algorithmus und erste Optimierung

• Das kernelCTF-PoW verwendet die sloth VDF, eine verifizierbare Delay Function auf Basis sequentieller Berechnungen
  • Für eine 1280-Bit-Ganzzahl x werden wiederholt modulares Quadrieren und Bit-Invertierung ausgeführt
• Schon bei den bestehenden Implementierungen (Python+gmpy und Rust) war Parallelisierung über mehrere Kerne wirkungslos, und auch GMP war bereits ausreichend optimiert
• Durch Ausnutzen der Tatsache, dass die Modulo-Operation auf einer Mersenne-Zahl (2^1279-1) basiert, gelang jedoch mit einer manuell geschriebenen C++-Implementierung eine Beschleunigung auf 1,9 bis 1,4 Sekunden

Der große Wechsel zu AVX512 und eine ultraschnelle SIMD-basierte Implementierung

• Danach richtete sich der Fokus auf die AVX512-ISA und insbesondere auf AVX512IFMA mit 52-Bit-Multiply-Accumulate-Befehlen
• Die 1280-Bit-Zahl wurde in 52-Bit-Limbs aufgeteilt, um die SIMD-Beschleunigung zu maximieren (25 Limbs → Nutzung von 4 zmm-Registern)
• Durch wiederholtes Low-Level-Tuning an Symmetrie der modularen Quadrierung, Akkumulationsmasken, Memory-Broadcasts, Registerzuweisung und branchless Vergleichen wurde weiter optimiert
• Mit ASM (Inline-Assembly) wurden ineffiziente Register-Spills/Reloads des Compilers verhindert, und durch optimierte Broadcast- und Masking-Strategien konnte die Laufzeit schließlich auf 0,21 Sekunden gesenkt werden

Automatisierung der PoW-Einreichung und reales Wettbewerbsszenario

• Für die finale Einreichung wurde ein Zen-5-Google-Cloud-Server in der Region Amsterdam verwendet, um auch die Netzwerklatenz bis zum Google-Formular zu minimieren
• Mit einem automatisierten Einreichungsprogramm (Patchen der POST-Anfrage an das Google-Formular, durch Teamarbeit weiter optimiert) gelang die erfolgreiche Flag-Einreichung in der Rekordzeit von 3,6 Sekunden
• Das kernelCTF-Team kündigte daraufhin offiziell die Abschaffung der PoW-Richtlinie an, wodurch der Wettbewerb um PoW-Optimierung endete und die Technik offengelegt werden konnte

Erweiterte Implementierungsdetails

Optimierung modularer Arithmetik

• Die Modulo-Operation mit 2^1279-1 (Primzahl) wurde durch einige Bit-Shifts und Grundrechenoperationen ersetzt, wodurch im Vergleich zu Standard-GMP eine deutlich schnellere modulare Arithmetik erreicht wurde

Big-Int-Squaring auf Basis von AVX512IFMA

• Mithilfe der AVX512-Befehle zur 52-Bit-Multiply-Accumulate (vpmadd52luq, vpmadd52huq) wurden parallele Multiplikation und Akkumulation von 8er-Limb-Gruppen umgesetzt
• Da die Struktur aus 25 Limbs besteht, wurden diese auf 4 zmm-Register verteilt und eine Logik entworfen, die unnötiges Masking und überflüssige Akkumulation minimiert

Datenlayout und Registereinsatz

• SIMD-Engpässe wurden durch ein nach Offsets organisiertes Layout, gestaffelte Datenanordnung und Umverteilung zwischen Registern (valignq, Broadcasts) beseitigt
• Durch Verdopplung der Akkumulatoren wurde maximaler Durchsatz erzielt, ohne auf freie Multiplikationseinheiten warten zu müssen
• Auch die Carry-Propagation wurde nur im unbedingt nötigen Umfang durchgeführt

Finale Einreichungsautomatisierung und Zusammenarbeit

• Teammitglieder wurden in den frühen Morgenstunden gezielt eingesetzt, um den Kampagnenzeitpunkt zu treffen, während Netzstandort und Exploit-Ausführung optimiert wurden
• Bei der tatsächlichen Einreichung lief alles durchgängig automatisiert ab: PoW-Lösung, Exploit-Ausführung, Einfügen der Flag und die Google-Form-POST-Anfrage

Fazit und Bedeutung

• Die Optimierung des kernelCTF-PoW ist eine Aufgabe, die ein anatomisch präzises Verständnis der Hardware von der Bit-Ebene über Speicher und Register bis hin zu CNN erfordert
• Mit dem Wegfall der PoW-Richtlinie verlagert sich der Wettbewerb auf reine Netzwerk- und Exploit-Geschwindigkeit
• Dieses Beispiel zeigt das Zusammentreffen von praxisnahem Hacking und High-Performance-Computing und dürfte mit seinem Know-how zur Algorithmus-Optimierung sowie dem Open-Source-Code auch künftig einen Beitrag zur Forschungsgemeinschaft leisten

Hinweise und Anhang

• Der vollständige Code des PoW-Algorithmus sowie Konvertierungsfunktionen (GMP <-> 52-Bit-Array), SIMD-basierte modulare Arithmetik und ASM-Tuning-Code wurden vollständig veröffentlicht
• Der in rund 12 Stunden intensiv entwickelte und produktiv eingesetzte, noch etwas „raue“ Code wurde unter der Lizenz GNU AGPL 3.0 als Open Source veröffentlicht
• Bei Fragen oder für Zusammenarbeit rund um VDF ist Kontakt über Discord (@forevermilk) möglich

[GN⁺]

Hacker-News-Kommentare

• Das erstplatzierte Team gewann mit 3,6 Sekunden, der Zweitplatzierte erreichte 3,73 oder 3,74 Sekunden; daher liegt die Vermutung nahe, dass auch der Zweitplatzierte PoW optimiert oder möglicherweise ein FPGA verwendet hat. Verglichen mit früheren FPGA-Einreichungen von über 4 Sekunden bleibt der Eindruck, dass der Autor ruhig hätte erwähnen können, dass auch die Zweitplatzierung in dieser Woche ein historisch außergewöhnlicher Wert gewesen sein könnte.

• Diese Methode wirkt sehr ähnlich zu Verfahren aus AVX-512-optimierten RSA-Implementierungen, was naheliegt, weil auch RSA sehr große Exponentiationen benötigt. Das Paper(https://dpitt.me/files/sime.pdf) behandelt Windowing-Techniken und die frei anpassbare Fenstergröße. Zusätzlich speichern AVX-512-RSA-Implementierungen Multiplikationsergebnisse im Bereich [0..2^{window-size}) in einer Tabelle, um das Ergebnis pro Fenster zu verwenden. Ein konkretes Beispiel findet sich in aws-lc code's rsaz-2k-avx512.pl.

  • Schade, dass man so etwas nicht früher gesehen hat, denn es hätte bei der Entwicklung helfen können. Auf Zen 5 wäre durch Nutzung der zmm-Register der doppelte Multiplikationsdurchsatz zu erwarten. Im bestehenden Code werden Maskenregister in GPRs umgewandelt, was auf Zen 4/5 ineffizient ist. Außerdem stellt sich die Frage, ob Carry-Propagation wirklich zwingend in einem einzigen Schritt erfolgen muss. Tatsächlich geht der Code iterativ davon aus, dass nur einmal ein Carry entsteht, was in den meisten Situationen die Latenz reduziert. Allerdings bleibt dadurch die Möglichkeit von Timing-Angriffen durch Branches bestehen.

• Zur Behauptung, AVX512 werde über mehrere Generationen hinweg auf Consumer-CPUs unterstützt: Soweit erinnerlich war AVX512 vor Rocket Lake (11. Generation) nur bei Enthusiast-, Xeon- und einigen mobilen Prozessoren verfügbar. Nach der 12. Generation und der Einführung von P-/E-Kernen wurde es binnen weniger Monate deaktiviert und verschwand wieder. Es wird prognostiziert, dass Intel es erneut einführen wird, falls AMD mit AVX512 Erfolg hat. Der Kommentator nutzt selbst einen i9-11900.

  • P-Core-CPUs der 12. Generation unterstützten oder bewarben AVX512 überhaupt nicht und hatten es standardmäßig deaktiviert. Aufgrund des Platzbedarfs der E-Cores fehlte AVX512 im gesamten CPU-Design. Über einen BIOS-Trick ließ sich AVX512 zwar auf den verbleibenden Kernen aktivieren, wenn man die E-Cores deaktivierte, allerdings nur um den Preis, auf die E-Cores zu verzichten.
  • In Intels aktuellem AVX10-Technical-Whitepaper(https://cdrdv2.intel.com/v1/dl/getContent/784343) werden 512-Bit-AVX auf P- und E-Kernen als Standard dargestellt. Damit entfernt man sich von Konfigurationen, die auf 256 Bit beschränkt sind, und kündigt eine ernsthafte Rückkehr von AVX-512 nicht nur auf Servern, sondern künftig auch in Consumer-CPUs an. Das wird als Reaktion darauf interpretiert, dass AMD seine AVX-512-Unterstützung ausweitet.

• Es wird infrage gestellt, ob diese Art von CTF-Wettbewerb sinnvoll ist. Statt eines Rennens um die schnellste Einreichung wäre es womöglich besser, wenn alle Teams, die innerhalb eines festen Einreichungsfensters eine Flag abgeben, das Preisgeld teilen.

  • Dem wird entgegengehalten, dass ein solches Modell ein Metagame fördern könnte, in dem Teilnehmer Exploit-Informationen nicht sofort offenlegen, sondern für spätere Runden zurückhalten, was die unmittelbare Meldung behindern würde. Außerdem bestünde die Gefahr nicht konstruktiver Konkurrenz durch Strategien beim Einreichungszeitpunkt.
  • Es wird auch erwähnt, dass sich dadurch die Metagame-Struktur ändern und die Motivation zur Teilnahme sinken könnte, sodass mehr Leute kernelCTF-Einreichungen gar nicht erst in Betracht ziehen würden.

• Wenn ich es richtig verstanden habe, geht es um einen 4-Sekunden-Proof-of-Work und eine monatliche Auszahlung; deshalb die Frage, ob tatsächlich jeden Monat so viele Exploits auftauchen, dass ein so harter Wettbewerb entsteht.

  • Der Server wurde alle zwei Wochen geöffnet, und das PoW sollte lediglich leichte Verzögerung erzeugen, um übermäßige Zugriffsanfragen zu verhindern. Öffentliche CTFs sind oft so umkämpft, dass sogar DDoS-ähnliche Aktionen versucht werden. Später entfernte Google den Proof-of-Work-Schritt.
  • Die Behauptung, der Mythos um die Sicherheit des Linux-Kernels sei in Wirklichkeit nur eine Illusion.
  • Bei diesem CTF ging es nicht um Remote Code Execution, sondern um Privilege Escalation, also Exploits zur Rechteausweitung von einem normalen Benutzer zu Root. Solche Privilege-Escalation-Bugs seien tatsächlich sehr häufig.

• Eine erstaunliche Herausforderung, aber die Komplexität und absurd-komische Atmosphäre der Hürden auf dem Weg zum Sieg hinterlassen Eindruck; es wirkt fast wie eine Rube-Goldberg-Maschine.

• Wer mehr über die im Haupttext erwähnte Base-52-Thematik erfahren möchte, dem sei dieser heute vielbeachtete Beitrag empfohlen(https://news.ycombinator.com/item?id=44132673).

• Der Eindruck, dass Mathematik großartig ist.

• Vorstellung von sloth, einer für das Proof of Work verwendeten VDF(Verifiable Delay Function): Sie verlangt eine Reihe langer Berechnungen, um den Zeitablauf nachzuweisen, während sich das Ergebnis schnell verifizieren lässt. Da die Berechnung seriell ist, lässt sich die Laufzeit auch mit vielen Kernen nicht verkürzen. Es stellt sich die Frage, ob dieses Gebiet für CPU-Hersteller ein neuer Markt werden könnte. Vorgeschlagen werden dedizierte Instruktionen für sloth-Iterationen und Ergebnisse sowie hardwarebasierter Schutz gegen Overclocking. Als Idee wird auch genannt, die CPU-Uptime zu überwachen und zusammen mit der Challenge zu signieren. Das ähnelt einem Proof-of-Stake-Konzept, bei dem die CPU produktiv genutzt wird und zugleich der Besitz der CPU für n Sekunden nachgewiesen wird.

• Es wird gefragt, wie die im Blog gezeigte Python-Funktion äquivalent zu Googles PoW-Implementierung ist; der Zusammenhang wirke schwer nachzuvollziehen.

  • Im Google-Code ist exponent = (p + 1) // 4 gleich 2^1277. Um eine Zahl auf einen derart riesigen Exponenten zu heben, muss 1277-mal quadriert werden, und genau das implementiert die Python-Funktion. Wenn der Ausgangswert x ist, verdoppelt sich der Exponent bei jedem Quadrieren, sodass man am Ende bei 2^1277 landet; so wird das Prinzip erklärt.