No Padding, No Problem picoCTF 2021 Solution

Description

1. Step 1

   Collect n, e, and c from the oracle

   Observation

   I noticed the challenge title said 'no padding' and described a decryption oracle, which indicated textbook RSA with no OAEP, and that the server's only restriction was refusing to decrypt the exact ciphertext c, so gathering n, e, and c was the necessary first step before probing that restriction.

   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 2

   Blind the ciphertext using RSA homomorphism

   Observation

   I noticed the oracle accepts any ciphertext except the literal bytes of c, which suggested using RSA's multiplicative homomorphism to transform c into a new ciphertext c_new that the oracle would decrypt, yielding a known multiple of the plaintext flag.

   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 does not correspond to any meaningful plaintext operation - the oracle decrypts the sum to a random-looking integer, not 2*m. Only multiplication of ciphertexts maps cleanly to multiplication of plaintexts, so the blinded value must be c_new = (c * pow(2, e, n)) % n.

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

   Without the mod n reduction, c_new is a huge multi-thousand-bit integer that is not a valid RSA ciphertext in [0, n). The oracle will reject it or return an error because RSA operations require the input to be in the group Z_n. The reduction modulo n is mandatory to keep the blinded ciphertext in the correct range.

   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 3

   Submit to oracle and divide by 2 to recover m

   Observation

   I noticed the oracle returned 2*m mod n rather than m directly, which meant I needed to multiply by the modular inverse of 2 mod n using pow(2, -1, n) to strip the blinding factor and recover the original plaintext 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).

   two_m is 2*m reduced mod n, not the literal integer 2*m. If 2*m > n (which it almost always is for a 1024-bit or 2048-bit modulus), integer division by 2 gives the wrong answer entirely - it divides the reduced residue, not the true product. The correct operation is multiplication by the modular inverse of 2 mod n, which undoes the mod-n reduction properly.

   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.