Vitrium Stash
10 minutes to read
We are given the Python source code of the server:
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()
The code just implements a signing server using JSON, we can generate a username and get the signature for the corresponding JSON text:
$ 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}"}
Source code analysis
Option 0 simply returns the public DSA parameters, although we already know some of them from the source code:
if option == 0:
print(json.dumps({
'p': p,
'q': q,
'g': g,
'y': y
}))
Option 1, as shown before, allows us to enter a username and get a signature:
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
}))
Option 2 will give us the flag if we are able to input the signature of a JSON message that has field admin set to 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...")
But notice that our messages from option 1 have admin set to false by default, so we can’t just use the server to sign an arbitrary message. Also, we don’t have the DSA private key $x$, so we can’t easily craft a signature for a given message.
DSA implementation
The DSA implementation is almost correct. The weird thing is that the algorithm signs the message itself, and not a hash digest:
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
As a result, the server computes:
$$ \begin{cases} r = (g^k \mod{p}) \mod{q} \\ s = k^{-1} \cdot (m + x \cdot r) \mod{q} \end{cases} $$
Where $k$ is a random nonce value. Typically, $s$ is computed as $k^{-1} \cdot (H(m) + x \cdot r) \mod{q}$, where $H$ is a hash function such as SHA256.
So, we must somehow exploit this bug to find the signature for a message $m$ that has admin set to true.
Solution
First of all, we can start by getting a signature for some message $m_0$. So, we have a pair of values $(r_0, s_0)$ such that
$$ \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} $$
Since there is no hash function, the signature $(r_0, s_0)$ is also valid for a number $m_0 + z \cdot q$, for any $z \in \mathbb{Z}$ because $m_0 + z \cdot q \equiv m_0 \pmod{q}$.
But we would need some specific value of $z$ such that $m_0 + z \cdot q$ can be represented as printable ASCII, and also to have a JSON structure with admin set to true.
It is possible to continue with this approach, but we can be smarter. Let’s take a look at the verification function:
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
If we provide a message $m’$ such that $m’ \equiv 0 \pmod{q}$, then $u_1 = m’ \cdot w \mod{q} = 0$, where $w = s^{-1} \mod{q}$. Also, $u_2 = r \cdot w = r \cdot s^{-1} \mod{q}$.
Then,
$$ \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} $$
Finally, the verification is successful if $r$ equals $v$. As can be seen, if $m’$ is a multiple of $q$, then we only need to set $r = s = y \mod{q}$, becuase
$$ \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} $$
So, our approach will be to send $(r, s) = (y \mod{q}, y \mod{q})$ and find a message $m’$ which is a multiple of $q$ and also can be converted to ASCII printable text with a JSON structure and admin set to true.
Lattice
We can express a byte string as a vector of integers between $0$ and $255$ (according to their ASCII code). For instance,
$$ \mathtt{''asdf''} \sim [97, 115, 100, 102] $$
And the above string has the following integer representation:
$$ \mathtt{''asdf''} \sim 97 \cdot 256^3 + 115 \cdot 256^2 + 100 \cdot 256^1 + 102 \cdot 256^0 $$
So, if we define an arbitrary JSON message $m$ like
{"admin": true, "username": "MyHjLgKSSoOnSDwUrJfDllllllllllllllllllllllllllllllllllllllllllllllllll"}
It will have an integer representation like
$$ m \sim \sum_{i = 0}^N m_i \cdot 256^i $$
The idea here is to add small differences to each character, so that we get:
$$ m' \sim \sum_{i = 0}^N (m_i + d_i) \cdot 256^i $$
And we will try that $m’$ is a multiple of $q$. Also, we will need that $d_0 = d_1 = 0$ so that we don’t break the JSON structure (the last characters must be "}).
Therefore, let’s say that for some $\alpha \in \mathbb{Z}$ we have $m’ = \alpha \cdot q$, therefore
$$ \alpha \cdot q = \sum_{i = 0}^N (m_i + d_i) \cdot 256^i = m + \sum_{i = 0}^N d_i \cdot 256^i $$
Reordering the equation, we have:
$$ \sum_{i = 0}^N d_i \cdot 256^i = \alpha \cdot q - m $$
Actually, since we want $d_0 = d_1 = 0$, and $d_i = 0$ for $i > a$, given an arbitrary offset $a$, we can simplify to
$$ \sum_{i = 2}^{a} d_i \cdot 256^i = \alpha \cdot q - m $$
Since we are trying to find small values $d_i$, we can construct the following lattice basis that contains a short vector with values $d_i$:
$$ M = \begin{pmatrix} m & q & 256^2 & 256^3 & \dots & 256^a \\ & & 1 & & & \\ & & & 1 & & \\ & & & & \ddots & \\ & & & & & 1 \\ B & & & & & \end{pmatrix} $$
In the lattice generated by the columns of $M$, we have the following short vector:
$$ \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} $$
Therefore, we can try to use LLL to reduce the lattice basis and search for a vector that has the first component equal to $0$ and the last component equal to $B$, which is an arbitrary large value (for instance, $2^{256}$).
Once we have $d_2$ to $d_a$, we can simply add them to $m$ to get $m’$:
$$ m' = m + \sum_{i = 0}^N d_i \cdot 256^i = m + \sum_{i = 2}^a d_i \cdot 256^i $$
With this, we will have $m’ \equiv 0 \pmod{q}$, which is what we need to perform the exploitation.
Notice that the initial JSON message contains several l characters because it is a character that lies in the middle of the character set, so it doesn’t matter if $d_i$ are positive or negative as long as they have a small absolute value.
On the other hand, we need to add some random characters before in case the resulting message $m’$ is not valid ASCII or valid JSON.
Implementation
We can use the following script to generate a JSON message that has admin set to true and is a multiple of $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
Now, we can connect to the remote instance, input $r = s = y \mod{q}$ and send the previous $m’$ message to get the flag.
First, we take $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 >
Next, we compute $y \mod{q}$:
$ python3 -q
>>> q = 26189572440233739420990528170531051459310363621928135990243626537967
>>> y = 29864779004942820791753633735710480440075792979078921806508182812517786831040689682372332770032640785047421078597860854868227302097145607352774509412408846060799440538494461317733610678904629248550587673778090074507395490496234018568232426741308523148994848677932744874840901126585423051040666775499204372310436223086068018560677136835534505872848013529133653719490999167396396366119083207981752673921029594722283965110371069136960587847825027463182632807120771240114399262843297259816181495979255718780932439653441608306878359314848158741717879305580477761914781395733088260798209746245307748440037323555224739916443
>>> y % q
22295154601668891446656757951969034321533599760990325063219058105856
Finally, we input $r$, $s$ and $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}