第5世代でペラップの鳴き声だけから64bit LCGのseedを見つける
概要
Mathematica (or Wolfram Cloud)を使ったら、ペラップの鳴き声だけから64bit LCGのseedを特定できた。 これは64bit LCGの上位5bitの連続した値を13個観測してseedを十分現実的な時間で復元したことになる。
内容
第5世代のポケモンでは64bitの線形合同法 (LCG)を疑似乱数の一部に使っている。 ペラップというポケモンのおしゃべりという特別な技において、マイクで収録した音を再生でき、その音程は再生するたび変わる。そこにLCGが使われている。 その音程の情報だけからLCGのseedを特定できたというのが今回の内容である。 計算時間はWolfram Cloud上でおよそ14秒である。 なお、このゲームのseedは現在時刻などのパラメータから決定されており、それはツールから完全に再現可能になっているので、このゲームの乱数調整には今回の結果はあまり影響を与えないと考えられる。
実践
まず、ペラップの鳴き声から乱数値を得る。13回の鳴き声が必要だ。 これはすでにツールがある。
このツールは周波数で表示するので、それを0~31の値に変換しておく。たとえば次のようなRubyのスクリプトでできる。
list = " 988 1016 1011 1058 1020 1042 1081 899 1040 951 1030 961 953 " a = list.split("\n").select{|x| x != "" }.map(&:to_i) mi = 1 * 880 ma = 1.25 * 880 p a.map{|x| (32 * (x - mi) / (ma - mi)).floor }
これをMathematica (or Wolfram Could)に入れる。 まず必要となる関数を定義しておく (汚い定義だが)。
SolveLCG[a_, c_, b_, r_, h1_, h2_, h3_, h4_, h5_, h6_, h7_, h8_, h9_, h10_, h11_, h12_, h13_] := With[{M = 2^b, m = 2^(b - r)}, Solve[{ s == l1 + h1 m, a s+c == l2 + h2 m + k2 M, a^2 s+(1+a)c == l3 + h3 m + k3 M, a^3 s+(1+a+a^2)c == l4 + h4 m + k4 M, a^4 s+(1+a+a^2+a^3)c == l5 + h5 m + k5 M, a^5 s+(1+a+a^2+a^3+a^4)c == l6 + h6 m + k6 M, a^6 s+(1+a+a^2+a^3+a^4+a^5)c == l7 + h7 m + k7 M, a^7 s +(1+a+a^2+a^3+a^4+a^5+a^6)c== l8 + h8 m + k8 M, a^8s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7)c == l9 + h9 m + k9 M, a^9s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8)c == l10 + h10 m + k10 M, a^10s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8+a^9)c == l11 + h11 m + k11 M, a^11s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8+a^9+a^10)c == l12 + h12 m + k12 M, a^12s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8+a^9+a^10+a^11)c == l13 + h13 m + k13 M, l1 >= 0, l1 < m, l2 >= 0, l2 < m, l3 >= 0, l3 < m, l4 >= 0, l4 < m, l5 >= 0, l5 < m, l6 >= 0, l6 < m, l7 >= 0, l7 < m, l8 >= 0, l8 < m, l9 >= 0, l9 < m, l10 >= 0, l10 < m, l11 >= 0, l11 < m, l12 >= 0, l12 < m, l13 >= 0, l13 < m}, Integers]]
そして次のような文を実行する。
SolveLCG[6726279311198226789, 2531011, 64, 5, 15, 19, 19, 25, 20, 23, 29, 2, 23, 10, 21, 11, 10]
6726279311198226789, 2531011, 64, 5,
までは固定でその後の引数を先ほどの0-31の値の列を入れる。
これで実行すると解が出る。その中のs
がseedである。
出たseedが本当にあっているか確かめたい場合は次のようなペラップの鳴き声の音程のリスト出力するプログラムで、13回目以降も一致しているか確かめればよい。
A = 0x5d588b656c078965 C = 0x269ec3 M = 2**64 s = 8978365926194661437 50.times do |i| x = s >> (64 - 13) x = x.to_f / 8192 puts "%03d %02d %s" % [i, (1 + x * 0.25) * 880, "*" * (x * 10).to_i] s = (s * A + C) % M end
参考文献
Mathematicaのプログラムは上の文献を参考にした。
追記 (2020/9/7)
Wolfram言語のコードが汚かったので任意個数の入力を取れるバージョンを作成。
SolveLCG[a_, c_, b_, r_, h_] := With[{M = 2^b, m = 2^(b - r)}, Solve[Flatten[Map[Function[i,{Mod[a^(i-1), M] s +Mod[ Sum[a^j, {j, 0, i-2}]c, M] == Subscript[l, i] + h[[i]] m+If[i > 1, Subscript[k, i]M, 0] ,Subscript[l, i]>= 0, Subscript[l, i] < m}], Range[Length[h]]]], Integers]]
これで
SolveLCG[6726279311198226789, 2531011, 64, 5, {15, 19, 19, 25, 20, 23, 29, 2, 23, 10, 21, 11, 10}]
などとすればよい。
Walkie-Talkieをビルドする方法
Walkie-Talkieをビルドします。
古いdevkitProが必要です。
linuxバージョンはここから落とせるようです。
この場合32bitのlinuxで動きますから、それを用意します。私はVirtualBoxの上でCentOS 6を立ち上げました。
devkitProをホームディレクトリの下に用意する
上のリンクからdevkitARM_r23b-i686-linux.tar.bz2とlibnds-20071023.tar.bz2をダウンロードして解凍します。
$ tar xf devkitARM_r23b-i686-linux.tar.bz2 $ tar xf libnds-20071023.tar.bz2
~/devkitpro以下にコピーします。
$ mkdir -p ~/devkitpro/libnds $ mv devkitARM ~/devkitpro $ mv include lib ~/devkitpro/libnds
環境編集をエクスポートします。
$ export DEVKITARM=/home/user/devkitpro/devkitARM $ export DEVKITPRO=/home/user/devkitpro
Walkie-Talkieをビルドする
Walkie-Talkieのソースコードをhttp://home.kabelfoon.nl/~moongies/nds_en.htmlからダウンロードします。
解凍します。
$ tar xf walkietalkie-src-0v3.tar.gz $ cd walkietalkie-0v3
まずmisc/libnds/ipc.hのコメントがバグっているで修正します。
--- walkietalkie-0v3.orig/misc/libnds/ipc.h 2008-11-10 06:49:14.000000000 +0900 +++ walkietalkie-0v3/misc/libnds/ipc.h 2020-01-22 14:54:11.477041756 +0900 @@ -24,14 +24,14 @@ must not be misrepresented as being the original software. 3. This notice may not be removed or altered from any source distribution. - +*/ /* =========================== nov 2008: adapted by Eric for walkie-talkie v0.1 =========================== */ ----------------------------------------------------------------------------------*/ +/*---------------------------------------------------------------------------------*/ #ifndef NDS_IPC_INCLUDE #define NDS_IPC_INCLUDE
次にlibndsのipc.hを今書き換えたもので上書きしましょう。
cp misc/libnds/ipc.h ~/devkitpro/libnds/include/nds
次に中にあるliblobbyをビルドしましょう。
$ cd misc/liblobby $ tar xf liblobby_for_walkietalkie.tar.gz $ cd liblobby_for_walkietalkie $ make
ビルドできたらlib/liblobby7d.a, lib/liblobby9d.aが出来ているはずです。
ビルドできたものをdevkitproにコピーします。
cp include lib ~/devkitpro/libnds
walkietalkieのディレクトリに戻りましょう。
$ cd ../../..
makeします。
$ make
これでwalkietalkie-0v3.ndsができるはずです。
終わりに
新しいdevkitProでもビルドできるようにしたいですね…。
GBAのROMを二次元コードを使ってダンプするNDSプログラム
pattirudonアルゴリズムのオーダー
このアルゴリズムのオーダーを調べます。
つまり、線形な遷移で決まっている疑似乱数で、状態から乱数は足し算で決まっているものとする。 このとき乱数値からseedを復元するアルゴリズムを考える。 ただし、簡単のため一個の乱数で見れるbit長を固定でkとする。
seedの長さをn bitとする。 このときアルゴリズムの計算時間は次の通り。
アルゴリズム | 計算時間 |
---|---|
愚直なアルゴリズム | Θ(2n) |
pattirudonアルゴリズム | Ω(2n/2) |
ただしseedの候補を決めたとき、それが本当にseedかはΘ(1)時間でできるものと仮定する。
ここにΘ(f(n))はちょうどf(n)のオーダー、Ω(f(n))は少なくともf(n)のオーダーを意味する。
説明
何個の乱数を見るかをlとする。最適なlを調べる。
seedから乱数値を決める足し算する前の値を得る写像をf: F_2^n -> F_2^(2kl)とする (1個の乱数ごとに2l bitあることに注意)。 探索しないといけないbit数はkl + dim(Ker f)である。 ここにklは足し算する前の値の片割れのbit数、dim(Ker f)はそれを決めたときのf(x) = aの解空間の次元。
次元公式よりdim(Ker f) = n - dim(Im f) ≦ n - 2klなため、
(探索しないといけないbit数) = kl + dim(Ker f) ≧ kl + max{n - 2kl, 0} = max {n - kl, kl}。
これが最小となるのはl = n / (2k)のときで最小値はn / 2。 よって(n / 2) bitの探索をしなければいけないため、計算量はΩ(2n/2)である。
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}のこと
ゲームボーイのポケモンの疑似乱数
疑似乱数アルゴリズム、「pokemon rng ffd3」で検索したら出てきた。
http://tasvideos.org/GameResources/GBx/PokemonGen1.html
http://wiki.pokemonspeedruns.com/index.php/Pokémon_Red/Blue/Yellow_DSum_Manipulation
乱数生成のたびにIOレジスタの一つ0xff04の値を足す(あるいは引く)というもの
ポケモン赤の疑似乱数を0に固定するLuaスクリプト書いた。攻撃が必ず急所に当たるようになったのでたぶんうまく動いている
https://gist.github.com/oupo/58b2a858360b574661a3
ここによると金銀のRNGも赤緑と同じみたいですね
線形合同法とp進整数と縮小写像
を素数,を正整数,を整数とする. を $$f(x) = a x + b$$ で定める.
命題1
がの倍数であると仮定する. このとき次が成立する.
証明.(1)と(2):
$$ f(x) = x \iff (a-1)x \equiv -b \pmod{p^e} $$ だが,今がの倍数なので,はと互いに素.よってこの一次合同方程式には解が一意に存在する.
(3): 数列の一般項は $$ x_n = a^n x_0 + (1 + a + a^2 + \dots + a^{n-1})b $$ となる.がの倍数なのでとなるがある.するとなら $$ x_n = (1 + a + a^2 + \dots + a^{{n_0}-1})b $$ となって一定値をとる. ■
ところで次のようなよく知られた定理がある.
定理 (Banachの不動点定理)
を空でない完備距離空間,を次を満たす写像とする: あるがあって任意のについて $$ d(f(x), f(y)) \leq k\,d(x, y). $$ このときの不動点がただ一つ存在する. また任意のに対して数列は不動点に収束する.
Banachの不動点定理によって最初の命題を証明できないだろうか.には距離は離散距離しか入らないので使えそうにない.そこで進整数環と呼ばれる空間を考える.
進整数環の定義はここではしないが,次のような性質を持つ.
は上の写像であったが,これを上に修正したものをで表す: $$ \tilde{f}: \mathbb{Z}_p \ni x \mapsto (ax+b) \in \mathbb{Z}_p$$
このはBanachの定理の仮定を満たす.実際,
\begin{align*} d(\tilde{f}(x), \tilde{f}(y)) &= |(ax+b)-(ay+b)|_p \\ &= |a(x-y)|_p \\ &= |a|_p |x-y|_p \\ &= |a|_p d(x, y) \end{align*}
であり,がの倍数だからである.
よっての不動点が存在し,それをで移せばの不動点を得る.ゆえに命題の(1)が示された. また,に離散位相を入れたとき,が連続写像になるので,そこから命題の(3)を得る. (なお,残念ながら,命題の(2)はこの方法では示せない.)
以上よりBanachの不動点定理によって最初の命題を(一部分を除いて)示せることがわかった.
(偶数なことに注意!), としてみると次の表のようになる.下の桁から順に固定されていっている様子がわかる.