pattirudon氏のアルゴリズムについて
背景
ポケモンソード・シールドのレイドバトルと呼ばれるイベントではxoroshiro128+という疑似乱数を使ってモンスターを生成している。 これについて、セーブデータを抽出せず、ゲームのプレイから得られる情報からxoroshiro128+の乱数の種を復元できないかということが問題になっていた。
xoroshiro128+は状態遷移はF_2線形 *1であるが、状態から乱数値を得るのに算術和を使っており、それが非線形なため復元は難しいのではないかとされていた。 しかし、驚くべきことにpattirudon氏はそれを可能にした。
ゲームでのxoroshiro128+の使われ方
ゲームのセーブデータにレイドバトルの各巣ごとの64bitのseedが格納されている。 seedはレイドバトルのイベントを起こしたり、日付が変わったりするごとに以下の式で更新される。
seed = (seed + 0x82a2b175229d6a5b) mod 2^64
レイドバトルのイベントを起こしたときは、巣のseedと定数を使ってxoroshiro128+の種を与える。
s0 = seed s1 = 0x82a2b175229d6a5b
この種からxoroshiro128+で暗号化定数やPIDや個体値、特性、性格などのモンスターの属性が決定される。 その決定のされ方は以下に書かれている。
xoroshiro128+について
xoroshiro128+は詳細を省けば以下のような疑似乱数生成器である。 線形写像next: F_2^128 -> F_2^128が固定されており、状態遷移はこのnextで行う。 状態から疑似乱数の発生は次のようになっている
u64 s0, s1; // 状態
u64 getrand() {
u32 val = s0 + s1;
(s0, s1) = next(s0, s1);
return val;
}
つまり、算術和を使っている。これが問題の困難な点である。
なお、このゲームでは0以上m未満の乱数を生成する場合は、m以上の最小の2べきの数2^kをとりgetrand() % 2^kで乱数を発生させている。これがm以上の数ならばm未満の数が出るまでgetrand()を繰り返し呼んでいる。
ゲーム内からわかる情報
上に述べた通り、モンスターの属性がxoroshiro128+で決定されているわけだが、そのすべてがゲーム内からわかるわけではない。 暗号化定数やPIDはそれぞれ32bitの情報があり、これが分かれば簡単にseedを復元できたはずだが、それはゲーム内から得られない。 分かる情報はV固定箇所(3bit)、個体値(5bitの情報が5つ)、特性(1bit)である。 合計29bitの情報が分かる。 もちろん非線形関数を使っているので、単純な64-29=35bitのしらみつぶしというわけにはいかない。
pattirudon氏のアルゴリズム
pattirudon氏が気づいたのは「乱数値はseedから非線形だが、その乱数値の一歩手前の足し算する前の値は線形に得られる」という点である。 つまりseedから次の情報は線形に得られる。
- V固定箇所の3bitを決める足し算する前の値6bit
- 各個体値5bitを決める足し算する前の値10bit (それが5つで50bit)
- 特性を決める1bit (これは最下位bitを使っているため線形である)
よって64bitのseedからこれら57bitの情報を得る線形写像f: F_2^64 -> F_2^57が定まる。
ゲーム内からわかる情報(足し算の結果)29bitがあり、足し算の片割れの情報28bit分をしらみつぶししてF_2^57の元xを考える。 ここでf(seed) = xという方程式を解けばよい。 fのkernelの次元が7なので各xについて解は128個求まる。 そのそれぞれについて、2匹目のモンスターの情報を使い絞り込む。
これは28bit + 7bit = 35bitの空間の探索なので現実的な時間で終了する。
補足
話を少し単純化した部分がある。 V固定箇所は6通りであるが、これをgetrand() % 8で決めるため、6未満の値が出るまで乱数を振っている。 したがって、本当はこの部分に不定個数の乱数消費がある。 この部分が現時点のツール (ver.1.0)では1個の消費で済んでいると仮定しているようだ。 つまりここで2個以上消費したseedは検索にヒットしないはずである。
それから、seedから57bitの情報を得る部分は、s1の定数があるため、実際には線形ではなく線形写像と並行移動の合成である。 しかしこれは考える方程式の定数項に影響を及ぼすだけである。
*1:F_2とは2元体{0, 1}のこと
