Signing Factory

8 minutes to read

We are given the Python source code of the server that contains the 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()

Source code analysis

The server offers three options:

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

The first option allows us to get a token for a username, which is computed as a signature:

        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())}")

The second option allows us to log in, providing both username and 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.")

If we manage to have the token for the administrator user, then we will get the flag. However, as shown in the first option, we can’t get a token for the administrator user directly.

Last but not least, we have the third option:

        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)}")

This option will show the public key parameters for the signature scheme, but we need to solve a problem:

    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)]

The above function ps_and_qs is just an alias of sympy.ntheory.factorint. The rest are defined in the constructor of 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

In summary, the server will compute self.hash_var(self.n), which is a relatively small value. Then, it will take its factors and multiply each of them by a random number modulo golden_ratio:

We will be given the product result and the random number, so we can just isolate using modular arithmetic:

Signature scheme

The signature scheme is 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)

The idea of this is to sign the hash of a message with the following operation:

Notice that is the private exponent, and is the public modulus. Then, if someone wants to verify the message , it suffices to take the hash of the message and the public RSA parameters to test if

Which is true because .

Solution

So, once we solve the equations problem and we have the public RSA parameters, we are left with getting the token for the administrator user.

For this, we already know the username and the hash (let’s call them and ). We need a signature such that

But we cannot register an account such that . Instead, what we can do is factor the hash . Let’s say . Then, we can try to find messages such that .

With this, and due to RSA malleability, we have that

As can be seen, we only need to sign those messages and then multiply their signatures to get .

This is possible because the hash of the administrator user is a composite number:

$ 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

Now, how can we find a message such that ? Well, the hash_var function is not a good hash function:

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

We can express it in mathematical terms as follows:

So, we can undo the hash like this:

Actually, we can find infinite messages that have the same hash because we can add multiples of golden_ratio:

The only check on is that the username must be alphanumeric, but we can test several values of until we pass the check.

Implementation

So, first we need to solve the equations problem to get the public RSA key:

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())

Then, we factor the hash of the administrator user, undo the factor hashes and sign each part:

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()))

Finally, we send the product of the previous signatures, which must match with the administrator token, so we will get the 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

If we run the script, we will get the 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

The full script can be found in here: solve.py.