CSAW CTF Quals 2015 Reversing 200 Writeup
この2日間CSAW CTF Qualsが開かれていたようなので、大学のサークルの中でCTF team無所属勢として参加してみた。
1日目はおでかけしていたので、夜行で東京に帰ってきて2日目昼ごろから参戦。
いかんせんCTF初心者なのでいろいろ手間取り、結局最終的にReversing 200のHacing Timeなら解けるかもと思い集中的に着手したのが残り6時間くらいの時点だった。
最後の最後でflagのデコーダーを書き上げるのが間に合わず、得点につながらなかったのでものすごく悔しい。
とはいえ、おそらく初めて独力で解いたまともな問題なので、この機会にwrite upを残してみる。
Hacking Time
まずは.nesファイルが配布される。もしやと思ったが
やはりファミコンのROMだ。何はともあれまずはエミュレータに通してみる。
はじめ、ここで面倒くさがってMacで動きそうなエミュレータを探して動かしたが、デバッガの使い方がよくわからず（バグっている？）、xxdで無謀にも直読みトライなどをしてみたり、そうこうしているうちに時間を浪費してしまった。
なんかゲームが始まるのでとりあえずホイホイ進む。Aボタンはデフォルトではmキーに割り当てられているらしい。
よくわからないけどおもちゃのオーバーフロー脆弱性持ちバッファを溢れさせる。
すると"Hacker Detected"となり、検知システムを落とすためのパスワードを要求される。
さすがにこれだとどうしようもないので、バイナリを見てみる。すると
頭のあたりにゲーム画面中で表示されていたメッセージが見つかる。しかも、パスワード受理後のメッセージも見えていて、"THEY MIGHT USE THAT PASSWORD IN OTHER PLACES THAT MIGHT LEAD TO SCORE"とある。つまりはこのパスワードを解読すれば、それがflagになっているということだろう。
ROMのデバッグ
そこまでわかれば、次はG-NESのデバッガとメモリビューワーを起動してデバッグする。
のだが、ここでどこにブレークポイントを仕掛ければいいのかわからないという問題に直面した。
僕は残念ながら、
勘でブレークポイントを仕掛けまくった。
多少のあたりはつけた。LOCKDOWN画面はどこかをずっとループしてるんだろうな、と考えたので、実行命令をトレースしまくって、ループ箇所を推定した。「どうせその周辺のどこかのサブルーチンに飛ぶんでしょー（ﾍﾗﾍﾗ」とか言いつつ、周辺のrts命令（Return-To-Subroutine）にブレークポイントをかけまくった。
あともう一つ重要なヒントがあって、パスワードを入力するということはメモリ上のどこかに保持してるだろうから、何かわかりやすいパスワードを入れてメモリビューワーでそのアドレスを特定できるんじゃないかと思った。パスワードは24桁みたいなので、差し当たり"A"*24を入れてみた。
ビンゴ！0x0005〜がパスワード用バッファっぽい。ので、0x0005から読み出そうとしている箇所があれば、そこらへんがパスワードのvalidation routineだと検討がつく。
ちなみにNESはlittle-endianなので、バイナリで見るときは0500になることに注意する。
MOS 6502アーキテクチャ
ここらへんまでくるとそろそろアセンブリを読む必要が出てくるので、NESのアーキテクチャについて軽く勉強する。
NESのアーキテクチャはMOS 6502（正確にはその派生）というものらしく、これはかのApple IIにも使われていたそうな。
ポイントは
あたりだろうか。以下のページに詳しい。
【参考】6502 Assembly - NES Hacker Wiki
6502は主に以下のレジスタを持つ。
| レジスタ名 | 略記 | ビット長 |
|---|---|---|
| Accumulator | A | 8 |
| X Index Register | X | 8 |
| Y Index Register | Y | 8 |
| Process Status | P | 8 |
| Program Counter | PC | 16 |
| Stack Pointer | SP | 16 |
基本はアキュムレータマシンらしいので、すべての演算はAレジスタに対して行う。たまに修飾としてXやYも使う。
汎用レジスタ（A,X,Yのことを指している）は8bitなのに、PCやSPは16bitで16bitアドレス空間を扱っている。ここはちょっと不思議。
ただし、実はSPの上位8bitは固定されているとかなんとか。まあ今回はあまり気にすることじゃない。
CISCっぽくアドレッシングモードが多彩なのが特徴なのだが、その中でも6502でよく目にするのがZero-Page Addressing。
これは、オペランドとして8bitの即値をとり、上位8bitをさらに0埋めした値をアドレスとしてアクセスするらしい。
例えば
lda $EE
なら0x00EE番地から値をAレジスタにロードする(LoaD-to-Accumulator)。
このあたりまで理解しておけば、6502アセンブリが一通り読めるようになる。
命令は6502 Opcodes - NES Hacker Wikiを参考にするとよい。
パスワード照合ルーチン
ここまで準備してパスワード照合部分を探しだす。すると、0x82F1〜0x0x8348番地にそれらしい部分が見つかる。
（こればっかりは正直当てずっぽうだった。何か良い方法があれば是非ご教授くださいませ）
ldy #$00 lda #$00 sta $3B lda #0005,y tax rol a txa rol a tax rol a txa rol a tax rol a txa rol a pha lda $3B tax ror a txa ror a tax ror a txa ror a sta $3B tax rol a txa rol a tax rol a txa rol a tax rol a txa rol a tax rol a txa rol a eor $9576,y sta $001E,y iny cpy #$18 bne $82F7 ldy #$00 lda $001E,y bne $8346 iny cpy #$18 bne $8339 lda #$01 rts lda #$00 rts
大別すると前半(エンコード部分)と後半(バリデーション部分)にわけられる。
エンコード部分
ldy #$00 lda #$00 sta $3B lda $0005,y tax rol a txa rol a tax rol a txa rol a tax rol a txa rol a pha lda $3B tax ror a txa ror a tax ror a txa ror a sta $3B tax rol a txa rol a tax rol a txa rol a tax rol a txa rol a tax rol a txa rol a eor $9576,y sta $001E,y iny cpy #$18 bne $82F7
冒頭に0x0005から入力されたパスワードを読みだしている痕跡が見える。また、下の方でYレジスタと0x18(=24)を比較している部分があり、パスワード長が24桁ということからもおそらくここで間違いないことがわかる。
この部分、やたらと長いのだが冗長な部分がある。結局のところはローテート演算・排他的論理和演算による可逆暗号化を行っている。
lda $0005,y
のようにIndexレジスタを用いたアドレッシングを行っている箇所は、配列のアクセスのようなものと考える。
これを用いて下の方でエンコード結果を1バイトずつ$0x001Eから始まる24バイトのバッファに格納している。
エンコード部をPythonに直すとおおよそ次のような意味になる。
CODELEN = 0x18 DATA1 = [ # mem[0x955E] 0x70, 0x30, 0x53, 0xa1, 0xd3, 0x70, 0x3f, 0x64, 0xb3, 0x16, 0xe4, 0x04, 0x5f, 0x3a, 0xee, 0x42, 0xb1, 0xa1, 0x37, 0x15, 0x6e, 0x88, 0x2a, 0xab] DATA2 = [ # mem[0x9576] 0x20, 0xac, 0x7a, 0x25, 0xd7, 0x9c, 0xc2, 0x1d, 0x58, 0xd0, 0x13, 0x25, 0x96, 0x6a, 0xdc, 0x7e, 0x2e, 0xb4, 0xb4, 0x10, 0xcb, 0x1d, 0xc2, 0x66] def add(x, y): return 0xff & (x + y) def rol(x): return 0xff & ((x << 1) | (x >> 7)) def ror(x): return 0xff & ((x >> 1) | (x << 7)) def encode(c): a, x = 0, 0 tmp = 0 # stack mem = a # mem[0x003b] encoded = [] # mem[0x001e] m = [] for y in range(CODELEN): a = c[y] x = a = rol(rol(rol(a))) tmp = a a = mem x = a = ror(ror(a)) mem = a a = tmp # clc a = add(a, mem) a = a ^ DATA1[y] mem = a x = a = rol(rol(rol(rol(a)))) a = a ^ DATA2[y] encoded.append(a) # sta $001E, y m.append(mem) return encoded
バリデーション部分
ldy #$00 lda $001E,y bne $8346 iny cpy #$18 bne $8339 lda #$01 rts lda #$00 rts
キーとなるのはこの部分の2〜3行目。
lda $001E,y bne $8346
LDA命令はロードした値が0の場合はZeroフラグが立つ。BNE命令はBranch-on-Not-Equal-zero、つまり状態レジスタのZeroフラグが立っていなかったらジャンプする。
このジャンプ先は最終2行、0を戻り値としてリターンする。
もし24文字すべて0ならば真ん中のRTS命令でリターンするので戻り値は1。
つまり、前半のエンコードによって0x001E〜に格納されたデータがすべて0ならば、認証成功となる。
試しにパスワード入力画面において0x001E〜の24バイトをメモリビューワー上ですべて0に書き換えてエミュレータのAボタンを押すと、認証成功することが確認できる。
デコード
ここまでくれば、あとは上記のPythonのencode関数の「逆関数」に相当するものを書いて、そこに000...0を通せばflagが得られることが期待される。
大会中ではここで残り1時間となった。「デコードくらい1時間で出来るやろ！」と思っていたら土壷にハマってしまいタイムオーバーした………。
プログラム逆順に並べれば余裕余裕とか思ってタカをくくっていたけど、世の中そんな甘いもんじゃないっすよ………
たぶん漸化式書いて解くのが確実かつ速いのかなあと思う。
上記のPythonコードと比較すると、iは各ループごとのカウンタ(1〜24)、tはtmp（スタック）、cは入力されたパスワード、はループ中1回めにmemへの代入後のmemの値、mは2回目のmemへの代入後のmemの値、d^1とd^2はそれぞれDATA1とDATA2、aはそのままa、エンコード結果である（元々はAレジスタのつもりだった）。
は排他的論理和、lとrはそれぞれ左ローテートと右ローテートであり、肩の数字はローテートの適用回数である。
触れ忘れていたが、エンコード時に0x955E番地と0x9576番地から始まるそれぞれ24バイトのデータをXORのマスクに利用している。Pythonスクリプト中ではそれぞれをDATA1とDATA2としてある。実際の値はメモリビューワーで確認した。
以上の漸化式を解くと
デコード時
となる。m_0はmemの初期値で0である。
この漸化式をPythonに落としこむと当然ながら
すごいことになった。
#!/usr/bin/env python # coding: utf-8 import sys import struct CODELEN = 0x18 DATA1 = [ # mem[0x955E] 0x70, 0x30, 0x53, 0xa1, 0xd3, 0x70, 0x3f, 0x64, 0xb3, 0x16, 0xe4, 0x04, 0x5f, 0x3a, 0xee, 0x42, 0xb1, 0xa1, 0x37, 0x15, 0x6e, 0x88, 0x2a, 0xab] DATA2 = [ # mem[0x9576] 0x20, 0xac, 0x7a, 0x25, 0xd7, 0x9c, 0xc2, 0x1d, 0x58, 0xd0, 0x13, 0x25, 0x96, 0x6a, 0xdc, 0x7e, 0x2e, 0xb4, 0xb4, 0x10, 0xcb, 0x1d, 0xc2, 0x66] SPACES = [ 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20] SPACES_ENCODED = [ 0x37, 0x7a, 0x8a, 0x73, 0x4f, 0xad, 0x6d, 0xa0, 0x1c, 0x90, 0x7d, 0xce, 0x68, 0x06, 0x19, 0xdb, 0x4c, 0x06, 0x7b, 0x45, 0x48, 0x65, 0x4e, 0xef] def add(x, y): return 0xff & (x + y) def sub(x, y): return 0xff & (0xff + x - y + 1) def l(x): return 0xff & ((x << 1) | (x >> 7)) def r(x): return 0xff & ((x >> 1) | (x << 7)) # 与えられたパスワードをエンコードする def enc(c): m = [0] for i in range(CODELEN): m.append((l(l(l(c[i])))+r(r(m[i])))^DATA1[i]) e = [l(l(l(l((l(l(l(c[i])))+r(r(m[i])))^DATA1[i]))))^DATA2[i] for i in range(CODELEN)] return e # 与えられた列にエンコードされるパスワードを計算する def dec(c): m = [r(r(r(r(c[i] ^ DATA2[i])))) for i in range(CODELEN)] m.insert(0, 0) d = [r(r(r(sub(r(r(r(r((c[i]^DATA2[i])))))^DATA1[i],r(r(m[i])))))) for i in range(CODELEN)] return d def readcode(filename): with open(filename, 'rb') as f: buf = f.read(CODELEN) return [struct.unpack('B', buf[i:i+1])[0] for i in range(CODELEN)] if __name__ == '__main__': if len(sys.argv) < 2: # 可逆暗号なのでエンコードしてデコードすると元に戻る print("test mode ... ", end="") code = SPACES print(dec(enc(code)) == code) else: # 第1引数にエンコードされた列の入ったファイルを渡すとデコードする # システム上エンコードすると\x00...\x00となるパスワードがvalid code = readcode(sys.argv[1]) x = dec(code) print("".join([chr(c) for c in x]))
まあそもそもスクリプトと漸化式で変数名やインデックスの振り方が微妙に違うので読みづらい事この上ないことはご愛嬌なのだが
e = [l(l(l(l((l(l(l(c[i])))+r(r(m[i])))^DATA1[i]))))^DATA2[i] for i in range(CODELEN)]
d = [r(r(r(sub(r(r(r(r((c[i]^DATA2[i])))))^DATA1[i],r(r(m[i])))))) for i in range(CODELEN)]
S式かよ
とツッコみたくなった。おわり。
flagはNOHACK4UXWRATHOFKFUHRERXでした。あ、でもシステムには通せなかったので保証できません。
