この記事は Pokemon RNG Advent Calendar 2016 の10日目です。
いわゆる「乱数調整」とは関係ないのですが、箸休めということで。
Q.) お前誰だよ？
A.) 「ポケモンの友」の管理者です。
(XY以降は、アイドルプロデュース活動が忙しくて全然手が回っていません……)
以下本題。
ポケモン ダイヤモンド・パールから 「GTS」と「Wi-Fiバトルタワー」という施設が登場しました。
ネットワークサービス「ニンテンドーWi-Fiコネクション」を使って、 全世界のトレーナーと交換や対戦(※CPU戦)が楽しめるというものです。
さすがに10年も前のゲームなので、これらのサービスはすでに終了してしまっているのですが、
せっかくなので、当時を思い出しながら書いてみます。
まずはじめに、ニンテンドーDSとサーバーとの間でどのような通信がされているか調べました。
ゲームのROMデータはDSカードから吸い出すことができていたので、 その中に含まれているエンドポイントのホスト名はすぐにわかりました。
そこで、LAN内にある作業用PCにDNSサーバーとHTTPサーバーを立てて、 上記ホスト名が作業用マシンのIPに向くよう設定し、DS側のDNS設定を作業用マシンのIPに。
として通信内容を観察すると、ゲーム内でのいちどの通信で、HTTP GETを2回行っていることが分かりました。
「HTTP？HTTPSではなくて？」と思われたかた、 10年も前のゲームであり、処理能力がそんなに高くないゲーム機での通信ということを思い出してください。
処理の流れは以下のようになります。
- 通信を行いたいエンドポイントに対して、パラメータにプレイヤーIDのみをつけてリクエストする。
- サーバー側からは、ランダムに生成されたトークン文字列が返却される。
- ゲーム側で、上記トークン文字列に対応したハッシュ値を求める。
- 1.と同じエンドポイントに対して、プレイヤーID、3.のハッシュ値、送信したいデータをBASE64URLエンコードしたもの、をパラメータにしてリクエストする。
- サーバー側でデータに応じた処理が行われる。
- 結果がバイナリデータで返却される。
いわゆる「チャレンジ/レスポンス認証」というやつですね。
間にプロキシを挟んだ図は以下のようになります。
これで何度か通信をして、ある程度ログをためて分析、という手順で進めていきました。
さて、プレイヤーIDは上記通信に生の値が含まれているのですが、残りのデータはどうなっているのでしょうか？
まず、レスポンスのバイナリデータについては、とくに暗号化がされていないことがわかりました。 GTSに預けたポケモンの情報を取得したとき、セーブデータに格納されている状態のものがそのまま却ってきていたからです。
もちろん、このポケモン情報自体は、暗号化がされています。いわゆるbin状態のpkmというやつです。 (Pokemon NDS Structure - ProjectPokemon Wiki)
3.のハッシュ値の計算については、文字列の長さが40であったので、方式がSHA-1という予想はすぐにたちました。 ですが、トークン文字列そのままのSHA-1ハッシュ値を算出しても、4.で送信しているハッシュ値と合いません。 つまり、なんらかのソルト値を加えているようなのですが……。
そこで、ソルト値が送信するデータや時刻によってハッシュ値が変わるかどうか確かめるため、 1.の通信がプロキシサーバーに来たとき、APIサーバーにアクセスせず、固定値を返すようにしました。
……すると、なんと毎回同じハッシュ値となることが分かりました。 ソルト値は送信するデータや時刻によらない固定された値と考えられます。
と、ここでエンドポイントのホスト名を調べている途中で、近くに不自然な文字列があったことを思い出しました。
もしかして……と思い、そのROM内の文字列とトークン文字列をつなげた文字列のSHA-1ハッシュ値を算出したところ……ビンゴ。
さて、最後の本丸、4.のリクエストデータに関してです。
さらに調査を続けたところ、このデータは、なんらかの暗号化がされているものの、同じリクエスト内容であれば常に同じデータということがわかりました。
つまり、あらかじめゲーム側で通信を行った際のリクエストを保存しておけば、残りの通信についてはもうルーチンが判明しているので、同じ通信を、ゲームを介することなしに行うことが可能になりました。
そう、バトルタワーの特定ルームの登録状況や、GTSの特定ポケモンのトレード情報を、ゲーム側を介さずに定点観測できるようになったのです。
しかし、やはり送信データがどのように作られているか知りたい。
というわけで、たまったログデータをもとに推測してみることにしました。
以下は、プレイヤーID 80162411 で、バトルタワーの情報を取得した時のリクエストデータです。
| クエリパラメータ | バイナリに変換したデータ(16進) | ゲーム側からの取得内容 |
|---|---|---|
| SjsteZ/Myel= | 4A 3B 2D 79 9F CC C9 E9 | サービス稼働状態の確認 |
| SjsteZ/Myenk | 4A 3B 2D 79 9F CC C9 E9 E4 | ルーム数の確認 |
| Sjstd/lWXar5Wj== | 4A 3B 2D 77 F9 56 5D AA F9 5A | ランク1 ルーム7 の情報を取得 |
| Sjstdrw8G32pVz== | 4A 3B 2D 76 BC 3C 1B 7D A9 57 | ランク2 ルーム7 の情報を取得 |
| SjstcXeF2UBUQT== | 4A 3B 2D 71 77 85 D9 40 54 41 | ランク3 ルーム7 の情報を取得 |
| SjstcApqpwoHOj== | 4A 3B 2D 70 0A 6A A7 0A 07 3A | ランク4 ルーム7 の情報を取得 |
| Sjstc83zZd22ND== | 4A 3B 2D 73 CD F3 65 DD B6 34 | ランク5 ルーム7 の情報を取得 |
| SjstcoBYI6BkIT== | 4A 3B 2D 72 80 58 23 A0 64 21 | ランク6 ルーム7 の情報を取得 |
| SjstbVsh4WsJGz== | 4A 3B 2D 6D 5B 21 E1 6B 09 1B | ランク7 ルーム7 の情報を取得 |
| SjstbB6Grz66FD== | 4A 3B 2D 6C 1E 86 AF 3E BA 14 | ランク8 ルーム7 の情報を取得 |
| Sjstb9FvbQFjDj== | 4A 3B 2D 6F D1 6F 6D 01 63 0E | ランク9 ルーム7 の情報を取得 |
| SjstbpT0K9QQ+z== | 4A 3B 2D 6E 94 F4 2B D4 10 FB | ランク10 ルーム7 の情報を取得 |
ランクとルームの2バイトですみそうなところ、なぜか10バイトを送っています。 しかも、データの頭のほうが同じような値です。
4A 3B 2* … うーん？
ためしに、最初の4バイトと 4A 3B 2C 1D とのXORを取ってみます。
| ゲーム側からの取得内容 | 先頭4バイトのXORを計算したデータ(16進) |
|---|---|
| サービス稼働状態の確認 | 4A 3B 2D 79 xor 4A 3B 2C 1D = 00 00 01 64 |
| ルーム数の確認 | 4A 3B 2D 79 xor 4A 3B 2C 1D = 00 00 01 64 |
| ランク1 ルーム7 の情報を取得 | 4A 3B 2D 77 xor 4A 3B 2C 1D = 00 00 01 6A |
| ランク2 ルーム7 の情報を取得 | 4A 3B 2D 76 xor 4A 3B 2C 1D = 00 00 01 6B |
| ランク3 ルーム7 の情報を取得 | 4A 3B 2D 71 xor 4A 3B 2C 1D = 00 00 01 6C |
| ランク4 ルーム7 の情報を取得 | 4A 3B 2D 70 xor 4A 3B 2C 1D = 00 00 01 6D |
| ランク5 ルーム7 の情報を取得 | 4A 3B 2D 73 xor 4A 3B 2C 1D = 00 00 01 6E |
| ランク6 ルーム7 の情報を取得 | 4A 3B 2D 72 xor 4A 3B 2C 1D = 00 00 01 6F |
| ランク7 ルーム7 の情報を取得 | 4A 3B 2D 6D xor 4A 3B 2C 1D = 00 00 01 70 |
| ランク8 ルーム7 の情報を取得 | 4A 3B 2D 6C xor 4A 3B 2C 1D = 00 00 01 71 |
| ランク9 ルーム7 の情報を取得 | 4A 3B 2D 6F xor 4A 3B 2C 1D = 00 00 01 72 |
| ランク10 ルーム7 の情報を取得 | 4A 3B 2D 6E xor 4A 3B 2C 1D = 00 00 01 73 |
ランクが増えると、応じて1ずつ増えています。
もしかして、最初の4バイトは1オクテットのチェックサムなのでは……？
さらに、プレイヤーIDの 80162411 を16進数にすると0x04C72E6B 、 0x04 + 0xC7 + 0x2E + 0x6B = 0x0164 ……あれ？
| ゲーム側からの取得内容 | 予想データ | サム値 | 先頭4バイトのXOR |
|---|---|---|---|
| サービス稼働状態の確認 | 6B 2E C7 04 00 | 0x0164 | 00 00 01 64 |
| ルーム数の確認 | 6B 2E C7 04 00 | 0x0164 | 00 00 01 64 |
| ランク1 ルーム7 の情報を取得 | 6B 2E C7 04 01 07 | 0x016C | 00 00 01 6A |
| ランク2 ルーム7 の情報を取得 | 6B 2E C7 04 02 07 | 0x016D | 00 00 01 6B |
| ランク3 ルーム7 の情報を取得 | 6B 2E C7 04 03 07 | 0x016E | 00 00 01 6C |
| ランク4 ルーム7 の情報を取得 | 6B 2E C7 04 04 07 | 0x016F | 00 00 01 6D |
| ランク5 ルーム7 の情報を取得 | 6B 2E C7 04 05 07 | 0x0170 | 00 00 01 6E |
| ランク6 ルーム7 の情報を取得 | 6B 2E C7 04 06 07 | 0x0171 | 00 00 01 6F |
| ランク7 ルーム7 の情報を取得 | 6B 2E C7 04 07 07 | 0x0172 | 00 00 01 70 |
| ランク8 ルーム7 の情報を取得 | 6B 2E C7 04 08 07 | 0x0173 | 00 00 01 71 |
| ランク9 ルーム7 の情報を取得 | 6B 2E C7 04 09 07 | 0x0174 | 00 00 01 72 |
| ランク10 ルーム7 の情報を取得 | 6B 2E C7 04 10 07 | 0x0175 | 00 00 01 73 |
ルーム情報の取得で2ずれていますが、ランク1 = 内部値0 と考えるとつじつまが合います。
と、ここまでは来たのですが、5バイト目以降のデータがどのように作られているのか、さっぱり見当がつきません。
ということで、ここからアセンブラの出番です。
ゲームのROMデータを 4A 3B 2C 1D で検索したところ1件ヒット。 近くを逆アセンブルしてみます。
(以下、正確な位置で切り出せなかったので、アドレスが変な感じになってしまっています)
000000fa 480e ldr r0, [pc, #56] ($00000134) # r0 = 0x00000134 の値 = 0x4a3b2c1d 000000fc 4046 eor r6, r0 # r6 = r6 xor r0 000000fe 0e30 lsr r0, r6, #24 # r0 = r6 >>> 24 00000100 7038 strb r0, [r7, #0] # (r7 + 0)が指す先にr0の下位1バイトを格納 00000102 0c30 lsr r0, r6, #16 # r0 = r6 >>> 16 00000104 7078 strb r0, [r7, #1] # (r7 + 1)が指す先にr0の下位1バイトを格納 00000106 0a30 lsr r0, r6, #8 # r0 = r6 >>> 8 00000108 70b8 strb r0, [r7, #2] # (r7 + 2)が指す先にr0の下位1バイトを格納 0000010a 70fe strb r6, [r7, #3] # (r7 + 3)が指す先にr0の下位1バイトを格納 (中略) 00000134 2c1d cmp r4, #29 00000136 4a3b ldr r2, [pc, #236] ($00000224)
r5にデータ長さ、r6にSUM値、r7に送信するデータが格納されているメモリアドレスが入っているようです。 では、その少し手前を見てみます。
000000de 2400 mov r4, #0 # r4 = 0
000000e0 2d00 cmp r5, #0
000000e2 dd0a ble $000000fa # r5 <= 0 なら ★を飛ばす
# ★ {
000000e4 f000 f828 bl $00000138 # 0x00000138 を呼び出し
000000e8 9900 ldr r1, [sp, #0] # r1 = スタックポインタ内の値が指すアドレスに格納された値 (引数で渡された値と考えてください)
000000ea 5d09 ldrb r1, [r1, r4] # r1 = (r1 + r4)からバイト単位ロード
000000ec 4041 eor r1, r0 # r1 = r1 xor r0
000000ee 1c20 mov r0, r4 (add r0, r4, #0) # r0 = r4
000000f0 3008 add r0, #8 # r0 = r0 + 8
000000f2 5439 strb r1, [r7, r0] # (r7 + r0)が指す先にr1の下位1バイトを格納
000000f4 1c64 add r4, r4, #1 # r4 = r4 + 1
000000f6 42ac cmp r4, r5
000000f8 dbf4 blt $000000e4 # r4 <= r5 なら 0x000000e4 へジャンプ
# } ★
r1 に、暗号化前のリクエストデータが格納されているアドレスをロードして、作業しているようです。
1バイトごとに、0x00000138 を呼び出したあと、r0に入っている値とXORしていますね。 r0には何が入っているのでしょうか？ 呼び出し先のルーチンを見てみます。
00000138 4906 ldr r1, [pc, #24] ($00000154) # r1 = 0x022185a0 0000013a 680a ldr r2, [r1, #0] # r2 = r1のアドレスの値 0000013c 2045 mov r0, #69 # r0 = 69 (=0x45) 0000013e 4342 mul r2, r0 # r2 = r2 × r0 00000140 4805 ldr r0, [pc, #20] ($00000158) # r0 = 0x00001111 00000142 1812 add r2, r2, r0 # r2 = r2 + r0 00000144 4805 ldr r0, [pc, #20] ($0000015c) # r0 = 0x7fffffff 00000146 4002 and r2, r0 # r2 = r2 and r0 00000148 600a str r2, [r1, #0] # r1のアドレス(=0x022185a0)にr2を格納 0000014a 1410 asr r0, r2, #16 # r0 = r2の上位16ビット 0000014c 0600 lsl r0, r0, #24 # r0 = r0 <<< 24 0000014e 0e00 lsr r0, r0, #24 # r0 = r0 >>> 24 つまりこれで r2 の下から17-24ビット目の値だけが残る 00000150 4770 bx lr # 呼び出し元に戻る 00000152 46c0 nop (mov r8,r8) 00000154 85a0 strh r0, [r4, #44] 00000156 0221 lsl r1, r4, #8 00000158 1111 asr r1, r2, #4 0000015a 0000 lsl r0, r0, #0 0000015c ffff second half of BL instruction 0xffff 0000015e 7fff ldrb r7, [r7, #31]
r0 が ((アドレス[0x022185a0]に格納された値 × 0x45 + 0x1111) >>> 16) & 0xFF という値だと分かりました。
[0x022185a0]にはなにが格納されているのでしょうか？ 000000deの位置に戻って、もう少し手前を見てみます。
000000ac 1c30 mov r0, r6 (add r0, r6, #0) # r0 = r6 = SUM値 000000ae f000 f857 bl $00000160 # 00000160 を呼び出し 00000160 0401 lsl r1, r0, #16 # r1 = r0 <<< 16 00000162 4308 orr r0, r1 # r0 = r0 or r1 00000164 4901 ldr r1, [pc, #4] ($0000016c) # r1 = 0x022185a0 00000166 6008 str r0, [r1, #0] # r1のアドレスにr0を格納 00000168 4770 bx lr # 呼び出し元に戻る 0000016a 46c0 nop (mov r8,r8) 0000016c 85a0 strh r0, [r4, #44] 0000016e 0221 lsl r1, r4, #8
つまり アドレス0x022185a0に、SUM値の下位2バイトを上位2バイトにORしてできた値が入っているようです。
# 例) SUM値が 0x0164 なら、入っている値は 0x01640164
ということで、リクエストデータは以下の線形合同法を使ったストリーム暗号で暗号化されているということが分かりました。
S[0] = (1オクテットのチェックサム * 0x00010000) + (1オクテットのチェックサム) % 0x100000000 S[n+1] = (0x45 * S[n] + 0x1111) % 0x100000000 r[n] = (S[n] >>> 16) % 0x0100
……というようなことは、世界中のポケモンに詳しいハッカーが調べていて、
GTSの動作をエミュレートして任意のポケモンをGTS経由でゲーム内に送ったり、 GTSにあずけたポケモンの個体値を内部データから正確に表示する、 などのWebサービスが、DS末期に登場したりなどしました。
もちろん、これらの行為はいろいろと危険が危ないので、くれぐれもご用心を。