rsa_oracle picoCTF 2024 Solution

Description

1. Step 1Encrypt a small multiplier
   Ask the oracle to encrypt the value 2. The result (c_a) will later be multiplied with the captured password ciphertext (c).
   bash

   E → 0x02

   Copied!
   Learn more

   This challenge exploits the multiplicative homomorphism of textbook RSA. Encryption is c = m^e mod n. The full derivation, line by line:

   Enc(a)         = a^e          mod n
   Enc(b)         = b^e          mod n
   Enc(a) * Enc(b)= a^e * b^e    mod n
                 = (a*b)^e       mod n   <- exponents distribute over multiplication
                 = Enc(a * b)    mod n

   That last line is the crowbar. Multiplying two ciphertexts together is the same as encrypting the product of the two plaintexts. The oracle's blacklist only refuses the exact integer c, not anything else; c * c_a is numerically a different ciphertext, sails through the check, and decrypts to 2 * password, which we then halve.

   Toy walkthrough with n = 3233, e = 17 (so d = 2753):
     password m  = 65 ('A')
     c           = m^e mod n = 65^17 mod 3233 = 2790  <- this is the forbidden ciphertext
   
   Blinding factor a = 2:
     c_a = 2^17 mod 3233 = 1752
   
   Multiply blinded:
     c'  = c * c_a mod n = 2790 * 1752 mod 3233 = 3017
   
   Oracle decrypts c' (it is not equal to c, so the blocklist allows it):
     m'  = c'^d mod n = 3017^2753 mod 3233 = 130
   
   Unblind:
     m = m' / 2 = 130 / 2 = 65  -> 'A'  (recovered)

   The oracle's blacklist only refuses the exact integer c. Any multiplicatively scaled version sails through. Real RSA implementations use OAEP padding (PKCS#1 v2.1) precisely to break this homomorphism: random padding bytes are mixed into the message before exponentiation, so Enc(2*m) != 2 * Enc(m) and the unblinding step produces garbage.

2. Step 2Multiply and decrypt
   Submit c * c_a to the decrypt endpoint. The oracle refuses to decrypt the original password, but this scaled ciphertext is acceptable. Convert the hex response to an integer and divide by 2 to recover the password.
   bash

   p.sendline(str(c_a * c).encode())

   Copied!
   Learn more

   When you submit c_a * c mod n to the oracle, it decrypts it to get 2 * password mod n (by the homomorphic property). Dividing that result by 2 yields the original plaintext password. This is a textbook RSA blinding attack- you "blind" the forbidden ciphertext by multiplying it with a known factor, get the oracle to do the decryption, then "unblind" by dividing.

   The oracle's blacklist only checks for the exact ciphertext value c. By multiplying by c_a, you produce a numerically different ciphertext that passes the blocklist check but still encodes information about the original message.

   • The response comes back as a hex integer; convert with int(response, 16).
   • Plain integer division by 2 (not modular inverse) is sufficient here because we picked the blinding factor a = 2 and the recovered plaintext 2 * password is guaranteed even, so (2 * password) // 2 == password with no remainder. If the blinding factor were instead a non-trivial number like 3 or 7, you'd need password = m_blinded * pow(a, -1, n) % n (a modular inverse) to undo it.
   • In a proper RSA-OAEP implementation this trick does not work because padding bytes make the resulting plaintext garbage.
3. Step 3Use the recovered password
   Feed the plaintext password to OpenSSL to decrypt secret.enc and reveal the flag.
   bash

   openssl enc -aes-256-cbc -d -in secret.enc

   Copied!
   Example automation script: from pwn import * context.log_level = 'critical' p = remote("titan.picoctf.net", 62026) # c = the forbidden ciphertext we need decrypted (from password.enc). with open("password.enc") as f: c = int(f.read()) # Encrypt-call output: oracle prints the ciphertext as a decimal int on its own line. p.sendline(b"E") p.sendline(b"\x02") # blinding factor a = 2 c_a = int(p.recvline()) # c_a = Enc(2) = 2^e mod n # Decrypt-call output: oracle prints the plaintext as a hex string. p.sendline(b"D") p.sendline(str(c_a * c).encode()) # submit c_a * c (mod n implicit on server) password = int(p.recvline(), 16) // 2 # // 2 unblinds (we multiplied plaintext by 2) print(password.to_bytes((password.bit_length()+7)//8, 'big').decode())
   Learn more

   openssl enc is the symmetric encryption/decryption command. The flags used here specify AES-256 in CBC mode (-aes-256-cbc), decryption mode (-d), and the input file (-in secret.enc). OpenSSL will prompt for the password, which you recovered in the previous step.

   AES-256-CBC is a well-regarded symmetric cipher. Unlike RSA, it is not vulnerable to mathematical attacks - its security relies entirely on the secrecy of the key (here, derived from the password). This two-layer approach - RSA to protect the symmetric key, symmetric encryption for the bulk data - is called hybrid encryption and is the foundation of TLS, PGP, and most real-world secure communication protocols.

   The pwntools Python library used in the automation script is the standard CTF toolkit for interacting with remote services. remote(host, port) opens a TCP connection, and sendline/recvline handle communication. It vastly simplifies writing exploit scripts compared to raw socket code.

Alternate Solution

Flag

Decrypting secret.enc with the recovered password yields the flag above.