Randar: LLL格子簡約を利用してサーバーRNGをクラックするMinecraftの脆弱性
(github.com/spawnmason)Here are the key points from the Randar explanation and information, summarized in Markdown format:
Randarエクスプロイトの概要
- Randarは、Minecraft Beta 1.8から1.12.2までのバージョンに対するエクスプロイトで、Minecraftサーバー内で誤って再利用される
java.util.Randomをクラックすることで、他のプレイヤーの位置を明らかにできます - ブロックを壊した際にドロップするアイテムの正確な座標に基づき、LLL格子簡約を使ってRNGの内部状態を特定します
- このエクスプロイトは、2022年10月7日にn0pf0x（pcm1k）によって発見されました
Randarエクスプロイトの仕組み
- Minecraftのコードは、地形生成（Woodland Mansionなど）とゲーム内アクション（ブロック採掘など）の間でRNGを誤って再利用しています
- チャンクが読み込まれると、Woodland Mansionのような構造物を確認し、チャンク座標に基づいてRNGシードをリセットします
- その直後にプレイヤーがブロックを採掘すると、ドロップアイテムの座標はRNGの状態によって決まります
- 格子簡約を使うことで、ドロップアイテムの座標から正確なRNGの内部状態を特定できます
- RNGの状態を逆方向にたどることで、直近で読み込まれたチャンク座標が判明し、プレイヤーの位置が露出します
Randarから隠し拠点を守る方法
- 4 RNGステップ以内に別のリージョンが存在する特定の「おとり」Woodlandリージョンに拠点を建設すると、エクスプロイト利用者を欺けます
- 拠点全体がそのリージョン内に収まるようにし、おとり地点にAFKアカウントを配置すれば、さらに保護効果が高まります
完全なエクスプロイトコードとパッチ適用
- アイテムドロップ座標からRNG状態をクラックし、逆方向にたどってプレイヤー位置を見つけるための完全なJavaコードが提供されています
- 依然として脆弱なバージョンを使っているMinecraftサーバー向けのパッチは、
World.setRandomSeed()関数を変更し、ワールド生成に別のRNGインスタンスを使うようにするものです
n0pf0xによる追加メモ
- n0pf0xは、MasonのGPUハッシュマップ方式に対して、より高速なシードから座標へのルックアップのためにキャッシュシステムを使用しました
- The Endディメンションでヒットを追跡する手法についても説明されており、ここではチャンクが初回生成時にのみRNGへ影響するため、より扱いが難しくなります
- 「End Occupancy Tracker」は、tickごとのRNG呼び出し数に基づいてThe Endにいるプレイヤーを推定し、特定のヒットを引き起こしたプレイヤーの特定を支援します
GN⁺の見解
- Randarは、シードを突き止めることでワールド全域にわたってプレイヤーの位置を漏えいさせうるという点で、深刻なエクスプロイトです。1.13へ更新していない、あるいはパッチを適用していないサーバーでは重大な脅威となりえます
- とくにハッキングを許容するanarchyサーバーでは、チートツールとして悪用される可能性が高く、対策の整備が急務に見えます
- ワールド全域で単一のRNGを使う設計は利便性のためだったのでしょうが、脆弱性が見つかるとゲーム全体に影響しうる構造的欠陥に見えます。予測可能で反復的なシードが必要な部分は、別個のRNGで管理するのが望ましいです
- ただし、1.12以前のバージョンではPoCリプレイからも推測できるため、過去のリプレイで重要な拠点が露出していないか振り返る必要があります
- Minecraftに限らず、他のゲームでもシード再利用に起因する脆弱性が見つかった事例があります。ゲームの中核システムに使われるシードやRNGには細心の注意が必要です。疑似乱数の周期、シードのランダム性、シードの再利用などを点検すべきです
1件のコメント
Hacker Newsのコメント
以下は、Hacker Newsのコメントから要点をまとめたものです。
1999年から2000年の「International RoShamBo Programming Competition」では、「Nostradamus」というボットが、乱数生成器の状態を逆算することで、ランダムなベースラインボットの手を100%の精度で予測して優勝しました。
「Nostradamus」ボットで使われたのと同じアルゴリズムであるLLL格子簡約は、最近のHacker Newsで
tptacekが説明していたように、偏ったnonceからPuTTYの鍵を破ることにも使えます。SciCraftのMinecraftサーバーでは、YouTube動画で実演されているように、ゲームのRNG状態を決定論的に操作する高度な仕組みを使って、より良いアイテムドロップのために毎フレーム「ランダムな」落雷を発生させていました。
このエクスプロイトは、コード内で乱数源同士が相互作用することのリスクを浮き彫りにしており、興味深いと同時に警鐘的だと感じるコメント投稿者もいます。見返りが最も少ない部類に入る一方で、最も高度なエクスプロイトの1つだと考えられています。
Minecraftにおける「何でもありのバグ悪用サーバー」という発想は、仮想的なメタバースでの実際の戦いがどのようなものになるかになぞらえられています。
MinecraftのMOD／ハッキングコミュニティはその高度さで称賛されており、別のYouTube動画ではゲーム内RNGクラッキングの印象的な実例も示されています。
このRNG操作は、弱いTCP ISN RNGの位相空間プロットになぞらえられています。
一部のプレイヤーは、Minecraftの2b2tのような「アナーキー」サーバーを、サーバーが時に人気になりすぎるとしても、このゲーム本来の遊び方だと考えて楽しんでいます。
あるコメント投稿者は、Leijurvという著名なMinecraftゲームハッカーの職業的なバックグラウンドに興味を持っており、その見事なスキルから、インフォセックやアルゴリズム取引の仕事をしているのではないかと推測しています。