2020-09-04

第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回の鳴き声が必要だ。これはすでにツールがある。

ペラップの鳴き声からseedを特定するツールを作った - oupoの日記

このツールは周波数で表示するので、それを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である。

f:id:oupo:20200904144733p:plain

出た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

参考文献

cryptanalysis - How Brittle Are LCG-Cracking Techniques? - Cryptography Stack Exchange

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}]

などとすればよい。

2020-01-22

Walkie-Talkieをビルドする方法

Walkie-Talkieをビルドします。

f:id:oupo:20200122154201p:plain

古いdevkitProが必要です。

linuxバージョンはここから落とせるようです。

dslibris - Browse /tool/devkitpro/r23b at SourceForge.net

この場合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でもビルドできるようにしたいですね…。

2020-01-18

GBAのROMを二次元コードを使ってダンプするNDSプログラム

GBAのROMを二次元コードを使ってダンプするNDSプログラムとそれを読み取るwebプログラムを書きました。

f:id:oupo:20200118203856j:plain

f:id:oupo:20200118203921p:plain

このNDSプログラムは2.25KBずつブロックに分けて2次元コード化し表示を繰り返します。
4MBのROMのダンプにだいたい16分かかります。
実際に吸い出しに成功したスーパーマリオアドバンス。

f:id:oupo:20200118210330p:plain

二次元コードはQRコードを改造した独自仕様を採用。正方形ではなくDSの画面を全部使いたかったのと、機能モジュールがいらないと思ったので。 QRコードのライブラリ、QR-Code-generatorとzxing-jsをいじって使っています。
最初は1モジュールを2ピクセル×2ピクセルで描画していましたが、1モジュール1ピクセル×2ピクセルでも十分読み取れると分かってそうしました。
webプログラムはiPadのSafariだと最初カメラが止まる問題点がある。一旦カメラをオフにしてもう一度オンにすれば直ります。

2019-12-23

pattirudonアルゴリズムのオーダー

pattirudon氏のアルゴリズムについて - oupoの日記

このアルゴリズムのオーダーを調べます。

つまり、線形な遷移で決まっている疑似乱数で、状態から乱数は足し算で決まっているものとする。このとき乱数値からseedを復元するアルゴリズムを考える。ただし、簡単のため一個の乱数で見れるbit長を固定でkとする。

seedの長さをn bitとする。このときアルゴリズムの計算時間は次の通り。

アルゴリズム	計算時間
愚直なアルゴリズム	Θ(2ⁿ)
pattirudonアルゴリズム	Ω(2^n/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の探索をしなければいけないため、計算量はΩ(2^n/2)である。

2019-12-22

pattirudon氏のアルゴリズムについて

背景

ポケモンソード・シールドのレイドバトルと呼ばれるイベントではxoroshiro128+という疑似乱数を使ってモンスターを生成している。これについて、セーブデータを抽出せず、ゲームのプレイから得られる情報からxoroshiro128+の乱数の種を復元できないかということが問題になっていた。

xoroshiro128+は状態遷移はF_2線形 *1であるが、状態から乱数値を得るのに算術和を使っており、それが非線形なため復元は難しいのではないかとされていた。しかし、驚くべきことにpattirudon氏はそれを可能にした。

github.com

ゲームでのxoroshiro128+の使われ方

ゲームのセーブデータにレイドバトルの各巣ごとの64bitのseedが格納されている。 seedはレイドバトルのイベントを起こしたり、日付が変わったりするごとに以下の式で更新される。

seed = (seed + 0x82a2b175229d6a5b) mod 2^64

レイドバトルのイベントを起こしたときは、巣のseedと定数を使ってxoroshiro128+の種を与える。

s0 = seed
s1 = 0x82a2b175229d6a5b

この種からxoroshiro128+で暗号化定数やPIDや個体値、特性、性格などのモンスターの属性が決定される。その決定のされ方は以下に書かれている。

github.com

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が定まる。

f:id:oupo:20191223155858p:plain

ゲーム内からわかる情報(足し算の結果)29bitがあり、足し算の片割れの情報28bit分をしらみつぶししてF_2^57の元xを考える。ここでf(seed) = xという方程式を解けばよい。 fのkernelの次元が7なので各xについて解は128個求まる。そのそれぞれについて、2匹目のモンスターの情報を使い絞り込む。

これは28bit + 7bit = 35bitの空間の探索なので現実的な時間で終了する。

f:id:oupo:20191223155922p:plain

補足

話を少し単純化した部分がある。 V固定箇所は6通りであるが、これをgetrand() % 8で決めるため、6未満の値が出るまで乱数を振っている。したがって、本当はこの部分に不定個数の乱数消費がある。この部分が現時点のツール (ver.1.0)では1個の消費で済んでいると仮定しているようだ。つまりここで2個以上消費したseedは検索にヒットしないはずである。

それから、seedから57bitの情報を得る部分は、s1の定数があるため、実際には線形ではなく線形写像と並行移動の合成である。しかしこれは考える方程式の定数項に影響を及ぼすだけである。

*1:F_2とは2元体{0, 1}のこと

2019-05-03

ゲームボーイのポケモンの疑似乱数

疑似乱数アルゴリズム、「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も赤緑と同じみたいですね

http://tasvideos.org/4205S.html

2019-03-07

線形合同法とp進整数と縮小写像

$p$ を素数， $e$ を正整数， $a, b$ を整数とする． $f: \mathbb{Z}/p^e\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ を $$f(x) = a x + b$$ で定める．

命題1

$a$ が $p$ の倍数であると仮定する．このとき次が成立する．

$f$ の不動点，すなわち $$f(x) = x$$ を満たす $x \in \mathbb{Z}/p^e\mathbb{Z}$ が存在する．

$f$ の不動点は一意である．

任意の $x_0 \in \mathbb{Z}/p^e\mathbb{Z}$ について次で定義される数列: $$ x_n = f^n(x_0) $$ は不動点に収束する．（ここに $f^n$ は $f$ の $n$ 回合成）

証明．(1)と(2):

$$ f(x) = x \iff (a-1)x \equiv -b \pmod{p^e} $$ だが，今 $a$ が $p$ の倍数なので， $a-1$ は $p$ と互いに素．よってこの一次合同方程式には解が一意に存在する．

(3): 数列の一般項は $$ x_n = a^n x_0 + (1 + a + a^2 + \dots + a^{n-1})b $$ となる． $a$ が $p$ の倍数なので $a^{n_0} \equiv 0 \pmod{p^e}$ となる $n_0$ がある．すると $n > n_0$ なら $$ x_n = (1 + a + a^2 + \dots + a^{{n_0}-1})b $$ となって一定値をとる． ■

ところで次のようなよく知られた定理がある．

定理 (Banachの不動点定理)

$(X, d)$ を空でない完備距離空間， $f: X \to X$ を次を満たす写像とする: ある $k\ (0 \leq k \lt 1)$ があって任意の $x, y \in X$ について $$ d(f(x), f(y)) \leq k\,d(x, y). $$ このとき $f$ の不動点がただ一つ存在する．また任意の $x_0$ に対して数列 $x_n = f^n(x_0)$ は不動点に収束する．

Banachの不動点定理によって最初の命題を証明できないだろうか． $\mathbb{Z}/p^e\mathbb{Z}$ には距離は離散距離しか入らないので使えそうにない．そこで $p$ 進整数環 $\mathbb{Z}_p$ と呼ばれる空間を考える．

$p$ 進整数環の定義はここではしないが，次のような性質を持つ．

$\mathbb{Z}_p$ には環構造が入る
$\mathbb{Z} \subset \mathbb{Z}_p$ である
$x \in \mathbb{Z}_p$ に対して $x$ の $p$ 進絶対値 $|x|_p$ が定まる
$|x|_p = 0 \iff x = 0$
$|xy|_p = |x|_p |y|_p$
$|x + y|_p \leq \max\{|x|_p, |y|_p\}$
$x \in \mathbb{Z} \setminus \{0\}$ に対しては $x$ を素因数分解したときの $p$ の指数を $n$ としたとき $|x|_p = p^{-n}$
$d(x, y) = |x - y|_p$ と定めるとき $(\mathbb{Z}_p, d)$ は完備距離空間
全射環準同型 $\varphi_e: \mathbb{Z}_p \to \mathbb{Z}/p^e\mathbb{Z}$ があり，特に $x \in \mathbb{Z}$ なら $\varphi_e(x) = x \bmod p^e$

$f$ は $\mathbb{Z}/p^e\mathbb{Z}$ 上の写像であったが，これを $\mathbb{Z}_p$ 上に修正したものを $\tilde{f}$ で表す: $$ \tilde{f}: \mathbb{Z}_p \ni x \mapsto (ax+b) \in \mathbb{Z}_p$$

この $\tilde{f}$ は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*}

であり， $a$ が $p$ の倍数だから $|a|_p \lt 1$ である．

よって $\tilde{f}$ の不動点 $x$ が存在し，それを $\varphi_e$ で移せば $f$ の不動点を得る．ゆえに命題の(1)が示された．また， $\mathbb{Z}/p^e\mathbb{Z}$ に離散位相を入れたとき， $\varphi_e$ が連続写像になるので，そこから命題の(3)を得る． (なお，残念ながら，命題の(2)はこの方法では示せない．)

以上よりBanachの不動点定理によって最初の命題を(一部分を除いて)示せることがわかった．

$a = {\rm 0x12344}$ (偶数なことに注意！), $b = {\rm 0x6073}, p = 2, e = 20, x_0 = 1$ としてみると次の表のようになる．下の桁から順に固定されていっている様子がわかる．

$n$	$x_n$
$0$	${\rm 0x00001}$
$1$	${\rm 0x183b7}$
$2$	${\rm 0x0620f}$
$3$	${\rm 0x1796f}$
$4$	${\rm 0xdceef}$
$5$	${\rm 0x504ef}$
$6$	${\rm 0x15cef}$
$7$	${\rm 0x0bcef}$
$8$	${\rm 0x63cef}$
$9$	${\rm 0xc3cef}$
$10$	${\rm 0x43cef}$
$11$	${\rm 0x43cef}$
$12$	${\rm 0x43cef}$