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!'
Esquema Shamir Secret Sharing
El servidor está tratando de obtener un secreto de un esquema Shamir Secret Sharing. En este criptosistema, se genera un polinomio $P$. Este reto calcula un total de 7 coeficientes aleatorios en módulo $p$ (es decir, estamos trabajando en $\mathbb{F}_p$, o $\mathrm{GF}(p)$). Después de eso, se generan un total de 12 shares aleatorios, que son solo pares como $\big(i, P(i)\big)$, donde $i$ 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
$$ P(i) = a_7 i^7 + \dots + a_2 i^2 + a_1 i + s \mod{p} $$
Y al menos 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\} $$
Podemos hallar los coeficientes $s, a_1, \dots, a_7$ con un sistema de ecuaciones (o una ecuación matricial):
$$ \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} $$
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 $s$ debe cumplir que $2^s \equiv 1 \pmod{n}$, donde $n$ es RSA_n de params.txt.
Dada la escasa cantidad de información que tenemos, debemos forzar que $s = 0$, de manera que $2^s = 1$ y pasamos la comprobación. Para eso, podemos hacer que el servidor resuelva esta ecuación matricial:
$$ \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} $$
Entonces, enviaremos al servidor el share $(0, 0)$, y funcionará porque el módulo galois de Python dice que $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
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.