Internetwache CTF 2016 の writeup

2/20~2/22にあったInternetwache CTF 2016にTSGの有志で参加した際に自分の関わった問題のWriteUp。

感想

わりと初心者向けらしく、全完したチームがたくさんあった。
たまにエスパー問が混じっていたのでそのあたりは辛かった。
(自分が関わったやつでは、crypto50,code80,code90,reversing80あたりがエスパー問ではないかと思う)

reversing50

なにかの逆アセンブル結果みたいなやつが与えられ、ググるとR3000の命令であることが分かる。読んでいくと、中ほどで

ans = ""
for i in xrange(len(flag)):
    ans += chr(ord(flag[i]) ^ i)

print ans

みたいにfor文が回っていることが分かるので、これより元のflagを推測する。
(XORなので、逆に変換結果を突っ込んでやれば変換前のflagが分かる)

reversing60

x64のELFファイルが与えられる。

とりあえず実行すると、

Fatal error: File does not exist

と出るので、ltraceをかまして実行すると、.password なるファイルがいることが分かる。

で、そのファイルを作った後gdbで実行しながら挙動をみると、

int i=0;
int ok = 0;
for(;;){
	char c = fgetc();
	ok |= subrutin(i,c);
}

みたいになってることが分かる。
多分subrutinが全部0を返せばよさそう。
で、subrutinは、

subrutin(int i,char c){
	スタックの一部(たぶん配列かなにか,datとしておく)に数を積む;
	char nc = dat[i];
	ncを用いてなにごとかしている;
}

みたいになってる。
さて、「ncを用いてなにごとかしている」ところを解析してもよいのだが、ここでいったんdat配列の中を書き出してみると、

dat[] = {ee,e0,bc,f1,ee,eb,f2,d8,f4,ef,d2,f4,ec,d6,ba};

みたいになってる。
ここで、flagの形式がIW{*********}となってることを思いつつ、
ee が I に、e0 が W に、 bc が { に、 ba が } に
対応しているかとあたりをつけて手元で適当にいじってみると、

ord(c) + ord(dat[i]) == 0x137

みたいになってる、
ので、後は変換してやれば

v = "ee,e0,bc,f1,ee,eb,f2,d8,f4,ef,d2,f4,ec,d6,ba"
v = map(lambda x: int(x,16),v.split(','))

ans =""
for c in v:
	ans += chr(int("137",16) - c)

print ans

で、flagが出てくる。

reversing70

ARMのELFファイルが与えられる。
QEMUでも入れて解析する必要があるかなー、とか思っていたが、IDAのdemo版でも逆アセンブルができるそうなので、IDAの方に投げてみる。

見ると、mainは

main(){
	char s* = malloc(0x65);  // s .. [esp - 0xc] 
	int i = 0; //i.. [esp-0x8]
	
	for(;;){
		if (i + 1 == [esp - 0x10]){
			free(s);
			return;
		}
		
		printf("Enter Solution for task%d\n",i);
		scanf("%s",s);
		handle_task(i,s);
		i++;
	}
}

みたいになってて、handle_task()は、

handle_task(int ii,char* is){
	int i = ii;
	char* s = is;

	switch(i){
	case 0:
		if()printf("IW{S.E\n");
		break;
	case 1:
		if()puts("WI{QA3}");
		else printf(".R.V.E\n");
		break;
	case 2:
		if()puts("R>=F:");
		else printf(".Q.D.Q!\n");
		break;
	case 3:
		if()printf("A:R:M}\n");
		break;
	}
}

みたいになってることがおおざっぱに分かる。頑張ってそれぞれのif文内を読むと正解が分かるはずだが、まあフラッグの形式等その他もろもろから判断して、適当にありえそうな文字列を試してみると、flagは

IW{S.E.R.V.E.R>=F:A:R:M}

であることが分かる。

reversing80

Hello world program in esoteric languages - Esolang

を眺めてみると、TapeBagelという言語であることが分かるので、言語仕様を調べて動かそうとしてみる、が、動かない。(プログラム例もHello Worldしか見つからなかったし、実装もインタプリタ1つしかないし、ヒントは意味が分からないし、エスパーするしかないですよね...)
四苦八苦しているとcookies氏が倒してくれた。

reversing90

問題ファイルより抜粋

Scrambling:
F' D' U' L' U' F2 B2 D2 F' U D2 B' U' B2 R2 D2 B' R' U B2 L U R' U' L'

White side:
-------
|I|3| |
| |D|R|
| | | |
-------

Orange side:
-------
|C| | |
| | | |
| | | |
-------

Yellow side:
-------
|{| | |
|3| | |
| | |}|
-------


Red side:
-------
| | | |
|W| | |
| | | |
-------

スクランブルの書き方からしてもルービックキューブですね。
おそらく、この通りに箱に文字を貼って回すとフラッグが出るのだろうけれども、
フラッグが IW{*****} の形式で、また角のキューブは角に、辺のキューブは辺にしかこないことから、
IW{3D3CR} , IW{3DRC3} , IW{RD3C3}
のどれかであることが分かるので、あとは全探索submitしてやればよい(雑)

exploit60

telnet接続すると、向こうでなにかプログラムが動いていて、

Solve the following equations:
X > 1337
X * 7 + 4 = 1337

と言われる。
まあそんな整数Xはないわけですが、
とりあえず適当にでかい数(2000000000とか)を打ち込んでやると、

2000000000
2000000000 is bigger than 1337
-4235423 is not equal to 1337

とか返ってくるわけです。(値は適当)
X*7+4がオーバーフローして負の数になってしまってることが推測できるので、
1337より大きくて、うまくオーバーフロー後の結果が1337になるような数を計算して送りつけてやると、フラッグが表示される。
(自分は613566947でやった)

crypto70

自作ハッシュ関数の実装と、ハッシュ化した後のパスワード(00006800007d)が与えられるので、認証を突破してください、という問題。
おそらく、内部ではハッシュ化後の値を持っていて、入力された文字列のハッシュ値と持ってる値が等しければＯＫ,みたいな認証を行ってると推測できる。
当初は、ハッシュ関数の構造を解析すれば解けるかと思ったが思ったより面倒だったので深入りせず。
ソースコード中に

	t11 = t11 % 0xFF # Should be 0xFFFFFFFF, right?
	q2 = q2 % 0xFF # Same here... 0xFFFFFFFF

という部分があって、t11とq2を連結した結果がハッシュ値になるのだが、
これより実はハッシュ値がたかだか255^2パターンしかないことがわかる。
よって、弱衝突耐性がまったくなく、適当に探索していればハッシュ値が(00006800007d)になるような文字列を見つけることができる。
自分が見つけたのは(0xd49b00000000000000)

crypto90

銀行っぽいシステムが向こうで稼働していて、
create->completeの順で手続をすると、金が自分の口座に入金される。
預金が10^6以上になればflagが手に入るが、入金はたかだか20回しかできず、一回につき5000までしか入金できない、といった設定。

入金は、詳細には
create で入金金額mを決める,と、

def create(m):
	if m > 5000:
		return None
	t = os.urandom()
	myrand.init(t)
	s = "TRANSACTION: " + str(m)
	for i in xrange(len(s)):
		s[i] ^= myrand.get() % 256
	
	transactions.append(t)
	print s

みたいなことをして、その後、
completeで、

def complete(p,s):
	if(not len(s) in range(28, 35)):
		return None
	t = transactions[p]
	myrand.init(t)
	for i in xrange(len(s)):
		s[i] ^= myrand.get() % 256

	if(not "TRANSACTION" in pt):
		return None
	a = int(pt.replace("TRANSACTION:",""))
	Account.addmoney(a)

みたいなことをする、といった感じ。
myrandは、自作の線形合同法乱数生成機だった。

cerate時には、
t は予測不能、知ることもできない
m はある程度任意の整数が選べる
s は分かる

といった感じなので、sからmyrand.init(t)がどういう乱数列を返すのかが分かり、
myrandが線形合同法なので、得られた乱数列からその後どういう乱数が得られるのかが予測できる。(この問題を解くにはここまでしなくてもよかったらしいが)

よって、create(1)とかをしたあと、そこから得られた乱数列に従って、元に戻すと
"TRANSACTION:99999" になるような文字列を送りつける、と、
99999が入金される。
ので、これを11回繰り返してやればよい。

code50

code系は、全て、向こうのサーバで問題が動いてるのでそれを解け、みたいなの。

7 + X = 28

みたいな問題が飛んでくるので、方程式の解を返す問題。
Xを-5000から5000くらいまで試して、
左辺と右辺をevalして等しければOK,みたいなことをやっていた。

import socket
import re
import random
import time

cre = re.compile(r':.*')

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('188.166.133.53', 11027))
s = sock.recv(1024)

for i in xrange(1000):
	print s
	s = sock.recv(1024)
	print s
	ts = cre.findall(s)[0][1:].split('=')
	print ts
	
	ans = -1
	for tx in xrange(10000):
		x = tx-5000
		if eval(ts[0]) == eval(ts[1]):
			ans = x
			break

	print "ans .. " , ans
	
	s = sock.send(str(ans) + "\n")
	time.sleep(0.1)
	s = sock.recv(20)

code60

与えられた数より大きな最初の素数を返せ、という問題。
ミラー–ラビン素数判定法 - Wikipedia
を使えばよい。

code70

    def encode(self, eq):
        out = []
        for c in eq:
            q = bin(self._xor(ord(c),(2<<4))).lstrip("0b")
            q = "0" * ((2<<2)-len(q)) + q
            out.append(q)
        b = ''.join(out)
        pr = []
        for x in range(0,len(b),2):
            c = chr(int(b[x:x+2],2)+51)
            pr.append(c)
        s = '.'.join(pr)
        return s

というのが与えられて、これを用いてencodeしたと思しき文字列が飛んでくる、
ので、

def decode(s):
	t = map(lambda x: int(x,10)-3, s.split('.'))
	print t
	ls = len(t)
	
	res  =""
	for i in xrange(ls/4):
		p = 0
		for j in xrange(4):
			p *= 4
			p += t[i*4+j]
		
		c = xor(p,(2<<4))
		res += chr(c)
	
	return res

というのを作ってやって、decodeすると、code50の問題みたいな文字列が得られる。
code50のソルバを通して、答えをそのまま投げる……と、Wrongと返ってくる。
しばらくの試行錯誤の後、答えをencodeして投げればよいと分かる。(ちとエスパーかな)

code90

めちゃエスパー問だと思っている。闇。
なんか、二分木だのinvertだの、出てくる。問題文が読めない。木なのか森なのか判然してくれ。
そもそもLevel1に対して何を返せばよいのか分からなかった。
(1つの数字なのか、配列なのか。配列なら、フォーマットは数字をスペースで並べたものか、カンマで区切って括弧で囲えばいいのか)

与えられた配列pに対して、

def inv(p):
	if len(p)==0:
		return []
	h  = p[0]
	r,l = [],[]
	p = p[1:]
	for x in p:
		if x>h:
			l.append(x)
		else:
			r.append(x)
	return ([h] + inv(l) + inv(r))

をかけたのを返せばよいと分かったのは夜も遅くなってからだった。
エスパーはもうこりごり。