<- CRYPTO

Signing Factory

8 minutos de lectura

Se nos proporciona el código fuente en Python del servidor que contiene la flag:

from re import search as rsearch
from base64 import b64encode, b64decode
from hashlib import sha256
from sympy.ntheory import factorint as ps_and_qs
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

def show_menu():
    return input("""
An improved signing server with extra security features such as hashing usernames to avoid forging tokens!
Available options:

[0] Register an account.
[1] Login to your account.
[2] PublicKey of current session.
[3] Exit.

[+] Option >> """)

class Signer:
    def __init__(self, key_size=2048):
        self.key_size = key_size
        self.admin = bytes_to_long(b'System_Administrator')
        self.golden_ratio = 2654435761
        self.hash_var = lambda key: (((key % self.golden_ratio) * self.golden_ratio) >> 32)
        self.equation_output = lambda k, rnd: (k * rnd) % self.golden_ratio

        rsa_key = RSA.generate(key_size)
        self.n = rsa_key.n
        self.d = rsa_key.d
        self.e = rsa_key.e

    def numgen(self):
        while True:
            rnd = getPrime(32)
            if rnd < self.golden_ratio:
                return rnd

    def sign(self, username):
        h = self.hash_var(username)
        auth = pow(int(h), self.d, self.n)
        return auth

    def verify(self, recomputed_signature, token):
        return recomputed_signature == pow(token, self.e, self.n)

    def equations(self):
        h_n = self.hash_var(self.n)
        ps_n_qs = [k**v for k, v in ps_and_qs(h_n).items()]
        rnds = [self.numgen() for _ in ps_n_qs]
        return [f"equation(unknown, {rnd}, {self.golden_ratio}) = {self.equation_output(unknown, rnd)}" for unknown, rnd in zip(ps_n_qs, rnds)]

def main():
    signer = Signer()
    
    while True:
        user_inp = show_menu()
        if user_inp == '0':
            username = input("Enter a username: ")
            if rsearch('[^a-zA-Z0-9]', username):
                print("[-] Invalid characters detected. Symbols are not allowed.")
                continue

            numeric_username = int(username.encode().hex(), 16)

            if numeric_username % signer.golden_ratio == signer.admin % signer.golden_ratio:
                print("[-] Admin user already exists.")
                continue

            token = signer.sign(numeric_username)
            print(f"Your session token is {b64encode(str(token).encode())}")

        elif user_inp == '1':
            username = input("Enter your username: ")
            authToken = input("Enter your authentication token: ")

            try:
                authToken = b64decode(authToken.encode())
                authToken = int(authToken.decode())
            except:
                print("[-] Invalid format for authentication key.")
                continue
            
            numeric_username = int(username.encode().hex(), 16)

            recomputed_signature = signer.hash_var(numeric_username)
            if signer.verify(recomputed_signature, authToken):
                if numeric_username == signer.admin:
                    print(f"[+] Welcome back admin! The note you left behind from your previous session was: {FLAG}")
                else:
                    print(f"[+] Welcome {username}!")
            else:
                print("[-] No match found for that (username, token) pair.")

        elif user_inp == '2':
            print(f"\nTo avoid disclosing public keys to bots, a modern captcha must be completed. Kindly compute the hash of 'N' to get the full public key based on the following equations:\n{signer.equations()}\n")
            
            try:
                user_result = int(input("Enter the hash(N): "))
            except:
                print("Invalid input for a hash.")
                continue

            if user_result == signer.hash_var(signer.n):
                print(f"[+] Captcha successful!\n(e,N) = {(signer.e, signer.n)}")

        elif user_inp == '3':
            print("[-] Closing connection.")
            break

        else:
            print("[-] Invalid selection.")

if __name__ == '__main__':
    main()

Análisis del código fuente

El servidor ofrece tres opciones:

[0] Register an account.
[1] Login to your account.
[2] PublicKey of current session.

La primera opción nos permite obtener un token para un nombre de usuario, que se calcula como una firma:

        if user_inp == '0':
            username = input("Enter a username: ")
            if rsearch('[^a-zA-Z0-9]', username):
                print("[-] Invalid characters detected. Symbols are not allowed.")
                continue

            numeric_username = int(username.encode().hex(), 16)

            if numeric_username % signer.golden_ratio == signer.admin % signer.golden_ratio:
                print("[-] Admin user already exists.")
                continue

            token = signer.sign(numeric_username)
            print(f"Your session token is {b64encode(str(token).encode())}")

La segunda opción nos permite iniciar sesión, proporcionando nombre de usuario y un token:

        elif user_inp == '1':
            username = input("Enter your username: ")
            authToken = input("Enter your authentication token: ")

            try:
                authToken = b64decode(authToken.encode())
                authToken = int(authToken.decode())
            except:
                print("[-] Invalid format for authentication key.")
                continue
            
            numeric_username = int(username.encode().hex(), 16)

            recomputed_signature = signer.hash_var(numeric_username)
            if signer.verify(recomputed_signature, authToken):
                if numeric_username == signer.admin:
                    print(f"[+] Welcome back admin! The note you left behind from your previous session was: {FLAG}")
                else:
                    print(f"[+] Welcome {username}!")
            else:
                print("[-] No match found for that (username, token) pair.")

Si logramos tener el token para el usuario administrador, entonces obtendremos la flag. Sin embargo, como se muestra en la primera opción, no podemos obtener un token directamente para el usuario administrador.

Por último, pero no menos importante, tenemos la tercera opción:

        elif user_inp == '2':
            print(f"\nTo avoid disclosing public keys to bots, a modern captcha must be completed. Kindly compute the hash of 'N' to get the full public key based on the following equations:\n{signer.equations()}\n")
            
            try:
                user_result = int(input("Enter the hash(N): "))
            except:
                print("Invalid input for a hash.")
                continue

            if user_result == signer.hash_var(signer.n):
                print(f"[+] Captcha successful!\n(e,N) = {(signer.e, signer.n)}")

Esta opción mostrará los parámetros de clave pública para el esquema de firma, pero antes necesitamos resolver un problema:

    def equations(self):
        h_n = self.hash_var(self.n)
        ps_n_qs = [k**v for k, v in ps_and_qs(h_n).items()]
        rnds = [self.numgen() for _ in ps_n_qs]
        return [f"equation(unknown, {rnd}, {self.golden_ratio}) = {self.equation_output(unknown, rnd)}" for unknown, rnd in zip(ps_n_qs, rnds)]

La función anterior ps_and_qs is just an alias of sympy.ntheory.factorint. El resto se definen en el constructor de Signer:

class Signer:
    def __init__(self, key_size=2048):
        self.key_size = key_size
        self.admin = bytes_to_long(b'System_Administrator')
        self.golden_ratio = 2654435761
        self.hash_var = lambda key: (((key % self.golden_ratio) * self.golden_ratio) >> 32)
        self.equation_output = lambda k, rnd: (k * rnd) % self.golden_ratio

En resumen, el servidor calculará self.hash_var(self.n), que es un valor relativamente pequeño. Luego, tomará sus factores y multiplicará cada uno de ellos por un número aleatorio módulo golden_ratio:

Se nos proporcionará el resultado del producto y el número aleatorio, por lo que podemos despejar usando aritmética modular:

Esquema de firma

El esquema de firma es RSA-2048:

class Signer:
    def __init__(self, key_size=2048):
        # ...

        rsa_key = RSA.generate(key_size)
        self.n = rsa_key.n
        self.d = rsa_key.d
        self.e = rsa_key.e

    # ...

    def sign(self, username):
        h = self.hash_var(username)
        auth = pow(int(h), self.d, self.n)
        return auth

    def verify(self, recomputed_signature, token):
        return recomputed_signature == pow(token, self.e, self.n)

La idea de esto es firmar el hash de un mensaje con la siguiente operación:

Nótese que es el exponente privado, y es el módulo público. Entonces, si alguien quiere verificar el mensaje , es suficiente tomar el hash del mensaje y los parámetros públicos de RSA para probar que

Lo cual es cierto porque .

Solución

Entonces, una vez que resolvemos el problema de las ecuaciones y tenemos los parámetros públicos de RSA, nos queda obtener el token para el usuario administrador.

Para esto, ya conocemos el nombre de usuario y el hash (llamémoslos y ). Necesitamos una firma tal que

Pero no podemos registrar una cuenta de tal manera que . En cambio, lo que podemos hacer es factorizar el hash . Digamos que . Entonces, podemos intentar encontrar mensajes tales que .

Con esto, y debido a la maleabilidad de RSA, tenemos que

Como se puede ver, solo necesitamos firmar estos mensajes y luego multiplicar sus firmas para obtener .

Esto es posible porque el hash del usuario administrador es un número compuesto:

$ sage -q
sage: from Crypto.Util.number import bytes_to_long
sage:
sage: admin = bytes_to_long(b'System_Administrator')
sage: golden_ratio = 2654435761
sage: hash_var = lambda key: ((key % golden_ratio) * golden_ratio) >> 32
sage:
sage: hash_admin = hash_var(admin)
sage: hash_admin
1115247629
sage: factor(hash_admin)
67 * 16645487

Hash

Ahora, ¿cómo podemos encontrar un mensaje tal que ? Bueno, la función hash_var no es una función hash segura:

        self.hash_var = lambda key: (((key % self.golden_ratio) * self.golden_ratio) >> 32)

Podemos expresar la función en términos matemáticos de la siguiente manera:

Entonces, podemos deshacer el hash así:

En realidad, podemos encontrar infinitos mensajes que tengan el mismo hash porque podemos agregar múltiplos de golden_ratio:

La única comprobación que se hace en es que el nombre de usuario debe ser alfanumérico, pero podemos probar varios valores de hasta que esto suceda.

Implementación

Entonces, primero debemos resolver el problema de las ecuaciones para obtener la clave pública de RSA:

io.sendlineafter(b'[+] Option >> ', b'2')
io.recvuntil(b'following equations:')
io.recvline()
eqs = literal_eval(io.recvline().decode())

rnds = [int(re.findall(fr'equation\(unknown, (\d+), {golden_ratio}\)', eq)[0]) for eq in eqs]
ress = [int(eq.split(' = ')[1]) for eq in eqs]

hash_n = prod(res * pow(rnd, -1, golden_ratio) % golden_ratio for res, rnd in zip(ress, rnds))
io.sendlineafter(b'Enter the hash(N): ', str(hash_n).encode())

io.recvuntil(b'(e,N) = ')
e, n = literal_eval(io.recvline().decode())

Luego, factorizamos el hash del usuario administrador, deshacemos los factores del hash y firmamos cada parte:

hash_var = lambda key: ((key % golden_ratio) * golden_ratio) >> 32

admin = int(b'System_Administrator'.hex(), 16)
hash_admin = hash_var(admin)

tokens = []

for factor, exponent in factorint(hash_admin).items():
    k = 0
    target = ((factor ** exponent) << 32) // golden_ratio + 1

    while re.search(b'[^a-zA-Z0-9]', long_to_bytes((target % golden_ratio) + k * golden_ratio)):
        k += 1

    username = long_to_bytes((target % golden_ratio) + k * golden_ratio)
    io.sendlineafter(b'[+] Option >> ', b'0')
    io.sendlineafter(b'Enter a username: ', username)
    io.recvuntil(b'Your session token is ')
    tokens.append(int(b64d(literal_eval(io.recvline().decode())).decode()))

Finalmente, enviamos el producto de las firmas anteriores, que deben coincidir con el token del administrador, por lo que obtendremos la flag:

io.sendlineafter(b'[+] Option >> ', b'1')
io.sendlineafter(b'Enter your username: ', b'System_Administrator')
io.sendlineafter(b'Enter your authentication token: ', b64e(str(prod(tokens) % n).encode()).encode())

io.recvuntil(b'[+] Welcome back admin! The note you left behind from your previous session was: ')
io.success(io.recvline().decode())

Flag

Si ejecutamos el script, obtendremos la flag:

$ python3 solve.py 94.237.53.3:59847
[+] Opening connection to 94.237.53.3 on port 59847: Done
[+] HTB{sm4ll_f4c7025_619_p206l3m5}
[*] Closed connection to 94.237.53.3 port 59847

El script completo se puede encontrar aquí: solve.py.