rsa_oracle picoCTF 2024 Solution

Description

1. Step 1

   Encrypt a small multiplier

   Observation

   I noticed the oracle blacklists only the exact intercepted ciphertext (c) but will freely encrypt any value we choose, which suggested exploiting RSA's multiplicative homomorphism by first obtaining Enc(2) so we could later blind the forbidden ciphertext with it.

   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 accepts any value for encryption, so a large factor works mechanically - but unblinding then requires computing a modular inverse (pow(a, -1, n) % n) rather than plain division. Choosing a = 2 keeps unblinding trivial: the recovered blinded plaintext is guaranteed even, so integer division by 2 is exact with no modular arithmetic needed.

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

   The oracle checks the submitted integer against the exact value of c stored from the original interception. If they match, the oracle refuses with an error. The point of blinding is to produce a numerically distinct ciphertext (c * c_a mod n) that the equality check misses but that still encodes the original plaintext information.

   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 2

   Multiply and decrypt

   Observation

   I noticed that multiplying c by c_a (Enc(2)) produces a ciphertext that is numerically distinct from the blocked c but decrypts to 2 * password by the homomorphic property, which suggested submitting this blinded value to the D endpoint and then dividing the result by 2 to recover the original password.

   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 oracle expects the ciphertext as a decimal integer string when receiving input for decryption. Sending a hex-prefixed string (e.g. '0x...') or raw bytes will be parsed incorrectly on the server side, producing a decrypt error or garbage output. The pwntools script uses str(c_a * c).encode() explicitly to produce a plain decimal string.

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

   Because the blinding factor is exactly 2, the decrypted blinded plaintext (2 * password) is always an even integer in the mathematical sense - not a residue that wraps around mod n. Plain integer division (//) recovers password exactly. Using the modular inverse instead would multiply by a large number mod n and produce a completely wrong result.

   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 3

   Use the recovered password

   Observation

   I noticed that secret.enc was described as an AES-encrypted message and that the RSA oracle was used only to protect the symmetric password, which suggested the standard hybrid-encryption pattern where openssl enc -aes-256-cbc -d decrypts the bulk file once we supply the recovered plaintext 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.

   The password recovered from the blinding attack is a raw integer derived from the decrypted hex response. Passing the raw integer as a CLI -pass argument will fail because OpenSSL expects the password in the same encoding that was used during encryption (typically a human-readable ASCII string derived from the bytes). Print the integer as bytes first (password.to_bytes(...).decode()) and enter that string at the interactive prompt instead.

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

   The challenge uses RSA only to protect the symmetric key (the password). The actual file secret.enc is AES-256-CBC encrypted, not RSA encrypted - this is the hybrid encryption pattern. Using rsautl on secret.enc will fail because the file format is an OpenSSL symmetric envelope (magic header, salt, ciphertext), not a raw RSA ciphertext 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.