SECCON Beginners CTF 2021 Writeup

May 24, 2021

welcome welcome crypto Imaginary Field_trip p-8RSA reversing be_angry firmware pwnable web json cant_use_db misc depixelization

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

welcome

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

ctf4b{Welcome_to_SECCON_Beginners_CTF_2021}

crypto

Imaginary

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

例えば $x_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_key の $i$ 番目を $p_i$ , flag を bit 表記したときの $i$ 番目の値を $f_i (f_i \in \{ 0, 1 \})$ , cipher を $c$ と表します。少々天下りではありますが、以下のような行列計算を考えます。

\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}

この行列計算の答えは $(\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, q$ は近い値になっていることが期待されます。なので $n$ の平方根から徐々に値を小さくして $n$ を割り切れる数を探索することで $p, 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 等が使われています)

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

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

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

バイナリを解析すると、 0x2532 で Correct!! という文字列を扱っていることがわかります。問題名/文が示唆するように 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}

welcome welcome crypto Imaginary Field_trip p-8RSA reversing be_angry firmware pwnable web json cant_use_db misc depixelization