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 （鍵の一文字一文字）で
を繰り返していることになる。素数を法とした世界での線形な写像なので、どこかで一定の値で固定されるのでなければ（暗号文を見る限り違う）全体を
の一つの暗号とみなして問題ない（さらに言うとここまでの発想も、一部は実際には全体が一つの写像に落とし込めることに気付いてから、これが解けるのであればこうだろう、と考えた）
先頭が「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 を含むので、
つまり、
和と積がわかったので、二次方程式で解くことができる。二次方程式の公式を久しぶりに検索して計算。
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 に繋ぐとフラグが出てきた。