Introduction Link to heading

The challenge as hosted on Hack The Box entails the following

Challenge name: Signing Factory
Challenge Points: 30 points
Challenge Diff: Medium
Challenge Creators: [connar](https://app.hackthebox.com/users/704250)

The challenge test the ability to do a desmedt-odlyzko attack which usually entails forging of RSA digital signatures under the property of the homomorphic encryption. By escaping some regex operations and utilsing modular arithmetic we can be able to forge the valid value required.

The challenge Link to heading

Zip file:

ls -la
total 16
drwxr-xr-x 2 pyp pyp 4096 May 11 13:55 .
drwxrwxr-x 3 pyp pyp 4096 May 11 13:44 ..
-rw-r--r-- 1 pyp pyp 4130 May 11 13:55 server.py

Server.py:

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

We have a long python script that does a few quite things. Ill summarise the above script to see the main idea of what is happening:

  1. We have a class Signer with initalized parts,numgen, sign, verify, equations function.

    a. __init__ class: A 2048-bit RSA key is generated, An admin token used from the username System_Administrator, golden ratio value which is a prime number is also initialized, hash_var which appears to be a custom hash function is also initialized, equation_output function which generates a value which is a product of k and rnd modulo golden_ratio.

    b. numgen generates a 32-bit prime number which is less than the golden ratio

    c. sign takes in a username (in integer form), hashes it using hash_var and signs the value to get the signature as output

    d. verify ensures that the signature and the signed value match by restoring the original value from the signature.

    e. equations is an interesting function that generates a bunch of equations from the hash value of modulus (n). It first factors the hash value of n into factor: power inform of a dictionary and then raises the factor to the power and puts them into a list. It then uses each new factor with a random value to generate new output using equation_output and hence returns to the user.

  2. main function with the following parts:

    a. If user input = 0, then it allows us to retrieve a signature for a given username for as long it is not admin based token (this is was the initial way most people used to solve the challenge using hash collision) in base64 format. It ensures we cannot use bytes and hence need a way to circumvent this.

    b. user_input = 1 ;It allows us to verify our signature with our username; If admin gives back the flag else welcomes the user if correct.

    c. user_input = 2; Allows us to get the public_key iff I provide the hash_var(N).

    d. user_input = 3; Closes the connection

That was a lot to summary but the gist can be seen what needs to be done; We need to forge the admin_token's signature so that we can get back the flag. But how can we do that? Since we have the hashing function, we basically can be able to get: H(admin_token). Since we cannot sign that value directly, we should be able to use a certain property that exists in `RSA.

The attack Link to heading

RSA is homomorphic in nature. What does that mean? This means it behaves under the following rule: $$(m_{1} \cdot m_{2})^d \cong (m_{1})^{d} \cdot (m_{2})^d mod \space N$$ if the H(admin_token) can be factored (especially into small factors) then we can sign each individual part and combine them modulo N to get back admin_signature. But first we need the modulus from the public key. To recover the modulus which will be provided, we need to calculate the H(N) from the provided equations. The concept steming from this is group theory, since the golden ratio provided is a prime number we have the following: \(random \in F_{p}\) , since the random is a member of the field F, it must have an inverse in the same field. This is what allows us to recover our factors of H(N) and then finally recover H(N).

Proof of Concept Link to heading

We will use sagemath to prove the above two concepts:

  1. Homomorphic proof
sage: from Crypto.PublicKey import RSA
sage: rsa_key = RSA.generate(2048)
sage: N = rsa_key.n
sage: d = rsa_key.d
sage: e = rsa_key.e
sage: N
29303261531883758431855692557854460416730548680458466912109642695259186419849428637142234842901289859603587219578323567431197883208239617447462453233948709293817135197469017133043146663133221131009790335144558659018136253563720878514291014650378459590877564206343185428954219236245978730690186237671510072112930466236230852905683712960821318006639316542627662531768089923930048843560929701891354848015452882880921388959228873311382730783820037759375792939124316777176531017873772270011627420529039962493911576736288779429651851734171861260602612911083724920533408793350573551817537508852020164813505638829511831457889
sage: d
680720573545436615615580526092871966685936413120916233875595833664398090011283923749320706755566053994388457170861864079695963002835715742064347142001614173756896482402257301547024972121914084343831998311818423538442769924392592046982634643282200223894695540784512616788890079626504680467600598291270879280588191949549149974577266219669642159078228533733701304955897364423579642938166705744757655080712673438526695792925300620631786353189242958249325730593183596508778560718603077661581185847852656596015546213659522741958926972770329146916778702011101269959818223583183434955055420592855375689251651142135813337473
sage: e
65537
sage: M = (17 * 31)
sage: m1 = 17
sage: m2 = 31
sage: factor(M)
17 * 31
sage: m1 * m2 == M
True
sage: s1 = pow(m1,d,N)
sage: s2 = pow(m2,d,N)
sage: s3 = pow(M,d,N)
sage: (s1 * s2) % N == s3 % N
True
  1. Equation recovery proof
sage: from Crypto.Util.number import getPrime, bytes_to_long as b2l, long_to_bytes as l2b
sage: golden_ratio = 2654435761
sage: hash_var = lambda key: (((key % golden_ratio) * golden_ratio) >> 32)
sage: rnds = [getPrime(32) for _ in range(10)]
sage: N_hash = hash_var(N)
sage: N_hash
564517778
sage: factor(N_hash)
2 * 11 * 19 * 1350521
sage: factors = [2,11,19,1350521]
sage: product(factors) == N_hash
True
sage: equation_output = lambda k, rnd: (k * rnd) % golden_ratio
sage: rnds = [getPrime(32) for _ in range(4)] # 4 prime factors
sage: equations = [equation_output(factor_value, rnd) for rnd,factor_value in zip(rnds,factors)]
sage: equations
[1670423484, 1501749200, 2244615048, 1920451924]
sage: rnds
[3489647503, 4238832467, 3610816267, 4089469079]
sage: is_prime(golden_ratio)
True
sage: # Therefore an inverse of each element must exist in that field
sage: [(inverse_mod(rnd,golden_ratio) * equa_value) % golden_ratio for rnd,equa_value in zip(rnds, equations)]
[2, 11, 19, 1350521]
sage: [(inverse_mod(rnd,golden_ratio) * equa_value) % golden_ratio for rnd,equa_value in zip(rnds, equations)] == factors
True

With that we can confirm the recovery of the public key, The issue arises when trying to find out a suitable value to of the m1 and m2. If we go on the assumption that there is no regex, we would have been able to sign bytes but the regex only allows alphanumeric characters: We know we need to sign H(m1) and H(m2) such that H(m1) * H(m2) = H(admin_token).

sage: hash_admin = hash_var(b2l(b"System_Administrator"))
sage: factor(hash_admin)
67 * 16645487
sage: # We need two alphanumeric values that when H(m1) and H(m2) == 67 and 16645487
sage: # This can be done through bruteforce of the value by reversing the equation
sage: # hash_var(m1) % golden_ratio * golden_ratio >> 32 = output; Can be reversed to get  (output << 32) // golden_ratio + (1 or 2) = hash_var(m1) % golden_ratio
sage: # Remember that H(m1) mod golden_ratio can be re-written as H(m1) mod gr  + random_coeff * golden_ratio == (output << 32) // golden_ratio + (1 or 2) + random_coeff * golden_rati
....: o
sage: # If we desire output = 67 and 16645487
sage: ((67 << 32) // golden_ratio + 1) + 0 * golden_ratio
109
sage: l2b(((67 << 32) // golden_ratio + 1) + 0 * golden_ratio)
b'm'
sage: [l2b(((67 << 32) // golden_ratio + 1) + random_coeff * golden_ratio) for random_coeff in range(10)]
[b'm',
 b'\x9e7z\x1e',
 b'\x01<n\xf3\xcf',
 b'\x01\xda\xa6m\x80',
 b'\x02x\xdd\xe71',
 b'\x03\x17\x15`\xe2',
 b'\x03\xb5L\xda\x93',
 b'\x04S\x84TD',
 b'\x04\xf1\xbb\xcd\xf5',
 b'\x05\x8f\xf3G\xa6']
sage: [l2b(((16645487 << 32) // golden_ratio + 1) + random_coeff * golden_ratio) for random_coeff in range(10)]
[b'\x01\x9a\xf6\xe4',
 b'\x9f\xd2p\x95',
 b'\x01>\t\xeaF',
 b'\x01\xdcAc\xf7',
 b'\x02zx\xdd\xa8',
 b'\x03\x18\xb0WY',
 b'\x03\xb6\xe7\xd1\n',
 b'\x04U\x1fJ\xbb',
 b'\x04\xf3V\xc4l',
 b'\x05\x91\x8e>\x1d']

From the above we get a series of bytes and the equation is understood. We can retrieve the alphanumeric by making use of the same regex expression!. We can write a custom function for it:

from re import search as rsearch

def hash_forger(expected_hash_value:int)->str:
    '''
    By reversing the following algorithm: (key mod golden_ratio) * golden_ratio >> 32 = hash_value, we can get
    key = (hash_value << 32) // golden_ratio + 1 # This is an estimate as some accuracy is lost in the original equation
    '''
    expected_key = (expected_hash_value << 32) // golden_ratio + 1

    # Bruteforcing suitable usernames
    for brute_value in range(1000000):
        '''
        Using the relationship username = key mod golden_ratio, we can get
        username = (random value * golden_ratio + key)
        '''

        expected_username_value = (brute_value * golden_ratio + expected_key)
        if not rsearch(b"[^a-zA-Z0-9]",l2b(expected_username_value)):
            return l2b(expected_username_value).decode() # The value returned will allow us to circumvent the regex check

Testing it:

sage: hash_forger(67)
'm'
sage: hash_forger(16645487)
'04Jwk3'

We get values!

The solution Link to heading

From the above we can write a python script to do most of the work for us:

#!/usr/bin/python3
# Modules for import
from Crypto.Util.number import long_to_bytes as l2b, bytes_to_long as b2l, inverse
from pwn import *
from base64 import b64decode,b64encode
from sympy.ntheory import factorint as ps_and_qs
from re import search as rsearch


host,port = "94.237.62.149:56146".split(":")
if host == "":
    host = "localhost"

remote_conn = remote(host, int(port)) if args.REMOTE else process("./server.py")
GOLDEN_RATIO = golden_ratio = 2654435761
admin_username = "System_Administrator"

# Functions for solving challenge
hash_var = lambda key: (((key % GOLDEN_RATIO) * GOLDEN_RATIO) >> 32)
decoder = lambda user_input : int(base64.b64decode(user_input).decode())
product = lambda x,y: [y:=y*x1 for x1 in x][-1]

def hash_forger(expected_hash_value:int)->str:
    '''
    By reversing the following algorithm: (key mod golden_ratio) * golden_ratio >> 32 = hash_value, we can get
    key = (hash_value << 32) // golden_ratio + 1 # This is an estimate as some accuracy is lost in the original equation
    '''
    expected_key = (expected_hash_value << 32) // GOLDEN_RATIO + 1

    # Bruteforcing suitable usernames
    for brute_value in range(1000000):
        '''
        Using the relationship username = key mod golden_ratio, we can get
        username = (random value * golden_ratio + key)
        '''

        expected_username_value = (brute_value * golden_ratio + expected_key)
        if not rsearch(b"[^a-zA-Z0-9]",l2b(expected_username_value)):
            return l2b(expected_username_value).decode() # The value returned will allow us to circumvent the regex check

# Procedure for solving challenge
# Step 1: Retrieving the output in order to get the public key
log.info("Starting Stage 1: Retrieving the public key")

remote_conn.sendlineafter(b">> ",b"2")
remote_conn.recvuntil(b"equations:")
equations = eval(remote_conn.clean().decode().strip().split("\n")[0]) # We can fetch the equations and reverse it to get the hash of the modulus

'''
Using the understanding that:
(rnd * factor) mod golden_ration = value --> factor = (value * inverse(rnd, golden_ratio)) mod golden_ratio
'''

rnds = [int(value.split("=")[0].split(",")[1]) for value in equations]
factors = [(int(value.split("=")[-1]) * inverse(rnd,GOLDEN_RATIO)) % GOLDEN_RATIO for value,rnd in zip(equations,rnds)]
N_hash = product(factors,1)
log.info(f"Found hash of the modulus: {N_hash}")

remote_conn.sendline(f"{N_hash}".encode())

success_message = remote_conn.recvline_contains(b"Captcha")
if b"Captcha successful!" in success_message:
    success_message = remote_conn.recvline_contains(b"(e,N)")
    e,N = eval(success_message.split(b" = ")[-1])
    log.success(f"Stage 1 Completed successfully! -> Retrieved public key: {(e,N)}\n")
else:
    log.failure("Stage 1 failed!")
    exit()

# Step 2: Forging the respective hashes using prime factors of the hash of the admin username
log.info("Starting Stage 2: Forging the respective hashes...")
admin_token = hash_var(b2l(admin_username.encode()))
factors = [k**v for k, v in ps_and_qs(admin_token).items()]

log.info(f"Found prime factors of the admin token: {factors}")
forged_names = [hash_forger(factor) for factor in factors] # These names obey the regex check that exists and allows us to forge the hash for the factors of the admin username
log.info(f"Found valid forged names: {forged_names}")

'''
Remember the following:
m1 * m2 = admin_token
m1 ^ d mod N = forged_name1
m2 ^ d mod N = forged_name2

(forged_name1 * forged_name2) mod N = (admin_token ^ d) mod N
'''

signatures = []

# We send each factor and retrieve the signature
for forged_username in forged_names:
    remote_conn.sendline(b"0");remote_conn.sendline(forged_username.encode())
    remote_conn.recvuntil(b"token is ")

    token = eval(remote_conn.recvline().decode()).decode()
    signatures.append(decoder(token))

log.info(f"Found the respective signatures: {hex(signatures[0])},...")
admin_signature = product(signatures,1) % N
log.success(f"Found the admin signature: {hex(admin_signature)}")

# Step 3: Logging in as the admin and fetching the flag
log.info("Starting Stage 3: Logging in as the admin...")
remote_conn.sendline(b"1")
remote_conn.sendline(admin_username.encode());remote_conn.clean()
remote_conn.sendline(b64encode(str(admin_signature).encode()))

flag_message = remote_conn.recvline().decode().strip().split(" ")[-1]
if not args.REMOTE:
    flag = eval(flag_message).decode()
else:
    flag = flag_message

log.success(f"Found the flag: {flag}")
remote_conn.close()

Upon running (locally):

python3 sol.py
[*] Starting Stage 1: Retrieving the public key
[*] Found hash of the modulus: 1420777299
[+] Stage 1 Completed successfully! -> Retrieved public key: (65537, 17485640851729238233353910088521010670018740845038837807378465802891480243855911254421445692470330525017698694761424849717850212615307532593679757959997684997849590587706575433158945317455629723246596677536236407541382245089537729837583320289931281222723987020311904140188592769171770317204160985010102692448782602716357667692423793734486608401019872696461230212362223874573176248840107110047328116968321993250226102255749516233526640751348188096426521673637512331805351414039611423735573559072627775277509572923197543430665607765911984204021944609321555113956212531640151006941029828565185531984116175902954367945207)
[*] Starting Stage 2: Forging the respective hashes...
[*] Found prime factors of the admin token: [67, 16645487]
[*] Found valid forged names: ['m', '04Jwk3']
[*] Found the respective signatures: 0x26b0f985b12b1b9fb373f043e2bcd918e52a00ffed64306f6f5bf45d565417f37d6a8c88c082cdca03e13869bffc156c42db091a94ee1bcb34f5f0279781394becaff10b0882476b764256b71cd2d7ce42d45de74faa23f0096dc43d67c9ce9f47130b6d50e4edd437a0445386ac2fca3b8a7148ae6bd6180fb16a0c2e4504c38582c95599973229c2dd774c0e9b1276ee2218805b064a3188bf16e140debfe59daf5a99741bcaaa3e3a34e07ec224972c586b9210fbd9a3fe6508c1f3391b3f8ade4ba4c79d7d35bbdf565cf51165092672236b61f448cb8c3ca7865f859313d95bb9b24f0b78333bb44cf1e203e4e495853af2fb999a8f181d3496d55074a0,...
[+] Found the admin signature: 0x46cb26a62c9812b49f74f718caedf8067a851687c87179d9044a212f9c7f0abd4b5b886fd58c9fa457d2f27b1342ddfe325710fb4a00ef533bc27a81d416aa823f8c1ee4953884fe0cf143844da314fb2633e9d606503618f26586eaa658c9b31ee774ec6c73e18bfd6d36762b458707c964ec3203ddce6de5897484a4bd3e015e639b7675da0dad7a5b4537167dabf7559c7737b7bdb0c86bb4be550b4b30728e87a2d3ed10892feb778bb3f58cb06245e9e8feb9ec0008bc9bace3aa7c3580668c673fcf3b8278d14a2ed720a82c0dcd5a588cc07babaffb640e2ad45f9f8f692cfe2dc16b8fa74a86a1298fef2807bbc0bf0b9bd497625d06b963cb7d3766
[*] Starting Stage 3: Logging in as the admin...
[+] Found the flag: HTB{FAKE_FLAG_FOR_TESTING}

Running remotely:

[+] Opening connection to 83.136.254.53 on port 45916: Done
[*] Starting Stage 1: Retrieving the public key
[*] Found hash of the modulus: 1551684310
[+] Stage 1 Completed successfully! -> Retrieved public key: (65537, 23617070826033390757425723692527494939314844539186997285406601658643374068375139686142654056161698387679491466603162659399901199816689565001485276637830808746061285524319155211341133842055083907880539509627971226897371615175224020164454204124205714054370555373376439990090720212882743730052959863058181911385509219430537309131430817831668203600817246959349968603185039372229845148539071507795342031847119521803865344929748462695432892886437968548741219303684625520771055547680148832244507052247393286379995282851832562240942684643721111432658585930125297915333911527356904582757838477232458212717122364488797292081823)
[*] Starting Stage 2: Forging the respective hashes...
[*] Found prime factors of the admin token: [67, 16645487]
[*] Found valid forged names: ['m', '04Jwk3']
[*] Found the respective signatures: 0x24237ca6fe154d1c928320a3a4b152cfc3bc3de76becb00186d08e22b380f44842cacc6e3a20ee2d0445f5f9c89b5e851950c4aa4b30bb40651cf0b1268bf5acfe30228edf106f6d6d2d226ff24b3ba62fb3689e5fa8f100c53070058a2839c8250a82c5b0376905d604e8c49c4e1df4fa07dac9e7d3101513e31ce4e33ab75f6207be8b3360d1340d31476308bcf65d6918a510eca6e0330b84aa3a48e8044784d1195dd1cf05606ab99dddb6d4902a8911dbb4b2dd7c47f275975daa9c425de896c96c5ae102dd757185953200021dd31dd5ed08b5abdefba3cd4b3f998ffe0a77d225f5a75200f96dc5ff21fc8127aa528faf1fb9b8b0888294396ee56dd6,...
[+] Found the admin signature: 0xad7a4431638d2d48f6a669f351970a17b8e6817133808d909669e9ea237f55151b5282709c6c2258eab7e96f05c3a42b356bfebacffb687bcf662da1a6c6f154bba35b5e2b2290bff077da33d5f6ca152178c6da8156b9e3e721c7b810627ca0264d1983072fb6389d16ba3cc12ba905f1ae859c1e49d768b5551eaa7f75293698c4b4317ccf0bc5142b3177cb5f9c3e7e8e5e394cf580262b879d990329a8797fa02885c9348744cbdbf67a33b72416c4b450cb0b1146a3a8a4f5f9e8de777ddbacf2f2b6f21156bca5f75bf175650786bb404814e2578ebcba57b1b8aba15615692803cb91b817c0054e11a0877e43e6d1bbde8f6f0254d7c39a1238da92d7
[*] Starting Stage 3: Logging in as the admin...
[+] Found the flag: HTB{sm4ll_f4c7025_619_p206l3m5}
[*] Closed connection to 83.136.254.53 port 45916

We hence get the flag:

[+] Found the flag: HTB{sm4ll_f4c7025_619_p206l3m5}

Notes:

  • Originally the signing server above was vulnerable to a hash collision attack - this allowed us to sign another name which would give us the signature of H(admin_token) and this really made things easy.
  • Everything has been fully explained on the attack and since the H(admin_token) had small factors and hence allowed the attack to happen. A custom hash function is usually highly insecure and use of secure once should be implemented.

“When you change your thoughts, remember to also change your world.” —Norman Vincent Peale