年賀状CTF2016 (by @_N4NU_) writeup
先日、ふるかわ（@_N4NU_）さん作成の年賀状CTFを解きました。
年末年始にかけて泊まり仕事だったので、問題を見た時には、すでにakiym（@akiym）さんがAmazonコードを獲得した後でした。
「賞金もなくなったようだし、ちょっと覗くくらいにしておこうか……」と軽い気持ちで始めたのですが、やってみるとかなり面白い問題で、一気に最後まで解いてしまいました。ふるかわ（@_N4NU_）さんの許可も頂きましたので、writeupを公開します。
年賀状CTF公開！！！ はてなブログに投稿しました #はてなブログ
年賀状CTF（お年玉付き） - WTF!?
https://t.co/wiWOXHn4E6
— ふるかわ (@_N4NU_) 2015, 12月 31
2016年1月1日午前0時15分、上記ツイートから問題が公開されました。
ツイートされたブログ記事には、問題ファイルへのリンクが貼ってあります。
問題ファイルはdropboxに置かれているwc16g_tf_0003.pngという名前のPNGファイル（ https://www.dropbox.com/s/ptv100otuapnt38/wc16g_tf_0003.png?dl=0 ）で、内容は年賀状の画像です。
バイナリエディタで覗いてみると、IENDチャンクの後ろにかなり長いデータが付いていることが分かります。（0x33eb51以降）
これを切り取ってfileコマンドで調べると、
gzip compressed data, from Unix, last modified: Thu Dec 31 23:26:13 2015
なるほど。
解凍すると、ファイルが出現します。これをfileコマンドにかけると、
POSIX tar archive
展開すると、stage1というフォルダが出現します。
CTF開始です。
stage1フォルダの中には「stage1.pyc」と「stage2.tar.gz.gpg」の２つのファイルが入っています。
どうやらstage2に行くためには、stage1.pycの謎を解く必要がありそうです。
「.pyc」の拡張子から分かる通り、stage1.pycはpythonのバイトコードファイルです。そのままではちょっと読めません。
色々な手法がありますが、今回はuncompyle2（ https://github.com/wibiti/uncompyle2 ）を使って、元のpythonコードを取得しました。
取得できたコードはこちら。
import sys
from os.path import getsize, basename
try:
from PIL import Image
except ImportError:
import Image
if len(sys.argv) < 3:
sys.stderr.write('Usage: {0:s} png_file message\n'.format(sys.argv[0]))
sys.exit(1)
im = Image.open(sys.argv[1])
width, height = im.size
message = sys.argv[2]
for i in xrange(len(message)):
pix = list(im.getpixel((i % width, i / width)))
pix[i % 4] ^= ord(message[i])
im.putpixel((i % width, i / width), tuple(pix))
im.save(basename(sys.argv[1]).split('.')[0].encode('rot13') + '.png')
どうやら、このコードを使ってpngファイルにメッセージを書き込んだようです。具体的には、左上のpixelから、元のpixelのRGBAの値と、メッセージのASCIIコード値をxor演算することによって、メッセージを画像内に書き込んだようです。しかし、全てのRGBAの値がxorされる訳ではなく、1 pixelごとに「赤・緑・青・アルファチャンネル・赤・緑……」と、xorされる部分が変化しています。
メッセージを書き込んだ画像は、恐らく最初の問題ファイルwc16g_tf_0003.pngでしょう。よく見ると、画像の左上にメッセージを書き込んだ形跡が見えます。（何となく虹色に見える部分）
しかし、ここからが問題。どうやってメッセージを取り出すか？
隣接pixelとの比較では、どうやら色調が少し変わっているようで、無意味なメッセージしか抽出できません。
ここで、なぜかファイル名をrot13している点に注目します。ファイル名を知られたくない理由があるのでしょうか？
迷ったらGoogle、ということで、「wc16g_tf_0003」をrot13した「jp16t_gs_0003」をGoogle検索すると、下記のページがひっかかります。
（ https://yoshizen.wordpress.com/tag/new-years-card/ ）
ここには、まさに年賀状画像と同じ画像があります。しかし、ファイルはjpeg、これでは復号には使えません。
ページをよく読むと、「The card samples here are from Japan Post」と書いてあり、郵便年賀.jp（ http://yubin-nenga.jp/search/ ）へのリンクが貼られています。
郵便年賀.jpのページをよく探すと、元ファイル（jp16t_gs_0003.png）が見つかります。これを使って、以下のようなコードで復号します。
import sys
from os.path import getsize, basename
try:
from PIL import Image
except ImportError:
import Image
im = Image.open(sys.argv[1])
im2 = Image.open(sys.argv[2])
width, height = im.size
ans = ""
for i in xrange(100): # assume len(message) = 50
pix = list(im.getpixel((i % width, i / width)))
q = pix[i % 4]
pix = list(im2.getpixel((i % width, i / width)))
r = pix[i % 4]
ans = ans + chr(q^r)
print ans
実行すると、
$ python stage1.py wc16g_tf_0003.png jp16t_gs_0003.png
Congratz!!! Password: D3c0mpilin6_4nd_R3v3rs1n6_pyc_15_700_345y
このパスワードでgpgを復号できます。これにより、stage2.tar.gzが抽出されます。
いよいよstage 2です。
stage2フォルダの中には「LifeGame.html」があり、これを開くとライフゲームが始まります。
LifeGame.htmlのソースを見ると、単にmain.jsを実行しているだけということが分かります。問題のmain.jsはきつく難読化がかけられており、そのままでは読めません。解読が必要です。では、どのような難読化がかけられているのか？どうやって解読するか？これがstage 2最初の関門です。
JavaScriptの難読化については、はせがわようすけさんのスライド（ http://www.slideshare.net/hasegawayosuke/javascript-51570525 ）が詳しいです。これを読んで考えると、恐らくmain.jsはjjencodeで難読化したあと、さらにpackerをかけたものと考えられます。
方法は色々ありますが、今回、私はFireBugを使いました。
何のことはなく、ライフゲームを開いた状態でFireBugのスクリプトタグを開くと、難読化が解除された状態のスクリプトが表示されます。これをコピペしてエディタに貼り付け、解析します。
スクリプトを色々検索してみると、print_flagという文字列が目にとまります。
c_World.prototype.p_print_flag=function(){
var t_f=[207,254,234,234,142,150,114,155,197,161,205,206,185,51,30,134,203,178,68,94,49,202,160,223,204,209,190];
for(var t_i=0;t_i<t_f.length;t_i=t_i+1){
var t_s=0;
for(var t_j=0;t_j<8;t_j=t_j+1){
t_s+=this.p_GetCell(t_i+1,t_j+6).m_status<<7-t_j;
}
t_f[t_i]^=t_s;
}
print(string_fromchars(t_f));
}
どうやら、このルーチンでflagを生成しているようです。
これは
if(this.m_map.p_is_collect()){
this.m_map.p_print_flag();
}
で実行されます。is_collectで何をしているかを読むために、関連する部分を抜き出してみます。
c_World.prototype.p_GetCell=function(t_col,t_row){
if(t_col<this.m_cols && t_col>=0 && t_row<this.m_rows && t_row>=0){
return this.m_grid[t_row*this.m_cols+t_col];
}
return null;
}
c_World.prototype.p_is_collect=function(){
var t_collect=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,251,241,143,199,239,206,63,1,179,120,192,6,204,99,1,251,49,143,199,236,198,63,24,51,24,204,96,204,99,49,251,247,239,199,239,223,191,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
for(var t_i=0;t_i<this.m_grid.length;t_i=t_i+1){
if(((!((t_collect[((t_i/8)|0)]>>7-t_i % 8&1)!=0))?1:0)==this.m_grid[t_i].m_status){
return false;
}
}
return true;
}
this.m_grid=new_object_array(t_cols*t_rows);
this.m_map=c_World.m_new.call(new c_World,30,20);
要は、ライフゲームがある特定の状況になると、マップの状態を元にflagが生成されるということのようです。
マップの状態はm_gridに保存されており、これを元にp_print_flagでflagが生成されます。正しいm_gridを生成し、それを元にしてflagを生成するpythonコードを書くと、以下のようになります。
data = [207,254,234,234,142,150,114,155,197,161,205,206,185,51,30,134,203,178,68,94,49,202,160,223,204,209,190]
c = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,251,241,143,199,239,206,63,1,179,120,192,6,204,99,1,251,49,143,199,236,198,63,24,51,24,204,96,204,99,49,251,247,239,199,239,223,191,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
grid = [0]*600
# make correct grid
for a in range(0,600):
x = c[a/8] >> ((7-a)%8)
x = x & 1
grid[a] = x
print grid
for a in range(len(data)):
s = 0
for b in range(0,8):
s += (grid[ (b+6) * 30 + (a+1)] << (7-b) )
data[a] ^= s
print "%r" % "".join(map(chr,data))
これを実行すると、
'Password: L1F3_G4ME_15_FUN!'
これにより、「stage3.gz.gpg」より「stage3.gz」が生成されます。
いよいよ最終問題です。
「stage3.gz」からは「stage3」というファイルが解凍されます。
ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), statically linked, stripped
ということで、ELFバイナリの解析です。
普通に実行してみると、
$ ./stage3
Usage: ./stage3 flag
$ ./stage3 123
Invalid. Try again.
どうやら、正しいflagを引数に入れる必要があるようです。
実行ファイルをテキストエディタで開いてみると「UPX!」という文字が目に入ります。どうやら、UPXでパックされたバイナリのようです。
では、ということで解凍してみようとすると、
stage3: CantUnpackException: header corrupted 2
あれ？
どうやら、何らかの工作が施され、UPXの解凍ができなくなっているようです。
gdbで実行してEntryPointで処理を止め、i proc mapを実行しメモリ配置を確認すると、
Start Addr End Addr Size Offset objfile
0xc01000 0xc46000 0x45000 0x0 ./stage3
0x80ec000 0x80ed000 0x1000 0x0 ./stage3
0xf7ffb000 0xf7ffc000 0x1000 0x0 [vdso]
0xf7ffc000 0xf7ffe000 0x2000 0x0 [vvar]
0xfffdd000 0xffffe000 0x21000 0x0 [stack]
ここで、一度pin（ https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool ）を使ってitraceを取って、その最後の方を見てみます。(pin toolについての詳細はここでは省きます)
$ sudo ./pin -t './source/tools/ManualExamples/obj-ia32/itrace.so' -- ./stage3 123
Invalid. Try again.
$ tail ./itrace.out
0x804e8fa
0x806cc21
0x806cc25
0x806cc2a
0xf77dbd70
0xf77dbd71
0xf77dbd72
0xf77dbd73
0xf77dbd75
#eof
$
先ほどにはなかった「0x804e8fa」などのメモリ領域を実行していることが分かります。
gdbでブレークポイントをこのアドレスに仕掛けようとすると失敗します。しかし、ハードウェアブレークポイントであれば可能です。（ただし、実行中でないとハードウェアブレークポイントは仕掛けられないことに注意）
b *0xc454f8
r
hbreak *0x804e8fa
c
i proc map
Start Addr End Addr Size Offset objfile
0xc01000 0xc02000 0x1000 0x0 ./stage3
0x8048000 0x80e9000 0xa1000 0x0
0x80e9000 0x810f000 0x26000 0x0 [heap]
0xf7ffb000 0xf7ffc000 0x1000 0x0 [vdso]
0xf7ffc000 0xf7ffe000 0x2000 0x0 [vvar]
0xfffdd000 0xffffe000 0x21000 0x0 [stack]
0x8048000以降のメモリが確保され、実際に実行されていることが確認できました。
ここで、gdb上で「dump binary memory stage3_2 0x8048000 0x810efff」と入力すると、unpackされたstage3のバイナリがstage3_2というファイルにダンプできます。ようやくプログラム本体のreversingの開始です。
逆アセンブルを解析すると、main関数が0x8049067にあること、さらに0x8048ffdが入力文字列のチェック関数であることが分かります。
チェック関数は、ざっくり解説すると
「文字数が16文字であることを確認する」
「5文字目と12文字目が"-"であることを確認する」
「最後に連続して４つの関数（0x8048f9f、0x8048f3e、0x8048e90、0x8048e24）を実行する」
という流れになっています。この最後の４つの関数がくせ者。いずれもそれほど長くない関数なので、ハンドデコンパイルします。
（ここでデコンパイルをサボってしまうと嵌まります。IDA Proがあれば、この手間はいらないのかも知れませんが……）
このバイナリはlibcをstatic linkしているため惑わされやすいですが、とりあえず関係なさそうな関数は後で解析するとして、まず簡単にハンドデコンパイルすると、流れが見えてきます。
// 0x8048f9f
for (v8 = 0;v8 < 4; v8++)
{
for(v4 = 0;v4 < 4;v4++)
{
edx = v8*4 + v4;
0x80ec030[edx] = [ebp+0x8][edx]
}
}
// [ebp+0x8]には、入力文字列「XXXX-XXXXXX-XXXX」が入っている
// 0x80ec030以降16bytesに入力文字列をコピーする
//0x8048f3e
for (v8 = 0;v8 < 4; v8++)
{
sub_804eb90(0x2df);
for(v4 = 0;v4 < 4;v4++)
{
edx = v8*4 + v4;
0x80ec020[edx] = sub_804f120();
}
}
// sub_804eb90は恐らくsrand、sub_804f120は恐らくrand
// sub_804eb90に渡す数字を変えると、sub_804f120の出力も変わる
// rand()のデータを0x80ec020以降16bytesにコピーする
//0x8048e90
for (v10 = 0; v10 < 4; v10++)
{
for(vc = 0;vc < 4;vc++)
{
for(v8=0;v8 < 4;v8++)
{
0x80eb05c[ vc + v10 * 4 ] = 0x80eb05c[ vc + v10 * 4 ] + 0x80ec020[ v8 + v10*4 ] * 0x80ec030[vc + v8 * 4]
}
}
}
// 0x80ec020と0x80ec030を元にして、上記の計算式で0x80eb05c以降16bytesを生成する。
// 最後に、0x8048e24で、生成された0x80eb05cをハードコードされた回答0x80ea068と比較して終了。
この結果から、生成された0x80eb05cが、0x80ea068と同じになればOKということが分かります。
ここで、0x80eb05cの1,5,9,13文字目は、入力文字列1,5,9,13文字目と連動して変わります（入力文字列が１文字変わるだけで、４文字全てが変わります）
同様に、0x80eb05cの2,6,10,14文字目は、入力文字列2,6,10,14文字目に対応します。
さらに、アマゾンギフト券に使われる文字は"-1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"だけのようです。
gdbのダンプから、0x80ec020に入っているデータも分かります。
r 1234-123456-1234
x/s 0x80ec020
0x80ec020: "%\223@\356\a\r\265\365!|:\247\362\222\360e1234-123456-1234("
x/50wx 0x80ec020
0x80ec020: 0xee409325 0xf5b50d07 0xa73a7c21 0x65f092f2
(snip)
gdb-peda$ x/s 0x80ea068
0x80ea068: "\320?>\b[7y\036F\341\020P\261\346s\247"
ここまで分かれば、4文字ごとのブルートフォースで答えを割り出せることが分かります。最大でも4*(37^4) = 7496644通りの組み合わせの中に正解が存在するはずですので、十分に可能な範囲です。
実際のコードは以下のようになります。
data = "\320?>\b[7y\036F\341\020P\261\346s\247"
ans = [" "] * 16
possible = "-1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"
m = [[37,147,64,238],[7,13,181,245],[33,124,58,167],[242,146,240,101]] # from 0x80ec020
for now in range(0,4):
flag = 0
for a in possible:
if flag == 1:
break
for b in possible:
if flag == 1:
break
for c in possible:
if flag == 1:
break
for d in possible:
q = [0] * 4
for z in range(0,4):
q[z] = m[z][0] * ord(a) + m[z][1] * ord(b) + m[z][2] * ord(c) + m[z][3] * ord(d)
q[z] = q[z] % 256
if q[0] == ord(data[0+now]) and q[1] == ord(data[4+now]) and q[2] == ord(data[8+now]) and q[3] == ord(data[12+now]):
print a,b,c,d
ans[0+now] = a
ans[4+now] = b
ans[8+now] = c
ans[12+now] = d
flag = 1
break
print "".join(ans)
そして、結果は……。
7 - X U
M Z Z H
S 7 R S
5 W - S
7MS5-Z7WXZR-UHSS
確かめてみましょう。
$ ./stage3 7MS5-Z7WXZR-UHSS
Congrats! You got the amazon code.
ようやく到達！お疲れ様でした。
もっとうまいやり方もあるかも知れません。解けた方のwriteup、期待しています。
年始より楽しいCTFでした。ふるかわ（@_N4NU_）さん、ありがとうございました！