0xL4ugh CTF 2024¶

RSA_GCD¶

chall.py

import math
from Crypto.Util.number import *
from secret import flag,p,q
from gmpy2 import next_prime
m = bytes_to_long(flag.encode())
n=p*q


power1=getPrime(128)
power2=getPrime(128)
out1=pow((p+5*q),power1,n)
out2=pow((2*p-3*q),power2,n)
eq1 = next_prime(out1)

c = pow(m,eq1,n)


with open('chall2.txt', 'w') as f:
    f.write(f"power1={power1}\npower2={power2}\neq1={eq1}\nout2={out2}\nc={c}\nn={n}")

Đề bài cho mình thuật toán RSA với các tham số gồm power1, power2, eq1, out2, c và n.

Trong đó c là ciphertext RSA với modulo là n, số mũ là eq1.

Mình đã có out2 nhưng chưa có out1. Vì eq1 là số nguyên tố tiếp theo kể từ out1, nếu mình gọi eq0 là số nguyên tố trước eq1 thì out1 sẽ nằm trong khoảng [eq0, eq1] và mình sẽ bruteforce out1 trong khoảng này.

Để tìm $p$ và $q$, do $o_1 = (p+5q)^{e_1} \pmod n$ và $o_2 = (2p - 3q)^{e_2} \pmod n$ (ở đây $o_1$ và $o_2$ tương ứng out1 và out2, $e_1$ và $e_2$ tương ứng power1 và power2).

Vì $o_1^{e_2} = (p+5q)^{e_1 e_2} \pmod n$, mà $q \mid n$ nên

\[o_1^{e_2} = (p+5q)^{e_1 e_2} \pmod q = p^{e_1 e_2} \pmod q.\]

Thêm một bước nữa là

\[o_1^{e_2} \cdot 2^{e_1 e_2} = (2p)^{e_1 e_2} \pmod q.\]

Tương tự, $o_2^{e_1} = (2p)^{e_1 e_2} \pmod q$.

Như vậy $o_1^{e_2} \cdot 2^{e_1 e_2} - o_2^{e_1}$ chia hết cho $q$ nên có ước chung lớn nhất với $n$ bằng $q$. Từ đó mình tìm được $q$ và $p$ và decrypt plaintext. Các bạn có thể xem code giải ở đây.

Poisson¶

Đề bài mình để ở đây.

Đề bài cho mình đường cong elliptic với điểm generator $G$. Flag được biểu diễn bằng dãy nhị phân my_priv.

Ở mỗi vòng lặp ở vị trí count, chương trình sẽ

sinh random số $k$;
tính điểm $Q = my\_priv * G$;
random điểm $M$ trong elliptic;
tính điểm $C_1 = k * G$;
tính điểm $C_2 = M + k * Q$;
tính new_priv = poisson(my_priv, ind) là đảo bit ở vị trí ind. Ví dụ, với dãy nhị phân 111001 và ind là $2$ thì kết quả là 110001 (vị trí thứ hai là bit $1$ đổi thành bit $0$);
tính điểm $dec = C_2 - new\_priv * C_1$.

Mình để ý rằng, khi đảo một bit thì lúc trừ số ban đầu và số sau khi đảo sẽ ra lũy thừa của $2$ (có thể là số âm). Với ví dụ ở trên, 111001 - 110001 = 1000 chính là $2^3$.

Như vậy, biến đổi một chút mình có

\[\begin{split}dec = & C_2 - new\_priv * C_1 = M + k * Q - new\_priv * k * G \\ = & M + k * my\_priv * G - k * new\_priv * G \\ \Leftrightarrow dec - M = & (my\_priv - new\_priv) * k * G \\ = & (my\_priv - new\_priv) * C_1.\end{split}\]

Do đó, ở vị trí $i$, nếu $dec - M = 2^i * C_1$ thì bit ở vị trí $i$ là $1$ (do $1$ đổi thành $0$ nên số lúc trước lớn hơn số lúc sau). Tương tự, nếu $dec - M = -2^i * C_1$ thì bit ở vị trí $i$ là $0$.

Code giải mình để ở đây.

L4ugh¶

Đề gồm hai file là challenge.py và utils.py.

Ở bài này, đầu tiên chương trình sinh số nguyên tố $d$ có $666$ bit sao cho $333$ bit đầu cũng là số nguyên tố.

Đặt $d = d_e \cdot 2^{333} + d_g$, tương ứng trong chương trình $d_e$ là d_evil còn $d_g$ là d_good.

Chương trình cho phép chọn một trong ba option. Mình sẽ dùng option $1$ để tìm $d_e$, dùng option $2$ để tìm $d_g$. Để sử dụng option $3$ mình cần cung cấp $d$ hoàn chỉnh.

1. Tìm d "good"¶

Phần này dễ hơn nên mình làm trước. Từ d_good và $10$ số nguyên tố sinh ngẫu nhiên, mình cần nhập số user_input nào đó không nhiều hơn $333$ bit và chương trình sẽ trả lại mảng $d_g \cdot input + p_i$, $0 \leqslant i \leqslant 9$ và $p_i$ là số nguyên tố.

Mình muốn $d_g$ và $p_i$ độc lập với nhau, nghĩa là càng ít liên quan nhau càng tốt. Khi đó mình sẽ có lợi thế trích xuất thông tin hơn. Để ý rằng do $p_i$ là số nguyên tố $333$ bit nên nếu chọn $input = 2^{333}$ thì $p_i$ là $333$ bit thấp của kết quả và $d_g$ là $333$ bit cao của kết quả. Tuy nhiên $2^{333}$ có $334$ bit nên không được. Ở đây mình dùng trick lỏ là chọn $input = 2^{333} - 1$.

Khi đó

\[r_i = d_g \cdot (2^{333} - 1) + p_i = d_g \cdot 2^{333} + (p_i - d_g).\]

Lúc này $d_g$ thực sự là $333$ bit cao của $r_i$ nhưng chỉ khi $p_i - d_g > 0$. Từ $10$ phần tử của mảng mình có thể chọn ra vị trí mà $r_i - d_g \cdot (2^{333} - 1)$ là số nguyên tố. Khi đó mình lấy $d_g$ thôi.

from pwn import process, remote
import json
from Crypto.Util.number import isPrime
from sage.all import *

pr = process(["python", "challenge.py"])
#pr = remote("20.55.48.101", 1337)
pr.recvuntil(b'all input data is in json')

pr.recvuntil(b'option:\t')
pr.sendline(json.dumps({"option": "2"}).encode())

pr.recvuntil(b"Enter your payload:\t")
pr.sendline(str(2**333-1).encode())

res = eval(pr.recvline().strip().decode()[7:])

kres = [r // (2**333) for r in res]

d_goods = [r - k * (2**333 - 1) for r, k in zip(res, kres)]
d_good = None

for r, k in zip(res, kres):
    d_ = r - k * (2**333 - 1)
    if isPrime(d_):
        d_good = k

assert d_good != None
print(f"d_good = {d_good}")

d_good = 11676101755124723561993227185337871743077799520817686580225233864252891286503981386427236336665397269

2. Tìm d "evil"¶

Với $d_e$ là số nguyên tố, chương trình sinh các số $N_i = p_i \cdot q_i$ với $p_i$, $q_i$ là các số nguyên tố và tính nghịch đảo $e_i$ của $d_e$ trong modulo $\phi(N_i) = (p_i - 1) (q_i - 1)$.

Ta có $e_i d_e \equiv 1 \pmod{\phi(N_i)}$, tương đương với

\[e_i d_e - 1 = k \phi(N_i) = k_i (N_i - p_i - q_i + 1),\]

hay là

\[k_i (p_i + q_i - 1) - 1 = k_i N_i - e_i d_e.\]

Do $N_i$, $e_i$ là các số $1024$ bit, và $d_e$ là số $333$ bit nên suy ra $k_i$ cũng khoảng $333$ bit. Như vậy vế phải có $1024+333$ bit. Trong khi đó, vế trái sẽ có $333+512$ bit, nhỏ hơn nhiều so với vế phải. Điều này dẫn mình tới lattice.

Mình xây dựng lattice là ma trận sau

\[\begin{split}\begin{bmatrix} e_0 & e_1 & e_2 & 1 & 0 & 0 & 0 \\ N_0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & N_1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & N_2 & 0 & 0 & 0 & 1 \end{bmatrix}\end{split}\]

thì khi nhân hàng đầu với $-d_e$, nhân hàng hai với $k_0$, hàng thứ ba với $k_1$ và hàng thứ tư với $k_2$ thì mình có vector ngắn trong lattice là

\[\bm{v} = (k_0 (p_0 + q_0 - 1) - 1, \cdots, \cdots, -d_e, k_0, k_1, k_2).\]

Chạy LLL và lấy vị trí thứ ba trong vector ngắn (thêm giá trị tuyệt đối) là mình có $d_e$ rồi.

Nhưng mà khoan, không ra?

Nguyên nhân là vì các số hạng trong vector ngắn $\bm{v}$ không có cùng số bit. Ở trên mình đã nói $k_i (p_i + q_i - 1) - 1$ có $333 + 512$ bit, trong khi $-d_e$ có $333$ bit và $k_i$ cũng có $333$ bit. Do đó mình sẽ phải "scale" để chúng có số bit bằng nhau ở vector ngắn.

Quay ngược lên trên lattice, mình nhân thêm hệ số $2^L$ để đảm bảo khi nhân mỗi hàng với $-d_e$ và $k_i$ thì kết quả là vector ngắn $\bm{v}$ có số bit như nhau.

Lattice của mình lúc này sẽ là

\[\begin{split}\begin{bmatrix} e_0 & e_1 & e_2 & 2^{512} & 0 & 0 & 0 \\ N_0 & 0 & 0 & 0 & 2^{512} & 0 & 0 \\ 0 & N_1 & 0 & 0 & 0 & 2^{512} & 0 \\ 0 & 0 & N_2 & 0 & 0 & 0 & 2^{512} \\ \end{bmatrix}.\end{split}\]

Vector ngắn lúc này là

\[\bm{v} = (k_0 (p_0 + q_0 - 1) - 1, \cdots, \cdots, -d_e \cdot 2^{512}, k_0 \cdot 2^{512}, k_1 \cdot 2^{512}, k_2 \cdot 2^{512}).\]

Như vậy mỗi phần tử trong $\bm{v}$ đều có $512 + 333$ bit rồi.

pr.recvuntil(b'option:\t')
pr.sendline(json.dumps({"option": "1"}).encode())

Ns = eval(pr.recvline().strip().decode()[3:])
es = eval(pr.recvline().strip().decode()[3:])

print([int(e).bit_length() for e in es])

Mat = Matrix(ZZ, 4, 7)
for i in range(3):
    Mat[0, i] = es[i]
Mat[0, 3] = 2**512

for i in range(3):
    Mat[i+1, i] = Ns[i]
    Mat[i+1, i+4] = 2**512

N = Mat.LLL()

d_evil = abs(N[0][3]) // 2**512

assert isPrime(d_evil)

print(f"d_evil = {d_evil}")

Output của đoạn code trên là:

[1022, 1021, 1022]
d_evil = 9164192793237501841603085694166740261176767425415039425767329941821517155591215118383740675363639829

3. CBC Oracle¶

Tới đây thì dễ thở hơn rồi! Đầu tiên mình encrypt một lần và nhận về ciphertext. Chúng ta sẽ flip phần ciphertext để khi decrypt ra sẽ có đoạn isadmin: true.

Giả sử ciphertext gồm các block $C_0$, $C_1$, ... Plaintext gồm các block tương ứng là $P_0$, $P_1$, ...

Giả sử tiếp, đoạn isadmin: false nằm trong block $P_i$. Quá trình giải mã để tìm $P_i$ theo công thức $P_i = C_{i-1} \oplus \text{DEC}(C_i)$.

Do mình muốn $P_i'$ chứa isadmin: true (thêm dấu cách ở cuối để số ký tự trước và sau khi đổi bằng nhau). Khi đó mình sẽ đổi

\[C_{i-1}' = C_{i-1} \oplus \text{???isadmin: true ???}.\]

Các block ciphertext còn lại giữ nguyên.

Mình mang ciphertext mới đi decrypt thì sẽ nhận được lỗi do block đầu tiên khi decrypt ra không đúng (khác ciphertext ban đầu nên khi XOR với $IV$ không ra).

d = d_evil * 2**333 + d_good

pr.recvuntil(b'option:\t')
pr.sendline(json.dumps({"option": "3", "d": int(d)}).encode())

pr.recvuntil(b'2.sign in')
pr.sendline(json.dumps({"option": "1", "user": "user"}).encode())

data = pr.recvline().strip().decode()
data = data.replace("\'", "\"")

print(data, len(data))

idx = data.index("False")

ctx = pr.recvline().strip().decode()

iv, ct = ctx[:32], ctx[32:]
iv, ct = bytes.fromhex(iv), list(bytes.fromhex(ct))

tmp = [int(i).__xor__(int(j)) for i, j in zip(b'False', b'True ')]
for i, j in zip(range(idx, idx + len(tmp)), range(len(tmp))):
    ct[i - 16] = int(ct[i - 16]).__xor__(int(tmp[j]))

pr.recvuntil(b'option:\t')
pr.sendline(json.dumps({"option": "3", "d": int(d)}).encode())

pr.recvuntil(b'2.sign in')
pr.sendline(json.dumps({"option": "2", "token": iv.hex() + bytes(ct).hex()}).encode())

test = pr.recvline().strip().decode()

{"id": 190504, "isadmin": False, "username": "user"} 52

Do đó mình cũng phải sửa $IV$ để khi decrypt $C_0$ và xor với $IV'$ thì sẽ ra được $P_0$ ban đầu.

Để ý rằng $P_0' = IV \oplus \text{DEC}(C_0')$ nên $P_0 = P_0' \oplus IV \oplus P_0 \oplus \text{DEC}(C_0')$, suy ra $IV' = P_0' \oplus IV \oplus P_0$.

assert test[:17] == 'Unpadding Error: '

test = test[19:-1]

def convert(st: str):
    result = []
    i = 0
    while i < len(st):
        if st[i:i+2] != "\\x":
            result.append(ord(st[i]))
            i += 1
        else:
            result.append(int(st[i+2:i+4], 16))
            i += 4
    return bytes(result)

pti = convert(test) # P_0'
pti = bytes(p_ ^ d_ for p_, d_ in zip(pti, data[:16].encode())) # XOR with P_0
pti = bytes(p_ ^ i_ for p_, i_ in zip(pti, iv)) # XOR with IV

pr.recvuntil(b'option:\t')
pr.sendline(json.dumps({"option": "3", "d": int(d)}).encode())

pr.recvuntil(b'2.sign in')
pr.sendline(json.dumps({"option": "2", "token": pti.hex() + bytes(ct).hex()}).encode())

pr.recvline()
pr.recvline()
pr.recvline()

pr.recvuntil(b"2.Exit\n")
pr.sendline(json.dumps({"option": "1"}).encode())

print(pr.recvline())

pr.close()

# b'0xL4ugh{cryptocats_B3b0_4nd_M1ndfl4y3r}\n'

# b'0xL4ugh{Fak3_Fl@g}\n'

Một vấn đề là đoạn isadmin: false phải nằm cùng block nếu không sẽ không decrypt ra, việc này may rủi tùy vào $x$ được random như nào. Một vấn đề khác là bytes trong string nên mình phải viết hàm extract chuỗi byte đó ra nên không chắc sẽ tránh được lỗi.

Nhưng chạy tới một lúc nào đó sẽ có flag thôi :)))

Writeup của mình đến đây là hết. Cám ơn các bạn đã đọc.