DiceCTF Qual 2025 - winxy-pistol

,

Before all

恩，這次居然不是寫一整場 CTF 的 Write Up，主要是當時的我 (&最近) 基本上都在忙各種雜事 …
難得有 rating 80 以上的 CTF 比賽打欸
這題是 @QnQSec 在打的時候我臨時跳下去看得，剛好覺得蠻有趣就寫一下 Write Up

Writeup

Challenge Source

一個 RPG (?) 遊戲，本質上就是進行了一次 Oblivious Transfer(wiki)，簡單來說就是用 RSA 的方法，發信端發送兩筆隨機值，由接收端決定要接收那一筆的原始資料後提供一個數字，並由發送端以剛剛的(隨機值 + 接收端提供的數字) 做 Mask。
只有接收端決定要接收的資訊是他能 unmask 並取得值的。

但這次的跟一般不太一樣，在本來的加法 $(m_0+k_0)$ 的段落改用了 xor 運算。

而題目的任務是每次(連續 64 次)都從兩個訊息中還原出真正正確的那個(you continue walking……)，而另一種死亡提示則有固定的格式與回應 

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

Solution

注意到這邊的 N 是定值，為方便起見我每次提供的數字都是 $x_0$，意思就是我選擇的 k = 0

那麼對於選錯的情況其實也不是毫無收穫，首先我們知道我們真正想獲得的訊息是被 $(x_0-x_1)^d$ MASK 了，其次因為公鑰 N 是固定值，且死亡提示有固定格式。所以能透過開啟另一個 remote session，客製化送出數字嘗試構造對面的 mask = $(x_0-x_1)^d$，最後賭 1/2 的機率(能連很多次所以先 assume 100% 會成功)他會是死亡提示，嘗試爆破，相減並按照訊息格式過濾就能取得當前本來沒拿成功的訊息

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
from pwn import *
import hashlib
from tqdm import trange

n=130384696953971899628690721848889033882994533720464185052766383301994630563415990704603201379792729683585495846339364121536801007813544691669500891869527828303072450596801900956532044286332481629829421469305788118694261311048899345689331461633650477273068836367526585199709062458604136176004498784107766385593

z=0
z_key=hashlib.shake_256(z.to_bytes(1024//8, 'big')).digest(64)

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

death_causes = [f'you die of {cause}.'.encode() for cause in DEATH_CAUSES]

def trial(c):
    rr=remote('dicec.tf', 31002)
    print(rr.recvuntil(b'the tunnel forks ahead. do you take the left or right path?\n'))
    rr.recvlines(2)
    xx0=int(rr.recvline().split(b': ')[1].decode())
    xx1=int(rr.recvline().split(b': ')[1].decode())
    #r.recv()
    rr.sendline(str((xx0+c)%n).encode())
    cc0=rr.recvline()
    print(len(cc0), cc0)
    cc0=bytes.fromhex(cc0.split(b'c0: ')[1].decode())
    rr.close()
    return [xor(cc0, cause.ljust(64, b'\x00')) for cause in death_causes]

r=remote('dicec.tf', 31002)
        
for i in trange(64):
    print(r.recvuntil(b'the tunnel forks ahead. do you take the left or right path?\n'))
    print(r.recvlines(2))
    x0=int(r.recvline().split(b': ')[1].decode())
    x1=int(r.recvline().split(b': ')[1].decode())
    #r.recv()
    r.sendline(str(x0).encode())
    c0=bytes.fromhex(r.recvline().split(b'c0: ')[1].decode())
    c1=bytes.fromhex(r.recvline().split(b'c1: ')[1].decode())
    print(len(c0), len(c1))
    if b'you continue walking. turn to page ' in xor(z_key, c0):
        #print(xor(z_key, c0).split(b'you continue walking. turn to page ')[1].replace(b'\x00', b''))
        r.sendline(xor(z_key, c0).split(b'you continue walking. turn to page ')[1].replace(b'\x00', b'')[:-1])
    else:
        found=False
        while found==False:
            print(f"Trying: {(x0-x1)%n}")
            for t_key in trial((x0-x1)%n):
                print(len(t_key), xor(t_key, c1))
                if b'you continue walking. turn to page ' in xor(t_key, c1):
                    print('meow')
                    #print(xor(t_key, c1).split(b'you continue walking. turn to page ')[1].replace(b'\x00', b''))
                    r.sendline(xor(t_key, c1).split(b'you continue walking. turn to page ')[1].replace(b'\x00', b'')[:-1])
                    found=True

r.interactive()