Baby RSA 1 - Write-up

Thông Tin Challenge

• Danh mục: Cryptography
• Độ khó: Trung bình - Khó
• Lỗ hổng: Kiểm soát tùy ý q_inv trong tái kết hợp RSA-CRT

Tổng Quan

Server tạo RSA keypair và cho phép:

• Decrypt ciphertext tùy ý với "magic number" do user cung cấp (q_inv)
• Tiết lộ public key (n, e)
• Tiết lộ encrypted flag

Phân Tích Lỗ Hổng

Triển Khai RSA-CRT

def decrypt_data(c, private_key, q_inv):
    p, q, d = private_key[0], private_key[1], private_key[2] 
    dp, dq = d % (p - 1), d % (q - 1) 
    m1 = pow(c, dp, p)
    m2 = pow(c, dq, q)
    h = q_inv * (m1 - m2) % p
    m = m2 + h * q % (p * q) 
    return long_to_bytes(m)

Lỗi: q_inv nên là inverse(q, p) nhưng lại do user kiểm soát!

Tấn Công Toán Học

Với ciphertext c cố định và hai giá trị q_inv khác nhau (a và b):

Δ = m(a) - m(b) = [((a-b)(m1 - m2) mod p)] * q

Do đó: gcd(n, |Δ|) = q với xác suất cao!

Sơ Đồ Tấn Công

graph TD
    A[Start] --> B[Query Server]
    B --> C1[Get Public Key n,e]
    B --> C2[Get Encrypted Flag]
    
    D[Prepare Attack] --> E[Choose Random c]
    E --> F1[Decrypt c with q_inv=1]
    E --> F2[Decrypt c with q_inv=2]
    
    F1 --> G[Calculate Difference]
    F2 --> G
    G --> H[GCD with n]
    
    H --> I[Factor Found: q]
    I --> J[Calculate p = n/q]
    
    J --> K[Reconstruct Private Key d]
    K --> L[Decrypt Flag]
    L --> M[Success!]
    
    style A fill:#f9f,stroke:#333,stroke-width:4px
    style M fill:#9f9,stroke:#333,stroke-width:4px

Kế Hoạch Tấn Công

1. Query public key (n, e) và flag_enc
2. Chọn c ngẫu nhiên ≠ flag_enc
3. Decrypt c với q_inv=1 → nhận dec1
4. Decrypt c với q_inv=2 → nhận dec2
5. Tính g = gcd(n, |dec1 - dec2|)
6. Tìm thấy phân tích thừa số! Tái tạo private key d
7. Decrypt flag_enc

Flag

BPCTF{Thank_you_naul_for_finding_this_not_so_intended_solution_901832123ab}

Bài Học Rút Ra

• Không bao giờ cho phép user kiểm soát tham số CRT!
• q_inv phải được tính trước: q_inv = inverse(q, p)
• Fault attacks trên CRT có thể phá vỡ hoàn toàn RSA
• Thông tin lỗi có thể leak secrets ngay cả không có giải mã "đúng"