Dice CTF 2025
Giải Dice CTF 2025
Crypto
crypto/vorpal-sword
File 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
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
#!/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}')
Phân tích code: Đây là một bài về Oblivious transfer 1-2 RSA
Đầu tiên là hàm run_ot(key,msg0,msg1)
Key là bộ RSA 1024 bits. $\displaystyle x_{0} ,x_{1}$ được tạo ra bởi secrets.randbelow(key.n) tức là một số ngẫu nhiên nằm trong khoảng $\displaystyle [ 0,n)$. Server sẽ trả về cho ta $\displaystyle ( n,e,x_{0} ,x_{1})$.
Sau đó ta được nhập vào giá trị của một số nguyên $\displaystyle v$ thỏa mãn $\displaystyle 0\leqslant v\leqslant n$.
Tiếp đó server sẽ tính toán hai giá trị $\displaystyle k_{0} =( v-x_{0})^{d}\bmod n$ và $\displaystyle k_{1} =( v-x_{1})^{d}\bmod n$.
$\displaystyle m_{0} ,m_{1}$ là hai msg ban đầu của ta nhưng được chuyển sang số nguyên. Sau khi lấy giá trị nguyên $\displaystyle m_{0} ,m_{1}$ thì server sẽ tính toán và trả về $\displaystyle c_{0} =( m_{0} +k_{0}) \ \bmod \ n$ và $\displaystyle c_{1} =( m_{1} +k_{1}) \ \bmod n$.
Kế đến là cách để lấy lại flag: Game sẽ có tổng cộng 64 vòng và ta cần phải pass qua hết 64 vòng. Ở mỗi vòng server sẽ gen một RSA key 1024 bits, page là một số được sinh ngẫu nhiên và có độ lớn 32 bit. 2 msgs của ta được tạo ra như sau:
1
2
live = f'you continue walking. turn to page {page}.'
die = f'you die of {secrets.choice(DEATH_CAUSES)}.'
Dòng sau:
1
msgs = (live, die) if secrets.randbits(1) else (die, live)
Đảo ngẫu nhiên thứ tự của 2 msgs này.
DEATH_CAUSES chọn ngẫu nhiên từ list:
1
2
3
4
5
6
7
8
9
10
11
12
DEATH_CAUSES = [
'a fever',
'dysentery',
'measles',
'cholera',
'typhoid',
'exhaustion',
'a snakebite',
'a broken leg',
'a broken arm',
'drowning',
]
Sau khi setup xong thì tới phần kiểm tra: Ta được nhập vào một số $v$, server sẽ trả về nốt $c_{0}$ và $c_{1}$ và ta sẽ dùng dữ kiện này để đoán giá trị của pages.
Hmmmm vậy ý tưởng của bài này là sao? Lúc đầu mình thử nhập $v=x_{0}$ thì từ công thức tính $\displaystyle c_{0} =( m_{0} +k_{0})\bmod n$ và $\displaystyle k_{i} =( v-x_{i})^{d}\bmod n$ thì mình sẽ có một trong hai $\displaystyle c_{i} =m_{i}$. Sau đó mình chuyển long_to_bytes là ra lại pages. Nhưng xác suất để bốc trúng là $\displaystyle \frac{1}{2}$ và để Pass cả 64 vòng thì xác suất là $\displaystyle \frac{1}{2^{64}}$ :)).
Ý tưởng tiếp theo, nghe có vẻ khả thi hơn đó là làm cách nào đó phân biệt được giữa $c_{0}$ và $c_{1}$ cái nào thực sự chứa pages. Cách phân biệt duy nhất theo mình nghĩ đó là bruteforce thôi :v vì mình biết trước được msgs của die nó như thế nào và cũng tự tạo ra được một danh sách tất cả các msgs có thể có.
Vì vậy mình sẽ cố gắng tìm một số $v$ mà sau khi tính $k_{0}$ và $k_{1}$ thì ta có một quan hệ tuyến tính giữa chúng, lý do mà mình tạo như vậy là để có thể tạo ra một quan hệ tuyến tính giữa $m_{0}$ và $m_{1}$ bằng cách xét một biểu thức tuyến tính giữa $c_{0}$ và $c_{1}$.
Đại loại thì nó sẽ như này
Ta cần $\displaystyle k_{0} =-s\times k_{1}$, hai số này được tính bởi:
\[k_{0} =( v-x_{0})^{d}(\bmod n) \Longrightarrow k_{0}^{e} =v-x_{0}(\bmod n)\\ k_{1} =( v-x_{1})^{d}(\bmod n) \Longrightarrow k_{1}^{e} =v-x_{1}(\bmod n)\]Mà ta có do $\displaystyle e$ lẻ cho nên
\[k_{0}^{e} =-s^{e} \times k_{1}^{e}\\ \Longrightarrow v-x_{0} =k_{0}^{e} =-s^{e} \times ( v-x_{1})\\ =-s^{e} \times v+s^{e} \times x_{1}\\ \Longrightarrow v+v\times s^{e} =s^{e} \times x_{1} +x_{0}\\ \Longrightarrow v\left( s^{e} +1\right) =s^{e} \times x_{1} +x_{0}\\ \Longrightarrow v=\frac{s^{e} \times x_{1} +x_{0}}{s^{e} +1}\]Tất cả được tính trên mod n. Ta chọn $\displaystyle s=2$ và thay vào tính v = (x0 + pow(scale, e, n) * x1) * pow(1 + pow(scale, e, n), -1, n) % n
Thực ra thì mình cũng có một thắc mắc là nếu như $s^{e}+1$ không có nghịch đảo modulo $n$ thì sao. Hmmm, nhưng mà code vẫn chạy bth nên mình cx k biết vì sao.
Code giải:
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
from pwn import *
from Crypto.Util.number import *
import re
DEATH_CAUSES = [
'a fever',
'dysentery',
'measles',
'cholera',
'typhoid',
'exhaustion',
'a snakebite',
'a broken leg',
'a broken arm',
'drowning',
]
death_msgs = [f'you die of {cause}.' for cause in DEATH_CAUSES]
death_vals = [int.from_bytes(msg.encode(), 'big') for msg in death_msgs]
HOST="dicec.tf"
PORT=31001
io=remote(HOST,PORT)
def extract_page(data):
match = re.search(rb"turn to page (\d+)\.", data)
if match:
page_str = match.group(1).decode()
if page_str.isdigit():
return int(page_str)
return None
def round(server):
server.recvuntil(b"n: ")
n=int(server.recvline().strip())
server.recvuntil(b"e: ")
e=int(server.recvline().strip())
server.recvuntil(b"x0: ")
x0=int(server.recvline().strip())
server.recvuntil(b"x1: ")
x1=int(server.recvline().strip())
scale=2
v = (x0 + pow(scale, e, n) * x1) * pow(1 + pow(scale, e, n), -1, n) % n
server.sendlineafter("v: ",str(v).encode())
server.recvuntil(b"c0: ")
c0=int(server.recvline().strip())
server.recvuntil(b"c1: ")
c1=int(server.recvline().strip())
comp=c0+scale*c1 # comp=m0+scale*m1
# truong hop m0 la die
page=None
for d in death_vals:
cand=((comp-d) * (pow(scale,-1,n))) % n
pos=long_to_bytes(cand)
print("debug case 1: ",pos)
page=extract_page(pos)
if page is not None:
break
# truong hop m1 la die
if page is None:
for d in death_vals:
cand=(comp-scale*d)%n
pos=long_to_bytes(cand)
print("debug case 2: ",pos)
page=extract_page(pos)
if page is not None:
break
if page is not None:
print(f"tìm được valid pages: {page}")
server.sendlineafter(b"turn to page: ",str(page).encode())
else:
print("bug cmnr")
for _ in range(64):
round(io)
io.interactive()