- World of Warcraft の Lua アドオン環境は UI を簡単に変更できるようにしたが、ゲーム行動の自動化を防ぐために情報アクセスと実行権限を分離していた
- Blizzard のセキュリティモデルは、情報を多く読める 非保護環境 と行動を実行する 保護環境 を分けており、この境界が自動化防止の中核だった
- 保護環境で許可されていた
random は MSVC の C rand の薄いラッパーで、グローバル状態を共有する弱い 線形合同生成器 だったため、情報伝達チャネルになり得た
- 2 回の RNG 出力だけで内部状態候補を最大 8 個まで絞り込み、追加の出力で単一候補を選んだ後、望む行動インデックスが出るまで RNG を進められた
- 表向きはランダムな行動選択に見えても、実際には望む呪文のような行動を選ばせることができ、その後 Blizzard がどのように修正したのかは定かではない
World of Warcraft のアドオンがプログラミング入門のきっかけに
- World of Warcraft のアドオンは、Lua で書かれた
.lua ソースファイルをいくつかフォルダに入れるだけで、ゲームが直接読み込む仕組みだった
- ファイルを修正して保存し、インターフェースを再読み込みすればすぐに結果を確認できたため、参入障壁 は非常に低かった
- 最初は他人のコードをコピーしてリファクタリングしたり組み合わせたりしながら、欲しい機能を作る形でいくつものアドオンを作っていた
- 時間がたつにつれて実際のゲームプレイよりアドオン作成そのものに多くの時間を使うようになり、World of Warcraft が本格的にプログラミングを始めるきっかけになった
Blizzard のアドオンセキュリティモデル
- ユーザーが完全にプログラム可能なアドオンを作れるようにするとボット問題が生じ得るため、Blizzard は一般プレイヤーが行える自動化を制限する構造を作った
- UI 要素の大半と情報収集 API は制限なく使えた
- たとえばキャラクターの体力を読み取って前景フレームの大きさを調整する ヘルスバー を作れた
- キャラクター移動、呪文詠唱、アイテム使用のように実際のゲーム行動を行う API は保護されており、公式 Blizzard コードからしか呼び出せなかった
- 正確なワールド位置やカメラ方向を得る API も、ある時点から保護対象になった
- ボス戦を簡単にするため、ゲームワールド上に 3D 要素を描画するアドオンへの対策だった
保護環境と非保護環境の分離
- 一部の UI 要素は実際のゲーム行動と相互作用する必要があったため、クリック時に 保護環境 でコードを実行する特殊なボタンを作れた
- こうしたボタンは戦闘中に作成、削除、移動できなかった
- 戦闘中にカーソル下へ条件付きでボタンを配置して行動を自動化する手法を防いでいた
- 保護環境ではどの呪文を唱えるかをプログラム的に設定できたが、任意の自動化に必要な外部状態へのアクセスは遮断されていた
- 許可されていたのはマクロシステム相当の一部の情報収集 API だけで、アビリティの再使用待機時間やユニット体力のように最適な呪文選択に必要な情報は提供されなかった
- 結果として 2 つの環境は異なる権限を持っていた
- 非保護環境: 多くの情報を得られるが行動できない
- 保護環境: 行動できるが自動化に必要な情報を得られない
random がバックドアチャネルになった
- 目的はサードパーティソフトウェアで保護制限を無効化することではなく、技術的に許可された手段だけで保護環境を回避できるか確かめることだった
- 保護環境で許可されている関数一覧を調べているうちに
random を見つけた
- コンピュータの乱数生成器の多くは内部状態を持つ 疑似乱数生成器 なので、その状態を操作できれば外部情報を保護環境へ渡せると判断した
- 実際の
random は C の rand を包んだ小さなラッパーだった
- World of Warcraft は MSVC でコンパイルされていたため、
rand 実装はグローバル状態ベースの生成器だった
uint32_t state;
int rand() {
state = state * 214013 + 2531011;
return (state >> 16) & 0x7fff;
}
- この実装は単一のグローバル乱数状態をプロセス全体で共有しており、弱い 線形合同生成器 だった
MSVC rand の状態復元
rand の出力は、状態の一部である 15 ビットをそのまま露出している- 状態空間が小さく、出力の一部が見えているため、可能な状態候補を保持しながら追加出力で候補を削れる
- より効率的な方法は、2 回の RNG 出力
r0、r1 を観測して隠れた 16 ビットの状態部分の候補を計算することだった
- MSVC
rand の定数は次のとおり
- 1 回目と 2 回目の呼び出し後の隠れた 16 ビット部分をそれぞれ
h0、h1 とすると、状態遷移式から h0 の候補を導けた
- 計算の結果、
k は -1 <= k < 7 の範囲だけ見ればよいため、隠れた状態候補は最大 8 個 まで減った
- その後は追加の RNG 呼び出し結果と候補 RNG の出力を比較して誤った候補を除外した
- 例の Python 実装では
while ループを使っていたが、実際には 3 回目の出力まであれば単一候補へ絞り込めるようだった
- 当時はこの離散数学的導出を自力で行うのが難しく、crypto.SE で質問し、「同僚にこの RNG がどれほど弱いかを見せたい」と説明していた
保護環境で望む行動を選ぶ方法
- RNG の内部状態を復元できるようになると、保護環境に任意の自動化判断を伝えられた
- 動作手順は次のとおりだった
- 保護環境コードが実行される直前に走る 非保護フック を登録する
- フック内ではすべての情報へアクセスできるので、どの行動を取るかを決定する
- 決めた行動をハードコードされた行動リストから探し、インデックスに変換する
- 前述の方法で現在の RNG 状態を復元する
- 次の RNG 出力を行動リスト長で割った余りが望むインデックスでなければ、RNG を進めて再確認する
- 望む出力が出る順番になったらフックが戻り、保護環境が
random を呼び出してそのインデックスの行動を実行する
- 保護環境ではランダムな数で行動リストをインデックスしているように見えるが、実際には次の
random 呼び出し時点を調整することで望む行動が選ばれていた
- 行動リストのサイズが
n なら、望む値を伝えるため平均して RNG を n 段階進める必要があったが、実用上は問題にならなかった
その後
- 数年後に再び試したとき、この手法はもう動かなかった
- Blizzard がいつこの弱く共有された RNG 状態の問題を修正したのか、あるいは問題として認識していたのかは分からない
- 考えられる変更としては、別のアルゴリズムへ切り替えたか、保護環境に適切に分離された RNG 状態を持たせた可能性がある
- 使うつもりだったコードではなかったが、見かけ上はランダムなものを望む結果へ操作することに成功した、限定的なゲームセキュリティ回避の事例だった
1件のコメント
Hacker Newsのコメント
ずっと昔にWoWのGMとして働いていたとき、人気アドオン Titan Bar の特定バージョンにバグがあり、「GMにチケットを送信」UI を表示する API を延々と呼び出し続けることがあった
キャンセルしてもまた表示され、問題のアドオンを削除する以外では、テキストボックスに何かを書いて送信しないとそのウィンドウを消せなかった
GM側としては1日2日本当に大変で、多くのプレイヤーは GM が何なのか、チケットを送れることすら知らなかった
「おそらくアドオンのせいでチケットが送信され、カスタマーサポート担当の私が連絡しています」と説明するのも、たいてい簡単ではなかった
通常の応答時間が実質的に壊れてしまったため、開発者はホットフィックスを出し、その API 呼び出しを Blizzard自身の LUA コード からしかできないよう保護の内側に入れた
総ゴールドや修理率のような複数の UI 要素を1本のバーに統合してくれるアドオンだった
奇妙なことに、ほぼ同じ「乱数生成器を逆算する」という質問に、Crypto.SE に投稿される数か月前、StackOverflow で答えたことがある: https://stackoverflow.com/a/15237585/1204143
ただし MSVC の乱数生成器ではなく、Java の乱数生成器 を攻撃した
どちらも内部状態を切り詰めた値を出力する単純な線形合同生成器（LCG）構造なので、攻撃手法も非常によく似ている
import java.util.Random;
public class Hayley {
public static void main(String... args) {
byte[] b1 = new byte[4], b2 = new byte[2];
(new Random(0x2effe2140e00L)).nextBytes(b1);
(new Random(0xc2f0097)).nextBytes(b2);
System.out.println(new String(b1) + new String(b2));
}
}
サーバー側でも同じ乱数生成器を使っていた可能性があったのか気になる
もしそうなら、利用量が非常に少ないサーバー、低遅延、現在の乱数生成器の状態をかなり正確に絞り込める能力、そして乱数に応じて経済的な偏りが大きいイベントを素早く再発生させる能力があれば、理論上は悪用できそうだ
Blizzard は、迷信深いプレイヤーたちが「戦利品シード」のようなものがあると固く信じる噂を打ち消そうとする、だいたい失敗に終わった試みの中で、サーバー側の乱数生成方式の詳細をかなり多く公開していた
乱数生成器の経済学とインセンティブ は興味深い
実質的に賭けるものがなく、人々が簡単には気づかないなら、ゲームのように不完全、あるいは悪い乱数生成器でも十分なことがある
しかし暗号資産ウォレットやオンラインカジノのように金や安全性がかかると、突然ものすごく重要になる
さらに深刻なのは、提示された 線形合同乱数生成器 が、異なる数をわずか 12,445 個生成しただけで繰り返すことだ
このアルゴリズムでも、より良いパラメータを使うだけではるかに妥当になったはずだ
煙の軌跡の中の粒子の動きのような単純な処理には、単純で 高速な乱数生成器 が必要だ
暗号やカジノゲームなどでは、少なくとも 32 バイトの状態を持つより良い乱数生成器を使うだけでなく、結果予測をさらに防ぐために、エンジンをランダムな間隔で追加で進めたりもする
World of Warcraft は、私がプログラミングに興味を持つきっかけだった
リリース当時は6歳で、プライベートサーバーが出始めると自分で NPC を作る方法が知りたくなって Lua を覚えた
当時活動していた MMOwned フォーラムの投稿もまだたくさん残っており、その頃の学びを助けてくれた人の一人は今でも時々書き込んでいる
自分でプライベートサーバーのコアをコンパイルしながら、コンパイル、SVN、パッチの適用を学んだし、魔法使いの Fireball 関連のバグがあった気もするが正確には覚えていない
今ではインターネットの良い部分のかなり多くが、ドーパミンを誘発するソーシャルメディアアプリや Reddit のような 閉鎖的なフォーラム に置き換えられてしまった感じがする
今でも HN に居続けている理由も、たぶん昔のフォーラムを思い出させるからだと思う
「算術的手法で乱数を作り出そうとする者は、もちろん罪の状態にある。何度も指摘されてきたように、乱数というものは存在しない。あるのは乱数を生み出す方法だけであり、厳密な算術手続きは当然ながらそのような方法ではない。」 — John von Neumann
Neumann 本人に不満があるわけではないが、これを賢い警句のように広める人たちは、たいてい誤った情報しか伝えていない
文脈としては、不要な哲学ジョークに近い
私たちはすでに何十年も、速くて信頼できる 暗号学的乱数生成器 を持っている
ごく小さなシードと算術演算だけでも正しく動作し、生成された数は他の正当な乱数源と見分けがつかず、どんな目的にも使える
あまりに多くの人がこれを理解しておらず、「本物の乱数」というインチキを売る会社まで現れている
本当にひどい乱数生成器の好例として Monster Hunter 3 Ultimate があり、たぶん他の作品にもあるかもしれない
良い戦利品を得るために完全に悪用可能だっただけでなく、「charm table」まで生まれた
一部のアイテムはステータスがランダムに生成されるが、初期シードがセーブファイルに保存されるため、入手できるアイテムの範囲が制限される
運が悪いと、実質的に周期が非常に短い乱数生成器である「呪われたテーブル」に当たり、最高値を絶対に引けないことがある
ゲームを壊すほどではないが、高レベルプレイにはよくない
オークションハウスのスクリプトを書いていた
全オークションをスキャンし、割安なアイテムを買って再出品していた
誰かがもっと安く出したら取り消して、その少し下で出し直すことができ、実質 無限ゴールド だった
「うーん、実際かなりいい例えだな。違いは……うーん……かなりいい例えだな！」
「変数は変わらず、定数は一定でないとき」
https://www.theregister.com/2006/07/26/constants_are_not/
「この文章のタイトルにある、プログラミングの気まぐれさを嘆く『Variables Won't Constants Aren't』を、Creative Computing で初めて読んだのは C が作られる何年も前だった。」
このミームの決定版だと感じる特定の文書があるなら読んでみたい