Time Capsule

1. Challenge Overview

Summary. The service implements textbook RSA encryption with a public exponent of e = 5. It reuses the same plaintext (the flag) for every encryption while generating a fresh 1024-bit modulus each time. Collecting two ciphertexts and combining them with the Chinese Remainder Theorem (CRT) recovers m^5 exactly, after which an integer 5th root yields the flag. No factoring is required.

2. Provided Source Code

from Crypto.Util.number import bytes_to_long, getPrime
import socketserver
import json

FLAG = b'[REDACTED]'

class TimeCapsule():
    def __init__(self, msg):
        self.msg = msg
        self.bit_size = 1024
        self.e = 5

    def _get_new_pubkey(self):
        while True:
            p = getPrime(self.bit_size // 2)
            q = getPrime(self.bit_size // 2)
            n = p * q
            phi = (p - 1) * (q - 1)
            try:
                pow(self.e, -1, phi)
                break
            except ValueError:
                pass
        return n, self.e

    def get_new_time_capsule(self):
        n, e = self._get_new_pubkey()
        m = bytes_to_long(self.msg)
        m = pow(m, e, n)
        return {"time_capsule": f"{m:X}", "pubkey": [f"{n:X}", f"{e:X}"]}

def challenge(req):
    time_capsule = TimeCapsule(FLAG)          # <-- same msg reused
    while True:
        try:
            req.sendall(b'Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) ')
            msg = req.recv(4096).decode().strip().upper()
            if msg == 'Y' or msg == 'YES':
                capsule = time_capsule.get_new_time_capsule()  # <-- fresh n each time
                req.sendall(json.dumps(capsule).encode() + b'\n')
            elif msg == 'N' or msg == "NO":
                req.sendall(b'Thank you, take care\n')
                break
            else:
                req.sendall(b'I\'m sorry I don\'t understand\n')
        except:
            return

3. Vulnerability Analysis

Three independent design choices combine into a complete break:

1. Small public exponent — self.e = 5. The code even guards against an invalid e (it regenerates p,q until 5 is invertible mod phi(n)), which means the authors knew e was small and went out of their way to keep it small and usable.

2. Message reuse — time_capsule = TimeCapsule(FLAG) is instantiated once, before the loop. Every capsule encrypts the identical plaintext m = bytes_to_long(FLAG).

3. Fresh modulus per capsule — _get_new_pubkey() draws new p, q on every call, so each response is: c_i = m^5 (mod n_i), with distinct n_i

The flag is short (~35 bytes → m < 2^280), therefore m^5 < 2^1400. The product of just two 1024-bit moduli is about 2^2048 > 2^1400, so m^5 never actually wraps around the combined modulus. This is exactly the precondition for Håstad's broadcast attack.

4. Exploitation

4.1 Reconnaissance / Interaction

Connected to the service and sent Y repeatedly, harvesting (c_i, n_i, e=5) tuples. The server prompt is not newline-terminated (... (Y/n) with a trailing space, no \n), so a robust collector was used that reads by availability and regex-extracts each JSON object rather than assuming line framing.

Collected 8 capsules, e.g.:

[0] n=A1B06CB0549C…  c=358FD1DD78B6…
[1] n=967692604653…  c=339A12114841…
[2] n=9D41802366A7…  c=92A922BEBA70…
[3] n=8BD3CD1A52EF…  c=22A5D8433036…
…
[7] n=CBCFB49506E5…  c=77273E05F268…

4.2 Precondition checks

• e = 5 confirmed from the pubkey field.
• Pairwise gcd(n_i, n_j) == 1 for all 8 moduli — they are coprime, so CRT applies cleanly.

4.3 Chinese Remainder Theorem

Combined ciphertexts with the standard CRT (using pow(Mi, -1, m) for modular inverses):

M ≡ c_1 (mod n_1)
M ≡ c_2 (mod n_2)

Because m^5 < n_1 · n_2, the CRT result M equals the true integer m^5 (not merely m^5 mod N).

4.4 Integer 5th root

Took the exact integer 5th root of M via binary search (since M is a perfect 5th power). Verified correctness by re-encrypting: pow(m, 5, n_i) == c_i for every collected pair.

4.5 Results

e   = 5
num capsules = 8
m^e = 60222703216991723400896935611290377369451090117748355626588188127748777887605199005043629107938717425146115720040534532878250344911478543476035962359514021177352577862197382575981345584203655606236078211695991372921996113614939800630843735306107095629315859429285627820465793608409357274153378888592522535530765683506676500860162124152806217549586334803871530328776024103189374825571031181368031122915388013651885836012756786675021405847977357
m   = 35970961710345507498932045278388335485301801627259486491503367005922441822236783551931517
flag = [REDACTED]

5. Flag

[REDACTED]

6. Step-by-Step Walkthrough

# 1) Connect and collect capsules (send 'Y' several times)
python collect3.py        # -> saves capsules.json (8 x {time_capsule, pubkey})

# 2) Recover flag via Håstad broadcast
python solve.py           # CRT + integer 5th root -> [REDACTED]

Collector (collect3.py) — key detail is the non-newline-terminated prompt, handled by availability reads + JSON regex:

for i in range(8):
    s.sendall(b"Y\n")
    time.sleep(0.4)
    txt = recv_all().decode(errors="replace")
    for m in re.finditer(r'\{[^{}]*\}', txt):
        obj = json.loads(m.group())
        capsules.append(obj)

Solver (solve.py) — core logic:

def crt(residues, moduli):
    M = 1
    for m in moduli: M *= m
    x = 0
    for (r, m) in zip(residues, moduli):
        Mi = M // m
        inv = pow(Mi, -1, m)
        x += r * Mi * inv
    return x % M

def iroot(n, k):
    lo, hi = 0, 1 << ((n.bit_length() + k - 1) // k + 1)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid ** k <= n: lo = mid
        else:              hi = mid - 1
    return lo

M = crt(cs, ns)                 # m^5 as an integer
m = iroot(M, e)                 # exact 5th root
flag = m.to_bytes((m.bit_length()+7)//8, "big")

7. Why It Worked

• Small e + small m ⇒ m^e stays below the combined modulus, so CRT recovers the exact power rather than a residue class.
• Message reuse ⇒ all ciphertexts are encryptions of the same m, the essential requirement for the broadcast attack.
• Coprime moduli ⇒ CRT has a unique, computable solution.

8. Mitigations

• Use a proper padding scheme (OAEP / PKCS#1 v1.5) — textbook RSA is never safe in practice.
• Use a standard exponent (e = 65537) and, more importantly, do not reuse a message across multiple public keys.
• Randomize per-encryption (e.g., OAEP's random nonce) so identical plaintexts never produce identical m.

9. Artifacts