- Crusaders of Rustチームは、Linux packet schedulerの CVE-2025-38001 エクスプロイトを提出しようとしていたが、kernelCTFの先着順という仕組みのため、バグそのものよりも PoWの短縮が勝負どころになった
- 提出プロセスは、12:00 UTCに接続、約4秒のPoW、約2.5秒のVM起動、エクスプロイト実行、Google Form提出という流れで、前回ラウンドの4.5秒での提出記録がボトルネックを明らかにした
- 対象のPoWは「sloth」という VDF で、1280ビット整数に対して
2^1279 - 1 を法とする累乗を繰り返す逐次計算であり、CPU/GPUコアを増やす方法では短縮が難しかった
- GMP/C++とMersenne剰余削減で1.9秒、
-march=native の静的リンクで約1.4秒まで短縮した後、AVX512IFMA の52ビット整数 fused multiply-add により、Ryzen 9950Xで約0.21秒まで短縮した
- 2025年5月16日、チームはZen 5 Google Cloudサーバーと最適化されたPOST提出経路により、3.6秒 でフラグを提出し、5月28日にkernelCTFはPoWの廃止を発表した
競争条件: 問題はバグより速い提出だった
- 2025年5月、Crusaders of RustチームのWilliam LiuとSavy Dicanosaは、Linux packet schedulerのuse-after-freeバグ CVE-2025-38001 を発見し、エクスプロイトを開発した
- Williamは修士論文のためにLinuxをファジングしている最中にバグを見つけた
- Savyはエクスプロイトの実行時間を約0.55秒まで短縮した
- Google kernelCTF は2週間ごとにUTC正午に提出ウィンドウを開き、サーバーをエクスプロイトしてフラグをGoogle Formに最初に提出したチームだけが報酬を受け取る仕組みだった
- 提出は常に同じ順序で進む
- 12:00:00 UTCにkernelCTFサーバーへ接続
- proof of workの解決、約4秒
- インスタンス起動待ち、約2.5秒
- エクスプロイトのアップロードと実行
- フラグをGoogle Formに提出
- 予想バウンティは $51,000 だった
- 基本報酬 $21,337
- 実行安定性報酬 $10,000
- 0-dayバグ報酬 $20,000
以前の提出記録が明らかにしたPoWのボトルネック
- 2025年5月2日の提出ウィンドウでは、最初の提出は正午から 4.5秒 後に届いた
- PoW約4秒とVM起動約2.5秒だけを合わせても6.5秒が必要なため、4.5秒という記録は単純計算と合わなかった
- kernelCTFサーバーコードの丸め処理の特性により、VMインスタンスは実際には11:59:59に起動しており、時間上の矛盾は解消された
- それでもフラグ生成のタイムスタンプは、勝利チームがPoWを 1秒未満 で解いていたことを示していた
- 競合チームが FPGA を使っていたなら、1秒未満のPoWも可能だったかもしれない
- FPGAは特定の作業を非常に高速に実行できるカスタムハードウェアである
- 汎用的な作業には適さず、価格とプログラミング難度が高い
sloth VDF: 並列化しにくいPoW
- kernelCTFのPoWは「sloth」という 検証可能遅延関数（VDF） だった
- VDFは長い逐次計算によって時間が経過したことを証明し、結果の証明は比較的高速に検証できる暗号学的プリミティブである
- 計算自体が逐次的なため、CPUやGPUのコアを増やしても実行時間を短縮しにくい
- 最適化対象の中核ループは次の構造だった
difficulty=7337- 各difficulty反復ごとに
x = (x * x) % (2 ** 1279 - 1) を1277回実行
- その後、
x の最下位ビットを反転
- Googleの基準実装はPythonで gmpy を使っており、gmpyはGMPへのPythonバインディングである
- GMPは、プラットフォーム別の加算・乗算カーネルをアセンブリで実装した多倍長整数ライブラリである
GMPベースの第1次最適化
- 最初の最適化は、
2^1279 - 1 が Mersenne数 である点を利用した剰余削減だった
- 2560ビットの中間積を下位1279ビットと上位ビットに分けて加算する
- 結果がモジュラス以上なら1回引く方法で
% 演算を置き換える
- Python FFIのオーバーヘッドを減らすためC++へ移植し、このバージョンはM1 MacBook Proで 1.9秒 で実行された
- Williamはlibgmpをローカルで
-march=native によりコンパイルして静的リンクし、Intel Ice LakeノートPCで約 1.4秒 まで短縮した
- Rustで書かれた同様の最適化ソルバーは同じMersenne手法を使っていたが、約2.4秒かかった
- その後FLINTも試したが、GMPと速度はほぼ同じだった
AVX512IFMAで大きな整数の平方を再実装
- AVX512 はIntel x86 ISA拡張で、ベクトルレジスタの数と幅を増やし、マスク予測と複数の新命令を追加する
- IntelはAlder Lake以降、クライアントCPUでAVX512対応を無効化した
- サーバー領域では対応が続き、AMDはZen 4とZen 5でコンシューマーCPUとサーバーCPUの両方にAVX512を実装した
- 核心は AVX512IFMA だった
vpmadd52luq: 52ビット積の下位半分を64ビットアキュムレータに加算vpmadd52huq: 52ビット積の上位半分を64ビットアキュムレータに加算
- これらの命令は52×52→104ビット積の下位・上位部分を計算し、ベクトルレジスタに累積する
- Zen 5は512ビットのデータパスを持っているため、この命令をクロックあたり2個開始できた
- 自然な基数は
2^52 で、1280ビット整数は 25個の52ビットlimb で表現される
- 1つの512ビットzmmレジスタには8個のlimbを格納できる
- 全体の値は4つのzmmレジスタに収まる
乗算の配置とMersenne剰余削減
- 1280ビット平方は、25個の52ビットlimbを平方して50個のlimbからなる中間結果を作る方式で実装された
- 平方の対称性を利用して、必要な乗算数をほぼ半分に減らした
- 対角成分
ai^2
i < j の交差項 2 * ai * aj
- 交差項の計算では、連続する8個のlimbの スライディングウィンドウ を単一のmultiplier limbと掛け合わせ、シャッフルを減らした
- AVX512のmerge maskingにより、最終和に含まれない乗算は累積しないように処理した
- 剰余削減は、上位1279ビットを下位1279ビットに加算する方法で行った
- アキュムレータ要素が
2^52 - 1 を超える可能性があるため、carry伝播は加算後まで遅らせる
- 結果が
2^1279 - 1 以上かどうかは、1280番目のビットが1かどうかで判断する
2^1279 - 1 を引くことは、1280番目のビットを消して最下位limbに1を加えることと同じである
- 最後の段階には、ごく小さなoverflowの可能性が残っていた
- 最後のlimbがちょうど
2^52 - 1 の場合、carry伝播が必要になる
- ランダムなPoW基準での発生確率は実行あたり約20億分の2と見なし、無視した
0.45秒から0.21秒まで縮めた細かな最適化
- 最初のAVX512IFMAバージョンは、借りた Ryzen 9950X でPoWを約0.45秒で処理した
- multiply-add命令はレイテンシが4サイクルで、クロックあたり2個を開始できるため、乗算ユニットを飽和させるには少なくとも8個のアキュムレータが必要だった
- 既存ではアキュムレータが7個しかなかった
- 下位半分用7個と上位半分用7個、合計14個のアキュムレータを使い、最後に合算する方式へ変更した
- この変更で約 0.32秒 まで短縮された
- GCCとclangはループをアンロールする際に
vbroadcastsd zmm, m64 を生成し、レジスタ割り当ての過程でベクトルレジスタが不足してstack spillとreloadが発生した
- インラインアセンブリで
vpmadd52luq/vpmadd52huq が memory broadcast operand を使うよう強制した
- multiplier limbを別のベクトルレジスタに入れず、メモリから読み出してすべてのベクトル要素へ複製する
- このbroadcast loadはベクトルALU資源を使わず、load unitで処理される
- この段階で約 0.23秒 まで短縮された
- 整数をメモリにアラインして保存した後、非アラインロードでwindowを作る方式は store-forwarding stall を引き起こした
valignq でzmmレジスタ内の非アラインロードを模倣し、メモリアクセスを減らした- 最終的なPoW時間は約 0.21秒 になった
2025年5月16日の提出結果
- チームは2025年5月16日午前4:30 PSTに最終提出の準備をした
- Google Form提出サーバーと地理的に近いオランダの Zen 5 Google Cloudサーバー を使い、レイテンシを減らした
- 提出の数分前には、ダミーフラグでGoogle Form POSTリクエストを傍受して記録しておいた
- Bryce CasajeとLarry YuanがForm提出プログラムを設計・最適化した
- Max Caiも開発と提出を支援した
- 5:00にサーバーがkernelCTFサーバーに接続し、PoWを解き、Savyの最適化エクスプロイトを実行した後、フラグをPOSTリクエストに挿入して送信した
- 結果は 3.6秒 での提出で、当時のkernelCTF史上最速の提出だった
- kernelCTF運営者は同日、バウンティ資格を確認した
PoW廃止と最終ソルバーの公開
- 2025年5月28日、kernelCTF運営者のkoczkatamasは PoW廃止 を発表した
- PoWがなくなったことで、slot競争はエクスプロイト実行時間とネットワーク遅延時間が中心になった
- この変更により、FPGAやインラインアセンブリ最適化の知識がなくても、専門チームと同じ条件で競争できるようになった
- 最終ソルバーのコードは、2025年5月14〜15日の約12時間の作業の成果であり、GNU AGPL 3.0 で公開された
- ビルド例は
gcc main.c -O3 -march=znver5 -masm=intel -lgmp だった
1件のコメント
Hacker News のコメント
素晴らしい内容です。この方式は AVX-512 最適化 RSA 実装とも非常によく似ています。RSA も非常に大きな指数演算を行う必要があるためです。
この論文[1]は RSA がウィンドウ化をどう行うかを扱っており、ウィンドウサイズが任意であり得ることを示す公式も含んでいます。AVX-512 RSA 実装ではさらに、[0..2^{window-size}) の範囲の乗算結果をテーブルに保存しておき、各ウィンドウごとにその結果をテーブル[2]から取り出した後、シフト/並べ替えだけを行います。
https://dpitt.me/files/sime.pdf（ジャーナルから取ったものなので自分のドメインでホストしています）
https://github.com/aws/aws-lc/blob/9c8bd6d7b8adccdd8af4242e0...
また、マスクレジスタを算術演算のために汎用レジスタへ移していますが、Zen 4/5 では最適ではありません。別件として、桁上がりを本当に一度に伝播させる必要があるのかも気になります。私のコードでは、桁上がりは1回だけ起きると仮定し、必要ならループに戻るようにして、一般的なケースのレイテンシを下げました。ただし分岐があるとタイミング攻撃の問題が出る可能性はあります。
dpitt.me/files/sime.pdfは archive.org にもアップできます: https://archive.org/download/sime_20250531/sime.pdf「コンシューマー向け CPU で何世代にもわたって [AVX512] をサポートしていたにもかかわらず」という部分は少し変です。
Rocket Lake（第11世代）以前は、AVX-512 はハイエンド趣味向け CPU、Xeon CPU、一部のモバイルプロセッサにしかなく、モバイルプロセッサをコンシューマー向け CPU と呼ぶのは微妙です。第12世代では性能/効率コア構成のため、数か月後にそのコアで無効化され、その後は見かけなくなりました。それでも AMD が AVX-512 である程度成功すれば、Intel が再導入する可能性は高いと思います。ちなみに私はまだ Intel i9-11900 を使っています。
その流れで合っています。数か月前の Intel の更新版 AVX10 ホワイトペーパー[1]も、これを裏づけているように見えます。512ビット AVX が P コアと E コアの両方で標準になると明記し、256ビット専用構成から離れるとしています。
これは、AVX-512 がサーバーだけでなく、E コアを持つ将来のコンシューマー向け CPU にも本格的に戻ってくるという強いシグナルに見えます。おそらく AMD によるより広い AVX-512 採用に追いつこうとしているのでしょう。
[1] - https://cdrdv2.intel.com/v1/dl/getContent/784343（PDF）
第12世代の性能コア搭載 CPU は、そもそも AVX512 対応を表示していませんでしたし、デフォルトで有効にもなっていませんでした。
効率コアには面積の都合で AVX512 が入っていなかったため、CPU 全体として AVX512 非対応と見なされました。一部 BIOS オプションの特殊な挙動を利用して効率コアを切り、残った CPU で AVX512 を有効にできただけで、その代償として E コアを諦める必要がありました。
優勝記録は3.6秒でしたが、2位は3.73秒で、優勝記録と同じ桁数にそろえると3.74秒でした。だとすると、2位も Proof of Work を最適化していたか、FPGA を使っていたと見るべきなのでしょうか？
筆者は以前の提出を高価な FPGA ベースだったと説明しているにもかかわらず、4秒以上だったと言っていました。だとすれば、その週の2位が史上2番目に速い提出だった可能性もあったはずで、それについて何か言及していそうなものだと思います。
印象的ですが、最適化対象を間違えているように見えます。CTF が提出運用の勝負になってはいけません。
提出ウィンドウ内にフラグを送ったすべてのチームで賞金を分け合うほうが、全員にとってよいのではないかと思います。
そのため実際には「誤った」行動を積極的に奨励してしまうかもしれません。
理解が正しければ、4秒の Proof of Work があり、賞金は月1回支払われる仕組みです。
本当に毎月人々が競争するほど、エクスプロイトはそんなに多いのでしょうか？
公開 CTF は難しいものです。結局、あるチームはゴールまで走る過程で DDoS に近い行動を取ることになります。その後 Google は Proof of Work のステップを削除しました。
すごい内容ですが、このチャレンジに勝つために越えなければならない障害を見ると、コメディのように読めます。本当に ルーブ・ゴールドバーグ・マシンみたいです。
この記事で言及されている 52進表現 についてもっと知りたいなら、今日のフロントページにある別の記事も見る価値があります: https://news.ycombinator.com/item?id=44132673
細かい指摘ですが、静的リンクはインライン化をしてくれるわけではなく、PLT オーバーヘッドを取り除くだけです。インライン化の機会を増やすのは LTO です。
なぜ競争させるのか理解できません。ユニークなエクスプロイトごとに普通に報奨金を出せばよいのでは？
そして Linux はバグが多すぎるので、すべての 0-day にお金を払い始めると制御不能になります。Google もかつて、人々が溜め込んだバグを吐き出させるため、競争なしの期間限定プロモーションを行い、すべての 0-day を認めたところ、提出が殺到しました。同時にコミュニティを怒らせたくはないので、こういう仕組みになっているのです。
これだけ年月が経っても、専門家が 3秒で Linux マシンを掌握できるというのは少し憂鬱です。