Right Decision
6 minutes to read
We are given the Python source code of the server:
import random
import string
import Crypto.Util.number as number
import numpy as np
import json
import socketserver
import galois
from hashlib import md5
PORT = 31339
with open('params.txt') as f:
params = json.load(f)
p = params['galois_p']
k = params['k']
n = params['RSA_n']
gf = galois.GF(p,verify=False,primitive_element=2)
with open('votes.txt') as f:
votes = json.load(f)
with open('flag.txt') as f:
flag = f.read()
def check_secret(s):
#check if secret is real phi for public key n
return pow(2,s,n)==1
def parse_new_vote(data):
all_votes = votes.copy()
all_votes.append(json.loads(data))
#check if we have k true votes
true_votes = sum([v['vote'] for v in all_votes])
if true_votes<k:
return 'bad vote!'
#calculate Shamir's shared secret
matrix = [[ gf(vote['i'])**(k-j-1) for j in range(k)] for vote in all_votes]
values = [vote['value'] for vote in all_votes]
matrix = gf(matrix)
values = gf(values)
r = np.linalg.solve(matrix,values)
for_test = int(r[-1])
# ok, now check that secret is correct
if check_secret(for_test):
return flag
else:
return 'bad vote!'
class CheckHandler(socketserver.BaseRequestHandler):
def check_pow(self):
prefix = ''.join(random.choices(string.ascii_letters,k=10))
pow_size = 7 # 3.5 byte
hash_bytes = ''.join(random.choices('abcdef1234567890',k=pow_size))
self.request.sendall(("Welcome! Please provide proof of work. \nPrefix: "+prefix+"\nTarget hash starts with:"+hash_bytes+'\nEnter: ').encode('utf-8'))
response = self.request.recv(100).decode('utf-8').strip()
if md5((prefix+response).encode('utf-8')).hexdigest().startswith(hash_bytes):
self.request.sendall(b'Proof of work confirmed. Go on!\n\n')
return True
else:
self.request.sendall(b'Proof of work is bad. Bye!')
return False
def handle(self):
if not self.check_pow():
return
self.request.sendall(b'Present your vote: \n')
data = self.request.recv(10000).strip()
try:
resp = parse_new_vote(data)
except:
resp = 'bad vote!'
self.request.sendall(resp.encode('utf-8'))
if __name__ == '__main__':
server = socketserver.TCPServer(('0.0.0.0',PORT),CheckHandler)
server.serve_forever()
We also have a file called params.txt
:
{
"galois_p": 127565284730312646553375947539569963612271276691294919038907416228778295885089952093173530295471922692908242244691270727451374200759526569869002350751157383015664400638918501977660629515157731611428156095347144982827738475149294582300188035537706925404854054211627533159533475668296133391267035049519537737679813344822038401054924266596297699758214265058133863564732413127288172620441778571568962546897580938750395372813602044655552302706253347483100357925210368111147516631727520073230204482941050192384044837645689448019556921790323616986735989290473620939174442910621540803192860746865199650188951655452863376501469,
"RSA_n": 18141013871549177982603879826337829360672081233095023845052116131066815233112928848835168574431833802012934732570850891978945025167307606642366153675840027583109031851021883470562692973435322619556561826968374043994421750335061575009111417689557487654206088723261855198743677521550036290467882493641276068194522246562795662731208584508836914014511427666053293141751951371263648185119030495257660916898105585124171160171304695513105742935157996249980843458353189328555608042283381228194530517852196344161861739787918301531083130524479993092016085402580721130124868101594520481148725215077702413171316510371381790801607,
"k": 8
}
And the script generate_secrets.py
:
import random
import Crypto.Util.number as number
import numpy as np
import json
import sys
import galois
p = number.getPrime(2050)
f = galois.GF(p,verify=False,primitive_element=2)
k=8
num = 12
secret = sys.argv[1]
a = [random.randint(0,f.order) for _ in range(k-1)]
a.append(secret)
a = f(a)
def poly(a,x):
return np.sum([ a[i]*(x**(len(a)-i-1)) for i in range(len(a))])
i_s = [random.randint(0,f.order) for i in range(1,num+1,1)]
shared_secrets = [(i,poly(a,f(i))) for i in i_s]
print ('\n'.join( [ '{"i":%d,"value":%d}' %(s[0],int(s[1])) for s in shared_secrets ]))
We have another file called votes.txt
, but everything is REDACTED
:
[
{
"vote": true,
"i": REDACTED,
"value": REDACTED
},
{
"vote": true,
"i": REDACTED,
"value": REDACTED
},
{
"vote": true,
"i": REDACTED,
"value": REDACTED
},
{
"vote": true,
"i": REDACTED,
"value": REDACTED
},
{
"vote": true,
"i": REDACTED,
"value": REDACTED
},
{
"vote": true,
"i": REDACTED,
"value": REDACTED
},
{
"vote": true,
"i": REDACTED,
"value": REDACTED
}
]
Source code analysis
The server starts with a proof of work (which is totally unnecesary) and then allows us to add a new vote and validate it:
def handle(self):
if not self.check_pow():
return
self.request.sendall(b'Present your vote: \n')
data = self.request.recv(10000).strip()
try:
resp = parse_new_vote(data)
except:
resp = 'bad vote!'
self.request.sendall(resp.encode('utf-8'))
And this is parse_new_vote
:
def check_secret(s):
#check if secret is real phi for public key n
return pow(2,s,n)==1
def parse_new_vote(data):
all_votes = votes.copy()
all_votes.append(json.loads(data))
#check if we have k true votes
true_votes = sum([v['vote'] for v in all_votes])
if true_votes<k:
return 'bad vote!'
#calculate Shamir's shared secret
matrix = [[ gf(vote['i'])**(k-j-1) for j in range(k)] for vote in all_votes]
values = [vote['value'] for vote in all_votes]
matrix = gf(matrix)
values = gf(values)
r = np.linalg.solve(matrix,values)
for_test = int(r[-1])
# ok, now check that secret is correct
if check_secret(for_test):
return flag
else:
return 'bad vote!'
Shamir Secret Sharing scheme
The server is trying to obtain a secret from a Shamir Secret Sharing scheme. In this cryptosystem, a polynomial
The secret is usually encoded in the last coefficient of the polynomial (the independent term). Therefore, having a total of 8 shares would give us the ability to build a system of equations and solve it to find the 8 coefficients of the polynomial (7 random plus the secret).
So, in summary, given
And at least 8 shares:
We can solve for the coefficients
Solution
This time, the secret is not that important, since the server is trying to decode the secret using 7 shares stored in the server plus the share that we provide (the vote). However, we are not given the shares, and the secret RSA_n
from params.txt
.
Given the scarce amount of information we have, we must force that
So, we will send the server the share galois
module in Python says that
$ python3 -q
>>> import galois
>>>
>>> p = 127565284730312646553375947539569963612271276691294919038907416228778295885089952093173530295471922692908242244691270727451374200759526569869002350751157383015664400638918501977660629515157731611428156095347144982827738475149294582300188035537706925404854054211627533159533475668296133391267035049519537737679813344822038401054924266596297699758214265058133863564732413127288172620441778571568962546897580938750395372813602044655552302706253347483100357925210368111147516631727520073230204482941050192384044837645689448019556921790323616986735989290473620939174442910621540803192860746865199650188951655452863376501469
>>> gf = galois.GF(p, verify=False, primitive_element=2)
>>>
>>> gf(0) ** 0 == 1
True
So, after computing the proof of work, we simply need to send the share to the server and get the flag. This can be easily implemented in Python:
if __name__ == '__main__':
io = get_process()
io.sendlineafter(b'Enter: ', hash_pow(*parse_pow()).encode())
io.sendlineafter(b'Present your vote: ', b'{"vote":true,"i":0,"value":0}')
print(io.recvall().decode())
Flag
If we run the script, we will get the flag (depending on the proof of work):
$ python3 solve.py right-decision.ctfz.one 31339
[+] Opening connection to right-decision.ctfz.one on port 31339: Done
[+] Receiving all data: Done (37B)
[*] Closed connection to right-decision.ctfz.one port 31339
ctfzone{Sh4m1r_$h3m4_1s_g00d_Bu7_m3}
The full script can be found in here: solve.py
.