世界を動かす技術を、日本語で。

AVX512を使用してGoogleのkernelCTF PoWを打破する

概要

  • 2025年5月、Crusaders of RustチームがLinuxのパケットスケジューラのuse-after-freeバグを発見・悪用
  • kernelCTFバグバウンティ競争の舞台裏と提出プロセスの高速化戦略
  • 証明作業(Proof of Work)として "sloth" VDF の最適化が鍵
  • AVX512IFMA命令セットを活用し、VDFソルバーの実装と高速化に成功
  • 最終的に高速化によりバウンティ獲得に貢献した経験談

kernelCTFバグバウンティ獲得までの舞台裏

  • 2025年5月、 William LiuSavy 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のような競争型バウンティでは、 技術力・戦略・実装速度 の総合力が求められる

Hackerたちの意見

ここで実装されているプルーフ・オブ・ワークは、「スロス」と呼ばれる特定の検証可能な遅延関数(VDF)です。VDFは、長い直列計算を要求することで、非自明な時間が経過したことを証明する暗号的なプリミティブです。この計算は、比較的早く検証できる証明を出力します。計算が直列であるため、より多くの計算リソース(例えば、より多くのCPUやGPUコア)にスケールしても、実行時間は短縮されません。こういうのって、CPUメーカーにとって市場のチャンスかも?特別な命令を2つ追加して、1つはシード値を使ってスロスを繰り返す命令、もう1つは結果を暗号的に署名して、このCPUモデルで生成されたことを証明する命令にするとか。オーバークロックを防ぐためにハードウェアのレート制限を設けるのもいいかもね。もう1つのアイデアは、CPUの稼働時間を監視して、その稼働時間とチャレンジを署名すること。署名後に稼働時間はクリアされる。これは、CPUの所有権をn秒捧げたことを証明する、ステークの証明に近い感じで、CPUを他の用途に生かしつつ使えるようにするってこと。

つまり、正しく理解してれば、4秒のプルーフ・オブ・ワークで、月に1回の報酬があるってこと?本当にそんなに多くのエクスプロイトがあって、みんな毎月それを取り合ってるの?

そう、Linuxカーネルのセキュリティの神話は、ただの神話だよ。

これはローカル特権昇格のエクスプロイト(通常ユーザーからrootになること)で、リモートコード実行ではないよ。特権昇格のバグは山ほどあるからね。

サーバーは2週間ごとにオープンしてたよ。作業証明は接続を少し遅くして、できるだけ多くの接続リクエストをスパムするインセンティブを減らすためのものだった。パブリックCTFは難しいんだよね、どうしてもどのチームかがゴールに向かってDDoSに似たことを試みるから。これがあった後、Googleは作業証明のステップを取り除いたんだ。

なんかおかしいなと思うのは、> 「消費者向けCPUで数世代にわたってAVX512をサポートしているにもかかわらず…」ってこと。ロケットレイク(第11世代)以前は、AVX512はエンスージアスト向けのCPUやXeon CPU、あるいは一部のモバイルプロセッサでしか使えなかった(消費者向けCPUとは言えないけど)。第12世代では、そのコアの中で数ヶ月後に無効化されて、二度と見られなくなった。AMDがAVX512で何らかの成功を収めたら、インテルは再導入すると思うけど。ちなみに、今もここでインテルのi9-11900 CPUを使ってるよ。 ;)

修正したよ :) ありがとう!

12世代(そのパフォーマンスコアと効率コアの概念)では、数ヶ月後にそれを無効にしちゃって、それ以降は見かけなくなったんだ。パフォーマンスコアを持つ12世代のCPUは、AVX512のサポートを宣伝すらしてなかったし、初めから有効にもなってなかった。効率コアにはスペースの関係でAVX512が含まれてなかったから、全体のCPUがAVX512を持ってないと見なされてたんだ。効率コアを無効にして残りのCPUでAVX512を有効にするには、BIOSのオプションのちょっとしたトリックを使う必要があった。Eコアを諦める必要があったんだよね。

それは納得できるね。数ヶ月前のIntelの更新されたAVX10ホワイトペーパーがこれを確認しているみたい。512ビットのAVXがPコアとEコアの両方で標準になるって明言してるし、256ビットだけの構成から移行するってさ。これはAVX-512が本格的に復活することを強く示唆してるね、サーバーだけじゃなくて、将来の消費者向けCPUでもEコアと一緒にね。AMDのAVX-512の普及に追いつこうとしてるんだろうね。

すごいね!この方法は、AVX-512最適化されたRSA実装の動きに非常に似てる。RSAも非常に大きな累乗を計算しなきゃいけないから。この記事[1]では、RSAがウィンドウ処理をどうやってるかについて説明していて、ウィンドウサイズが任意であることを示す式も含まれてる。ただ、AVX-512のRSA実装がもう1つやってることは、[0..2^{ウィンドウサイズ})の範囲の乗算結果をテーブルに保存すること。その後、各ウィンドウについて、その結果をテーブルから取り出して、シフトや再配置だけを行うんだ。1. https://dpitt.me/files/sime.pdf (ジャーナルから引っ張ってきたので、私のドメインにホストしてる) 2. https://github.com/aws/aws-lc/blob/9c8bd6d7b8adccdd8af4242e0...

おお、面白いね。開発中にこれを見ておくべきだったな…。そのコードは、例えばZen 5用にもう一つのバージョンが必要そうだね。zmmレジスタを使うことで、2倍の乗算スループットが得られるはず。あと、マスクレジスタが算術用にGPRにバウンスされるけど、Zen 4/5では最適じゃないんだよね。別に、キャリーを一度に伝播させる必要があるのか気になってる。 (少なくとも、そうなってると思うけど?)キャリーインが高位12ビットにあるものを超えて追加のキャリーアウトを引き起こす可能性は非常に小さいから、私のコードではキャリーは一度だけ発生して、必要ならループバックする前提にしてる。それで、一般的なケースでのレイテンシが減るんだ。ただ、分岐があるとタイミング攻撃の問題が出るかもしれないね。

誰か、ブログに載ってたPython関数とGoogleのPOW実装で示されてたものがどう等しいのか教えてくれない?ちょっと追いづらいんだけど。

Googleのコードの「exponent = (p + 1) // 4」は2^1277だよ。そんな巨大な数を累乗するには、1277回平方するんだ(それがPythonの関数がやってること)。最初の値が「x」なら、平方するたびに「x」の数が倍になるから、最後には2^1277になるんだ。

この記事が言及しているベース52表現についてもっと知りたいなら、今日のフロントページにあるこの別の投稿を見てみてね: https://news.ycombinator.com/item?id=44132673

すごいね。でも、なんか間違ったところを最適化してる気がする。CTFは提出のオペレーションじゃなくて、全チームが提出ウィンドウ内にフラグを送ったら、みんなで賞金を分け合う方がいいんじゃないかな。

それは別のメタゲームになるね。深く考えたわけじゃないけど、結果的には人々がやる気を失って、kernelCTFに提出することを考えなくなるんじゃないかな。

それに加えて、これって人々が脆弱性をすぐに報告するんじゃなくて、次回のために温存しちゃうことを助長してる気がする。報告タイミングのトリックがなくても、次回提出できるようにってね。だから、実際に「間違った」ことを促してる可能性もあるよね。

レースの目的がよくわからないな。ユニークなエクスプロイトごとに報酬を出せばいいんじゃない?

ボスがそのクールなプログラムを運営するために厳密な予算を求めてるんだ。これらのプログラムの理由(少なくとも部分的には)は、エクスプロイトや緩和策のダイナミクスを測ることであって、バグを買うことじゃないんだよね。Linuxはバグが多すぎて、0-dayごとにお金を払うと制御が効かなくなる。Googleも一度そうしようとしたけど(人々が蓄えていたバグを引き出すために)、期間限定のプロモーションをやったら、すごい量の応募が来ちゃった。同時にコミュニティを怒らせたくないから、こうなってるんだ。

すごいことだけど、このチャレンジをクリアするための障害がコメディみたいに感じる。まるでルーブ・ゴールドバーグみたいだね。