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

Donde es un valor nonce aleatorio. Por lo general, se calcula como , donde es una función hash como SHA256.

Entonces, de alguna manera debemos explotar este error para encontrar la firma para un mensaje que tiene admin a true.

Solución

En primer lugar, podemos comenzar obteniendo una firma para algún mensaje . Entonces, tenemos un par de valores tales que

Dado que no hay función hash, la firma también es válida para un número , para cualquier ya que .

Pero necesitaríamos algún valor específico de tal que 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 tal que , entonces , donde . Por otro lado, .

Entonces,

Finalmente, la verificación es exitosa si es igual a . Como se puede ver, si es un múltiplo de , solo necesitamos establecer , ya que

Entonces, nuestro enfoque será enviar y encuentrar un mensaje que sea un múltiplo de 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 y (de acuerdo con su código ASCII). Por ejemplo,

Y la cadena anterior tiene la siguiente representación como número entero:

Entonces, si definimos un mensaje JSON arbitrario como

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

Tendrá la siguiente representación como número entera:

La idea aquí es agregar pequeñas diferencias a cada carácter, para obtener:

E intentaremos que sea un múltiplo de . Además, necesitaremos que para no romper la estructura JSON (los últimos caracteres tienen que ser "}).

Por lo tanto, digamos que para algún tenemos , por tanto

Reordenando la ecuación, tenemos:

En realidad, ya que queremos que , y que para , dado un offset arbitrario , podemos simplificar a

Como estamos tratando de encontrar valores pequeños de , podemos construir la siguiente base de retículo (lattice) que contiene un vector corto con los valores :

En el retículo generado por las columnas de , tenemos el siguiente vector corto:

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 y la última componente igual a , que es un valor grande arbitrario (por ejemplo, ).

Una vez que tenemos a , simplemente podemos sumarlos a para obtener :

Con esto, tendremos , 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 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 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 :

#!/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

Ahora, podemos conectarnos a la instancia remota, poner y enviar el mensaje anterior para obtener la flag.

Primero, tomamos :

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

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

Finalmente, enviamos , y :

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}