Cara Mengalahkan PoW kernelCTF Google dengan AVX512

• Tim Crusaders of Rust mencoba mengirim eksploit CVE-2025-38001 pada Linux packet scheduler, tetapi karena struktur kernelCTF yang berdasarkan siapa tercepat, mempercepat PoW menjadi penentu kemenangan, bukan bug itu sendiri
• Proses pengiriman berurutan dari koneksi pukul 12:00 UTC, PoW sekitar 4 detik, boot VM sekitar 2,5 detik, eksekusi eksploit, hingga pengiriman Google Form; rekor pengiriman 4,5 detik dari ronde sebelumnya menunjukkan letak bottleneck
• PoW target adalah VDF “sloth”, komputasi serial yang mengulang pemangkatan modular 2^1279 - 1 pada bilangan bulat 1280-bit, sehingga sulit dipercepat hanya dengan menambah core CPU/GPU
• Dengan GMP/C++ dan reduksi modular Mersenne, waktunya turun menjadi 1,9 detik; setelah static linking dengan -march=native, turun lagi menjadi sekitar 1,4 detik; lalu dengan fused multiply-add bilangan bulat 52-bit dari AVX512IFMA, dipangkas hingga sekitar 0,21 detik di Ryzen 9950X
• Pada 16 Mei 2025, tim mengirim flag dalam 3,6 detik menggunakan server Zen 5 Google Cloud dan jalur pengiriman POST yang dioptimalkan; pada 28 Mei, kernelCTF mengumumkan penghapusan PoW

---

Kondisi kompetitif: masalahnya adalah pengiriman yang lebih cepat daripada bug

• Pada Mei 2025, William Liu dan Savy Dicanosa dari tim Crusaders of Rust menemukan bug use-after-free CVE-2025-38001 pada Linux packet scheduler dan mengembangkan eksploit
  • William menemukan bug tersebut saat melakukan fuzzing Linux untuk tesis magisternya
  • Savy memangkas waktu eksekusi eksploit hingga sekitar 0,55 detik
• kernelCTF Google membuka jendela pengiriman setiap dua minggu pada tengah hari UTC, dengan struktur hadiah hanya untuk tim pertama yang mengeksploitasi server dan mengirim flag ke Google Form
• Pengiriman selalu berlangsung dalam urutan yang sama
  • Terhubung ke server kernelCTF pada 12:00:00 UTC
  • Menyelesaikan proof of work, sekitar 4 detik
  • Menunggu instance boot, sekitar 2,5 detik
  • Mengunggah dan menjalankan eksploit
  • Mengirim flag ke Google Form
• Perkiraan bounty adalah $51.000
  • Hadiah dasar $21.337
  • Hadiah stabilitas eksekusi $10.000
  • Hadiah bug 0-day $20.000

Rekor pengiriman sebelumnya mengungkap bottleneck PoW

• Pada jendela pengiriman 2 Mei 2025, pengiriman pertama masuk 4,5 detik setelah tengah hari
• Jika PoW sekitar 4 detik dan boot VM sekitar 2,5 detik saja sudah membutuhkan 6,5 detik, maka rekor 4,5 detik tidak cocok dengan perhitungan sederhana
• Karena karakteristik pembulatan pada kode server kernelCTF, instance VM sebenarnya boot pada 11:59:59, sehingga kontradiksi waktu tersebut hilang
• Meski begitu, timestamp pembuatan flag menunjukkan bahwa tim pemenang menyelesaikan PoW dalam kurang dari 1 detik
• Jika tim pesaing menggunakan FPGA, PoW di bawah 1 detik mungkin saja tercapai
  • FPGA adalah hardware khusus yang dapat menjalankan tugas tertentu dengan sangat cepat
  • FPGA kurang cocok untuk tugas serbaguna, serta mahal dan sulit diprogram

VDF sloth: PoW yang sulit diparalelkan

• PoW kernelCTF adalah verifiable delay function (VDF) bernama “sloth”
• VDF adalah primitif kriptografis yang membuktikan bahwa waktu telah berlalu melalui komputasi serial panjang, sementara bukti hasilnya dapat diverifikasi relatif cepat
• Karena komputasinya bersifat serial, sulit mengurangi waktu eksekusi dengan menambah core CPU atau GPU
• Loop inti yang menjadi target optimasi memiliki struktur berikut
  • difficulty=7337
  • Pada setiap iterasi difficulty, menjalankan x = (x * x) % (2 ** 1279 - 1) sebanyak 1277 kali
  • Setelah itu membalik bit paling rendah dari x
• Implementasi acuan Google menggunakan gmpy di Python, dan gmpy adalah binding Python untuk GMP
  • GMP adalah library bilangan bulat multipresisi yang mengimplementasikan kernel penjumlahan dan perkalian spesifik platform dalam assembly

Optimasi tahap pertama berbasis GMP

• Optimasi pertama memanfaatkan fakta bahwa 2^1279 - 1 adalah bilangan Mersenne untuk melakukan reduksi modular
  • Hasil perkalian sementara 2560-bit dibagi menjadi 1279 bit bawah dan bit atas, lalu dijumlahkan
  • Jika hasilnya lebih besar atau sama dengan modulus, kurangi sekali; cara ini menggantikan operasi %
• Untuk mengurangi overhead Python FFI, implementasi dipindahkan ke C++, dan versi ini berjalan dalam 1,9 detik di M1 MacBook Pro
• William mengompilasi libgmp secara lokal dengan -march=native dan melakukan static linking, menurunkan waktu hingga sekitar 1,4 detik di laptop Intel Ice Lake
• Solver optimasi serupa yang ditulis dalam Rust menggunakan teknik Mersenne yang sama, tetapi membutuhkan sekitar 2,4 detik
• Setelah itu FLINT juga diuji, tetapi kecepatannya hampir sama dengan GMP

Menulis ulang kuadrat bilangan bulat besar dengan AVX512IFMA

• AVX512 adalah ekstensi ISA Intel x86 yang menambah jumlah dan lebar register vektor, mask prediction, serta beberapa instruksi baru
  • Intel menonaktifkan dukungan AVX512 pada CPU klien sejak Alder Lake
  • Di ranah server, dukungan tetap berlanjut, dan AMD mengimplementasikan AVX512 pada CPU konsumen maupun server di Zen 4 dan Zen 5
• Kuncinya adalah AVX512IFMA
  • vpmadd52luq: menambahkan separuh bawah dari perkalian 52-bit ke akumulator 64-bit
  • vpmadd52huq: menambahkan separuh atas dari perkalian 52-bit ke akumulator 64-bit
• Instruksi-instruksi ini menghitung bagian bawah dan atas dari perkalian 52×52→104-bit lalu mengakumulasikannya ke register vektor
• Zen 5 memiliki data path 512-bit, sehingga dapat memulai 2 instruksi ini per clock
• Basis alami yang dipakai adalah 2^52, dan bilangan bulat 1280-bit direpresentasikan sebagai 25 limb 52-bit
  • Satu register zmm 512-bit dapat menampung 8 limb
  • Seluruh nilai masuk ke 4 register zmm

Penjadwalan perkalian dan reduksi Mersenne

• Kuadrat 1280-bit diimplementasikan dengan menguadratkan 25 limb 52-bit untuk menghasilkan hasil sementara 50 limb
• Simetri operasi kuadrat dimanfaatkan untuk mengurangi jumlah perkalian yang dibutuhkan hingga hampir separuh
  • Komponen diagonal ai^2
  • Suku silang 2 * ai * aj untuk i < j
• Dalam perhitungan suku silang, sliding window berisi 8 limb berurutan dikalikan dengan satu multiplier limb untuk mengurangi shuffle
• Dengan merge masking AVX512, perkalian yang tidak masuk ke penjumlahan akhir dibuat agar tidak diakumulasikan
• Reduksi modular dilakukan dengan menambahkan 1279 bit atas ke 1279 bit bawah
  • Karena elemen akumulator bisa melebihi 2^52 - 1, propagasi carry ditunda sampai setelah penjumlahan
  • Apakah hasilnya lebih besar atau sama dengan 2^1279 - 1 ditentukan dari apakah bit ke-1280 bernilai 1
  • Mengurangkan 2^1279 - 1 sama dengan menghapus bit ke-1280 dan menambahkan 1 ke limb paling rendah
• Pada tahap terakhir, masih ada kemungkinan overflow yang sangat kecil
  • Jika limb terakhir tepat 2^52 - 1, propagasi carry diperlukan
  • Untuk PoW acak, peluang terjadinya dilaporkan sekitar 2 dari 2 miliar per eksekusi, sehingga diabaikan

Mikro-optimasi dari 0,45 detik ke 0,21 detik

• Versi AVX512IFMA pertama memproses PoW dalam sekitar 0,45 detik di Ryzen 9950X sewaan
• Instruksi multiply-add memiliki latensi 4 siklus dan dapat dimulai 2 kali per clock, sehingga setidaknya diperlukan 8 akumulator untuk memenuhi unit perkalian
  • Sebelumnya hanya ada 7 akumulator
  • Diubah menjadi 7 akumulator untuk separuh bawah dan 7 untuk separuh atas, total 14 akumulator, lalu digabungkan di akhir
  • Perubahan ini menurunkan waktu hingga sekitar 0,32 detik
• GCC dan clang menghasilkan vbroadcastsd zmm, m64 saat melakukan unroll loop, dan dalam proses alokasi register terjadi kekurangan register vektor sehingga muncul stack spill dan reload
  • Dengan inline assembly, vpmadd52luq/vpmadd52huq dipaksa memakai memory broadcast operand
  • Multiplier limb tidak disimpan dalam register vektor terpisah, melainkan dibaca dari memori dan direplikasi ke semua elemen vektor
  • Broadcast load ini diproses di load unit tanpa memakai resource ALU vektor
  • Pada tahap ini, waktu turun hingga sekitar 0,23 detik
• Cara menyimpan bilangan bulat secara aligned di memori lalu membuat window dengan unaligned load menyebabkan store-forwarding stall
  • Dengan valignq, unaligned load ditiru di dalam register zmm, sehingga akses memori berkurang
  • Waktu akhir PoW menjadi sekitar 0,21 detik

Hasil pengiriman pada 16 Mei 2025

• Tim menyiapkan pengiriman akhir pada 16 Mei 2025 pukul 4:30 pagi PST
• Untuk mengurangi latensi, mereka menggunakan server Zen 5 Google Cloud di Belanda yang secara geografis dekat dengan server pengiriman Google Form
• Beberapa menit sebelum pengiriman, mereka mencegat dan menyimpan request POST Google Form dengan flag dummy
  • Bryce Casaje dan Larry Yuan merancang dan mengoptimalkan program pengiriman Form
  • Max Cai juga membantu pengembangan dan pengiriman
• Pada pukul 5:00, server terhubung ke server kernelCTF, menyelesaikan PoW, menjalankan eksploit yang dioptimalkan Savy, lalu memasukkan flag ke request POST dan mengirimkannya
• Hasilnya adalah pengiriman dalam 3,6 detik, yang pada saat itu merupakan pengiriman tercepat dalam sejarah kernelCTF
• Operator kernelCTF mengonfirmasi kelayakan bounty pada hari yang sama

Penghapusan PoW dan rilis solver akhir

• Pada 28 Mei 2025, operator kernelCTF koczkatamas mengumumkan penghapusan PoW
• Setelah PoW hilang, persaingan slot bergeser ke waktu eksekusi eksploit dan latensi jaringan
• Perubahan ini memungkinkan peserta bersaing dalam kondisi yang sama dengan tim profesional tanpa pengetahuan optimasi FPGA atau inline assembly
• Kode solver akhir merupakan hasil sekitar 12 jam kerja pada 14–15 Mei 2025, dan dirilis dengan lisensi GNU AGPL 3.0
• Contoh build-nya adalah gcc main.c -O3 -march=znver5 -masm=intel -lgmp

[GN⁺]

Komentar Hacker News

• Kontennya keren. Pendekatan ini juga sangat mirip dengan implementasi RSA yang dioptimalkan untuk AVX-512, karena RSA juga harus melakukan operasi eksponen yang sangat besar.
  Makalah ini[1] membahas bagaimana RSA melakukan windowing, dan juga menyertakan formula yang menunjukkan bahwa ukuran jendela bisa sembarang. Implementasi RSA AVX-512 juga menyimpan hasil perkalian dalam rentang [0..2^{window-size}) di tabel, lalu untuk setiap jendela mengambil hasil tersebut dari tabel[2] dan hanya melakukan shift/rearrangement.

  1. https://dpitt.me/files/sime.pdf (saya hosting di domain saya karena diambil dari jurnal)

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

  • Menarik. Sepertinya saya seharusnya melihat ini saat mengembangkan. Kode itu akan bagus kalau punya satu versi tambahan, misalnya untuk Zen 5, dan dengan memakai register zmm, throughput perkalian tampaknya bisa menjadi 2x.
    Selain itu, register mask dipindahkan ke register general-purpose untuk operasi aritmetika, yang di Zen 4/5 bukan pilihan optimal. Secara terpisah, saya juga penasaran apakah carry benar-benar harus dipropagasikan sekaligus. Di kode saya, saya mengasumsikan carry hanya muncul satu kali dan berputar dalam loop bila perlu, sehingga latensi pada kasus umum berkurang. Namun, kalau ada branch, memang bisa timbul masalah timing attack.
  • dpitt.me/files/sime.pdf juga bisa diunggah ke archive.org: https://archive.org/download/sime_20250531/sime.pdf

• Bagian “meski [AVX512] sudah didukung selama beberapa generasi di CPU konsumen” agak aneh.
  Sebelum Rocket Lake (generasi ke-11), AVX-512 hanya ada di CPU hobi kelas atas, CPU Xeon, dan sebagian prosesor mobile; menyebut prosesor mobile sebagai CPU konsumen juga terasa kurang pas. Pada generasi ke-12, karena struktur core performa/efisiensi, dukungan itu dinonaktifkan di core tersebut beberapa bulan kemudian dan tidak muncul lagi. Meski begitu, kalau AMD cukup sukses dengan AVX-512, saya rasa kemungkinan besar Intel akan mengadopsinya lagi. Sebagai catatan, saya masih memakai Intel i9-11900.

  • Alurnya benar. Whitepaper AVX10[1] Intel yang diperbarui beberapa bulan lalu juga tampaknya mengonfirmasi hal ini. Di sana dinyatakan bahwa AVX 512-bit akan menjadi standar untuk P-core maupun E-core, dan mereka akan keluar dari konfigurasi yang hanya 256-bit.
    Ini terlihat sebagai sinyal kuat bahwa AVX-512 akan benar-benar kembali bukan hanya di server, tetapi juga di CPU konsumen masa depan yang memiliki E-core. Mungkin untuk mengejar adopsi AVX-512 AMD yang lebih luas.

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

  • CPU generasi ke-12 dengan performance core sejak awal bahkan tidak menampilkan dukungan AVX512, dan tidak diaktifkan secara default.
    Karena efficiency core tidak memasukkan AVX512 karena alasan area die, keseluruhan CPU dianggap tidak mendukung AVX512. Hanya saja, dengan memanfaatkan perilaku aneh pada beberapa opsi BIOS, orang bisa mematikan efficiency core dan mengaktifkan AVX512 pada CPU yang tersisa, dengan konsekuensi harus mengorbankan E-core.

• Rekor pemenangnya 3,6 detik, tetapi posisi kedua 3,73 detik; kalau dibulatkan ke jumlah digit yang sama dengan rekor pemenang, itu 3,74 detik. Jadi apakah posisi kedua juga mengoptimalkan proof of work, atau memakai FPGA?
  Penulis mengatakan submission sebelumnya berbasis FPGA mahal tetapi tetap di atas 4 detik. Kalau begitu, posisi kedua minggu itu mungkin saja merupakan submission tercepat kedua sepanjang masa; rasanya mereka mungkin akan menyebut sesuatu tentang itu.

  • Di gambarnya tertulis dupe. Mungkin tim penulis asli mencoba mengirim secara paralel lewat beberapa akun.

• Mengesankan, tetapi sepertinya target optimisasinya keliru. CTF seharusnya tidak menjadi adu operasi submission.
  Bukankah lebih baik untuk semua pihak jika semua tim yang mengirim flag dalam jendela submission berbagi hadiahnya?

  • Struktur seperti ini juga membuat orang menahan exploit alih-alih segera melaporkannya. Kalau kali ini tidak dapat hadiah, mereka bisa mengincar submission berikutnya, sehingga sekalipun tanpa permainan timing submission, tetap ada insentif untuk menunda.
    Jadi dalam praktiknya, ini bahkan bisa secara aktif mendorong perilaku yang “salah”.
  • Itu akan menjadi metagame lain. Saya belum memikirkannya terlalu dalam, tetapi hasil akhirnya tampaknya kemungkinan besar orang akan kehilangan motivasi dan tidak lagi mempertimbangkan untuk mengirim ke kernelCTF.
  • Benar, tetapi pada dasarnya hampir semua CTF punya elemen seperti ini.

• Kalau pemahaman saya benar, ada proof of work 4 detik, dan hadiahnya dibayarkan sebulan sekali.
  Apakah memang ada exploit sebanyak itu sampai orang-orang berkompetisi setiap bulan?

  • Servernya dibuka setiap dua minggu. Proof of work adalah mekanisme untuk sedikit memperlambat koneksi, demi mengurangi insentif mengirim spam permintaan koneksi sebanyak mungkin.
    CTF publik itu sulit. Pada akhirnya, beberapa tim akan melakukan perilaku yang mirip DDoS dalam proses berlari menuju garis finis. Setelah itu Google menghapus tahap proof of work.
  • Ini bukan remote code execution, melainkan exploit local privilege escalation, yaitu jenis yang membuat pengguna biasa menjadi root. Bug privilege escalation itu sangat umum.
  • Mitos keamanan kernel Linux memang benar-benar hanya mitos.

• Kontennya hebat, tetapi kalau melihat rintangan yang harus dilewati untuk menang di challenge ini, rasanya seperti membaca komedi. Benar-benar seperti mesin Rube Goldberg.

• Kalau ingin tahu lebih banyak tentang representasi basis-52 yang disebut di tulisan ini, ada tulisan lain di front page hari ini yang juga layak dilihat: https://news.ycombinator.com/item?id=44132673

• Koreksi kecil, static linking tidak melakukan inlining; itu hanya menghilangkan overhead PLT. Yang meningkatkan peluang inlining adalah LTO.

• Saya tidak mengerti mengapa harus dibuat kompetisi. Tidak bisakah cukup memberi imbalan untuk setiap exploit unik?

  • Karena atasan yang menjalankan program keren seperti ini menginginkan anggaran tetap yang ketat. Pembenaran untuk program semacam ini, setidaknya sebagian, bukan membeli bug, melainkan mengukur tren exploit dan teknik mitigasi.
    Dan Linux punya terlalu banyak bug, sehingga kalau mulai membayar untuk semua 0-day, semuanya akan lepas kendali. Google juga pernah menjalankan promosi terbatas tanpa kompetisi untuk menguras bug yang ditimbun orang, dan ketika mereka menerima semua 0-day, submission membanjir. Pada saat yang sama, mereka tidak ingin membuat komunitas marah, jadi strukturnya menjadi seperti ini.

• Agak menyedihkan bahwa setelah waktu selama ini berlalu, para ahli masih bisa mengambil alih mesin Linux dalam 3 detik.