Right Decision

6 minutos de lectura

Se nos proporciona el código fuente en Python del servidor:

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()

También tenemos un archivo llamado params.txt:

{
    "galois_p": 127565284730312646553375947539569963612271276691294919038907416228778295885089952093173530295471922692908242244691270727451374200759526569869002350751157383015664400638918501977660629515157731611428156095347144982827738475149294582300188035537706925404854054211627533159533475668296133391267035049519537737679813344822038401054924266596297699758214265058133863564732413127288172620441778571568962546897580938750395372813602044655552302706253347483100357925210368111147516631727520073230204482941050192384044837645689448019556921790323616986735989290473620939174442910621540803192860746865199650188951655452863376501469,
    "RSA_n": 18141013871549177982603879826337829360672081233095023845052116131066815233112928848835168574431833802012934732570850891978945025167307606642366153675840027583109031851021883470562692973435322619556561826968374043994421750335061575009111417689557487654206088723261855198743677521550036290467882493641276068194522246562795662731208584508836914014511427666053293141751951371263648185119030495257660916898105585124171160171304695513105742935157996249980843458353189328555608042283381228194530517852196344161861739787918301531083130524479993092016085402580721130124868101594520481148725215077702413171316510371381790801607,
    "k": 8
}

Y el 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 ]))

Tenemos otro archivo llamado votes.txt, pero todo aparece como 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
    }
]

Análisis del código fuente

El servidor comienza con una proof of work (que es totalmente innecesaria) y luego nos permite agregar un nuevo voto y validarlo:

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

Esta es la función 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!'

El servidor está tratando de obtener un secreto de un esquema Shamir Secret Sharing. En este criptosistema, se genera un polinomio . Este reto calcula un total de 7 coeficientes aleatorios en módulo (es decir, estamos trabajando en , o ). Después de eso, se generan un total de 12 shares aleatorios, que son solo pares como , donde es aleatorio.

El secreto generalmente se codifica en el último coeficiente del polinomio (el término independiente). Por lo tanto, tener un total de 8 shares nos daría la capacidad de construir un sistema de ecuaciones y resolverlo para encontrar los 8 coeficientes del polinomio (7 aleatorios más el secreto).

En resumen, dado

Y al menos 8 shares:

Podemos hallar los coeficientes con un sistema de ecuaciones (o una ecuación matricial):

Solución

Esta vez, el secreto no es tan importante, ya que el servidor está tratando de decodificar el secreto usando 7 shares almacenados en el servidor más el share que proporcionamos (el voto). Sin embargo, no se nos dan los shares, y el secreto debe cumplir que , donde es RSA_n de params.txt.

Dada la escasa cantidad de información que tenemos, debemos forzar que , de manera que y pasamos la comprobación. Para eso, podemos hacer que el servidor resuelva esta ecuación matricial:

Entonces, enviaremos al servidor el share , y funcionará porque el módulo galois de Python dice que :

$ python3 -q
>>> import galois
>>>
>>> p = 127565284730312646553375947539569963612271276691294919038907416228778295885089952093173530295471922692908242244691270727451374200759526569869002350751157383015664400638918501977660629515157731611428156095347144982827738475149294582300188035537706925404854054211627533159533475668296133391267035049519537737679813344822038401054924266596297699758214265058133863564732413127288172620441778571568962546897580938750395372813602044655552302706253347483100357925210368111147516631727520073230204482941050192384044837645689448019556921790323616986735989290473620939174442910621540803192860746865199650188951655452863376501469
>>> gf = galois.GF(p, verify=False, primitive_element=2)
>>>
>>> gf(0) ** 0 == 1
True

Entonces, después de calcular la proof of work simplemente necesitamos enviar el share al servidor y obtener la flag. Esto se puede implementar fácilmente en 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

Si ejecutamos el script, obtendremos la flag (dependiendo de la 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}

El script completo se puede encontrar aquí: solve.py.

Análisis del código fuente

Esquema Shamir Secret Sharing

Solución

Flag