Tokyo Westerns/MMA CTF 2nd 2016 writeup

投稿日時: 投稿者:

Tokyo Westerns/MMA CTF 2nd 2016に yharima チームで参加していたので自分が解いた分の writeup です。510点、105位でした。

Super Express

以下のようなソースコードと、それで暗号化されたデータが渡された。

import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'

if len(key) % 2 == 1:
    print("Key Length Error")
    sys.exit(1)

n = len(key) / 2
encrypted = ''
for c in flag:
    c = ord(c)
    for a, b in zip(key[0:n], key[n:2*n]):
        c = (ord(a) * c + ord(b)) % 251
    encrypted += '%02x' % c

print encrypted

鍵が長いが、よく見ると一文字ごとに暗号化している。251は素数なので、結局平文mに対して、色々な a,b （鍵の一文字一文字）で
c = am + b \mod p
を繰り返していることになる。素数を法とした世界での線形な写像なので、どこかで一定の値で固定されるのでなければ（暗号文を見る限り違う）全体を
C = Am + B \mod p
の一つの暗号とみなして問題ない（さらに言うとここまでの発想も、一部は実際には全体が一つの写像に落とし込めることに気付いてから、これが解けるのであればこうだろう、と考えた）

先頭が「TWCTF{」であることはわかっているので、わかっている二文字から係数を計算して逆元を計算して、 offset を調整して解くとフラグ。

import sys

intxt = sys.stdin.readline()

# cf: http://arc360.info/algo/privatekey.html
def euclidean(x, y):
	x1 = 1
	y1 = 0
	z1 = x
	x2 = 0
	y2 = 1
	z2 = y

	while z2 != 1:
		q = (z1 - (z1 % z2)) / z2
		x1 = x1 - q * x2
		y1 = y1 - q * y2
		z1 = z1 - q * z2

		x1, y1, z1, x2, y2, z2 = x2, y2, z2, x1, y1, z1

	while x2 < 0:
		x2 += y
	
	return x2

d1 = euclidean(156, 251)
ret=''
for i in range(0,len(intxt) / 2):
	cur=0
	ta = intxt[i*2]

	if ta=="\n":
		break
	if ord(ta)>=ord('a'):
		cur+=ord(ta)-ord('a')+10
	else:
		cur+=ord(ta)-ord('0')
	cur*=16

	ta = intxt[i*2+1]

	if ta=="\n":
		break
	if ord(ta)>=ord('a'):
		cur+=ord(ta)-ord('a')+10
	else:
		cur+=ord(ta)-ord('0')
	ret+= chr((d1 * cur + 67 - 16) %251)
print ret

Twin Primes

RSA 暗号。双子素数二組 (p, p+2), (q, q+2) を元に、 N1 = pq, N2 = (p+2)(q+2) が公開鍵として採用されている（N1, N2, eが公開）。

N2 と N1 がわかっていて、どちらも展開すると pq を含むので、

N_2 - N_1 \\ = (p+2)(q+2) - pq \\ = 2(p+q)+4

つまり、
p+q = \cfrac{(N_2-N_1) - 4}{2} \\ pq = N_1

和と積がわかったので、二次方程式で解くことができる。二次方程式の公式を久しぶりに検索して計算。

n1 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
e1 = 65537

n2 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859
e2 = 65537

cipher = 7991219189591014572196623817385737879027208108469800802629706564258508626010674513875496029177290575819650366802730803283761137036255380767766538866086463895539973594615882321974738140931689333873106124459849322556754579010062541988138211176574621668101228531769828358289973150393343109948611583609219420213530834364837438730411379305046156670015024547263019932288989808228091601206948741304222197779808592738075111024678982273856922586615415238555211148847427589678238745186253649783665607928382002868111278077054871294837923189536714235044041993541158402943372188779797996711792610439969105993917373651847337638929
# cf: http://arc360.info/algo/privatekey.html
def euclidean(x, y):
	x1 = 1
	y1 = 0
	z1 = x
	x2 = 0
	y2 = 1
	z2 = y

	while z2 != 1:
		q = (z1 - (z1 % z2)) / z2
		x1 = x1 - q * x2
		y1 = y1 - q * y2
		z1 = z1 - q * z2

		x1, y1, z1, x2, y2, z2 = x2, y2, z2, x1, y1, z1

	while x2 < 0:
		x2 += y
	
	return x2

def find_root(x):
	lo = 1
	hi = x

	while lo < hi:
		mi = (lo + hi) / 2

		if mi * mi > x:
			hi = mi - 1
			continue

		if mi * mi < x:
			lo = mi + 1
			continue
		
		if mi * mi == x:
			lo = mi
			hi = mi
	
	if lo * lo == x:
		return lo
	else:
		return -1

def decrypt_rsa(N, e, d, cipher):
	c_powers = [cipher]
	cur_power = 1

	while cur_power <= d:
		tmp = c_powers[len(c_powers) - 1]
		c_powers.append((tmp * tmp) % N)
		cur_power *= 2

	cur_power = 1
	cur_pos = 0
	ans = 1

	while cur_power <= d:
		if d & cur_power > 0:
			ans *= 	c_powers[cur_pos]
			ans %= N
		cur_pos += 1
		cur_power *= 2

	return ans

wa = ((n2-n1)-4)/2

p = (wa + find_root(wa * wa - 4 * n1)) / 2
q = (wa - find_root(wa * wa - 4 * n1)) / 2

d1 = euclidean(e1, (p-1)*(q-1))
d2 = euclidean(e2, (p+1)*(q+1))

ans = decrypt_rsa(n1, e1, d1, decrypt_rsa(n2, e2, d2, cipher))
ans_array = []
while ans:
	ans_array.append(chr(ans % 256))
	ans /= 256

ans_array.reverse()

print ''.join(ans_array)

glance

横幅がとても狭く高速で何かが流れるアニメーション GIF に対し「電車のドアの隙間から見えた」旨。アニメーションを展開して画像を結合。

$ convert +adjoin glance.gif part.gif
$ convert +append `for ((i=0; i<=200; ++i)); do echo part-$i.gif; done` output.png

Global Pages

何かページの記事のようなものが表示されている。

http://globalpage.chal.ctf.westerns.tokyo/?page=tokyo

に接続すると、

Warning: include(tokyo/en-US.php): failed to open stream: No such file or directory in /var/www/globalpage/index.php on line 41

のようなエラーが出ている。tokyoの部分を変えると ja.php に関しても同様のエラーが出るようになる。ただし、 page= の部分に色々流し込んだ時、 %00 を流し込むとそこでファイル名が切れるが、ピリオドとスラッシュだけは入らず消される。

とりあえずこの tokyo/ja.php などは http://globalpage.chal.ctf.westerns.tokyo/tokyo/ に相当するディレクトリにあると思われるのでここに繋ぐと、各言語用の PHP ファイルがおいてある。

ふと Accept-Language を変えるとほかの言語が表示されたりそちらもファイル名に流し込まれたりすることに気付く。ピリオドやスラッシュも流し込めたが僕はここで PHP の include の仕様を調べるも失敗。

ここまでチャットに書くと、 yuta1024 が、CTF for Beginners 2015 のえるざっぷ氏の writeupの Web500 の手法が動くことに気付き、 index.php、次いでそこから include されていた flag.php の中身を BASE64 で吸い出してフラグを見つけていた。

PHP には include で指定した URL からデータを読みだしてそのまま PHP コードとして解釈して実行する豪快な機能があるが、さすがにデフォルトで無効化されている。allow_url_includeを1にすると有効だが今回は無効だった。その場合でも、 「php://filter/convert.base64-encode/resource=index.php」は URL とみなされないらしく、 filter 経由でデータを解釈できるらしい。

Poems

ポエム投稿サイト。ポエムを投稿するとランダムなIDが与えられ、それをファイル名として保存するようになっている。最初のポエムを読みだせという問題。

ソースコードが配布されている。また、 Ubuntu 16.04 + Apache であることが示されている。

ソースコードを見ると、 Slim フレームワークを使っており、 ../poem/list.txt に ID 一覧が保存されていること、 /admin に行けばその一覧の中身を表示してくれることがわかる。ところが、ソースコード側で認証がかかっていないにもかかわらず、 /admin に行くと Basic 認証を求められる。

とりあえずディレクトリトラバーサルで任意のファイルを読み出せるので、 http://poems.chal.ctf.westerns.tokyo/poems?p=../../../../../../../../etc/apache2/sites-enabled/000-default.conf に接続すると、 Apache の設定で

<Location /admin>

で Basic 認証がかかっていることがわかる。パスワードファイルは見ることができたが暗号化されていて、 1000回 md5 した形式らしかったのと数分 John The Ripper を走らせても無理だった、とか言っていたら、パスワードクラックは不要というヒントが出された。

そこでふと、普通の PHP フレームワークなら特に設定しなければ public をそのまま DocumentRoot にしても動作するように /index.php/本来のpath みたいなのを URI に投げ込んでも繋いでくれることを思い出し、 http://poems.chal.ctf.westerns.tokyo/index.php/admin に接続すると認証なく ID 一覧を見ることができた。先頭の ID をポエムの URL に繋ぐとフラグが出てきた。

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。