Mystery Box -- HackTheBox

Description

"They released this new mystery box thing to modify messages or something, but i'm sure my signing server will be fine."

The server generates a 1024-bit RSA key (two 512-bit primes) with a 128-bit prime public exponent e. It offers two operations:

1. Sign -- sign any message, but refuses to sign the admin message directly
2. Verify -- verify a message+signature pair; if the message is the admin message and signature is valid, prints the flag

The admin message is to_sign = bytes_to_long(b"Username: Admin, Access code: CryptoBestCategoryF3") (asserted to be prime).

Critical detail: the server does NOT reveal the public key (n, e).

Analysis

Vulnerability: Textbook RSA without Hashing

The server uses raw RSA signatures: sign(m) = m^d mod n, verify(m, s) = (s^e mod n == m). There is no hash applied before signing. This makes RSA multiplicatively homomorphic:

sign(a) * sign(b) = a^d * b^d = (a*b)^d = sign(a*b)  (mod n)

This means if we can sign two messages whose product equals to_sign mod n, we can forge the admin signature by multiplying their individual signatures.

Challenge: Unknown Modulus n

The server doesn't reveal n or e. However, we can recover n using the homomorphic property. For any messages a, b:

sign(a) * sign(b) - sign(a*b) ≡ 0  (mod n)

So sign(a) * sign(b) - sign(a*b) is a multiple of n. Taking the GCD of several such multiples recovers n.

Solution

Step 1: Recover n via GCD

Sign several small primes and their products:

# Sign individual messages
sigs = {m: sign(m) for m in [2, 3, 5, 7, 11, 13]}

# Sign products
prod_sigs = {(a,b): sign(a*b) for (a,b) in [(2,3), (2,5), (3,5), (2,7), ...]}

...