Cara Mengalahkan PoW kernelCTF Google dengan AVX512

• Tim Crusaders of Rust menemukan bug use-after-free pada packet scheduler Linux dan mengembangkan exploit-nya
• Karena dibutuhkannya solusi PoW (Proof of Work) yang cepat untuk kompetisi Google kernelCTF, mereka mencoba optimasi berperforma tinggi
• Dengan assembly kustom dan optimasi SIMD yang memanfaatkan instruksi AVX512IFMA, mereka mencapai performa hampir 7 kali lebih cepat dibanding implementasi Python/GMP dan Rust yang ada
• Dengan penyetelan rinci hingga prinsip kerja, operasi modular, manajemen memori, dan pemanfaatan register, waktu pemrosesan PoW berhasil dipangkas sampai 0,21 detik
• Pada akhirnya mereka berhasil mengajukan submission ke kernelCTF dalam waktu tercepat sepanjang sejarah (3,6 detik), setelah itu kebijakan PoW resmi dihapus

---

Gambaran umum dan tujuan

• Pada Mei 2025, William Liu dan Savy Dicanosa dari tim Crusaders of Rust menemukan kerentanan use-after-free di Linux dan mengikuti kompetisi kernelCTF milik Google
• Tulisan ini membahas proses optimasi untuk menyelesaikan verifikasi PoW (Proof of Work) secepat mungkin agar bisa melakukan submission lebih cepat daripada tim-tim global lain dalam persaingan bounty yang terbatas

Proses submission kernelCTF dan latar persaingan

• kernelCTF adalah kompetisi dengan hadiah besar, sehingga tim keamanan profesional dari seluruh dunia ikut serta dengan fokus penuh pada otomatisasi submission dan optimasi PoW
• Setiap kali jendela submission dibuka (setiap 2 minggu), hanya satu tim tercepat yang mendapatkan hadiah
• Prosedur submission:
  • Mengakses server tepat waktu
  • Menyelesaikan PoW yang memakan beberapa detik
  • Menunggu VM selesai boot
  • Menjalankan kode exploit dan memperoleh flag
  • Mengirim Google Form
• Belakangan sempat ada rekor submission flag yang berhasil dalam 4,5 detik, tetapi karena PoW dan boot VM saja sudah memakan 6,5 detik, peningkatan kecepatan penyelesaian PoW menjadi tugas yang wajib diselesaikan

Analisis algoritme PoW (VDF-Sloth) dan optimasi pertama

• PoW kernelCTF menggunakan sloth VDF, yaitu verifiable delay function berbasis komputasi sekuensial
  • Untuk bilangan bulat 1280-bit x, dilakukan operasi berulang kuadrat modular & pembalikan bit
• Pada implementasi lama (Python+gmpy dan Rust), paralelisasi multi-core memang tidak membantu, dan GMP sendiri sudah cukup teroptimasi
• Namun, dengan memanfaatkan fakta bahwa operasi modulo berbasis bilangan Mersenne (2^1279-1), mereka berhasil meningkatkan performa menjadi 1,9~1,4 detik lewat implementasi modular manual C++ yang lebih cepat

Peralihan besar ke AVX512 dan implementasi supercepat berbasis SIMD

• Setelah itu, perhatian diarahkan ke ISA AVX512, khususnya AVX512IFMA (instruksi perkalian 52-bit dan akumulasi)
• Bilangan 1280-bit dipecah menjadi limb 52-bit untuk memaksimalkan akselerasi SIMD (25 limb → memakai 4 register zmm)
• Mereka berulang kali melakukan tuning level rendah seperti simetri pada operasi modular square, mask akumulasi, memory broadcast, optimasi penempatan register, dan perbandingan tanpa branch
• Dengan menggunakan ASM (inline assembly) untuk mencegah register spill/reload yang tidak efisien dari compiler, serta optimasi broadcast dan masking, kecepatan akhir berhasil didorong hingga 0,21 detik

Otomatisasi submission PoW dan skenario kompetisi nyata

• Pada submission final, mereka menggunakan server Zen 5 Google Cloud (wilayah Amsterdam) untuk meminimalkan latensi jaringan hingga ke Google Form
• Dengan program submission otomatis (patch pada request POST Google Form dan optimasi lewat kolaborasi internal tim), mereka berhasil mengirim flag hanya dalam 3,6 detik, rekor tercepat sepanjang sejarah
• Secara resmi, pengelola kernelCTF kemudian mengumumkan penghapusan kebijakan PoW, sehingga kompetisi optimasi PoW berakhir dan teknik mereka pun bisa dipublikasikan

Detail implementasi lanjutan

Optimasi operasi modular

• Operasi modulo 2^1279-1 (Prime) diganti dengan beberapa bit shift dan operasi aritmetika sederhana, sehingga operasi modular menjadi jauh lebih cepat dibanding GMP standar

Big-int squaring berbasis AVX512IFMA

• Memanfaatkan instruksi akumulasi perkalian 52-bit AVX512 (vpmadd52luq, vpmadd52huq) untuk perkalian dan akumulasi paralel atas kelompok 8 limb
• Karena strukturnya terdiri dari 25 limb, data dibagi ke 4 zmm, dan dirancang logika untuk meminimalkan masking/akumulasi yang tidak perlu

Tata letak data dan pemanfaatan register

• Bottleneck SIMD diatasi lewat unit per offset, tata letak data bertingkat, dan penataan ulang antar-register (valignq, broadcast)
• Dengan menggandakan accumulator, mereka memperoleh throughput maksimum tanpa menunggu unit perkalian menganggur
• Bahkan carry propagation pun hanya dilakukan seminimal mungkin sesuai kebutuhan

Otomatisasi submission final dan kolaborasi

• Penempatan anggota tim dilakukan untuk menyerang kampanye pada jam-jam dini hari, sambil mengoptimalkan lokasi jaringan dan eksekusi exploit
• Pada submission nyata, seluruh proses otomatis dilakukan secara konsisten, mulai dari penyelesaian PoW, eksekusi exploit, penyisipan flag, hingga request POST ke Google Form

Kesimpulan dan makna

• Optimasi PoW kernelCTF adalah pekerjaan yang menuntut pemahaman anatomis hardware, dari level bit hingga memori, register, dan CNN
• Setelah kebijakan PoW dihapus, fokus persaingan menjadi semata-mata pada kecepatan jaringan/eksploit murni
• Kasus ini menunjukkan pertemuan antara hacking dunia nyata dan komputasi performa tinggi, sekaligus memperlihatkan bahwa pengetahuan optimasi algoritme dan kode open source ke depan akan terus berkontribusi bagi komunitas peneliti

Referensi dan lampiran

• Seluruh kode algoritme PoW dan fungsi konversi (GMP <-> array 52-bit), operasi modular berbasis SIMD, serta kode tuning ASM telah dipublikasikan
• Meski merupakan kode yang “kasar” dan dikembangkan secara intensif selama sekitar 12 jam untuk langsung dipakai di lapangan, kode tersebut dirilis dengan lisensi GNU AGPL 3.0
• Untuk pertanyaan atau kolaborasi terkait VDF, dapat menghubungi Discord(@forevermilk)

[GN⁺]

Komentar Hacker News

• Tim yang menang dengan waktu 3,6 detik dan peringkat kedua mencatat 3,73 atau 3,74 detik; ada dugaan peringkat kedua juga mengoptimalkan PoW atau mungkin memakai FPGA. Dibandingkan kiriman FPGA lama yang butuh lebih dari 4 detik, terasa sayang penulis tidak menyebut bahwa catatan peringkat kedua minggu ini juga mungkin termasuk rekor sepanjang masa.

• Kesan saya, metode ini sangat mirip dengan cara yang dipakai pada implementasi RSA yang dioptimalkan untuk AVX-512, karena RSA juga membutuhkan operasi perpangkatan yang sangat besar. Makalah ini (https://dpitt.me/files/sime.pdf) membahas teknik windowing dan bahwa ukuran window bisa disesuaikan secara arbitrer. Tambahan pada implementasi RSA AVX-512 adalah hasil perkalian disimpan dalam tabel pada rentang [0..2^{window-size}) agar hasilnya bisa dipakai pada tiap window. Contoh nyata bisa dilihat di rsaz-2k-avx512.pl pada kode aws-lc.

  • Andai melihat hal seperti ini lebih awal, mungkin bisa jadi referensi saat pengembangan. Di Zen 5, pemanfaatan register zmm diharapkan memberi throughput perkalian 2x. Pada kode lama, register mask diubah menjadi GPR, dan itu tidak efisien di Zen 4/5. Saya juga bertanya-tanya apakah propagasi carry memang harus dilakukan sekaligus. Dalam praktiknya, kode itu mengulang dengan asumsi carry hanya muncul sekali, yang membantu mengurangi latensi pada kebanyakan situasi. Namun, masih ada kemungkinan serangan timing akibat branch.

• Soal klaim bahwa AVX512 didukung di CPU konsumen selama beberapa generasi, saya ingat sebelum Rocket Lake (generasi ke-11), AVX512 hanya tersedia di lini enthusiast, Xeon, dan sebagian prosesor mobile. Setelah generasi ke-12 dan masuknya P/E-core, fitur itu dinonaktifkan dalam beberapa bulan lalu menghilang. Ada prediksi bahwa jika AMD sukses dengan AVX512, Intel akan mengadopsinya lagi. Saya sendiri memakai i9-11900.

  • CPU P-core generasi ke-12 bahkan tidak benar-benar mendukung atau mengiklankan AVX512, dan secara bawaan dimatikan. Karena ruang untuk E-core, AVX512 praktis tidak disertakan di seluruh CPU. Yang sempat mungkin hanya akal-akalan lewat opsi BIOS: mematikan E-core lalu mengaktifkan AVX512 pada core yang tersisa. Tapi konsekuensinya harus mengorbankan E-core.
  • Dalam whitepaper teknologi Intel AVX10 terbaru (https://cdrdv2.intel.com/v1/dl/getContent/784343), AVX 512-bit ditetapkan sebagai standar baik untuk P-core maupun E-core. Ini keluar dari konfigurasi yang dibatasi 256-bit, dan mengisyaratkan kembalinya AVX-512 secara serius bukan hanya di server tetapi juga pada CPU konsumen mendatang. Ini bisa ditafsirkan sebagai upaya Intel mengejar perluasan AVX-512 oleh AMD.

• Ada yang mempertanyakan esensi lomba CTF ini: alih-alih balapan kecepatan submit, mungkin lebih baik semua tim yang mengirim flag dalam jendela submit tertentu berbagi hadiah.

  • Keberatan terhadap model itu adalah peserta bisa memilih menahan informasi exploit alih-alih segera mengungkapkannya, demi menantang ronde berikutnya, sehingga memunculkan metagame yang menghambat pelaporan langsung. Ada juga kekhawatiran efek samping berupa kompetisi yang tidak konstruktif, seperti strategi waktu submit.
  • Disebut juga bahwa struktur metagame akan berubah, dan justru bisa mengurangi motivasi berpartisipasi sehingga makin banyak orang tidak mempertimbangkan submit ke kernelCTF.

• Kalau saya memahaminya dengan benar, ada proof of work 4 detik dan struktur pembayaran sebulan sekali; saya jadi penasaran apakah memang sebanyak itu exploit muncul setiap bulan sampai persaingannya seintens ini.

  • Server dibuka tiap dua minggu, dan PoW dimaksudkan untuk memberi sedikit jeda agar tidak terjadi terlalu banyak permintaan koneksi. CTF publik kadang memang cukup sengit sampai ada upaya mirip DDoS. Setelah itu Google menghapus tahap proof of work.
  • Ada klaim bahwa mitos tentang keamanan kernel Linux pada kenyataannya hanyalah ilusi.
  • CTF kali ini bukan remote code execution, melainkan exploit privilege escalation (naik dari pengguna biasa ke root), dan bug privilege escalation memang sangat umum.

• Tantangannya luar biasa, tetapi kompleksitas rintangan untuk menang dan nuansa konyolnya terasa mencolok; ada ungkapan lucu bahwa situasinya seperti mesin Rube Goldberg.

• Jika ingin tahu lebih banyak soal base-52 yang disebut di artikel, disarankan melihat posting yang sedang panas hari ini (https://news.ycombinator.com/item?id=44132673).

• Kesan singkat: matematika itu keren.

• Diperkenalkan sloth, sebuah VDF (Verifiable Delay Function) yang dipakai untuk proof of work: ia menuntut serangkaian komputasi panjang untuk membuktikan berlalunya waktu, tetapi hasilnya bisa diverifikasi dengan cepat. Karena komputasinya bersifat serial, runtime tidak bisa dipersingkat walaupun memakai banyak core. Ada rasa penasaran apakah bidang seperti ini bisa menjadi pasar baru bagi produsen CPU. Bahkan ada usulan instruksi khusus untuk iterasi dan hasil sloth, plus fitur anti-overclock berbasis hardware. Ide lain adalah CPU memantau uptime lalu menandatanganinya bersama challenge; ini mirip konsep proof of stake yang tetap memungkinkan CPU dipakai produktif sambil membuktikan kepemilikan CPU selama n detik.

• Saya penasaran bagaimana fungsi Python di blog itu ekuivalen dengan implementasi PoW Google; rasanya sulit diikuti.

  • Di kode Google, exponent = (p + 1) // 4 bernilai 2^1277, sehingga untuk menaikkan suatu bilangan ke eksponen sebesar itu perlu melakukan kuadrat 1277 kali, dan fungsi Python tersebut memang mengimplementasikan itu. Jika nilai awalnya x, maka setiap operasi kuadrat menggandakan jumlah perkalian, sehingga pada akhirnya menjadi 2^1277; penjelasannya seperti itu.