No Padding, No Problem picoCTF 2021 Solution

Description

1. Step 1Collect n, e, and c from the oracle
   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
   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!
   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
   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!
   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.

Alternate Solution

Flag

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