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!'

The server is trying to obtain a secret from a Shamir Secret Sharing scheme. In this cryptosystem, a polynomial $P$ is generated. This challenge computes a total of 7 random coefficients $\mod{p}$ (that is, we are working in $\mathbb{F}_p$, or $\mathrm{GF}(p)$). After that, a total of 12 random shares are generated, which are just pairs like $\big(i, P(i)\big)$, for $i$ random.

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

$$ P(i) = a_7 i^7 + \dots + a_2 i^2 + a_1 i + s \mod{p} $$

And at least 8 shares:

$$ \Big\{\big(i_0, P(i_0)\big), \big(i_1, P(i_1)\big), \dots, \big(i_7, P(i_7)\big)\Big\} $$

We can solve for the coefficients $s, a_1, \dots, a_7$ with a system of equations (or a matrix equation):

$$ \begin{pmatrix} i_0^7 & \dots & i_0^2 & i_0 & 1 \\ i_1^7 & \dots & i_1^2 & i_1 & 1 \\ \vdots & \ddots & \vdots & \vdots & \vdots \\ i_7^7 & \dots & i_7^2 & i_7 & 1 \end{pmatrix} \cdot \begin{pmatrix} a_7 \\ \vdots \\ a_1 \\ s \end{pmatrix} = \begin{pmatrix} P(i_0) \\ P(i_1) \\ \vdots \\ P(i_7) \end{pmatrix} $$

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 $s$ must satisfy that $2^s \equiv 1 \pmod{n}$, where $n$ is RSA_n from params.txt.

Given the scarce amount of information we have, we must force that $s = 0$, so that $2^s = 1$ and we pass the check. For that, we can trick the server to solve this matrix equation:

$$ \begin{pmatrix} i_0^7 & \dots & i_0^2 & i_0 & 1 \\ i_1^7 & \dots & i_1^2 & i_1 & 1 \\ \vdots & \ddots & \vdots & \vdots & \vdots \\ i_6^7 & \dots & i_6^2 & i_6 & 1 \\ 0 & \dots & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} a_7 \\ \vdots \\ a_1 \\ s \end{pmatrix} = \begin{pmatrix} P(i_0) \\ P(i_1) \\ \vdots \\ P(i_6) \\ 0 \end{pmatrix} $$

So, we will send the server the share $(0, 0)$, and it will work because galois module in Python says that $0^0 \mod{p} = 1$:

$ 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.