Posted on February 18, 2019
Original Challenge can be found here
What we are given is:
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.
m be the flag, encoded as an integer in
c = m^e mod n
e = 65537
f(x) = x^(1/e)that works for any
The key observation is that textbook RSA is homomorphic.
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'))