No Padding, No Problem picoCTF 2021 Solution

Description

1. Step 1Collect n, e, and c from the oracle

   Observation

   The title says no padding and the challenge describes a decryption oracle, which means textbook RSA with no OAEP. The server's only restriction is refusing to decrypt the exact ciphertext c, so collect n, e, and c before probing that limit.

   Connect to the service. It prints the public key (n, e) and the encrypted flag ciphertext c. Copy these values. The oracle also allows you to decrypt any ciphertext - except c itself.

   Learn more

   A decryption oracle is a service that decrypts ciphertexts on demand. Real-world examples include padding oracle attacks on TLS and RSA PKCS#1 v1.5. The restriction here - refusing to decrypt the target ciphertext directly - is a byte-equality check, not a meaningful information-flow control. RSA's multiplicative homomorphism lets us submit a ciphertext that is not byte-equal to c but whose plaintext is a known function of the flag.

   Before designing the full attack, run a sanity check: send any ciphertext you cooked up (e.g., pow(2, e, n)) and confirm the oracle returns its plaintext. As long as the oracle accepts anything other than the literal target c, the attack works.

2. Step 2Blind the ciphertext using RSA homomorphism

   Observation

   The oracle accepts any ciphertext except the literal bytes of c. RSA's multiplicative homomorphism turns c into a different ciphertext the oracle will decrypt, and the result is a known multiple of the plaintext.

   RSA is multiplicatively homomorphic: Enc(a) * Enc(b) mod n = Enc(a*b) mod n. Encrypt 2 using the public key to get c2 = pow(2,e,n), then compute c_new = c * c2 % n. The oracle will decrypt c_new (it is not the original c), returning 2*m mod n.

   python

   python3 << 'EOF'
   n = <n>
   e = <e>
   c = <c>
   
   # Blind: multiply ciphertext by encryption of 2
   c2 = pow(2, e, n)
   c_new = (c * c2) % n
   print("Submit this to the oracle:", c_new)
   EOF

   Copied!

   Expected output

   picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_...}

   What didn't work first

   Tried: Submit c_new = c + pow(2, e, n) % n (adding ciphertexts instead of multiplying).

   RSA is multiplicatively homomorphic, not additively. Adding ciphertexts corresponds to no meaningful plaintext operation, so the oracle decrypts the sum to a random-looking integer. Only ciphertext multiplication maps cleanly onto plaintext multiplication, which is why the blinded value multiplies c by 2 raised to e, mod n.

   Tried: Skip the % n when computing c_new = c * c2 without reducing modulo n.

   The reduction is not mathematically required: modular exponentiation reduces its own base, so the unreduced product decrypts to the same 2*m mod n. Reduce anyway because the oracle takes a number as text and a service that range-checks or length-limits its input will reject a value larger than the modulus, and because keeping every intermediate below n is what makes the arithmetic auditable.

   Learn more

   Multiplicative homomorphism, proven. RSA encryption of an integer a is just modular exponentiation: Enc(a) = a^e mod n. Multiplying two ciphertexts gives:

   Enc(x) * Enc(y)  =  (x^e mod n) * (y^e mod n)
                    =  (x^e * y^e) mod n        # multiplication distributes over mod
                    =  ((x * y)^e) mod n        # because a^e * b^e = (a*b)^e
                    =  Enc(x * y)

   So multiplying ciphertexts multiplies plaintexts. This is a property, not a feature - in textbook RSA you cannot turn it off. To blind the target ciphertext c (decrypts to flag m):

   Choose r = 2 (any value coprime to n works).
   c2 = Enc(2) = 2^e mod n
   c_new = (c * c2) mod n
         = (m^e * 2^e) mod n
         = (2*m)^e mod n
         = Enc(2*m)
   
   The oracle decrypts c_new (which is not c byte-for-byte)
   and returns 2*m mod n.

   Worked tiny example. Take p = 11, q = 13, n = 143, e = 7, d = 103, plaintext m = 5:

   c = 5^7 mod 143 = 47
   c2 = 2^7 mod 143 = 128
   c_new = (47 * 128) mod 143 = 6016 mod 143 = 10
   
   Oracle decrypts: 10^103 mod 143 = 10
   Check: 2*5 = 10  ✓
   Recover m: 10 * inverse(2, 143) mod 143
     inverse(2, 143): 2*72 = 144 = 143 + 1, so inverse = 72
     10 * 72 mod 143 = 720 mod 143 = 5  ✓

   Why oracle filters fail. The defender's only check is "is the submitted ciphertext byte-equal to c?" Multiplying by Enc(2) changes every byte, so the filter passes. Variants: Enc(3), Enc(arbitrary r) - any non-zero r coprime to n works. This is identical to the defensive technique RSA blinding: a server multiplies its private-key operation by r^e, decrypts, then divides by r to defeat timing attacks. Same math, opposite side of the table.

3. Step 3Submit to oracle and divide by 2 to recover m

   Observation

   The oracle returns twice the plaintext, reduced mod n, rather than the plaintext itself. Multiplying by the modular inverse of 2 mod n strips the blinding factor and leaves the original integer.

   Paste c_new into the oracle. It returns 2*m mod n. Divide by 2 modulo n using the modular inverse: m = (2*m) * pow(2, -1, n) % n. Convert the integer to bytes to read the flag.

   python

   python3 << 'EOF'
   from Crypto.Util.number import long_to_bytes
   
   n = <n>
   two_m = <oracle_response>  # oracle's decryption of c_new
   
   m = (two_m * pow(2, -1, n)) % n
   print(long_to_bytes(m).decode())
   EOF

   Copied!

   What didn't work first

   Tried: Compute m = two_m // 2 (integer floor division instead of modular inverse).

   For this challenge floor division happens to work, because the flag is only a few hundred bits while n is 1024 or 2048, so 2*m never exceeds n and no reduction takes place. That makes it right by luck rather than by construction: the oracle returns 2*m mod n, and the moment twice the plaintext does exceed n you would be halving a reduced residue instead of the true product. Multiply by the modular inverse of 2 instead, which undoes the reduction correctly.

   Tried: Call two_m.to_bytes(...).decode() directly on the oracle response without first computing m.

   The oracle returns 2*m mod n, not m. Decoding that integer to bytes gives a garbled string that does not start with picoCTF{. The modular inverse step is required to peel off the blinding factor before the integer-to-bytes conversion.

   Learn more

   Why 2^(-1) mod n exists. The modular inverse of a mod n exists iff gcd(a, n) = 1. For RSA, n = p*q with p, q distinct odd primes, so gcd(2, p*q) = 1 always - 2 shares no factor with either prime. Bezout's identity then guarantees integers u, v with 2u + nv = 1, and u mod n is the inverse. Python computes it via pow(2, -1, n) (3.8+).

   The full recovery in one line. Given two_m = (2*m) mod n:

   m = (two_m * pow(2, -1, n)) mod n
   
   Why this is correct:
      m = (2*m * 2^(-1)) mod n
        = m * (2 * 2^(-1)) mod n
        = m * 1 mod n
        = m

   Going from integer back to bytes. RSA encrypts integers, but the flag is text. The encoder packed bytes as a big-endian integer: m = b[0]*256^(L-1) + b[1]*256^(L-2) + ... + b[L-1]. long_to_bytes(m) from Crypto.Util.number reverses this. Note the gotcha: long_to_bytes returns the minimal byte length, so a plaintext that starts with a null byte (0x00) silently loses that leading zero. If the decoded text looks one byte short or fails to start with picoCTF, manually prepend b'\\x00' until the length matches the expected modulus byte width.

   The defense: OAEP padding. Optimal Asymmetric Encryption Padding randomizes the message before encryption, so the same plaintext encrypts to different ciphertexts every time. It also enforces a non-malleability property: any ciphertext modification (including multiplication by another ciphertext) produces an invalid OAEP-padded plaintext that the decryption routine rejects. This kills the blinding attack entirely. Modern RSA must always use OAEP - never use textbook RSA for confidentiality.

Flag

RSA is multiplicatively homomorphic - multiplying ciphertexts multiplies plaintexts. Blind the target ciphertext to get the oracle to decrypt it.