SECCON Beginners CTF 2021 Writeup

Sun May 23 2021

    5/22-5/23 で開催していた SECCON Beginners CTF 2021 に参加しました。 去年の beginners あたりから CTF にはまったため、自分の中では beginners は思い出深い大会です。結果は 18th/943 (得点のあるチームのみカウント) でした。去年は 38th (by 自分の writeup) だったので1年いろいろやった成果が出たと思ってよさそう。 解いた問題のうち、 medium 難易度以上のものについて writeup を書きます。

    welcome

    welcome

    welcome 問題、どんだけスタンバイしてても first blood を取れたことがない気がする、一体どんな技術が必要なのでしょう…

    ctf4b{Welcome_to_SECCON_Beginners_CTF_2021}

    crypto

    Imaginary

    ECB モードの AES で暗号文を捏造する問題。今回の crypto 問題セットの中では一番時間がかかりました…

    例えば x0+iy0,x1+iy1x_0 + iy_0, x_1 + iy_1 という2変数を与えると、 {"x0 + y0i": [x0, y0], "x1 + y1i": [x1, y1]} というような dict の json を AES で暗号化したものが手に入ります。フラグを手に入れるには、この dict に "1337i" という key をもたせる必要があります。

    app.py
    (snip)
        def _export(self):
            cipher = AES.new(key, AES.MODE_ECB)
            dump = pad(json.dumps(self.numbers).encode(), AES.block_size)
            print(dump)
            self.request.sendall(dump + b'\n')
            enc = cipher.encrypt(dump)
            self.request.sendall(b'Exported:\n')
            self.request.sendall(enc.hex().encode() + b'\n')
    
        def _secret(self):
            if '1337i' in self.numbers:
                self.request.sendall(b'Congratulations!\n')
                self.request.sendall(f'The flag is {flag}\n'.encode())
    (snip)

    ECB モードは各ブロック単体で (他のブロックに非依存で) 暗号/復号を行うため、ちょうどブロック長の整数倍になっている {"...": [..., ...], " という形のものと、 1337i": [..., ...]} という形のものを暗号化したものを concat して復号すれば、 {"...": [..., ...], "1337i": [..., ....]} となるはずです。

    from pwn import *
    
    _r = remote("imaginary.quals.beginners.seccon.jp", 1337)
    
    # 空 dict に戻せるように export
    _r.sendlineafter("> ", "4")
    _r.recvline()
    _r.recvline()
    default_dict = _r.recvline().strip()
    
    # 1337i... の export
    _r.sendlineafter("> ", "1")
    _r.sendlineafter("> ", "123")
    _r.sendlineafter("> ", "123")
    _r.sendlineafter("> ", "1")
    _r.sendlineafter("> ", "0")
    _r.sendlineafter("> ", "1337")
    _r.sendlineafter("> ", "4")
    _r.recvline()
    _r.recvline()
    enc_1337 = _r.recvline().strip()
    
    _r.sendlineafter("> ", "3")
    _r.sendlineafter("> ", default_dict)
    
    # ..." の export
    _r.sendlineafter("> ", "1")
    _r.sendlineafter("> ", "12345")
    _r.sendlineafter("> ", "123")
    _r.sendlineafter("> ", "1")
    _r.sendlineafter("> ", "0")
    _r.sendlineafter("> ", "0")
    _r.sendlineafter("> ", "4")
    _r.recvline()
    _r.recvline()
    first_block = _r.recvline().strip()
    
    _r.sendlineafter("> ", "3")
    _r.sendlineafter("> ", first_block[:64] + enc_1337[64:])
    
    _r.sendlineafter("> ", "5")
    _r.interactive()

    ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

    Field_trip

    knapsack 暗号の問題です。

    pub_keyii 番目を pip_i, flag を bit 表記したときの ii 番目の値を fi(fi{0,1})f_i (f_i \in \{ 0, 1 \}), ciphercc と表します。 少々天下りではありますが、以下のような行列計算を考えます。

    (f0f1fn2fn11)(2000p00200p10020pn20002pn11111c)\begin{pmatrix} f_0 & f_1 & \cdots & f_{n-2} & f_{n-1} & 1 \end{pmatrix} \begin{pmatrix} 2 & 0 & \cdots & 0 & 0 & p_0 \\ 0 & 2 & \cdots & 0 & 0 & p_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 2 & 0 & p_{n-2} \\ 0 & 0 & \cdots & 0 & 2 & p_{n-1} \\ -1 & -1 & \cdots & -1 & -1 & -c \end{pmatrix}

    この行列計算の答えは (±1,±1,,±1,±1,0)(\pm 1, \pm 1, \cdots, \pm 1, \pm 1, 0) となります。 右の行列の値が全て既知の値であることに注意すると、 LLL によりこのような格子基底ベクトルが求められる可能性が有ります。 (LLL の概念や、解が求まるかのチェック方法については過去に自分のブログで雑にまとめましたので そちら をご覧いただければ)

    これを sagemath で実装します。

    M = matrix(ZZ, len(pub_key) + 1, len(pub_key) + 1)
    for i in range(len(pub_key)):
        M[i, len(pub_key)] = pub_key[i]
    M[len(pub_key), len(pub_key)] = -cipher
    for i in range(len(pub_key)):
        M[i, i] = 2
        M[len(pub_key), i] = -1
    
    
    V = M.LLL()
    
    # 求まった格子基底ベクトルについて、 (+-1, ..., +-1, 0) となるものを探す 
    ans_vec = None
    for v in V:
        valid = True
        for vi in v[:-1]:
            if abs(vi) != 1:
                valid = False
        if v[-1] != 0:
            valid = False
        if valid:
            ans_vec = v
            break
    
    ans = 0
    for c in ans_vec[:-1]:
        ans *= 2
        ans += (c + 1) // 2
    print(bytes.fromhex(hex(ans)[2:]))

    ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

    p-8RSA

    RSA の問題。

    problem.py
    from Crypto.Util.number import *
    from random import getrandbits
    from os import urandom
    from flag import flag
    
    
    def gen_primes(bits, e):
        q = getStrongPrime(bits)
        p = q
        while True:
            p = p-8 # p-8
            phi = (p - 1) * (q - 1)
            if isPrime(p) and GCD(phi, e) != 1:
                break
        return p, q
    
    flag = flag.encode("utf-8") + urandom(64)
    flag = bytes_to_long(flag)
    
    e = 17
    p, q = gen_primes(512, e)
    n = p * q
    
    print("n =", n)
    print("e =", e)
    print("c =", pow(flag, e, n))

    gen_primes に注目すると、p,qp, q は近い値になっていることが期待されます。なので nn の平方根から徐々に値を小さくして nn を割り切れる数を探索することで p,qp, q が求まります。

    sqrt_n = int(round(sqrt(n)))
    for i in range(100000):
        if n % (sqrt_n - i) == 0:
            p = sqrt_n - i
            q = n // p
            break
    assert p * q == n

    (sage でやったので round 等が使われています)

    ここからいつものように ϕ=(p1)(q1)\phi = (p-1)(q-1) を計算して d=e1modϕd=e^{-1} \mod \phi を求めようとすると、エラーが出ます。今回のパラメータだと gcd(e,ϕ)1\gcd(e, \phi) \ne 1 なので逆元が存在しません。なので解も (フラグの形式を考えなければ) 一意には定まりません。

    ではどうすればいいかというと、 mecmodnm^e \equiv c \mod n となる mm を全列挙し、フラグの形式になっているものを解とします。方法としては 自分が以前ブログにまとめた方法 でいけます。

    lambda_ = lcm(p - 1, q - 1)
    L = int(pow(2, lambda_ // e, n))
    d = int(pow(e, -1, lambda_ // e))
    for i in range(e):
        tmp = pow(c, d, n) * pow(L, i, n)
        try:
            tmp_flag = bytes.fromhex(hex(tmp)[2:])
            if b"ctf4b" in tmp_flag:
                print(tmp_flag)
                break
        except:
            continue

    ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}

    reversing

    be_angry

    バイナリを解析すると、 0x2532Correct!! という文字列を扱っていることがわかります。問題名/文が示唆するように angr で解きます。

    import angr
    
    offset = 0x400000
    p = angr.Project("./chall")
    state = p.factory.entry_state()
    sim = p.factory.simulation_manager(state)
    sim.explore(find=offset+0x2532)
    print(sim.found[0].posix.dumps(0))

    ctf4b{3nc0d3_4r1thm3t1c}

    firmware

    与えられた firmware.bin の中身を見ると ELF の文字列があり、その周辺がプログラムになっているのでは?と思いその周辺部を抜き出して ELF ファイルを作り出しました。

    with open("./firmware.bin", "rb") as f:
        buf = f.read()
    elf_idx = buf.index(b"ELF")
    with open("./tmp", "wb") as f:
        f.write(buf[elf_idx - 1: elf_idx - 1 + 40000])

    これを ghidra で解析すると、入力値と 0x53 の xor を取ったものがある値と一致しているかをチェックしている部分を見つけました。 memory のアドレスとかをたどるのはだるかったので、 firmware.bin の全ての文字に対して 0x53 で xor をとり、フラグっぽくなっている部分を探しました。 cSSStSSSfSSS4SSSbSSS{SSS... となっている部分がありました。

    ctf4b{i0t_dev1ce_firmw4re_ana1ysi3_rev3a1s_a_l0t_of_5ecre7s}

    pwnable

    クソ雑魚なので medium 以上は1問も解けませんでした…精進します。 uma_catch あんなにも脆弱性あるのに解けなかった…

    web

    json

    問題の URL にアクセスすると、 このページはローカルネットワーク(192.168.111.0/24)内の端末からのみ閲覧できます。 と言われます。コードの該当部はここ。

    bff/main.go
    (snip)
    // check if the accessed user is in the local network (192.168.111.0/24)
    func checkLocal() gin.HandlerFunc {
    	return func(c *gin.Context) {
    		clientIP := c.ClientIP()
    		ip := net.ParseIP(clientIP).To4()
    		if ip[0] != byte(192) || ip[1] != byte(168) || ip[2] != byte(111) {
    			c.HTML(200, "error.tmpl", gin.H{
    				"ip": clientIP,
    			})
    			c.Abort()
    			return
    		}
    	}
    }
    (snip)

    これはヘッダーに X-Forwarded-For: 192.168.111.0 を入れることで突破できました。

    フラグは api/main.go の以下の部分で手に入りそうです。

    api/main.go
    (snip)
    		if id == 2 {
    			// Flag!!!
    			flag := os.Getenv("FLAG")
    			c.String(200, flag)
    			return
    		}
    (snip)

    しかし {"id": 2} を api に POST すると、 bff/main.go の以下の部分で弾かれてしまいます。

    bff/main.go
    (snip)
    		if info.ID == 2 {
    			c.JSON(400, gin.H{"error": "It is forbidden to retrieve Flag from this BFF server."})
    			return
    		}
    (snip)

    詳細は追っていないのですが、バイパスが雑なのかと思い、 {"id": 2, "id": 1} を POST したら無事フラグが手に入りました。

    ctf4b{j50n_is_v4ry_u5efu1_bu7_s0metim3s_it_bi7es_b4ck}

    cant_use_db

    ソースコードを読んでいると、 /buy_noodles/buy_soup に謎の time.sleep が挟まっていました。

    app.py
    (snip)
    @app.route("/buy_noodles", methods=["POST"])
    def buy_noodles():
        user_id = session.get("user")
        if not user_id:
            return redirect("/")
        balance, noodles, soup = get_userdata(user_id)
        if balance >= 10000:
            noodles += 1
            open(f"./users/{user_id}/noodles.txt", "w").write(str(noodles))
            time.sleep(random.uniform(-0.2, 0.2) + 1.0)
            balance -= 10000
            open(f"./users/{user_id}/balance.txt", "w").write(str(balance))
            return "💸$10000"
        return "ERROR: INSUFFICIENT FUNDS"
    
    
    @app.route("/buy_soup", methods=["POST"])
    def buy_soup():
        user_id = session.get("user")
        if not user_id:
            return redirect("/")
        balance, noodles, soup = get_userdata(user_id)
        if balance >= 20000:
            soup += 1
            open(f"./users/{user_id}/soup.txt", "w").write(str(soup))
            time.sleep(random.uniform(-0.2, 0.2) + 1.0)
            balance -= 20000
            open(f"./users/{user_id}/balance.txt", "w").write(str(balance))
            return "💸💸$20000"
        return "ERROR: INSUFFICIENT FUNDS"
    (snip)

    問題名の示す通り DB を使っていないため、 balance 計算の処理が非同期になってしまいます。 なのでブラウザ上で Soup, Noodles, Noodles と高速に押すことでフラグ入手の条件を満たすことができました。

    ctf4b{r4m3n_15_4n_3553n714l_d15h_f0r_h4ck1n6}

    misc

    depixelization

    フラグの文字を画像化し、いろいろな不可逆な処理を加えたものが与えられました。 各種処理は不可逆なのですが、各文字の処理された結果は決定的なので、各文字の処理結果と与えられた画像を文字ごとに区切ったものとでL1ノルムが近い文字を探すプログラムを書きました。

    import cv2
    import numpy as np
    import matplotlib.pyplot as plt
    
    images = cv2.imread("output.png")
    
    default_img = np.full((100, 85, 3), (255, 255, 255), dtype=np.uint8)
    candidates = list(map(chr, range(32, 128)))
    image_candidates = []
    for c in candidates:
        img = default_img.copy()
        cv2.putText(img, c, (0, 80), cv2.FONT_HERSHEY_PLAIN, 8, (0, 0, 0), 5, cv2.LINE_AA)
    
        cv2.putText(img, "P", (0, 90), cv2.FONT_HERSHEY_PLAIN, 7, (0, 0, 0), 5, cv2.LINE_AA)
        cv2.putText(img, "I", (0, 90), cv2.FONT_HERSHEY_PLAIN, 8, (0, 0, 0), 5, cv2.LINE_AA)
        cv2.putText(img, "X", (0, 90), cv2.FONT_HERSHEY_PLAIN, 9, (0, 0, 0), 5, cv2.LINE_AA)
        simg = cv2.resize(img, None, fx=0.1, fy=0.1, interpolation=cv2.INTER_NEAREST)  # WTF :-o
        img = cv2.resize(simg, img.shape[:2][::-1], interpolation=cv2.INTER_NEAREST)
        image_candidates.append(img)
    
    flag = ""
    for i in range(0, images.shape[1], 85):
        img = images[:, i: i+85, :]
        min_dist = 10**10
        min_dist_idx = None
        for j, c in enumerate(image_candidates):
            tmp = np.mean(np.abs(img - c))
            if tmp < min_dist:
                min_dist = tmp
                min_dist_idx = j
        assert min_dist_idx is not None
        flag += candidates[min_dist_idx]
    print(flag)

    ctf4b{1f_y0u_p1x_y0u_c4n_d3p1x}