SECCON CTF 2014 決勝戦 六(6) Writeup

2015/02/07,2015/02/08にteam 0x0(@nash_fs, @superbacker, @waidotto, @wafrelka)でSECCON CTF 2014決勝戦に参加していました。
結果は5位/24で、3連覇達成はなりませんでした。

以下、サーバ六(6)のWriteupです。

概要

サーバ6はCrypt系で、次のような内容でした。

1.Your team can upload a python code(enc/dec pair).
2.After your team uploads your code, you will not be allowed to upload again for 1 hour.
3.You will be able to get a keyword for AP if you break ID1-4 codes.
4.All codes will be ranked by its code size.
5.Your team will gain DP while your code keep 1st place.
6.Your team's defense flags are written automatically into the flag page.
7.The flag page is here(フラグページヘのリンク).

8.INPUT will consist of 64 characters (A-Za-z0-9_/)
9.OUTPUT must consist of 64 characters (A-Za-z0-9_/)

(*) AP=ATTACK POINT, DP=DEFENCE POINT




ID: 00000001

単純な換字式暗号です。
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_/
を入力すればテーブルが得られます。

s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_/'

table = 'b1gkVL0PTaQwprGUvK5mtnZBMD8SI3oHqACRzJE_7y6iOud2hW9jflNFxeX4/sYc'

cipher = 'U8OOh7i3YI8_YJo8i_Yi7IzY37Y5u9JoY97dYOCud8uC7_YHC_3YbY8_3YhiCuoYu7YhACJoYE8C_J9Y7IIdiio3YA8OYA8IzoiYuAoY7iYdOoYhi7uoYio83YiCqAuY'

plain = ''
for c in cipher:
	plain += s[table.find(c)]

print plain

ID: 00000002

各文字の変換結果は入力の文字数 mod 4にのみ依存しており、暗号文が64文字なので、やはり
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_/
を入力すればテーブルが得られます。

s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_/'

table = 'RhW4NCBlFexfymtp/oELivM69cQSqYgIjkdurJz28AwP0U5D1Zb3HaXKTnOV_7sG'

cipher = 'pQ0018PYsa7_nskQqrgP0szQrgsSg0Usa77OsdYg2UdIdqQUd82sQskQqrgPsd0sQYzd2d0UPQUd82szb0gJIs1kbsUkgsUdzgs1gJJszQbsd0sUkgs0k85JYsUdUJgs'

plain = ''
for c in cipher:
	plain += s[table.find(c)]

	print plain

ID: 00000003

@wafrelkaが解いてくれました。
文字ごとにテーブルをローテートしているらしい？です。

ID: 00000004

試しにABを投げてみると、次の出力が得られます。

AAAAAlBoSAB

明らかにBase64なのでデコードします。

00 00 00 02 50 68 48 00

他にもいくつか投げてみると、次のようなことがわかります。

  • 単一の文字からなる場合のみランレングス圧縮
  • 複数の文字がある場合、はじめの4バイトは文字列長
  • なんかハフマン符号っぽい(勘)

既存の圧縮アルゴリズムかと思いましたが、よくわからなかったので自力で解きました。

入力をもう少し長くしてbbbbbaaaddddcceeeeeとしてBase64デコードして先頭4バイトを取り除いて2進数にすると、次が得られます。

00101100 01010110 01010101 10010001
01100001 10110001 10000000 00011011
01101010 10101111 11010101 01010000
00000000

このビット列をしばらく眺めると次のように見えます。

001 01100010 #'b'
1 01100101 #'e'
01 01100100 #'d'
01 01100001 #'a'
1 01100011 #'c'
00 00 00 00 00
110 110 110
10 10 10 10
111 111
01 01 01 01 01
000000000000

これから'b'->00, 'a'->110, 'd'->10, 'c'->111, 'e'->01という符号が得られます。
これをハフマン木で書いてみると次のようになります。

これから次のようなアルゴリズムで復号できると推測できます。

  1. 連続する0の数だけ左下へ行く(行きがけに'*'で埋める)
  2. 1が来たら、その後ろ8ビットを文字として置く
  3. 一つ上る
  4. 現在いる場所の右下が空になるまで上る
  5. 木が埋まっていなければ1.に戻る
  6. 出来上がったハフマン木に従って文字数ぶん復号する

次のようなコードで復号できました。

import math

s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_/'

cipher = 'AAAAgBX7KsK03QWS3Leud1FmWe5LyodjFstpL6Eo1JFKpioWItFrXBdrv6Vrf9ZwOK3TmBqriKkisDVXD/E45TcNOQUwNumw8L8pNiO4vLfxzsz6FYGDMB25IvYwO2ZI6qzbhOMi4dfSGkQfd8h5YAB=='
bc = cipher.decode('base64')
length = int(bc[:4].encode('hex'), 16)
bc = ''.join(['{0:08b}'.format(ord(x)) for x in bc[4:]])

tree = [None] * (2**16)
def downLeft(p):
    return p * 2 + 1
def downRight(p):
    return p * 2 + 2
def up(p):
    return (p - 1) // 2
def depth(p):
    return math.floor(math.log(ptr + 1, 2))
ptr = 0

break_flag = False
while True:
    while bc[0] == '0':
        bc = bc[1:]
        tree[ptr] = '*'
        ptr = downLeft(ptr)
    bc = bc[1:]
    tree[ptr] = chr(int(bc[:8], 2))
    bc = bc[8:]
    ptr = up(ptr)
    while tree[downRight(ptr)] != None:
        ptr = up(ptr)
        if ptr == 0 and tree[downRight(ptr)] != None:
            break_flag = True
            break
    if break_flag:
        break
    ptr = downRight(ptr)

plain = ''
while 0 < len(bc):
    ptr = 0
    while tree[ptr] == '*':
        if bc[0] == '0':
            ptr = downLeft(ptr)
        if bc[0] == '1':
            ptr = downRight(ptr)
        bc = bc[1:]
    plain += tree[ptr]
    if length <= len(plain):
        break
    
print plain

Defence Point

プレイヤーはenc.pyとdec.pyをアップロードすることができ、plain == decode(encode(plain))ならば受理されます。
len(enc.py) + len(dec.py)が小さいほどランキング上位に入れます。
最短は、enc.py, dec.pyをともに

INPUT=OUTPUT

にすればOKです。
ただし、他のプレイヤーが暗号文を復号してcipher == encode(plain)にできればそのコードをランキングから落とすことができます。
しかしplain == decode(encode(plain))のチェックはアップロード時にしか行われないため、
例えばenc.pyとdec.pyを

OUTPUT=`id(0)`+INPUT

OUTPUT=INPUT[8:]

とすることで、36バイトのコードで実質的にcipher == encode(plain)にできなくなってしまいます。
これによってDefence Pointを稼いでいたチームが多かったようです。

その他

このサーバはどうやらcode golfをするのが正攻法(？)だったようです。
enc.pyでなんとかしてリバールシェルを起動させたりファイルを読んだりしようとしましたが、サンドボックス内で動いていたためダメでした。
アップロード時にSyntaxErrorなどが起きる場合、エラーメッセージが返されるので、例えば

raise NameError('hoge')

などとするとhogeが返ってきます。
これを利用して得られた情報をいくつか記します。

repr(os.uname())

('Linux', 'ubuntu', '3.13.0-32-generic', '#57-Ubuntu SMP Tue Jul 15 03:51:08 UTC 2014', 'x86_64')
sys.version

2.7.6 (default, Mar 22 2014, 22:59:56) 
[GCC 4.8.2]
os.getcwd()

/usr/lib/cgi-bin
repr(os.environ)

{'HTTP_REFERER': 'http://6.finals.seccon.jp/', 'CONTEXT_DOCUMENT_ROOT': '/usr/lib/cgi-bin/', 'SERVER_SOFTWARE': 'Apache/2.4.7 (Ubuntu)', 'CONTEXT_PREFIX': '/cgi-bin/', 'SERVER_SIGNATURE': '<address>Apache/2.4.7 (Ubuntu) Server at 6.finals.seccon.jp Port 80</address>\n', 'REQUEST_METHOD': 'POST', 'SERVER_PROTOCOL': 'HTTP/1.1', 'QUERY_STRING': '', 'PATH': '/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin', 'CONTENT_LENGTH': '1156', 'HTTP_USER_AGENT': 'Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:35.0) Gecko/20100101 Firefox/35.0', 'HTTP_CONNECTION': 'keep-alive', 'SERVER_NAME': '6.finals.seccon.jp', 'REMOTE_ADDR': '192.168.2.6', 'SERVER_PORT': '80', 'SERVER_ADDR': '10.100.6.1', 'DOCUMENT_ROOT': '/var/www/html', 'SCRIPT_FILENAME': '/usr/lib/cgi-bin/cg.cgi', 'SERVER_ADMIN': 'webmaster@localhost', 'HTTP_HOST': '6.finals.seccon.jp', 'SCRIPT_NAME': '/cgi-bin/cg.cgi', 'HTTP_CACHE_CONTROL': 'max-age=0', 'REQUEST_URI': '/cgi-bin/cg.cgi', 'HTTP_ACCEPT': 'text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8', 'GATEWAY_INTERFACE': 'CGI/1.1', 'REMOTE_PORT': '58079', 'HTTP_ACCEPT_LANGUAGE': 'ja,en-us;q=0.7,en;q=0.3', 'REQUEST_SCHEME': 'http', 'CONTENT_TYPE': 'multipart/form-data; boundary=---------------------------743837628893702018431594614', 'HTTP_ACCEPT_ENCODING': 'gzip, deflate'}
traceback.format_exc()

Traceback (most recent call last):
  File "/usr/lib/cgi-bin/pysbox.py", line 105, in _child_main
  OSError: [Errno 9] Bad file descriptor
repr(sys.modules)

長いので/cgi-bin/内のものだけ示します。

{'hadoken': <module 'hadoken' from '/usr/lib/cgi-bin/hadoken.py'>
 'cryptolog': <module 'cryptolog' from '/usr/lib/cgi-bin/cryptolog.py'>
 'acctrl2': <module 'acctrl2' from '/usr/lib/cgi-bin/acctrl2.py'>
 'pysbox': <module 'pysbox' from '/usr/lib/cgi-bin/pysbox.py'>
 '__main__': <module '__main__' from '/usr/lib/cgi-bin/cg.cgi'>
 'pysqldb': <module 'pysqldb' from '/usr/lib/cgi-bin/pysqldb.pyc'>}

/cgi-bin/pysbox.pyなどのファイルにアクセスしてもすべてInternal Server Errorでダメでした。
__main__.get_chars()が'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_/'を返すなどはわかりましたが、pythonに詳しくないので他のクラスや関数の中身はわかりませんでした。

hadoken.pyという名前が謎だったので競技終了後に愛甲さんに聞いてみたところ、
「えっ、なんでそれ知ってるの」という反応でした(「波動拳システム(=NIRVANA)」のことらしいです)。

反省

Attack PointはいつSubmitしても同じなので、ホテルに帰ってから挑戦するべきでした。
初日はDefence Pointを確実に稼いだほうが良いです。
実際に、優勝したTOEFL Beginnerは挑戦者の少ないサーバを狙って確実にDefence Pointを稼いでいたようです。

おわりに

今年もとても楽しかったです。
運営の皆様ありがとうございました。