The VolgaCTF 2019 Qualifier (ctftime.org) took place from 29/03/2019, 15:00 UTC to 31/03/2019 15:00 UTC.
There has been a really interesting RSA crypto challenge called Blind, which I would like to share with you in this writeup.
The article is divided into the following sections:
→ Challenge description
→ What does the script do?
→ Blind RSA Signature
→ Retrieving the Flag
Blind (200 pts)
Challenge description
The challenge description provides the ip/port of the CTF server running the challenge as well as a python script called server.py, which runs on the server:
So let’s have a look at the python script:
#!/usr/bin/env python
from __future__ import print_function
import os
import sys
import shlex
import subprocess
from private_key import d
"""
Utils
"""
def run_cmd(cmd):
try:
args = shlex.split(cmd)
return subprocess.check_output(args)
except Exception as ex:
return str(ex)
"""
Signature
"""
class RSA:
def __init__(self, e, d, n):
self.e = e
self.d = d
self.n = n
def sign(self, message):
message = int(message.encode('hex'), 16)
return pow(message, self.d, self.n)
def verify(self, message, signature):
message = int(message.encode('hex'), 16)
verify = pow(signature, self.e, self.n)
return message == verify
"""
Keys
"""
n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537
"""
Communication utils
"""
def read_message():
return sys.stdin.readline()
def send_message(message):
sys.stdout.write('{0}\r\n'.format(message))
sys.stdout.flush()
def eprint(*args, **kwargs):
print(*args, file=sys.stderr, **kwargs)
"""
Main
"""
def check_cmd_signatures(signature):
cmd1 = 'exit'
cmd2 = 'leave'
assert (signature.verify(cmd1, signature.sign(cmd1)))
assert (signature.verify(cmd2, signature.sign(cmd2)))
class SignatureException(Exception):
pass
if __name__ == '__main__':
signature = RSA(e, d, n)
check_cmd_signatures(signature)
try:
while True:
send_message('Enter your command:')
message = read_message().strip()
(sgn, cmd_exp) = message.split(' ', 1)
eprint('Accepting command {0}'.format(cmd_exp))
eprint('Accepting command signature: {0}'.format(sgn))
cmd_l = shlex.split(cmd_exp)
cmd = cmd_l[0]
if cmd == 'ls' or cmd == 'dir':
ret_str = run_cmd(cmd_exp)
send_message(ret_str)
elif cmd == 'cd':
try:
sgn = int(sgn)
if not signature.verify(cmd_exp, sgn):
raise SignatureException('Signature verification check failed')
os.chdir(cmd_l[1])
send_message('')
except Exception as ex:
send_message(str(ex))
elif cmd == 'cat':
try:
sgn = int(sgn)
if not signature.verify(cmd_exp, sgn):
raise SignatureException('Signature verification check failed')
if len(cmd_l) == 1:
raise Exception('Nothing to cat')
ret_str = run_cmd(cmd_exp)
send_message(ret_str)
except Exception as ex:
send_message(str(ex))
elif cmd == 'sign':
try:
send_message('Enter your command to sign:')
message = read_message().strip()
message = message.decode('base64')
cmd_l = shlex.split(message)
sign_cmd = cmd_l[0]
if sign_cmd not in ['cat', 'cd']:
sgn = signature.sign(sign_cmd)
send_message(str(sgn))
else:
send_message('Invalid command')
except Exception as ex:
send_message(str(ex))
elif cmd == 'exit' or cmd == 'leave':
sgn = int(sgn)
if not signature.verify(cmd_exp, sgn):
raise SignatureException('Signature verification check failed')
break
else:
send_message('Unknown command {0}'.format(cmd))
break
except SignatureException as ex:
send_message(str(ex))
eprint(str(ex))
except Exception as ex:
send_message('Something must have gone very, very wrong...')
eprint(str(ex))
finally:
pass
What does the script do?
The script reads a line from stdin and splits this line by spaces storing the first word in sgn and all following words in cmd_exp:
send_message('Enter your command:')
message = read_message().strip()
(sgn, cmd_exp) = message.split(' ', 1)
The value stored in cmd_exp is split again, this time by calling shlex.split(cmd_exp). This function splits the given string using a shell-like syntax (documentation shlex). The first element of the result is stored in cmd:
cmd_l = shlex.split(cmd_exp)
cmd = cmd_l[0]
Depending on the value of cmd one of the following if/elif blocks is run. If cmd is ls or dir, the command stored in cmd_exp is directly executed and the result displayed:
if cmd == 'ls' or cmd == 'dir':
ret_str = run_cmd(cmd_exp)
send_message(ret_str)
The function run_cmd calls subprocess.check_output(...) to execute the command:
def run_cmd(cmd):
try:
args = shlex.split(cmd)
return subprocess.check_output(args)
except Exception as ex:
return str(ex)
This means that we can run ls or dir without minding the value of sgn (though we must provide a value, so let’s just take 1 for now):
root@kali:~# nc blind.q.2019.volgactf.ru 7070
Enter your command:
1 ls
flag
private_key.py
server.py
As we can see, the flag seems to be right in front of us. We only have to run cat flag. So let’s have a look at the cmd == 'cat' elif block:
elif cmd == 'cat':
try:
sgn = int(sgn)
if not signature.verify(cmd_exp, sgn):
raise SignatureException('Signature verification check failed')
if len(cmd_l) == 1:
raise Exception('Nothing to cat')
ret_str = run_cmd(cmd_exp)
send_message(ret_str)
except Exception as ex:
send_message(str(ex))
Now the previously mentioned value of sgn comes into play. The variable is passed to the function signature.verify(...) along with the variable cmd_exp. If the function returns false (not), a SignatureException is raised and the command is not executed. In order to understand what the function signature.verify(...) does, let’s have a look at the whole RSA class:
"""
Signature
"""
class RSA:
def __init__(self, e, d, n):
self.e = e
self.d = d
self.n = n
def sign(self, message):
message = int(message.encode('hex'), 16)
return pow(message, self.d, self.n)
def verify(self, message, signature):
message = int(message.encode('hex'), 16)
verify = pow(signature, self.e, self.n)
return message == verify
As the comment above the class indicates, the class implements a simple RSA message signing. In order to sign a message, it is converted to an integer and raised to the power of d modulo n: sign = message^d % n. d is the private key we have already seen in the above output of ls, but haven’t access to (from private_key import d). To verify the signature of a message, the signature is raised to the power of e modulo n (verify = sign^e % n) and then compared to the original message. If both values match, the signature is correct (also see wikipedia). The public key (n and e) are part of the source code and we thus know those values:
"""
Keys
"""
n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537
What does this mean for the command cat flag, we would like to run? Well, we need the correct signature for this command. Otherwise the signature check will fail and the command is not executed. Looking a few lines ahead there actually is an elif block to sign commands:
elif cmd == 'sign':
try:
send_message('Enter your command to sign:')
message = read_message().strip()
message = message.decode('base64')
cmd_l = shlex.split(message)
sign_cmd = cmd_l[0]
if sign_cmd not in ['cat', 'cd']:
sgn = signature.sign(sign_cmd)
send_message(str(sgn))
else:
send_message('Invalid command')
except Exception as ex:
send_message(str(ex))
So we essentially can sign commands, but if the command contains cat or cd, we only get the message Invalid command (notice that the command, we want to sign, needs to be base64 encoded):
root@kali:~# echo -ne 'cat flag' | base64
Y2F0IGZsYWc=
root@kali:~# nc blind.q.2019.volgactf.ru 7070
Enter your command:
1 sign
Enter your command to sign:
Y2F0IGZsYWc=
Invalid command
Thus we need to find another way to sign the desired command cat flag.
Blind RSA Signature
When googling for possible attack surfaces in conjunction with the challenge’s title (Blind), I always immediately stumbled upon this wikipedia article about Blind RSA Signatures. You can read the mathematical details in the article, but the idea is quite straightforward:
- We modify the message we want to sign based upon an additional value
r(the blinding factor) - We let the server sign the modified message (forethought: not containing “
cat“) - We use
rto calculate the signature of the original message from the signature we received
In order to understand this technique let’s have a look at a quick example.
We choose the following values for n, e and d:
n = 143 e = 23 d = 47
Now we want to sign the message 7:
m = 7
The signature is calculated with the following equation:
s = m^d % n s = 7^47 % 143 = 28
Thus the signature of the original message is 28.
Now let’s suppose we can’t make the server sign a message containing 7 (or cat), but we still want to get the signature value. In order to achieve this, we choose a blinding factor r:
r = 3
This value is raised to the power of e and multiplied by the original message m (modulo n):
m1 = m*r^e % n m1 = 7*3^23 % 143 = 24
Now the modified message m1 does not containing the prohibited value (7) anymore. Thus we can make the server sign this message resulting in the signature s1:
s1 = m1^d % n s1 = 24^47 % 143 = 84
In order to restore the signature of the original message (s) from s1 we need to multiply it by r_inverse (to calculate the inverse, we can for example use gmpy for python: import gmpy; gmpy.invert(3,143) = 48):
s = s1*r_inverse % n s = 84*48 % 143 = 28
That’s it! We successfully got the signature for the original message without the server actually signing it.
Retrieving the Flag
Before implementing this technique for our specific use case, we have to deal with a little pitfall. The message, which is signed by the server, is passed to shlex.split(...) before actually being signed:
...
message = message.decode('base64')
cmd_l = shlex.split(message)
sign_cmd = cmd_l[0]
if sign_cmd not in ['cat', 'cd']:
sgn = signature.sign(sign_cmd)
This means that in order to sign an arbitrary message, we have to make sure that the message is not split apart by shlex.split(...). Otherwise only the first part of our message is signed.
Luckily we can choose almost any value for r (it only has to fulfill the condition gcd(r,n) = 1, which is the case for quite a lot of values since n is the product of two big primes).
In order to find a suitable value for r I wrote the following python script, which simply iterates over different values for r and checks if the modified message and the return value of a call shlex.split(...) are the same:
#!/usr/bin/env python
import shlex
n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537
m = int('cat flag'.encode('hex'), 16)
r = 1
while True:
m1 = (m*r**e)%n
m1 = hex(m1)[2:-1] # cut leading '0x' and trailing 'L'
if (len(m1)%2 == 1): m1 = '0' + m1 # adjust padding
m1 = m1.decode('hex')
try:
res = shlex.split(m1)[0]
except: pass
if (res == m1):
print('r = ' + str(r))
quit()
r += 1
Running the script yields r = 6631 as a suitable value:
root@kali:~# ./getBlindingFactor.py
r = 6631
At last we can implement the final script to retrieve the flag. I annotated the source code with comments, which hopefully makes things clear:
#!/usr/bin/env python
from pwn import *
import gmpy
n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537
m = int('cat flag'.encode('hex'), 16)
# suitable blinding factor
r = 6631
# calculate modified message m1
m1 = (m*r**e)%n
m1 = hex(m1)[2:] # cut leading '0x'
if (len(m1)%2 == 1): m1 = '0' + m1 # adjust padding
m1 = m1.decode('hex').encode('base64').replace('\n','') # encode
# connect to ctf server
p = remote('blind.q.2019.volgactf.ru', 7070)
p.recvuntil('Enter your command')
# sign modified message m1
p.sendline('1 sign')
p.recvuntil('Enter your command to sign:')
p.sendline(m1)
# receive signature s1
p.recvline()
resp = p.recvline()
s1 = int(resp)
# calculate signature s from s1 and r
s = s1*int(gmpy.invert(r,n))%n
# send command 'cat flag' with appropriate signature
p.sendline(str(s) + ' cat flag')
p.interactive()
Running the script yields the flag:
root@kali:~# ./catFlag.py
[+] Opening connection to blind.q.2019.volgactf.ru on port 7070: Done
[*] Switching to interactive mode
Enter your command:
VolgaCTF{B1ind_y0ur_tru3_int3nti0n5}
The flag is VolgaCTF{B1ind_y0ur_tru3_int3nti0n5}.
Thanks for reading the article 🙂
Nicely done, and loved the explanation with simple numbers. Keep up the good work, and keep them coming 🙂
Thank you 🙂
well done!
Thank you very much! The explaination is easy to understand for me. 😀
Great to hear that! Thanks
Thank you very much! The explanation is very clear and the example with small numbers is very helpful for me as a beginner.
you are the best! can you prepare video tutorials about exploit development?
Thank you very much!
That’s actually on my todo list 🙂
Thanks for the article!
The explaination is clear for me 🙂