概要
- 2025年5月、Crusaders of RustチームがLinuxのパケットスケジューラのuse-after-freeバグを発見・悪用
- kernelCTFバグバウンティ競争の舞台裏と提出プロセスの高速化戦略
- 証明作業(Proof of Work)として "sloth" VDF の最適化が鍵
- AVX512IFMA命令セットを活用し、VDFソルバーの実装と高速化に成功
- 最終的に高速化によりバウンティ獲得に貢献した経験談
kernelCTFバグバウンティ獲得までの舞台裏
- 2025年5月、 William Liu と Savy Dicanosa がLinuxのパケットスケジューラの use-after-freeバグ を発見
- Williamは自身の修士論文の一環としてLinuxを ファズ してバグを特定
- Savyが エクスプロイト を最適化し、実行時間を約0.55秒に短縮
- GoogleのkernelCTF バグバウンティは、提出枠が厳しく制限される競争型
- 2週間ごとに正午UTCに提出ウィンドウが開き、最初の成功チームのみ報酬獲得
- 提出には Proof of Work(PoW) が必須で、計算に数秒を要する
- 提出手順
- 12:00:00 UTCにサーバーへ接続
- PoWを解く(約4秒)
- インスタンスのブート待機(約2.5秒)
- エクスプロイトをアップロード・実行(約0.55秒)
- Google Formでフラグを提出し、タイムスタンプで勝敗決定
- プロのリサーチチームは FPGA などを使いPoW高速化を図り、4.5秒で提出した事例も観測
- 本来VMブートとPoWだけで6.5秒かかるはずが、サーバーのラウンド処理の癖で1秒早いタイムスタンプが発生
"sloth" VDFの最適化
- kernelCTFのPoWは sloth という VDF(Verifiable Delay Function) を採用
- 1280ビット整数を、難易度回数だけ1277回自乗・Mersenne数で剰余計算・LSB反転
- 直列計算のためマルチコアやGPUでは並列化困難
- 公式実装はPythonのgmpy(GMPライブラリ)を利用
- 最初の最適化
- Mersenne数(2^1279-1)に特化した剰余計算で高速化
- C++への移植でFFIオーバーヘッド除去
- Macbook Proで1.9秒、Intel Ice Lakeで1.4秒まで短縮
- GMPの汎用性によるオーバーヘッドがボトルネックとなり、さらなる高速化が課題
AVX512IFMAによる超高速化
- AVX512 はx86向けSIMD拡張命令セットで、特に AVX512IFMA は大整数演算を高速化
- 52ビット×52ビットの積和演算を512ビットレジスタで並列処理
- Zen 5等の最新CPUでクロック毎に2命令実行可能
- 実装戦略
- 1280ビット整数を52ビット×25リムブ(limb)に分割し、4つのzmmレジスタで管理
- 自乗計算は対称性を利用し、必要な積の回数を半減
- AVX512IFMAの低位・高位積和命令(vpmadd52luq, vpmadd52huq)を活用
- メモリシャッフルやマスク機能を駆使し、無駄な演算を最小化
- 実装は2日間で完遂し、従来のGMPベース実装を大幅に上回る性能を達成
- kernelCTFのPoWを 最速で突破 し、競合に先んじてバウンティ獲得に貢献
まとめ
- バグ発見だけでなく、 提出プロセス全体の最適化 がバグバウンティ競争の勝敗を分ける時代
- VDFやPoWの高速化 には数学的知識とハードウェア最適化技術が不可欠
- AVX512IFMA のような最新CPU機能を活用することで、従来の限界を突破可能
- kernelCTFのような競争型バウンティでは、 技術力・戦略・実装速度 の総合力が求められる