ImaginaryCTF 2025

Vừa qua mình có tham gia giải Imaginary CTF 2025 cùng team laviem, team mình kết thúc giải với vị trí thứ 22. Đây là các bài crypto mình đã giải được.

leaky-rsa

Source code:

#!/usr/local/bin/python3
import json
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secrets import randbelow, token_bytes
from hashlib import sha256

with open('flag.txt') as f:
    flag = f.read()

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = pow(e, -1, (p-1)*(q-1))

key_m = randbelow(n)
key_c = pow(key_m, e, n)

key = sha256(str(key_m).encode()).digest()[:16]
iv = token_bytes(16)
ct = AES.new(key, AES.MODE_CBC, IV=iv).encrypt(pad(flag.encode(), 16))

print(json.dumps({'n': n, 'c': key_c, 'iv': iv.hex(), 'ct': ct.hex()}))

def get_bit(n, k):
    return (n >> k) % 2

for _ in range(1024):
    idx = randbelow(4)
    print(json.dumps({'idx': idx}))
    try:
        response = json.loads(input())
        c = response['c'] % n
        assert c != key_c
        m = pow(c, d, n)
        b = get_bit(m, idx)
    except (json.JSONDecodeError, TypeError, KeyError, ValueError, AssertionError):
        b = 2
    print(json.dumps({'b': b}))
print(key_m)

Phân tích source một chút: ta thấy rằng, server sinh ra giá trị key_m ngẫu nhiên (dùng làm key để mã hóa flag bằng AES-CBC). Và server đã giấu nó đi bằng cách sử dụng RSA. Mục đích của ta là phải recover lại được key_m, ngoài ra server cho ta được phép thực hiện đúng 1024 thao tác, mỗi thao tác ta sẽ gửi giá trị c, server sẽ giải m = pow(c, d, n) và trả về bit nằm ở vị trí idx cho ta.

Nhưng khi đọc kĩ code bài này thì ta phát hiện một bug rất nghiêm trọng đó là: server đã trả về key_m ở dòng cuối cùng :)). Vậy việc đơn giản là gửi đại một số c nào đó để pass qua 1024 bước. Sau đó chỉ việc lấy key_m, decrypt AES và lấy flag.

Tất nhiên bài này không thể đơn giản như vậy được :))), vì vậy sau đó author đã up phiên bản revenge cho bài này.

Code solve:

from pwn import *
from Crypto.Util.number import *
from sage.all import *
from hashlib import sha256
from Crypto.Cipher import AES
import json

io = process(['python3', 'chall.py'], level='debug')
# io = remote('leaky-rsa.chal.imaginaryctf.org', 1337, level='debug')

data = io.recvline().strip().decode()
data = json.loads(data)
n = data['n']
c = data['c']
iv = bytes.fromhex(data['iv'])
ct = bytes.fromhex(data['ct'])

for _ in range(1024):
    io.recvline()
    io.sendline(json.dumps({'c': 0}))
    io.recvline()
key_m = int(io.recvline().strip().decode())

key = sha256(str(key_m).encode()).digest()[:16]
flag = AES.new(key, AES.MODE_CBC, IV=iv).decrypt(ct)
print(flag)

# ictf{p13cin9_7h3_b1t5_t0g37her_3f0068c1b9be2547ada52a8020420fb0}

leaky-rsa-revenge

Source code:

#!/usr/local/bin/python3
import json
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secrets import randbelow, token_bytes
from hashlib import sha256

with open('flag.txt') as f:
    flag = f.read()

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = pow(e, -1, (p-1)*(q-1))

key_m = randbelow(n)
key_c = pow(key_m, e, n)

key = sha256(str(key_m).encode()).digest()[:16]
iv = token_bytes(16)
ct = AES.new(key, AES.MODE_CBC, IV=iv).encrypt(pad(flag.encode(), 16))

print(json.dumps({'n': n, 'c': key_c, 'iv': iv.hex(), 'ct': ct.hex()}))

def get_bit(n, k):
    return (n >> k) % 2

for _ in range(1024):
    idx = randbelow(4)
    print(json.dumps({'idx': idx}))
    try:
        response = json.loads(input())
        c = response['c'] % n
        assert c != key_c
        m = pow(c, d, n)
        b = get_bit(m, idx)
    except (json.JSONDecodeError, TypeError, KeyError, ValueError, AssertionError):
        b = 2
    print(json.dumps({'b': b}))

Code vẫn y chang bài trên, chỉ khác ở chỗ server sẽ không cho ta key_m đơn giản như vậy nữa. Vậy, ta phải nghĩ cách làm sao để có thể recover được key_m khi sử dụng bit oracle mà server cung cấp.

Bài này là một phiên bản cải tiến của LSB Oracle Attack. Với phiên bản cổ điển, oracle chỉ trả về cho ta bit vị trí 0 (tức là lsb). Nếu ta gửi c' = c * 2^e (mod N), oracle sẽ trả về lsb của 2m mod N, khi đó:

• Nếu 2m < N thì 2m mod N = 2m (chắn) => oracle trả về 0.
• Nếu 2m >= N thì 2m mod N = 2m - N (mà 2m chẵn và N lẻ) => oracle trả về 1.

Do đó, phép nhân thêm 2^e vào c sẽ cho ta biết được m thuộc nửa trên [N/2, N) hay nửa dưới [0, N/2). Nếu lặp lại phép nhân 2^e này, ta sẽ dần dần thu hẹp lại được khoảng giá trị của m. Với độ phức tạp là số bit của m.

Đó là với trường hợp oracle chỉ trả về bit vị trí 0. Còn trong bài này, oracle trả về một vị trí ngẫu nhiên trong khoảng [0, 3], phải làm thế nào ?

Ta có:

\[m' = m \cdot 2^{i+idx} - q \cdot N\]

Trong đó $q = \lfloor \tfrac{m \cdot 2^{i+idx}}{N} \rfloor$. Do $i \ge 1$ và $idx \ge 0$ nên $m \cdot 2^{i+idx}$ luôn có các bit $0$ nằm ở cuối (ít nhất là $i+idx$ bit $0$). Vì vậy, các bit thấp của $m’$ sẽ hoàn toàn bị quyết định bởi $-q.N$. Cụ thể:

\[m' \equiv -q \cdot N \pmod {2^{i+idx}}\]

Giả sử ta chọn $N \equiv -1 \pmod {16}$:

\[\Rightarrow m' \equiv -q \cdot N \equiv -q \cdot (-1) \equiv q \pmod {16}\]

Khi đó, oracle trả về bit thứ $idx$ của $m’$ cũng chính là bit thứ $idx$ của $q$. Cụ thể hơn, oracle return:

\[b = (q \ >> \ idx) \pmod 2 \\ \Rightarrow b = \lfloor \tfrac{q}{2^{idx}} \rfloor \pmod 2 \\ \Rightarrow b = \lfloor \tfrac{m \cdot 2^i}{N} \rfloor \pmod 2\]

Như vậy, với mọi $idx \in [0, 3]$ thì bit mà oracle trả về cho sẽ luôn là LSB của $\lfloor \tfrac{m \cdot 2^i}{N} \rfloor$. Lại có:

\[m \cdot 2^{i} = q \cdot N + r\]

• Nếu $q$ chẵn (LSB oracle trả về là 0):

\[m \cdot 2^{i} = 2k \cdot N + r \\ \Rightarrow \frac{k \cdot N}{2^{i-1}} \le m < \frac{k \cdot N }{2^{i-1}} + \frac{N}{2^{i}} \ \ \ \ \ \ \ , \text{do} \ \ 0 \le r < N \\\]

• Nếu $q$ lẻ (LSB oracle trả về 1):

\[m \cdot 2^{i} = (2k+1) \cdot N + r \\ \Rightarrow \frac{(2k + 1) \cdot N}{2^{i}} \le m < \frac{(2k + 1) \cdot N}{2^{i}} + \frac{N}{2^{i}} \ \ \ \ \ \ \ , \text{do} \ \ 0 \le r < N \\ \Rightarrow \frac{k \cdot N}{2^{i-1}} + \frac{N}{2^{i}} \le m < \frac{(2k + 2) \cdot N}{2^{i}} \\ \Rightarrow \frac{k \cdot N}{2^{i-1}} + \frac{N}{2^{i}} \le m < \frac{(k + 1) \cdot N}{2^{i-1}} \\\]

Từ 2 trường hợp trên, dễ dàng nhận thấy khi gửi chosen_ct = long_to_bytes(c * pow(2**(i+idx), e, N) % N), nếu oracle trả về 0 thì giá trị m sẽ nằm trong nửa khoảng dưới của $[\frac{k \cdot N}{2^{i-1}}, \frac{(k+1) \cdot N}{2^{i-1}})$, và ngược lại khi oracle trả về 1 thì ta biết m sẽ thuộc khoảng nửa trên của $[\frac{k \cdot N}{2^{i-1}}, \frac{(k+1) \cdot N}{2^{i-1}})$.

Code solve:

from pwn import *
from Crypto.Util.number import *
from sage.all import *
from hashlib import sha256
from Crypto.Cipher import AES
import json

while True:
    io = process(['python3', 'chall.py'], level='debug')
    # io = remote('leaky-rsa-revenge.chal.imaginaryctf.org', 1337, level='debug')

    data = io.recvline().strip().decode()
    data = json.loads(data)
    N = data['n']
    c = data['c']
    e = 65537
    iv = bytes.fromhex(data['iv'])
    ct = bytes.fromhex(data['ct'])

    if N % 16 != 15:
        io.close()
        continue

    upper_limit = N
    lower_limit = 0
    i = 1
    while i <= 1024:
        idx = json.loads(io.recvline().strip().decode())['idx']

        chosen_ct = long_to_bytes(c * pow(2**(i+idx), e, N) % N)

        io.sendline(json.dumps({'c': bytes_to_long(chosen_ct)}).encode())
        output = json.loads(io.recvline().strip().decode())['b']

        if output == 0:
            upper_limit = (lower_limit + upper_limit) // 2
        elif output == 1:
            lower_limit = (lower_limit + upper_limit) // 2
        i += 1

    for offset in range(-10000, 10000):
        m = lower_limit + offset
        key = sha256(str(m).encode()).digest()[:16]
        cipher = AES.new(key, AES.MODE_CBC, iv)
        flag = cipher.decrypt(ct)
        if b'ictf' in flag:
            print(flag)
            exit()

# ictf{p13cin9_7h3_b1t5_t0g37her_7d092f5d43ebbf6fa60fba8c9e9ac4466daba9a71d04def7e5bf09bcce5649c8}

scalar-division

Source code:

assert ((E:=EllipticCurve(GF(0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21),[5,7])).order().factor(limit=2**10)[3][0]*E.lift_x(ZZ(int.from_bytes((flag:=input('ictf{')).encode())))).x() == 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5 and not print('\033[53C\033[1A}')

Phân tích source: ban đầu ta được cung cấp thông tin của một đường cong Elliptic với các hệ số là:

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
a = 5
b = 7

Lấy E.order() factor ra sau đó chọn thừa số nguyên tố thứ 3 (tạm gọi là q), sao đó tính:

\[Q = q \cdot P\]

Với P.x() là flag cần tìm, và ta đã biết giá trị Q.x(). Vì đã có Q.x và các hệ số của EC, ta có thể dễ dàng recover lại điểm Q. Bài toán của ta giờ đây là tìm điểm P khi biết điểm Q và giá trị q.

Ta đã biết, q = 457 là một ước nguyên tố của N = E.order(), điều này có nghĩa tồn tại một kernel (tập nghiệm khi nhân với q sẽ ra điểm vô cực $O$) có kích thước q phần tử.

Tính M = N / q, gọi d_M là nghịch đảo của q modulo M. Ta xây dựng một điểm P0 sao cho:

\[p \cdot P_0 = q \cdot (d_M \cdot Q) = Q\]

Khi đó, P0 chính là một trong các nghiệm của q . X = Q. Khi đã có P0, ta có thể sinh ra toàn bộ các nghiệm khác bằng cách cộng thêm các phần tử trong kernel. Vì N = q . M, thì với bất kỳ điểm S:

\[q \cdot (M \cdot S) = (qM) \cdot S = N \cdot S = O\]

Nghĩa là $M \cdot S \in ker([q])$, vậy nếu ta chọn được điểm S sao cho $M \cdot S \ne O$ thì $G_q = M \cdot S$ có bậc đúng bằng q (do kernel có q phần tử, mà q nguyên tố -> bất kỳ phần từ khác $O$ trong kernel đều sinh ra toàn bộ kernel). Vì kernel là nhóm cyclic bậc q, phần tử sinh $G_q$ nên toàn bộ kernel là:

\[\text{ker([q])} = \{ O, G_q, 2G_q, 3G_q,...,(q-1)G_q \}\]

Đến đây, ta đã có $P_0$ là một nghiệm của $Q = p \cdot P_0$ rồi, thì tất cả các nghiệm còn lại sẽ là:

\[P_0 + T, \ \ \ \ \ \text{với} \ T \in \text{ker([q])} \\ \text{hay} \ \ \ \{ P_0 + k \cdot G_q \ | \ k = 0,1,2,...,q-1 \}\]

Duyệt từng nghiệm và kiểm tra tọa độ x của nó có phải là flag hay không.

Code solve:

from sage.all import *
from Crypto.Util.number import *

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
A = 5
B = 7
q = 457
Qx = 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5

F = GF(p)
E = EllipticCurve(F, [A, B])
Q = E.lift_x(F(Qx))

N = E.order()
assert N % q == 0
M = N // q

d_M = inverse_mod(q, M)
P0 = d_M * Q

S = E.random_point()
G_q = M * S

while G_q.is_zero():
    S = E.random_point()
    G_q = M * S

for k in range(q):
    P_k = P0 + k * G_q
    m = P_k.x()

    flag = long_to_bytes(int(m))

    if all(32 <= b < 127 for b in flag):
        print("ictf{", end='')
        print(f"{flag.decode()}", end='')
        print("}")
        break

# ictf{mayb3_d0nt_m4ke_th3_sca1ar_a_f4ctor_0f_the_ord3r}