2023 Business CTF: Interception

Challenge Information

Summary

In the midst of conflict between Luson and Oumara nations, you’ve intercepted a secure communication channel. The channel uses RSA for asymmetric encryption and a custom PRNG-based AES key derivation for symmetric encryption. By exploiting the weak PRNG, you can recover the decryption key and read enemy plans.

Analysis

The OumaraSystem implements:

class GRAS:  # Weak PRNG
    def __init__(self, m, p, q):
        self.m = m
        self.a = 0xdeadbeef
        self.p = p
        self.q = q

    def generate_key(self):
        ct = 0x1337
        for _ in range(self.m):
            ct = pow(ct, self.a, self.m)
        return long_to_bytes(ct)[:16]

class OumaraSystem:
    def __init__(self, bits):
        # ... RSA setup with 2048-bit keys ...
        self.prng = GRAS(self.N, self.p, self.q)

Vulnerabilities:

1. Weak PRNG: Uses a fixed exponent (0xdeadbeef) with modular exponentiation
2. Predictable initialization: Always starts with ct = 0x1337
3. Insufficient iterations: Limited iterations of the power function

The symmetric key is generated by self.prng.generate_key(), which can be predicted.

Solution

The exploit involves:

1. Interact with the system: Send and receive messages through the communication channel

2. Extract information: Use the “Forgot decryption key” option to get a token containing bits of the private key

3. Recover the PRNG state:

   • The PRNG uses known parameters (N = p*q, p, q)
   • The output is deterministic given the secret exponent
   • Brute force or mathematically derive the symmetric key

4. Decrypt the plans: Once you recover the symmetric key used for the encrypted plans:

   cipher = AES.new(recovered_key, AES.MODE_ECB)
   plans = [unpad(cipher.decrypt(ep), 16).decode() for ep in encrypted_plans]

The key insight is that the PRNG’s output depends only on the modulus N and the fixed exponent, making it recoverable through the leaked token information.

Key Takeaways

• Custom PRNG implementations are extremely dangerous for cryptography
• Using fixed exponents in power functions significantly weakens security
• RSA parameters (p, q, N) must remain secret
• Token generation must not leak information about private keys
• Always use established, peer-reviewed cryptographic libraries
• Combining weak PRNG with strong RSA creates a false sense of security