rsa_oracle picoCTF 2024 Solution

Description

1. Step 1Encrypt a small multiplier

   Observation

   The oracle refuses only the exact intercepted ciphertext, but will encrypt anything else you ask for. RSA is multiplicative, so get Enc(2) first and use it to blind the forbidden value.

   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!

   What didn't work first

   Tried: Encrypting a large random number instead of 2 as the blinding factor, thinking a bigger factor is harder to detect.

   The oracle will encrypt any value, so a large factor works mechanically, but then unblinding needs a modular inverse instead of plain division. Picking 2 keeps it simple: the blinded plaintext is guaranteed even, so integer division is exact.

   Tried: Sending the password ciphertext directly to the D (decrypt) endpoint without multiplying it first, assuming the blacklist might not catch it.

   The oracle compares what you submit against the exact intercepted value and refuses a match. Blinding exists to produce a numerically different ciphertext that slips past that equality check while still carrying the original plaintext.

   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

   Observation

   Multiplying the blocked ciphertext by Enc(2) gives a numerically different value that decrypts to twice the password. Submit that to the decrypt endpoint and halve the result.

   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!

   What didn't work first

   Tried: Submitting c_a * c as a hex string instead of a decimal integer string, because the oracle prints ciphertexts in various formats.

   The decrypt endpoint wants a decimal integer string. A 0x-prefixed string or raw bytes gets parsed wrong on the server and yields an error or garbage. The script sends str(c_a * c).encode() for exactly that reason.

   Tried: Dividing the hex response by 2 using modular inverse (pow(2, -1, n) % n) instead of plain integer division.

   With a blinding factor of 2, the decrypted value is genuinely twice the password, not a residue that wrapped around the modulus. Integer division recovers it exactly. A modular inverse would multiply by a large number mod n and give something else entirely.

   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

   Observation

   secret.enc is AES-encrypted, and the RSA oracle only guards the symmetric password. That is ordinary hybrid encryption, so openssl decrypts the file once you supply 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!

   Expected output

   picoCTF{su((3ss_(r@ck1ng_r3@_24bc...}

   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())

   What didn't work first

   Tried: Running openssl enc -aes-256-cbc -d -in secret.enc -pass pass:PASSWORD with the recovered integer value as the password argument directly.

   What comes out of the blinding attack is a raw integer from the decrypted hex. Passing that integer to -pass fails, because OpenSSL wants the password in the encoding used at encryption time, an ordinary ASCII string. Convert the integer to bytes, decode it, and type that at the prompt.

   Tried: Trying openssl rsautl -decrypt instead of openssl enc, thinking secret.enc is RSA-encrypted since the challenge involves RSA.

   RSA here protects only the password. secret.enc itself is AES-256-CBC, the usual hybrid arrangement. rsautl fails on it because the file is an OpenSSL symmetric envelope with a magic header and salt, not a raw RSA blob.

   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.

Flag

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