ReMeeting the Wheel - HackTheBox Challenge Writeup

Challenge Information

Description

While Alice was daydreaming, she thought of using RSA to transfer an AES key for faster encryption, what an innovative idea! However, Bob warned her that if she made a mistake, Eve could potentially split the AES key into two equal-sized pieces. Would it cause any trouble?

The flavor text is the whole hint: Alice wraps an AES key in RSA, and that AES key is secretly constructed as a product of two roughly-equal-sized factors. The challenge is testing whether unpadded (“textbook”) RSA leaks enough structure to recover a multiplicatively-composed secret.

Solution

Artifact recovery

The staged challenge directory had a 0-byte source.py and no output.txt at all — a known failure mode where challenge staging silently produces empty files. Checking the original archive directly confirmed the real content was intact:

unzip -l /out/a12c7354-8c66-4ead-b5da-c90b70519973.zip
# source.py   1748 bytes
# output.txt   952 bytes

Non-zero listed sizes meant the zip itself was fine — it was just password-protected, and staging had extracted empties without the password. Re-extracting with the standard HTB archive password fixed it:

unzip -o -P hackthebox a12c7354-8c66-4ead-b5da-c90b70519973.zip

The vulnerability

Reading source.py revealed the key-generation logic:

class AESGen:
    def __init__(self, bits):
        key1 = randint(1 << bits, 1 << (bits + 1))
        key2 = randint(1 << bits, 1 << (bits + 1))
        self.k = key1 * key2
        # self.k is used to derive the actual AES key
        self.key = sha256(str(self.k).encode()).digest()

# ...
enc_aes_key = rsa.encrypt(k)   # textbook RSA, no OAEP/PKCS1 padding

Two independent problems stack here:

1. The AES key isn’t random — it’s a product. AESGen(20) picks key1 and key2 each uniformly from [2^20, 2^21), then sets k = key1 * key2. That makes k a 42-bit number, but crucially not a uniformly random 42-bit number — it factors into two ~20-bit pieces.
2. RSA encryption of k is unpadded. c = k^e mod n with no OAEP/PKCS1 padding, which means RSA’s multiplicative homomorphism is preserved:

c = k^e mod n
  = (key1 · key2)^e mod n
  = key1^e · key2^e mod n

Because the ciphertext itself splits into a product of two independently-computable terms, this is a textbook Boneh–Joux–Nguyen meet-in-the-middle setup. Instead of brute-forcing k across its full 2^42 search space, the two ~2^20 factor spaces can be attacked independently and joined via a hash table — collapsing the work to roughly 2 × 2^20 operations.

Key Steps

1. Recover the artifacts from the password-protected zip

unzip -l /out/<uuid>.zip                 # confirm non-zero sizes -> it's just encrypted
unzip -o -P hackthebox /out/<uuid>.zip   # extract with the standard HTB zip password
cat output.txt                           # -> n, e, enc_aes_key, enc_secret (ciphertexts)

2. Build the meet-in-the-middle table and search

import gmpy2
from gmpy2 import mpz, invert

# RSA public params and ciphertext from output.txt
n = mpz(0x...)          # RSA modulus
e = mpz(0x...)          # RSA public exponent
c = mpz(0x...)          # enc_aes_key: k^e mod n

LO, HI = 1 << 20, 1 << 21   # bounds each factor was drawn from

# --- forward table: key2 -> key2^e mod n ---
# keyed on a 64-bit truncation of the group element to keep the
# ~1M-entry table around ~60MB instead of ~400MB
table = {}
for key2 in range(LO, HI):
    val = gmpy2.powmod(key2, e, n)
    table[int(val) & ((1 << 64) - 1)] = key2

# --- meet in the middle: for each key1, check if c * inv(key1^e) lands in the table ---
found = None
for key1 in range(LO, HI):
    val = (c * invert(gmpy2.powmod(key1, e, n), n)) % n
    trunc = int(val) & ((1 << 64) - 1)
    if trunc in table:
        key2 = table[trunc]
        # re-verify on the full (non-truncated) value to rule out a
        # collision from the 64-bit truncation
        if gmpy2.powmod(key1, e, n) * gmpy2.powmod(key2, e, n) % n == c:
            found = (key1, key2)
            break

key1, key2 = found
k = key1 * key2
print(key1, key2, k)

This ran in ~12 seconds and hit:

key1 = 1401735
key2 = 1997695
k    = 2800239000825   # 42-bit product, matches the source's internal assert

3. Rebuild the AES key and decrypt the secret

from hashlib import sha256
from Crypto.Cipher import AES

aes_key = sha256(str(k).encode()).digest()
cipher = AES.new(aes_key, AES.MODE_ECB)   # or whatever mode source.py used
flag = cipher.decrypt(bytes.fromhex(enc_secret_hex))
print(flag)   # HTB{REDACTED}

Tools Used

• Python 3 with gmpy2 — fast modular exponentiation/inversion for the meet-in-the-middle search
• pycryptodome — AES decryption once the key material was recovered
• unzip — recovering the password-protected challenge archive
• hashlib — reproducing the sha256(str(k)) AES key derivation

Key Learnings

• Never derive a symmetric key from a value with exploitable algebraic structure. k = key1 * key2 looks like a big random number, but a product of two bounded factors is far weaker than a uniformly random value of the same bit length — its structure is exactly what an attacker needs.
• Unpadded RSA is multiplicative, and that’s dangerous whenever the plaintext has structure. Enc(a·b) = Enc(a)·Enc(b) mod n under textbook RSA. Real-world padding schemes (OAEP) exist precisely to destroy this property.
• Meet-in-the-middle turns O(2^n) into O(2^(n/2)) whenever a value splits into two independently-searchable halves. Recognizing that c factored the same way k did was the key insight — once seen, it’s a standard hash-table join rather than a brute force.
• Truncate table keys to control memory, but always re-verify the full value on a hit to rule out truncation collisions before trusting the result.
• Check the original archive before trusting a staged extraction. A 0-byte file after staging doesn’t always mean the source is broken — it can just mean the archive is encrypted and the extractor silently failed.