CTF-Writeups

[Cryptography 4] Radical Security Animal – Writeup

Category: Crypto
Points: 554
Flag: MCTF25{r4d1c4l_s3cur1ty}

---

1. Challenge Overview

We are given:

• A TCP service: 10.240.2.11:1337
• A Python file crypto.py that implements RSA with a small key size
• A PDF that hints the issue is related to the RSA key length

From crypto.py (simplified):

from Cryptodome.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

KEY_BITS = 256
E = 65537

p = getPrime(KEY_BITS // 2)
q = getPrime(KEY_BITS // 2)

n = p * q
phi = (p - 1) * (q - 1)
d = inverse(E, phi)

So the server is using RSA with:

• Public key: (n, e)
• Private key: d
• KEY_BITS = 256, which means p and q are 128-bit primes and n is only 256 bits

A 256-bit RSA modulus is way too small and can be factored easily. That’s the core vulnerability.

---

2. Talking to the Secure Crypto Oracle

We connect to the service:

nc 10.240.2.11 1337

The service responds with:

Connection established to Secure Crypto Oracle [SCO v1.0]
Session ready.

Options:
1. Encrypt message
2. Get Secret Message
3. Get Public Key

We need:

• The public key (n, e) from option 3
• The encrypted secret from option 2

First, get the public key:

Enter your choice (1-3): 3
Public Key (n, e): (74453105459613851322187047665994238471320654596065423955454287400990254712301, 65537)

Then, get the secret message:

Enter your choice (1-3): 2
57404030761199998498847049987163372359776031729451339753283863067115090061488

So we have:

n = 74453105459613851322187047665994238471320654596065423955454287400990254712301
e = 65537
C = 57404030761199998498847049987163372359776031729451339753283863067115090061488

The server is doing standard RSA encryption:

C = m^e mod n

where m is the secret message (the flag) converted to an integer.

---

3. Spotting the Vulnerability

From crypto.py:

KEY_BITS = 256
p = getPrime(KEY_BITS // 2)
q = getPrime(KEY_BITS // 2)
n = p * q

This means:

• p is a 128-bit prime
• q is a 128-bit prime
• n is a 256-bit modulus

Real-world RSA typically uses at least 2048-bit moduli. A 256-bit modulus is trivial to factor with modern tools.

So the attack strategy is:

1. Factor n into its prime factors p and q
2. Compute phi = (p - 1) * (q - 1)
3. Compute the private exponent d = e^(-1) mod phi
4. Decrypt the ciphertext C using d to recover m
5. Convert m back to bytes to reveal the flag string

---

4. Factoring the Modulus n

We paste the 77-digit number n into a big integer factorization tool (e.g. FactorDB / WebAssembly factorizer) and obtain:

p = 238310156548665930651417811579815413711
q = 312421033739741558015235161390562658691

Both are ~128-bit primes, and indeed:

n = p * q

So this is the correct factorization of the RSA modulus.

---

5. Reconstructing the Private Key and Decrypting

Given p, q, n, e, and the ciphertext C, we can perform textbook RSA decryption locally.

Step 1: Compute φ(n)

phi = (p - 1) * (q - 1)

Step 2: Compute the private exponent d

d is the modular inverse of e modulo phi:

d = pow(e, -1, phi)  # e^(-1) mod phi

Step 3: Decrypt the ciphertext

m = pow(C, d, n)  # m = C^d mod n

Step 4: Convert m to bytes and decode

Below is the complete Python script used:

# rsa_decrypt.py
from math import gcd

# Prime factors from factorization
p = 238310156548665930651417811579815413711
q = 312421033739741558015235161390562658691

n = p * q
e = 65537
C = 57404030761199998498847049987163372359776031729451339753283863067115090061488

phi = (p - 1) * (q - 1)

# Compute private exponent d
d = pow(e, -1, phi)

# Decrypt ciphertext: m = C^d mod n
m = pow(C, d, n)

# Convert integer m to bytes
def long_to_bytes(x: int) -> bytes:
    if x == 0:
        return b""
    length = (x.bit_length() + 7) // 8
    return x.to_bytes(length, "big")

pt = long_to_bytes(m)
print(pt)
print(pt.decode())

Run it:

python3 rsa_decrypt.py

Output:

b'MCTF25{r4d1c4l_s3cur1ty}'
MCTF25{r4d1c4l_s3cur1ty}

So the decrypted plaintext string is the flag.

---

6. Final Flag

MCTF25{r4d1c4l_s3cur1ty}

---

7. Summary

• The challenge uses RSA with an extremely small 256-bit modulus, which is insecure.
• The oracle gives:
  • The public key (n, e)
  • The encrypted secret message (ciphertext C)
• By factoring n into p and q, we can:
  • Compute phi = (p - 1) * (q - 1)
  • Compute the private exponent d = e^(-1) mod phi
  • Decrypt the ciphertext with m = C^d mod n
  • Convert m back to bytes to recover the flag

In one sentence:
Because the RSA key size was only 256 bits, we could factor n, reconstruct the private key, decrypt the oracle’s secret, and obtain the flag:

MCTF25{r4d1c4l_s3cur1ty}

---