Baby RSA 1 - Write-up

Challenge Information

• Category: Cryptography
• Difficulty: Medium - Hard
• Vulnerability: Arbitrary control of q_inv in RSA-CRT recombination

Overview

Server creates RSA keypair and allows:

• Decrypt random ciphertext with "magic number" provided by user (q_inv)
• Leak public key (n, e)
• Leak encrypted flag

Vulnerability Analysis

RSA-CRT Implementation

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)

Flaw: q_inv should be inverse(q, p) but is controlled by user!

Mathematical Attack

With fixed ciphertext c and two different values of q_inv (a and b):

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

Therefore: gcd(n, |Δ|) = q with high probability!

Attack Diagram

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

Attack Plan

1. Query public key (n, e) and flag_enc
2. Choose random c ≠ flag_enc
3. Decrypt c with q_inv=1 → get dec1
4. Decrypt c with q_inv=2 → get dec2
5. Calculate g = gcd(n, |dec1 - dec2|)
6. Factor found! Reconstruct private key d
7. Decrypt flag_enc

Flag

BPCTF{Thank_you_naul_for_finding_this_not_so_intended_solution_901832123ab}

Key Takeaways

• Never allow user to control CRT parameters!
• q_inv must be precomputed: q_inv = inverse(q, p)
• Fault attacks on CRT can completely break RSA
• Error information can leak secrets even without "correct" decryption