osu!gaming CTF 2025 Writeup

, ,

Before all

Rank 11 / Team: ICEDTEA
這周末有點久違的跟 ICEDTEA 一起打了 Project Sekai 辦的 osu!gamming CTF，整體題目其實不算難，Crypto 差一題 AK，偏可惜，如果我不要忙段考前拖更得那坨作業一定有機會打出來 TwT
還是來 writeup 一下，題目有些偏技巧，有點有趣

但感覺整的隊變強了不錯w
我打完 Crypto 沒空了本來要救 web 發現都打完了，然後可能是隊上 osu 玩家太多導致我們 osu 題打很快？！ 但我都看不懂在幹嘛w 暫時不是 osu 廚

其他就是，Crypto 狗在 LLM 的成長下是不是要失業了 T_T

Writeup

這次我只打了 Crypto

pls-nominate

RSA，一個長訊息被 e=5 加密了五次，所以不能直接廣播攻擊。
script.py 

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

FLAG = open("flag.txt", "rb").read()
message = bytes_to_long(
    b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 :steamhappy: i can bribe you with a flag if you do: " + FLAG
)

ns = [getPrime(727) * getPrime(727) for _ in range(5)]
e = 5
print(len(FLAG))
print(ns)
print([pow(message, e, n) for n in ns])

所以要透過 known high bits of message b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 :steamhappy: i can bribe you with a flag if you do: "，構造一個多項式然後一樣做 CRT，解 $(HIGH_BITS + x)^5 - CRT([Cs], [Ns]) \space (mod \space \prod N_i)$
然後因為 x 之於 $N^5$ 左右的量級一定相對小，直接 Coppersmith Method 找 small_roots 做完

exp.py
對不起我想完後直接把腳本詠唱出來了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from sage.all import *
from Crypto.Util.number import long_to_bytes

# 讀取 output.txt
with open("output.txt", "r") as f:
    lines = f.readlines()

# 解析資料
flag_length = int(lines[0].strip())
ns = eval(lines[1].strip())
cs = eval(lines[2].strip())

print(f"[+] Flag length: {flag_length}")
print(f"[+] Number of moduli: {len(ns)}")

# 已知的明文前綴
known_prefix = b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 :steamhappy: i can bribe you with a flag if you do: "

# 將已知前綴轉換為數字
from Crypto.Util.number import bytes_to_long
BIG_PART = bytes_to_long(known_prefix)*2^(8 * flag_length)

print(f"[+] Known prefix length: {len(known_prefix)} bytes")
print(f"[+] BIG_PART: {BIG_PART}")

# 使用中國剩餘定理合併所有密文
# 我們要找到 C，使得 C ≡ cs[i] (mod ns[i]) for all i
print("[+] Applying Chinese Remainder Theorem...")
N = 1
for n in ns:
    N *= n

C = crt(cs, ns)
print(f"[+] CRT result computed (mod N)")

# 設置多項式環
# 我們的目標是求解: (BIG_PART + x)^5 ≡ C (mod N)
# 即: (BIG_PART + x)^5 - C ≡ 0 (mod N)
print("[+] Setting up polynomial...")
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)

# 構造多項式 f(x) = (BIG_PART + x)^5 - C
f = (BIG_PART + x)^5 - C

print(f"[+] Polynomial: f(x) = (BIG_PART + x)^5 - C")
print(f"[+] Searching for small roots (flag length: {flag_length})...")

# 使用 small_roots 方法
# X 是 x 的上界，這裡設為 flag 可能的最大值
X = 2^(8 * flag_length)  # flag 最多 flag_length 個字節

try:
    roots = f.small_roots(X=X, beta=0.5)
    
    if roots:
        print(f"[+] Found {len(roots)} root(s)!")
        
        for i, root in enumerate(roots):
            print(f"\n[+] Testing root {i+1}: {root}")
            try:
                flag_value = int(root)
                if flag_value > 0:
                    flag = long_to_bytes(flag_value)
                    print(f"[+] Decoded bytes: {flag}")
                    
                    # 驗證結果
                    full_message = bytes_to_long(known_prefix + flag)
                    if all(pow(full_message, 5, ns[j]) == cs[j] for j in range(len(ns))):
                        print(f"\n[SUCCESS] Flag found: {flag.decode('utf-8', errors='ignore')}")
                        print(f"[SUCCESS] Full flag: {flag}")
                        break
                    else:
                        print("[!] Verification failed for this root")
            except Exception as e:
                print(f"[!] Error decoding root: {e}")
    else:
        print("[!] No roots found. Try adjusting parameters.")
        
except Exception as e:
    print(f"[!] Error during root finding: {e}")
    print("[!] You may need to adjust beta or X parameters")

linear-feedback

自己實作了一種 LFSR，然後生成一個 29 bits seed stream 和一個 21 bits seed stream 後做 xnor，要反推出 seed 們 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from secrets import randbits
from math import floor
from hashlib import sha256

class LFSR:
    def __init__(self, key, taps, format):
        self.key = key
        self.taps = taps
        self.state = list(map(int, list(format.format(key))))
    
    def _clock(self):
        ob = self.state[0]
        self.state = self.state[1:] + [sum([self.state[t] for t in self.taps]) % 2]
        return ob

def xnor_gate(a, b):
    if a == 0 and b == 0:
        return 1
    elif a == 0 and b == 1:
        return 0
    elif a == 1 and b == 0:
        return 0
    else:
        return 1

key1 = randbits(21)
key2 = randbits(29)
L1 = LFSR(key1, [2, 4, 5, 1, 7, 9, 8], "{:021b}")
L2 = LFSR(key2, [5, 3, 5, 5, 9, 9, 7], "{:029b}")

bits = [xnor_gate(L1._clock(), L2._clock()) for _ in range(floor(72.7))]
print(bits)

FLAG = open("flag.txt", "rb").read()
keystream = sha256((str(key1) + str(key2)).encode()).digest() * 2
print(bytes([b1 ^ b2 for b1, b2 in zip(FLAG, keystream)]).hex())

因為 xnor 運算是可反推的，最有效率的做法就是枚舉 21 bits 的所有可能，生成 stream 後反推 xnor 回去，然後計算 stream 前 29 bits 拿來生 LSFR 是不是一樣的結果，是的話它可能就是我們要的 KEY。

sol.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from hashlib import sha256
from tqdm import trange

result = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0]
enc = bytes.fromhex('9f7f799ec2fb64e743d8ed06ca6be98e24724c9ca48e21013c8baefe83b5a304af3f7ad6c4cc64fa4380e854e8')

class LFSR:
    def __init__(self, key, taps, format):
        self.key = key
        self.taps = taps
        self.state = list(map(int, list(format.format(key))))
    
    def _clock(self):
        ob = self.state[0]
        self.state = self.state[1:] + [sum([self.state[t] for t in self.taps]) % 2]
        return ob

def xnor_gate(a, b):
    if a == 0 and b == 0:
        return 1
    elif a == 0 and b == 1:
        return 0
    elif a == 1 and b == 0:
        return 0
    else:
        return 1

for i in trange(2**21):
    trial_L1 = LFSR(i, [2, 4, 5, 1, 7, 9, 8], "{:021b}")
    L2_stream = [xnor_gate(trial_L1._clock(), result[j]) for j in range(72)]
    trial_L2_key = int(''.join(map(str, L2_stream[:29])), 2)
    trial_L2 = LFSR(trial_L2_key, [5, 3, 5, 5, 9, 9, 7], "{:029b}")
    if [trial_L2._clock() for _ in range(72)] == L2_stream:
        print("[*] Possible Solution F0UND!")
        keystream = sha256((str(i) + str(trial_L2_key)).encode()).digest() * 2
        print(bytes([b1 ^ b2 for b1, b2 in zip(enc, keystream)]).hex())
        print(bytes([b1 ^ b2 for b1, b2 in zip(enc, keystream)]))

ssss

在質數 p25519 下做 Secret Sharing，多項式係數是 lcg 生出來的係數未知，oracle 最多可以做 14 次，就是回傳 f(x) 的值其中 x 介於 1 ~ p25519
要 leak 出常數項（lcg 的頭）來拿 flag
server.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/usr/local/bin/python3
from Crypto.Util.number import *
import random

p = 2**255 - 19
k = 15
SECRET = random.randrange(0, p)

def lcg(x, a, b, p):
    return (a * x + b) % p

a = random.randrange(0, p)
b = random.randrange(0, p)
poly = [SECRET]
while len(poly) != k: poly.append(lcg(poly[-1], a, b, p))

def evaluate_poly(f, x):
    return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p

print("welcome to ssss", flush=True)
for _ in range(k - 1):
    x = int(input())
    assert 0 < x < p, "no cheating!"
    print(evaluate_poly(poly, x), flush=True)

if int(input("secret? ")) == SECRET:
    FLAG = open("flag.txt").read()
    print(FLAG, flush=True)

整個問題其實有一個觀察是未知數從頭到尾只有 a, b, SECRET 三項，能把他們線性化就解完了。
一個代數小觀察：
$$
\begin{align}
\alpha = \frac{f(x)+f(-x)}{2} \newline
\beta = \frac{f(x)-f(-x)}{2}
\end{align}
$$

其中 $\alpha$ 是多項式 $f(x)$ 偶數項運算的加總結果， $\beta$ 是多項式 $f(x)$ 奇數項運算的加總結果，簡單推一下會發現

$\alpha = \beta \cdot x \cdot a + b \cdot (x^2 + x^4 + x^6 + \cdots + x^{14}) + SECRET$
於是做六次(三對) oracles 就可以 leak 出 a, b, SECRET 了，不過我的腳本保險起見領了四個數字確定三元等式有正確被解

exp.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from sage.all import *
from pwn import *

# nc ssss.challs.sekai.team 1337
r = remote('ssss.challs.sekai.team', 1337)
print(r.recvlines(2))
p = 2**255 - 19
ZZ = Zmod(p)

coeffs = []
results = []
oracles = []

def oracle(x):
    x = x%p
    r.sendline(str(x).encode())
    return int(r.recvline().decode())

for i in range(1, 5):
    pos_i = oracle(i)
    neg_i = oracle(-i)
    oracles.append([pos_i, neg_i])
    coeffs.append([(pos_i-neg_i)*i*pow(2, -1, p)%p, sum([i**(2*j) for j in range(1, 8)])%p, 1])
    results.append((pos_i+neg_i)*pow(2, -1, p)%p)

A_M = Matrix(ZZ, coeffs)
b_v = vector(ZZ, results)
# print(A_M, b_v, type(A_M), type(b_v))
print(A_M.solve_right(b_v))

k = 15
a, b, SECRET = A_M.solve_right(b_v)

poly = [SECRET]

def lcg(x, a, b, p):
    return (a * x + b) % p

while len(poly) != k: poly.append(lcg(poly[-1], a, b, p))

def evaluate_poly(f, x):
    return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p

print(oracles[0][0])
print(evaluate_poly(poly, 1))
for i in range(14-8):
    oracle(1337)

r.sendline(str(SECRET).encode())
r.interactive()
exit()

please-nominate

三條有幾個字元不一樣的訊息被三把不同的 RSA 公鑰加密。
要把 hidden 的 flag 解出來。
flag 很長 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *

FLAG = open("flag.txt").read()

BNS = ["Plus4j", "Mattay", "Dailycore"]
print(len(FLAG))

for BN in BNS:
    print("message for", BN)
    message = bytes_to_long(
        (f"hi there {BN}, " + FLAG).encode()
    )
    n = getPrime(727) * getPrime(727)
    e = 3
    print(n)
    print(pow(message, e, n))

一開始肯定想構造三條多項式像是(C_i 是密文輸出)
$P_i(X) = (HIGH_BITS\space_i + X)^3 - C_i \space (= 0)$
然後就會發現沒什麼用因為他們實際在不同的 Ring 下
所以先把他們抬到同一個 Ring 下，反正我是挑 $Zmod(N_1 \cdot N_2 \cdot N_3)$
接著因為中國剩餘定理，我知道像是 $N2\cdot N3 \cdot P_1(X)$ 多項式會對 $N_2, N_3$ 同餘 0，然後 對 $mod\space N_1$ 又是 $N2\cdot N3 \cdot P_1(X)$，所以顯然會有 $N2\cdot N3 \cdot P_1(X) \space (mod \space N_1 \cdot N_2 \cdot N_3)$ 的結果是可以直接被等價計算的。
（會這樣是因為我們不能直接知道 $P_1(X) \space (mod \space N_1 \cdot N_2 \cdot N_3)$ 的結果）

最後把三條多項式加在一起我們會知道他等於 0，最後因為 FLAG (X) 遠小於 $N_1 \cdot N_2 \cdot N_3$ 所以 Coppersmith Method 一樣可以把 small_roots 做出來 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from sage.all import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
from tqdm import trange

# 讀取 output.txt
with open("output.txt", "r") as f:
    lines = f.readlines()

# 解析資料
flag_len = int(lines[0].strip())
print(f"[+] Flag length: {flag_len}")

# BN 名稱列表
BNS = ["Plus4j", "Mattay", "Dailycore"]

# 存儲每個 BN 的 n 和 c
data = []
line_idx = 1
N = 1

for BN in BNS:
    # 跳過 "message for XXX" 這一行
    line_idx += 1
    n = int(lines[line_idx].strip())
    N *= n
    line_idx += 1
    c = int(lines[line_idx].strip())
    line_idx += 1
    data.append((BN, n, c))
    print(f"[+] {BN}: n={n}, c={c}")

print("\n[+] Starting to solve for each modulus...")

P.<x>=PolynomialRing(Zmod(N))
f = 0
under_N = 0
for i in range(3):
    prefix = f"hi there {data[i][0]}, "
    prefix_bytes = prefix.encode()
    r_i = bytes_to_long(prefix_bytes) * (2^(8 * flag_len))
    f += (N//data[i][1])*(x^3 + 3*x^2*r_i + 3*x*r_i^2)
    under_N += (N//data[i][1])*(data[i][2] - r_i^3)
 
f = f-under_N
f = f.monic()
for i in trange(1, 101):
    cur_sol = f.small_roots(X=2**(8*flag_len), beta=i/100)
    if len(cur_sol) > 0:
        print(long_to_bytes(int(cur_sol[0])))

*ssss+ (賽後 意念 upsolve)

殘念…
簡言之就是剛剛的 ssss lcg 的 mod 換成一個隨機的 prime(不公開)
之後有空補一下腳本，反正就是拿 $\pm 1 \pm 2 \cdots \pm 7$ 去做 oracle，然後我們能解出奇數項的所有係數，最後係數一樣是以 $a, b$ 為基組合出的某種線性關係，最後把相減的結果做 gcd 就可以 leak 出隨機的 prime 值，回推 a, b 然後把所有係數還原 leak 出 SECRET。