GoogleのkernelCTF PoWをAVX512で打ち破った方法

 (anemato.de)
2 ポイント 投稿者 GN⁺ 2025-05-31 | 1件のコメント | WhatsAppで共有
  • チーム Crusaders of Rust が Linuxパケットスケジューラのuse-after-freeバグ を発見し、エクスプロイトを開発
  • Google kernelCTF大会で 高速なPoW（Proof of Work）解法の必要性 から高性能最適化を試みた
  • AVX512IFMA命令を活用した独自アセンブリおよびSIMD最適化 により、既存のPython/GMPおよびRust実装に比べて約7倍の速度を達成
  • 動作原理、モジュラ演算、メモリ管理、レジスタ活用 まで細かくチューニングし、PoW処理時間を0.21秒まで短縮
  • 最終的に 史上最短時間（3.6秒）でkernelCTFへの提出に成功 し、その後PoWポリシーは正式に廃止された

概要と趣旨

  • 2025年5月、Crusaders of Rust チームのWilliam LiuとSavy DicanosaはLinuxの use-after-free脆弱性 を発見し、Googleの kernelCTF 大会に参加した
  • この記事は、PoW（Proof of Work）検証を高速に解き、制限のあるバウンティ競争で他の世界中のチームより速く提出するための 最適化プロセス を扱っている

kernelCTF提出プロセスと競争の背景

  • kernelCTFは 高額報奨金 のため、世界中の 専門セキュリティチーム が提出自動化とPoW最適化に全力を注いで参加する大会である
  • 提出ウィンドウ（2週間ごとにオープン）ごとに、最速の1チームだけが賞金 を受け取る
  • 提出手順:
    • 定刻にサーバーへ接続
    • 数秒かかるPoWの解答
    • VMの起動待ち
    • エクスプロイトコードの実行とflagの取得
    • Googleフォームの送信
  • 最近では4.5秒でflag提出に成功した記録もあったが、PoWとVM起動だけでも6.5秒かかるため、PoW解法の高速化が必須課題だった

PoW（VDF-Sloth）アルゴリズム分析と最初の最適化

  • kernelCTFのPoWは sloth VDF という逐次計算ベースの verifiable delay function を使っている
    • 1280ビット整数 x に対して モジュラ平方 & ビット反転 の反復演算
  • 既存実装（Python+gmpyおよびRust）でも、すでにマルチコア並列化は効果がなく、GMPも十分最適化されていた
  • しかし、モジュロ演算が Mersenne 数（2^1279-1）ベースである点を活用し、より高速なC++手書きモジュラ実装によって1.9〜1.4秒まで性能向上に成功した

AVX512IFMAへの大転換とSIMDベース超高速実装

  • その後、AVX512 ISA、とりわけ AVX512IFMA（52ビット乗算および積和命令） に着目
  • 1280ビット数を52ビット limb に分割し、SIMD高速化 を最大化した（25 limb → 4個のzmmレジスタを活用）
  • モジュラ平方演算の対称性、積和マスク、メモリブロードキャスト、レジスタ割り当て最適化、ブランチレス比較など、低レベルチューニング を繰り返した
  • ASM（インラインアセンブリ）を使ってコンパイラの非効率なレジスタ spill/reload を防ぎ、ブロードキャストとマスキング最適化で 最終的に0.21秒 まで高速化した

PoW提出自動化と実際の大会シナリオ

  • 最終提出では Zen 5 Google Cloudサーバー（アムステルダムリージョン）を利用し、Googleフォームまでのネットワーク遅延も最小化した
  • 自動提出プログラム（GoogleフォームPOSTリクエストのパッチ、チーム内協業による最適化）により、史上最短記録の3.6秒 でflag提出に成功した
  • kernelCTF運営は正式に PoWポリシーの廃止 を発表し、PoW最適化競争から解放されると同時に手法を公開できるようになった

高度な実装詳細

モジュラ演算の最適化

  • 2^1279-1（prime）モジュロ演算をビットシフトと数回の四則演算に置き換え、標準GMPに比べて非常に高速なモジュラ演算を実現

AVX512IFMAベースの多倍長整数平方

  • AVX512の52ビット乗算積和命令（vpmadd52luq, vpmadd52huq）を活用し、8個の limb 束の並列乗算と積和を実行
  • 25 limb 構造のため4個のzmmに分散し、不要なマスキングや積和を最小化するロジックを設計

データ配置とレジスタ活用

  • オフセットごとのユニット、階段状のデータ配置、レジスタ間再配置（valignq、ブロードキャスト）などでSIMDボトルネックを解消
  • アキュムレータを2倍に増やして乗算ユニット待ち（レイテンシ）なしで最大スループットを確保
  • キャリープロパゲーションも必要最小限だけ実行

最終提出の自動化と協業

  • 深夜帯のキャンペーン成功に向けたチームメンバー配置、ネットワーク位置とexploit実行の最適化
  • 実際の提出では、PoW解答、エクスプロイト実行、flag挿入、Google Form POSTリクエストまで一貫して自動化を実施

結論と意義

  • kernelCTF PoW最適化は、ビットレベルからメモリ、レジスタ、CNN までハードウェアを解剖するような理解 を要する作業である
  • PoWポリシーがなくなったことで、競争の焦点は「純粋なネットワーク/エクスプロイト速度」のみに移った
  • 本事例は 実戦ハッキングと高性能コンピューティングの出会い を示すと同時に、今後もアルゴリズム最適化ノウハウとオープンソースコードが研究者コミュニティに貢献していくことを示している

参考と付録

  • PoWアルゴリズム全体のコードと変換関数（GMP <-> 52ビット配列）、SIMDベースのモジュラ演算、ASMチューニングコードがすべて公開された
  • 約12時間にわたって集中的に開発し実戦投入した「荒削り」なコードだが、GNU AGPL 3.0ライセンスの下で公開されている
  • 質問やVDF関連の協業についてはDiscord（@forevermilk）で連絡できる

関連記事

1件のコメント

 
GN⁺ 2025-05-31
Hacker Newsの意見

  • 3.6秒で優勝したチームと2位は3.73秒または3.74秒という記録で、2位もPoWを最適化していたか、あるいはFPGAを使っていた可能性があるのではないかと思う。以前の4秒超のFPGA提出と比べると、著者が今回の2位記録も歴代級の記録かもしれないと触れてくれていればよかったのに、という惜しさが残る

  • この方法は、AVX-512に最適化されたRSA実装で使われるやり方と非常によく似ている印象がある。RSAでも非常に大きな冪乗演算が必要だからだ。論文(https://dpitt.me/files/sime.pdf)ではウィンドウィング手法と、ウィンドウサイズを任意に調整できることが扱われている。AVX-512のRSA実装では、乗算結果を[0..2^{window-size})の範囲でテーブルに保存し、各ウィンドウごとに結果を使う点が追加される。実例はaws-lcコードの rsaz-2k-avx512.plで確認できる

    • こういう内容を先に見ていれば開発の参考になったのに、という惜しさがある。Zen 5ではzmmレジスタ活用により2倍の乗算スループットが期待できる。既存コードではマスクレジスタがGPRに変換されるが、Zen 4/5ではこれは非効率だ。キャリー伝播は本当に一度に行う必要があるのか疑問だ。実際、コードではキャリーが1回しか発生しないと仮定して繰り返しており、これは大半の状況でレイテンシ削減に役立つ。ただし、ブランチによるタイミング攻撃の可能性は残る

  • AVX512が複数世代にわたってコンシューマ向けCPUでサポートされてきたという主張については、Rocket Lake（第11世代）まではAVX512はエンスージアスト向け、Xeon、一部のモバイルプロセッサでしか利用できなかったと記憶している。第12世代でP/Eコアが導入されて以降は、数か月で無効化されて消えた。AMDがAVX512で成功すればIntelが再導入するだろう、という予想もある。自分はi9-11900を使っている

    • 第12世代のPコアCPUは、そもそもAVX512対応をうたってもおらず、標準では無効化されていた。Eコアのスペースの都合で、CPU全体としてAVX512は非搭載だった。ただしBIOSオプションの裏技でEコアを無効化し、残りのコアでAVX512を有効にすることはできた。その代わりEコアを諦める必要があった点が言及されている
    • 最近のIntel AVX10技術ホワイトペーパー(https://cdrdv2.intel.com/v1/dl/getContent/784343)では、PコアとEコアの両方で512ビットAVXを標準として提示しており、256ビット限定構成から脱して、AVX-512がサーバーだけでなく今後のコンシューマCPUにも本格復帰することを予告している。これはAMDのAVX-512拡大にIntelが追随しようとしているものと解釈できる

  • CTF大会の本質に疑問がある。提出速度を競うのではなく、一定の提出ウィンドウ内にフラグを提出したチーム全員で賞金を分け合う方式のほうがよいのではないか、という意見

    • この方式だと、参加者がエクスプロイト情報をすぐに公開せず、その後のラウンド挑戦のために保留してしまい、即時報告を妨げるメタゲームを生む可能性があるという指摘がある。また、提出タイミングの戦略など、非建設的な競争を誘発する副作用も懸念される
    • メタゲームの構造が変わり、むしろ参加意欲が下がってkernelCTFへの提出を考えない人が増える可能性も言及されている

  • 自分の理解が正しければ、4秒のproof of workと月1回の支払いという仕組みらしいが、毎月これほど多くのエクスプロイトが現れて激しく競争しているのか気になる

    • サーバーは2週間ごとに開いており、PoWは過剰な接続リクエストを防ぐために少し遅延を与える目的だった。公開CTFは、しばしばDDoSまがいの作戦が試みられるほど熾烈だ。その後Googleはproof of workの段階を削除した
    • Linuxカーネルのセキュリティに関する神話は、実際には幻想にすぎないという主張
    • 今回のCTFはリモートコード実行ではなく、権限昇格（一般ユーザーからrootへの昇格）エクスプロイトに該当する。権限昇格バグは本当にありふれている

  • 驚くべき挑戦ではあるが、優勝までの障害物の複雑さとばかばかしさが印象的で、まるでルーブ・ゴールドバーグ・マシンのようだという面白い表現

  • 本文で触れられていたbase-52関連の内容をもっと知りたいなら、今日話題になっていたこの投稿(https://news.ycombinator.com/item?id=44132673)の参照がおすすめ

  • 数学はすごい、という感想

  • proof of workに使われたslothというVDF（Verifiable Delay Function）の紹介。長い一連の計算を要求して時間の経過を証明し、その結果は素早く検証できる。計算は直列的なので、複数コアを動員しても実行時間を短縮できない。こうした分野がCPUメーカーにとって新たな市場になりうるのか気になる。slothの反復と結果に対する専用命令や、ハードウェアベースのオーバークロック防止機能の搭載も提案されている。CPUのuptimeを監視し、チャレンジと一緒に署名する方式もアイデアとして示されており、これはCPUを生産に活用しつつ、n秒間のCPU所有権を証明するproof of stakeに似た概念だ

  • ブログに出てきたPython関数が、GoogleのPoW実装とどう等価なのか気になる。追うのが難しいという印象

    • Googleのコードで"exponent = (p + 1) // 4"が2^1277であること、数値をそのような巨大な指数まで持ち上げるには1277回の二乗が必要で、Python関数が実際にそれを実装している、という説明。初期値がxなら、各二乗のたびに指数は2倍になって最終的に2^1277になり、そういう原理だということだ