CHC Challenges 2019

RSA Challenge

Category: Crypto

Posted on February 18, 2019

Textbook RSA Decryption Oracle.md

Textbook RSA Decryption Oracle

Original Challenge can be found here

What we are given is:

  1. A base64-encoded ciphertext
  2. An RSA public key
  3. A decryption oracle

The first thing to try is clearly to send the provided ciphertext to the decryption oracle:

$ echo bXqnLSa8E8KbD3A/isI7++FNAFTXH6nF184TKUaQBePapvPfcnlZ782mDuMwL4E7Be57HcGBOFMIU/3ALuxq2+cUlyMK07jEU1vdJDbUgXbc3wEbJtWHbs1Y3DJb+DCi9PiDZplE2G1nAXkQQWTuv2+dCv6pUFRgWeocQty8y/s= |  nc chc.cs.cornell.edu 1352

We're not giving away the flag that easy!

So that didn’t work. But trying a different ciphertext (or just looking at the code) confirms that the oracle will decrypt any other ciphertext.

$ cat  <(head -c 118 /dev/zero) <(echo -n -e "testing...") |
openssl rsautl -encrypt -raw -pubin -inkey key.pub |
openssl base64  -A | xargs echo | nc chc.cs.cornell.edu 1352

testing...

This should immediately set off alarms, since clearly the decryption oracle is not doing any sort of padding validation. Textbook RSA is very insecure.

Let’s look at what we are given, mathematically.

Let m be the flag, encoded as an integer in Z/nZ.

We know:

  1. c = m^e mod n
  2. e = 65537
  3. A function f(x) = x^(1/e) that works for any x other than c.

The key observation is that textbook RSA is homomorphic.
In particular, m1^e * m2^e = (m1 * m2)^e mod n

Thus, we can send the server a new ciphertext, 2^e*c and the server will give back f(2^e*c) = f(2^e*m^e) = ((2*m)^e)^(1/e) = 2*m.

Then it is just a matter of dividing by 2. Remember that this is division in the ring Z/nZ, so we need to do a modular inversion and multiplication, not just integer division.

The whole code can be summed up as

#!/usr/bin/env python3
from base64 import b64encode, b64decode
from Crypto.PublicKey import RSA
import gmpy2
import socket

# Decode ciphertext into an integer
ctxt = b64decode("bXqnLSa8E8KbD3A/isI7++FNAFTXH6nF184TKUaQBePapvPfcnlZ782mDuMwL4E7Be57HcGBOFMIU/3ALuxq2+cUlyMK07jEU1vdJDbUgXbc3wEbJtWHbs1Y3DJb+DCi9PiDZplE2G1nAXkQQWTuv2+dCv6pUFRgWeocQty8y/s=")
c = int.from_bytes(ctxt, 'big')

# Extract public key parameters
with open('key.pub', 'r') as f:
    key = RSA.importKey(f.read())
    n = key.n
    e = key.e

# Construct (2*m)^e
exploit_ctxt = pow(2, e, n)*c % n

# Send to server
s = socket.create_connection(('chc.cs.cornell.edu', 1352))
s.sendall(b64encode(exploit_ctxt.to_bytes(128, 'big'))+b'\n')
r = int.from_bytes(s.recv(128), 'big')

# Divide by two to extract the key
m = int(gmpy2.invert(2, n))*r % n
print(m.to_bytes(128, 'big'))

Copyright © Cornell Hacking Club 2021