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 , 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:

Where is a random nonce value. Typically, is computed as , where is a hash function such as SHA256.

So, we must somehow exploit this bug to find the signature for a message that has admin set to true.

Solution

First of all, we can start by getting a signature for some message . So, we have a pair of values such that

Since there is no hash function, the signature is also valid for a number , for any because .

But we would need some specific value of such that 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 such that , then , where . Also, .

Then,

Finally, the verification is successful if equals . As can be seen, if is a multiple of , then we only need to set , becuase

So, our approach will be to send and find a message which is a multiple of 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 and (according to their ASCII code). For instance,

And the above string has the following integer representation:

So, if we define an arbitrary JSON message like

{"admin": true, "username": "MyHjLgKSSoOnSDwUrJfDllllllllllllllllllllllllllllllllllllllllllllllllll"}

It will have an integer representation like

The idea here is to add small differences to each character, so that we get:

And we will try that is a multiple of . Also, we will need that so that we don’t break the JSON structure (the last characters must be "}).

Therefore, let’s say that for some we have , therefore

Reordering the equation, we have:

Actually, since we want , and for , given an arbitrary offset , we can simplify to

Since we are trying to find small values , we can construct the following lattice basis that contains a short vector with values :

In the lattice generated by the columns of , we have the following short vector:

Therefore, we can try to use LLL to reduce the lattice basis and search for a vector that has the first component equal to and the last component equal to , which is an arbitrary large value (for instance, ).

Once we have to , we can simply add them to to get :

With this, we will have , 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 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 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 :

#!/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 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 and send the previous message to get the flag.

First, we take :

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

$ python3 -q
>>> q = 26189572440233739420990528170531051459310363621928135990243626537967
>>> y = 29864779004942820791753633735710480440075792979078921806508182812517786831040689682372332770032640785047421078597860854868227302097145607352774509412408846060799440538494461317733610678904629248550587673778090074507395490496234018568232426741308523148994848677932744874840901126585423051040666775499204372310436223086068018560677136835534505872848013529133653719490999167396396366119083207981752673921029594722283965110371069136960587847825027463182632807120771240114399262843297259816181495979255718780932439653441608306878359314848158741717879305580477761914781395733088260798209746245307748440037323555224739916443
>>> y % q
22295154601668891446656757951969034321533599760990325063219058105856

Finally, we input , and :

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}