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), ...]}

# Compute multiples of n
candidates = [sigs[a] * sigs[b] - prod_sigs[(a,b)] for (a,b) in products]

# GCD to recover n
n = gcd(candidates[0], candidates[1], ...)

# Remove small prime factors
for p in small_primes:
    while n % p == 0:
        n //= p

Step 2: Forge admin signature via blinding

Since to_sign is prime and we know n, we decompose the target:

a = 2
b = to_sign * pow(2, -1, n) % n  # b = to_sign / 2 mod n
# a * b ≡ to_sign (mod n)
# Neither a nor b equals to_sign, so server will sign both

Then forge:

forged_sig = (sign(2) * sign(b)) % n

Step 3: Submit forged signature

Send to_sign and forged_sig to the verify endpoint to get the flag.

Full Solve Script

from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime
import math

HOST = "154.57.164.83"
PORT = 31004

to_sign = bytes_to_long(b"Username: Admin, Access code: CryptoBestCategoryF3")

def connect():
    r = remote(HOST, PORT)
    r.recvuntil(b"public key!")
    return r

def sign_msg(r, msg_int):
    r.recvuntil(b"Enter your option: ")
    r.sendline(b"1")
    r.recvuntil(b"Enter your message to be signed in hex: ")
    msg_hex = long_to_bytes(msg_int).hex()
    r.sendline(msg_hex.encode())
    line = r.recvline().decode().strip()
    if "cannot sign" in line.lower():
        return None
    sig = int(line.split(": ")[-1])
    return sig

def verify_msg(r, msg_int, sig_int):
    r.recvuntil(b"Enter your option: ")
    r.sendline(b"2")
    r.recvuntil(b"Enter your message in hex: ")
    r.sendline(long_to_bytes(msg_int).hex().encode())
    r.recvuntil(b"Enter your signature in hex: ")
    r.sendline(long_to_bytes(sig_int).hex().encode())
    line = r.recvline().decode().strip()
    return line

r = connect()

# === Step 1: Recover n ===
msgs = [2, 3, 5, 7, 11, 13]
sigs = {}
for m in msgs:
    sigs[m] = sign_msg(r, m)

products = [(2, 3), (2, 5), (3, 5), (2, 7), (3, 7), (5, 7), (2, 11), (2, 13)]
prod_sigs = {}
for a, b in products:
    prod_sigs[(a, b)] = sign_msg(r, a * b)

candidates = []
for (a, b), s_ab in prod_sigs.items():
    diff = sigs[a] * sigs[b] - s_ab
    if diff != 0:
        candidates.append(abs(diff))

n = candidates[0]
for c in candidates[1:]:
    n = math.gcd(n, c)

# Clean small factors
for small_prime in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
    while n % small_prime == 0:
        n //= small_prime

log.info(f"Recovered n ({n.bit_length()} bits)")

# === Step 2: Forge admin signature via blinding ===
a = 2
b = (to_sign * pow(2, -1, n)) % n
sig_b = sign_msg(r, b)
forged_sig = (sigs[2] * sig_b) % n

log.info(f"Forged signature computed")

# === Step 3: Submit to get flag ===
result = verify_msg(r, to_sign, forged_sig)
log.success(result)

r.close()

Theory: Why Hashing Matters

In secure RSA signature schemes (e.g., PKCS#1 v1.5, PSS), the message is hashed before signing: sign(H(m)). This destroys the multiplicative homomorphism because H(a*b) != H(a) * H(b). Without hashing, RSA signatures are trivially forgeable via chosen-message attacks.

References

• RSA Blinding Attack (Wikipedia)
• Textbook RSA is not CMA-secure