# DownUnderCTF 2025 - SH-RSA
> **Bài viết này có khuynh hướng cá nhân hóa, không mang tính nghiêm túc cao và chỉ mang tính tham khảo.**
Ấu yè, lần đầu tiên giải được một câu khó của một giải lớn, đây là câu khi giải xong làm mình sung sướng khôn xiết đến nỗi không giải được câu nào khác (thực ra là do giải hoài không ra...). Ok bắt đầu vào đề!
sh-rsa.py
``` python
#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import mpz, next_prime
from hashlib import shake_128
import secrets, signal, os
def H(N, m):
return shake_128(long_to_bytes(N) + m).digest(8)
def sign(N, d, m):
return pow(mpz(bytes_to_long(H(N, m))), d, N)
def verify(N, e, m, s):
return long_to_bytes(pow(s, e, N))[:8] == H(N, m)
def main():
p = int(next_prime(secrets.randbits(2048)))
q = int(next_prime(secrets.randbits(2048)))
N = p * q
e = 0x10001
d = pow(e, -1, (p - 1) * (q - 1))
print(f'{N = }')
print(f'{e = }')
for i in range(92):
m = long_to_bytes(i)
s = sign(N, d, m)
print(m.hex(), hex(s))
signal.alarm(46)
s = int(input('s: '), 16)
if verify(N, e, b'challenge', s):
print(os.getenv('FLAG', 'DUCTF{test_flag}'))
else:
print('Nope')
if __name__ == '__main__':
main()
```
Đề này liên quan tới chữ ký dạng RSA và cho mình `N`,`e` và 92 cặp `m` và `s`. Và một trong những điều nghĩ tới đầu tiên là sẽ liên quan tới lattice, vì đề cho một con số khá là cụ thể 92 (chắc đã được cân đo đong đếm), với lại đề cũng có mô tả là:
> "You should only need a short amount of time to break this short hash RSA signature scheme!"
nên cũng có thể liên quan tới bruteforce vì có giới hạn thời gian (đề cho 46 giây để trả lời. `signal.alarm(46)`).
Khi phân tích code thì mình không thấy có gì hay ho ngoài dữ liệu được cho thì còn có hàm hash `H` chỉ cho ra 8 byte, việc này rõ ràng là không an toàn vì mặc dù dùng shake128 (được cho là an toàn) nhưng hash ngắn -> dễ bị hash collision :collision:, nhưng có lẽ nên tìm cái khác để khai thác thay vì đoán mò (tỉ lệ đoán trúng là $1/2^{64}$ và chỉ đoán được một lần mỗi lần lập kết nối tới server). À còn có việc tại sao trong hàm `sign` lại phải dùng `mpz`? Vì cái gì lạ mình cũng hỏi ChatGPT nên nó trả lời lại là vì "tính nhanh hơn".
Khi đọc xong code thì nhiệm vụ của mình là tìm một chữ ký `s` cho chữ `challenge` và chỉ cần chữ ký đó sau khi đã mũ `e` (`pow(s, e, N)`) có 8 byte trên cùng (hay có 64 MSB) trùng với hash của chữ `challenge` là sẽ có cờ. Tuy vậy, ta không được cấp khóa `d` để ký nên đành dùng cách khác. Cái mà mình cần làm còn được gọi là "Signature forgery".
Câu hỏi là làm sao để liên hệ giữa dữ liệu được cho `m`, `H(N,m)`, `s` và chữ ký cho `challenge` cần được tạo? Ở đây mình sẽ kí hiệu `H(N,m)` là $H(N,m)$.
Ta biết rằng `s = pow(mpz(bytes_to_long(H(N, m))), d, N)` hay $$s \equiv H(N,m)^d~(mod~N)$$ Và vì $ed \equiv 1~~mod(\phi)$ nên $$H(N,m) \equiv s^e~~(mod~N)$$ Vậy có thể suy ra
$$s_1 * s_2 \equiv H(N,m_1)^d * H(N,m_2)^d~~(mod~N)$$ $$s_1*s_2 \equiv (H(N,m_1)*H(N,m_2))^d~~(mod~N)$$ Cùng với là $$H(N,m_1) * H(N,m_2) \equiv s_1^e*s_2^e~~(mod~N)$$ $$H(N,m_1) * H(N,m_2) \equiv (s_1*s_2)^e~~(mod~N)$$ Ở đây ta biết được các hash $H(N,m_i)$ và các $s_i$, cùng với lại $N$ và $e$ nên nếu đoán được một tổ hợp tích các $s_i^e$ hay $H(N,m_i)$ sao cho $$s_1^{e*a_1}*s_2^{e*a_2}*...*s_{92}^{e*a_{92}} \approxeq s_{challenge}^e~~(mod~N)$$ $$H(N,m_1)^{a_1}*H(N,m_2)^{a_2}*...*H(N,m_{92})^{a_{92}} \approx H(N,challenge) * 2^{8x} + kN$$ Để ý việc không còn modulo và xuất hiện việc nhân với $2^{8x}, x\geqslant 0$ (tượng trưng cho shift byte) vì $s_{challenge}^e~~(mod~N)$ chỉ cần có 8 byte trên cùng là $H(N,challenge)$. Khi đã có các giá trị $a_i$ ta có thể có được $s_{challenge}$ vì $$s_1^{e*a_1}*s_2^{e*a_2}*...*s_{92}^{e*a_{92}} \approxeq s_{challenge}^e~~(mod~N)$$ $$(s_1^{a_1}*s_2^{a_2}*...*s_{92}^{a_{92}})^e \approxeq s_{challenge}^e~~(mod~N)$$ $$s_1^{a_1}*s_2^{a_2}*...*s_{92}^{a_{92}} \approxeq s_{challenge}~~(mod~N)$$ Tới đây mình đã biết được liên hệ giữa các $H(N,m_i)$ và $s_i$. Cùng với đó là cách để mang lại khả năng tìm được $s_{challenge}$ là tìm các $a_i$. Tiếp theo là làm sao để tìm các $a_i$?
Câu trả lời tình cờ tìm ra sau khi mình thấy bài toán này khá giống với "Bài toán xếp ba lô" (**Knapsack problem**) nhưng điểm khác ở đây là **thay vì cộng thì là nhân**. Mà giải quyết việc cộng thay vì nhân thì có thể dùng **Logarit**. Ví dụ như: $$\log(xy)=\log(x)+\log(y)$$ $$\log(x^2)=\log(x)+\log(x)=2\log(x)$$ Áp dụng vào vấn đề đang có $$H(N,m_1)^{a_1}*...*H(N,m_{92})^{a_{92}} \approx H(N,challenge) * 2^{8x} + kN$$ $$\log(H(N,m_1)^{a_1}*...*H(N,m_{92})^{a_{92}}) \approx \log(H(N,challenge) * 2^{8x} + kN)$$ $$a_1\log(H(N,m_1))+...+a_{92}\log(H(N,m_{92})) \approx \log(H(N,challenge) * 2^{8x} + kN)$$
Ok, vậy đến đây ta kết hợp giữa thuật toán xếp ba lô bằng lattice và logarit là sẽ có thể tìm được các $a_i$. Ta có thể dựng lattice như sau:
$$
\left(
\begin{array}{cccc|c}
1 & 0 & \cdots & 0 & Qf_1 \\
0 & 1 & \cdots & 0 & Qf_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & Qf_n \\
\frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & Qw
\end{array}
\right)
$$ Lattice trên sẽ có thể chứa véc tơ cần tìm là $[-a_1+1/2,-a_2+1/2,...,0]$, sau khi dùng thuật toán LLL để rút gọn cơ sở cho lattice (lattice basis reduction).
Với $f_i=\log(H(N,m_i))$ và $w=\log(H(N,challenge)*2^{8x} + kN)$, $Q$ là một biến số để tăng tỉ lệ chính xác (scaling) cho thuật toán LLL, cho $Q=10^{21}$ sẽ cho ra kết quả chính xác và tối ưu trong riêng bài toán này (vì các floating point của các số logarit $f_i$ rất quan trọng nên $Q$ càng lớn -> $Qf_i,Qw$ càng lớn -> càng nhiều thông tin -> càng chính xác, nhưng tỉ lệ ra đáp án chính xác sẽ càng thấp). Vì phương pháp giải bài toán xếp ba lô này thích hợp với số lượng $n$ nhỏ nên cho $n=30$ (việc kiếm được $n=30$ là chủ yếu do thực nghiệm, có thể cho $n \approx 30$ và thỏa điều kiện cho "low-density knapsack", $d = n/\log_2A < 0.9408$ với $A=max_{1\leq i \leq n}f_i$), vậy ta chỉ lấy ngẫu nhiên 30 từ 92 mẫu cho mỗi lần tìm (vậy ta có $C_{92}^{30}$ tổ hợp có thể xét, một con số rất lớn).
Có ba điểm cần lưu ý:
1. $\forall i \in [1, 30],\; a_i \geq 0$. Vì phép chia modulo khác với phép chia số thực, nên nếu gặp trường hợp $a_i < 0$ thì ta sẽ bỏ qua.
2. $H(N,challenge)*2^{8x} < N$. Vì nếu lớn hơn hoặc bằng sẽ bị modulo $N$ làm sai đi 8 byte trên cùng.
3. $kN, k\geq0$. Vì kết hợp với lưu ý 2, đối số của logarit $H(N,challenge)*2^{8x} + kN$ không thể là âm.
Và cuối cùng là nhờ vào sự may mắn, mình đã tìm ra được cờ với code giải như sau.
(code này đã được qua thẩm mỹ để tránh gây đau mắt)
solve.py
``` python
from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import mpz, next_prime
from pwn import remote, process
from hashlib import shake_128
from sage.all import *
from tqdm import tqdm
import secrets
import signal
import random
import os
def H(N, m):
return shake_128(long_to_bytes(N) + m).digest(8)
# r = process(['python3', 'sh-rsa.py'])
r = remote("chal.2025.ductf.net", 30012)
r.recvuntil(b'N = ')
N = int(r.recvline().strip())
r.recvuntil(b'e = ')
e = int(r.recvline().strip())
print(f"{N=}")
print(f"{e=}")
num_sample = 92
list_m = []
list_hash_m = []
list_hash_m_int = []
list_s = []
list_s_verify = []
target_m = b'challenge'
target_hash_m = H(N, target_m)
for i in tqdm(range(num_sample)):
m = int(r.recvuntil(b" ").strip(), 16)
list_m.append(m)
hash_m = H(N, long_to_bytes(m))
list_hash_m.append(hash_m)
s = int(r.recvline().strip(), 16)
list_s.append(s)
list_s_verify.append(pow(s, e, N))
hash_m_int = bytes_to_long(hash_m)
list_hash_m_int.append(hash_m_int)
print(list_s)
print(list_s_verify)
print(list_hash_m_int)
R = RealField(100)
def attack(list_s, list_s_verify, N, e, sample_test, scale=1, plus_target=0):
# for low_bytes_neg in tqdm(range(2048*2//8 - 8)):
for low_bytes_neg in range(2048*2//8 - 8):
size_N_bytes = N.bit_length() // 8
target_hash_m_int = bytes_to_long(target_hash_m)
len_target_s_verify_low_byte_numb = size_N_bytes - len(target_hash_m) - low_bytes_neg
target_s_verify_int = target_hash_m_int << (len_target_s_verify_low_byte_numb * 8)
# assert long_to_bytes(target_s_verify_int)[:8] == target_hash_m
mat = Matrix(QQ, sample_test+1, sample_test+1)
for i in range(sample_test):
mat[i, i] = 1
mat[i, -1] = int(R(list_s_verify[i]).log() * scale)
mat[-1, i] = 1/2
mat[-1, -1] = int(R(target_s_verify_int + plus_target).log() * scale)
# assert target_s_verify_int*scale_target + plus_target % N == target_s_verify_int
mat = mat.LLL()
for row in mat.rows():
if row[-1] == 0:
try:
send_s = 1
row_ei = []
for s, s_verif, i in zip(list_s, list_s_verify, row[:-1]):
ai = 1 - (i + 1 / 2)
# if ei is not an integer or negative, skip
if not ai.is_integer() or ai < 0:
break
ai = int(ai)
row_ei.append(ai)
send_s = send_s * pow(s, ai, N) % N
else:
predict = long_to_bytes(pow(send_s, e, N))
# if predict[:5] == target_hash_m[:5]:
# print("5 bytes match")
if predict[:6] == target_hash_m[:6]:
print("Nearly found it")
if predict[:7] == target_hash_m[:7]:
print("Found it nearly")
if predict[:8] == target_hash_m[:8]:
print("Found it")
print(f"{sample_test=}, {low_bytes_neg=}, {target_s_verify_int=}, {plus_target=}")
return send_s
except Exception as err:
print("Error processing row:", row)
print("Exception:", err)
continue
return None
# choose 30 randomly from 92 sample
def sample_generator(alist, sample_size=30):
while True:
yield random.sample(alist, sample_size)
num_sample_test = 30
Q = 10**21
k = 0
for comb in sample_generator(range(num_sample), num_sample_test):
print(comb)
list_s_sample = [list_s[i] for i in comb]
list_s_verify_sample = [list_s_verify[i] for i in comb]
s = attack(list_s_sample, list_s_verify_sample, N, e, num_sample_test, Q, N*k)
if s != None:
r.sendlineafter(b's: ', hex(s).encode())
print(r.recvline().decode())
r.close()
break
```
Khi thử thì mình chỉ có thể dùng $k=0$ để cho ra được kết quả, nguyên nhân mình vẫn chưa rõ... nhưng mà "it works". Vậy ta không cần tới 92 cặp `m`,`s` vì chỉ cần xấp xỉ 30 cặp, và cũng không cần tới 46 giây vì chỉ cần xấp xỉ 10 giây để giải bài này (dựa theo quan sát cá nhân... trust me bro...).
Flag: **DUCTF{how_did_you_break_64_bits_in_46_seconds!?}**
Sign in with Wallet
Connect another wallet