Vitrium Stash
10 minutos de lectura
Se nos proporciona el código fuente en Python del servidor:
from Crypto.Util.number import *
from secrets import *
import json
"""
from Crypto.PublicKey import DSA
k = DSA.generate(2048)
print(f"{k.p = }")
print(f"{k.q = }")
print(f"{k.g = }")
"""
p = 30514860220781649196505378618677588344627509796136052197766721133333403517227804826248671926331671978511695325934422209350872533631963158343821543243314354301612941382823755283391175569282500778759917825290265500008435125458284371701669393617263164707568562478942069967845682300866897274415749964510071038555145487346022921591488265881313448995313340365972250251431925090356830155846705412769705029295847471355919584592321591959772488755986181054597974081870037624260173234561447688627353479361867003340196122160639547860024025674714107946196423198018724048310862485718766310003158603549746994074302705926658218700843
q = 26189572440233739420990528170531051459310363621928135990243626537967
g = 6111748161621056558453263711027460170929636824002846224800107291166700007147256826554286465237732729099376511591848799483754962591483370638607627034808201246023891469880792589537431156477847873086973414247654773443349132863425799271140168302068820170758172107172379842519843597077356839020025609506792115532019927453283319270046204956352057936972814681479252626295814756888943630138110534869191473166355939365725603055249365076889191708484425425599800051451167006426087674425090967640170968963795028092131692666710522291627118158125917935888441403300632869010691598781782043810771106247022549721544793735832383283054
x = randbelow(p)
y = pow(g, x, p)
def sign(message):
m = bytes_to_long(message)
k = randbelow(p)
r = pow(g, k, p) % q
s = (inverse(k, q) * (m + x*r)) % q
return r, s
def verify(message, r, s):
assert 0 < r < q
assert 0 < s < q
m = bytes_to_long(message)
w = pow(s, -1, q)
u1 = (m * w) % q
u2 = (r * w) % q
v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
return r == v
menu = """Vitalium Storage Panel Menu:
[0] Get public key of server
[1] Make an account
[2] View coordinates of vitalium stashes
[3] Exit
"""
def panel():
while True:
try:
print(menu)
option = int(input("Enter option > "))
if option == 0:
print(json.dumps({
'p': p,
'q': q,
'g': g,
'y': y
}))
elif option == 1:
username = input("Enter username > ")
message = json.dumps({"username": username, "admin": False})
r, s = sign(message.encode())
print(json.dumps({
'r': r,
's': s,
'message': message
}))
elif option == 2:
r = int(input("r > "))
s = int(input("s > "))
message = input("message > ").encode()
if verify(message, r, s):
data = json.loads(message)
if data["admin"]:
print(f"Hello admin! Here are the coordinates to your vitalium stash: {open('flag.txt').read()}")
else:
print(f"You must be admin to see the coordinates.")
else:
print(f"Signature Invalid. Breach attempt detected, exiting...")
exit(-1)
else:
print("Exiting")
exit(0)
except Exception as e:
print("An error occurred, exiting", e)
exit(-1)
panel()
El código solo implementa un servidor de firma usando JSON, podemos generar un nombre de usuario y obtener la firma para el texto JSON correspondiente:
$ nc 83.136.253.251 42286
Vitalium Storage Panel Menu:
[0] Get public key of server
[1] Make an account
[2] View coordinates of vitalium stashes
[3] Exit
Enter option > 1
Enter username > asdf
{"r": 20268714356295630230026215152140525074497089569567597962628569458815, "s": 24501070630283507923614476530336629372052793840461516880969631938844, "message": "{\"username\": \"asdf\", \"admin\": false}"}
Análisis del código fuente
La opción 0 simplemente devuelve los parámetros DSA públicos, aunque ya conocemos algunos del código fuente:
if option == 0:
print(json.dumps({
'p': p,
'q': q,
'g': g,
'y': y
}))
La opción 1, como se muestra anteriormente, nos permite ingresar un nombre de usuario y obtener una firma:
elif option == 1:
username = input("Enter username > ")
message = json.dumps({"username": username, "admin": False})
r, s = sign(message.encode())
print(json.dumps({
'r': r,
's': s,
'message': message
}))
La opción 2 nos dará la flag si enviamos la firma de un mensaje JSON que tiene el campo admin a true:
elif option == 2:
r = int(input("r > "))
s = int(input("s > "))
message = input("message > ").encode()
if verify(message, r, s):
data = json.loads(message)
if data["admin"]:
print(f"Hello admin! Here are the coordinates to your vitalium stash: {open('flag.txt').read()}")
else:
print(f"You must be admin to see the coordinates.")
else:
print(f"Signature Invalid. Breach attempt detected, exiting...")
Pero obsérvese que nuestros mensajes de la opción 1 tienen admin a false de forma predeterminada, por lo que no podemos usar el servidor para firmar un mensaje arbitrario. Además, no tenemos la clave privada $x$ del DSA, por lo que no podemos elaborar fácilmente una firma para un mensaje determinado.
Implementación del DSA
La implementación del DSA es casi correcta. Lo extraño es que el algoritmo firma el mensaje en sí, y no un hash del mensaje:
def sign(message):
m = bytes_to_long(message)
k = randbelow(p)
r = pow(g, k, p) % q
s = (inverse(k, q) * (m + x*r)) % q
return r, s
Como resultado, el servidor calcula:
$$ \begin{cases} r = (g^k \mod{p}) \mod{q} \\ s = k^{-1} \cdot (m + x \cdot r) \mod{q} \end{cases} $$
Donde $k$ es un valor nonce aleatorio. Por lo general, $s$ se calcula como $k^{-1} \cdot (H(m) + x \cdot r) \mod{q}$, donde $H$ es una función hash como SHA256.
Entonces, de alguna manera debemos explotar este error para encontrar la firma para un mensaje $m$ que tiene admin a true.
Solución
En primer lugar, podemos comenzar obteniendo una firma para algún mensaje $m_0$. Entonces, tenemos un par de valores $(r_0, s_0)$ tales que
$$ \begin{cases} r_0 = (g^k \mod{p}) \mod{q} \\ s_0 = k^{-1} \cdot (m_0 + x \cdot r_0) \mod{q} \end{cases} $$
Dado que no hay función hash, la firma $(r_0, s_0)$ también es válida para un número $m_0 + z \cdot q$, para cualquier $z \in \mathbb{Z}$ ya que $m_0 + z \cdot q \equiv m_0 \pmod{q}$.
Pero necesitaríamos algún valor específico de $z$ tal que $m_0 + z \cdot q$ pueda representarse como ASCII imprimible, y que también tenga una estructura JSON con admin a true.
Es posible continuar con este enfoque, pero podemos ser más inteligentes. Echemos un vistazo a la función de verificación:
def verify(message, r, s):
assert 0 < r < q
assert 0 < s < q
m = bytes_to_long(message)
w = pow(s, -1, q)
u1 = (m * w) % q
u2 = (r * w) % q
v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
return r == v
Si proporcionamos un mensaje $m’$ tal que $m’ \equiv 0 \pmod{q}$, entonces $u_1 = m’ \cdot w \mod{q} = 0$, donde $w = s^{-1} \mod{q}$. Por otro lado, $u_2 = r \cdot w = r \cdot s^{-1} \mod{q}$.
Entonces,
$$ \begin{align} v & = (g^{u_1} \cdot y^{u_2} \mod{p}) \mod{q} \\ & = (g^0 \cdot y^{u_2} \mod{p}) \mod{q} \\ & = (y^{(r \cdot s^{-1} \mod{q})} \mod{p}) \mod{q} \end{align} $$
Finalmente, la verificación es exitosa si $r$ es igual a $v$. Como se puede ver, si $m’$ es un múltiplo de $q$, solo necesitamos establecer $r = s = y \mod{q}$, ya que
$$ \begin{align} v & = (y^{(r \cdot s^{-1} \mod{q})} \mod{p}) \mod{q} \\ & = (y^{(y \cdot y^{-1} \mod{q})} \mod{p}) \mod{q} \\ & = (y^1 \mod{p}) \mod{q} \\ & = y \mod{q} \end{align} $$
Entonces, nuestro enfoque será enviar $(r, s) = (y \mod{q}, y \mod{q})$ y encuentrar un mensaje $m’$ que sea un múltiplo de $q$ y también se puede convertir en texto imprimible ASCII con una estructura JSON y admin a true.
Retículo
Podemos expresar una cadena de bytes como vector de números enteros entre $0$ y $255$ (de acuerdo con su código ASCII). Por ejemplo,
$$ \mathtt{''asdf''} \sim [97, 115, 100, 102] $$
Y la cadena anterior tiene la siguiente representación como número entero:
$$ \mathtt{''asdf''} \sim 97 \cdot 256^3 + 115 \cdot 256^2 + 100 \cdot 256^1 + 102 \cdot 256^0 $$
Entonces, si definimos un mensaje JSON arbitrario $m$ como
{"admin": true, "username": "MyHjLgKSSoOnSDwUrJfDllllllllllllllllllllllllllllllllllllllllllllllllll"}
Tendrá la siguiente representación como número entera:
$$ m \sim \sum_{i = 0}^N m_i \cdot 256^i $$
La idea aquí es agregar pequeñas diferencias a cada carácter, para obtener:
$$ m' \sim \sum_{i = 0}^N (m_i + d_i) \cdot 256^i $$
E intentaremos que $m’$ sea un múltiplo de $q$. Además, necesitaremos que $d_0 = d_1 = 0$ para no romper la estructura JSON (los últimos caracteres tienen que ser "}).
Por lo tanto, digamos que para algún $\alpha \in \mathbb{Z}$ tenemos $m’ = \alpha \cdot q$, por tanto
$$ \alpha \cdot q = \sum_{i = 0}^N (m_i + d_i) \cdot 256^i = m + \sum_{i = 0}^N d_i \cdot 256^i $$
Reordenando la ecuación, tenemos:
$$ \sum_{i = 0}^N d_i \cdot 256^i = \alpha \cdot q - m $$
En realidad, ya que queremos que $d_0 = d_1 = 0$, y que $d_i = 0$ para $i > a$, dado un offset arbitrario $a$, podemos simplificar a
$$ \sum_{i = 2}^{a} d_i \cdot 256^i = \alpha \cdot q - m $$
Como estamos tratando de encontrar valores pequeños de $d_i$, podemos construir la siguiente base de retículo (lattice) que contiene un vector corto con los valores $d_i$:
$$ M = \begin{pmatrix} m & q & 256^2 & 256^3 & \dots & 256^a \\ & & 1 & & & \\ & & & 1 & & \\ & & & & \ddots & \\ & & & & & 1 \\ B & & & & & \end{pmatrix} $$
En el retículo generado por las columnas de $M$, tenemos el siguiente vector corto:
$$ \begin{pmatrix} m & q & 256^2 & 256^3 & \dots & 256^a \\ & & 1 & & & \\ & & & 1 & & \\ & & & & \ddots & \\ & & & & & 1 \\ B & & & & & \end{pmatrix} \cdot \begin{pmatrix} 1 \\ -\alpha \\ d_2 \\ d_3 \\ \vdots \\ d_a \\ \end{pmatrix} = \begin{pmatrix} 0 \\ d_2 \\ d_3 \\ \vdots \\ d_a \\ B \end{pmatrix} $$
Por lo tanto, podemos intentar usar LLL para reducir la base del retículo y buscar un vector que tenga la primera componente igual a $0$ y la última componente igual a $B$, que es un valor grande arbitrario (por ejemplo, $2^{256}$).
Una vez que tenemos $d_2$ a $d_a$, simplemente podemos sumarlos a $m$ para obtener $m’$:
$$ m' = m + \sum_{i = 0}^N d_i \cdot 256^i = m + \sum_{i = 2}^a d_i \cdot 256^i $$
Con esto, tendremos $m’ \equiv 0 \pmod{q}$, que es lo que necesitamos para realizar la explotación.
Obsérvese que el mensaje JSON inicial contiene varios caracteres l debido a que es un carácter que se encuentra en el medio del conjunto de caracteres, por lo que no importa si los $d_i$ son positivos o negativos siempre que tengan un valor absoluto pequeño.
Por otro lado, necesitamos agregar algunos caracteres aleatorios antes en caso de que el mensaje resultante $m’$ no sea ASCII válido o JSON válido.
Implementación
Podemos usar el siguiente script para generar un mensaje JSON que tiene admin a true y es múltiplo de $q$:
#!/usr/bin/env python3
import json
import random
import string
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
from sage.all import Matrix, ZZ
q = 26189572440233739420990528170531051459310363621928135990243626537967
a = 50
B = 2 ** 256
while True:
m = b2l(json.dumps({
'admin': True,
'username': ''.join(random.choices(string.ascii_letters, k=20)) + 'l' * a
}).encode())
M = Matrix(ZZ, [
[m, q] + [256 ** i for i in range(2, a)],
*[[0] * i + [1] + [0] * (a - i - 1) for i in range(2, a)],
[B, 0] + [0] * (a - 2),
])
L = M.transpose().LLL()
for row in L.rows():
if row[0] == 0 and row[-1] == B:
d = row[1:-1]
break
else:
continue
m_prime = m + sum(d_i * 256 ** (2 + i) for i, d_i in enumerate(d))
if m_prime % q != 0:
continue
try:
if not json.loads(l2b(m_prime))['admin']:
continue
except:
continue
print(l2b(m_prime).decode())
break
With this script, we get such messaage $m’$ we were looking for (there are plenty of them):
$ python3 solve.py
{"admin": true, "username": "ebSvBBWmADWTZGWfCynlllhlnrfsiesehvzlklo{jsxgpy{uuzhevbwe[_poYuyhh|k_et"}
Flag
Ahora, podemos conectarnos a la instancia remota, poner $r = s = y \mod{q}$ y enviar el mensaje $m’$ anterior para obtener la flag.
Primero, tomamos $y$:
$ nc 83.136.253.251 42286
Vitalium Storage Panel Menu:
[0] Get public key of server
[1] Make an account
[2] View coordinates of vitalium stashes
[3] Exit
Enter option > 0
{"p": 30514860220781649196505378618677588344627509796136052197766721133333403517227804826248671926331671978511695325934422209350872533631963158343821543243314354301612941382823755283391175569282500778759917825290265500008435125458284371701669393617263164707568562478942069967845682300866897274415749964510071038555145487346022921591488265881313448995313340365972250251431925090356830155846705412769705029295847471355919584592321591959772488755986181054597974081870037624260173234561447688627353479361867003340196122160639547860024025674714107946196423198018724048310862485718766310003158603549746994074302705926658218700843, "q": 26189572440233739420990528170531051459310363621928135990243626537967, "g": 6111748161621056558453263711027460170929636824002846224800107291166700007147256826554286465237732729099376511591848799483754962591483370638607627034808201246023891469880792589537431156477847873086973414247654773443349132863425799271140168302068820170758172107172379842519843597077356839020025609506792115532019927453283319270046204956352057936972814681479252626295814756888943630138110534869191473166355939365725603055249365076889191708484425425599800051451167006426087674425090967640170968963795028092131692666710522291627118158125917935888441403300632869010691598781782043810771106247022549721544793735832383283054, "y": 29864779004942820791753633735710480440075792979078921806508182812517786831040689682372332770032640785047421078597860854868227302097145607352774509412408846060799440538494461317733610678904629248550587673778090074507395490496234018568232426741308523148994848677932744874840901126585423051040666775499204372310436223086068018560677136835534505872848013529133653719490999167396396366119083207981752673921029594722283965110371069136960587847825027463182632807120771240114399262843297259816181495979255718780932439653441608306878359314848158741717879305580477761914781395733088260798209746245307748440037323555224739916443}
Vitalium Storage Panel Menu:
[0] Get public key of server
[1] Make an account
[2] View coordinates of vitalium stashes
[3] Exit
Enter option >
A continuación, calculamos $y \mod{q}$:
$ python3 -q
>>> q = 26189572440233739420990528170531051459310363621928135990243626537967
>>> y = 29864779004942820791753633735710480440075792979078921806508182812517786831040689682372332770032640785047421078597860854868227302097145607352774509412408846060799440538494461317733610678904629248550587673778090074507395490496234018568232426741308523148994848677932744874840901126585423051040666775499204372310436223086068018560677136835534505872848013529133653719490999167396396366119083207981752673921029594722283965110371069136960587847825027463182632807120771240114399262843297259816181495979255718780932439653441608306878359314848158741717879305580477761914781395733088260798209746245307748440037323555224739916443
>>> y % q
22295154601668891446656757951969034321533599760990325063219058105856
Finalmente, enviamos $r$, $s$ y $m’$:
Enter option > 2
r > 22295154601668891446656757951969034321533599760990325063219058105856
s > 22295154601668891446656757951969034321533599760990325063219058105856
message > {"admin": true, "username": "ebSvBBWmADWTZGWfCynlllhlnrfsiesehvzlklo{jsxgpy{uuzhevbwe[_poYuyhh|k_et"}
Hello admin! Here are the coordinates to your vitalium stash: HTB{CVP_1s_t00_p0w3rful___H3r3_4r3_th3_v1t4l1um_c00rd1n4t3s:37.187561,-115.885322}