Megalomaniac 2 — cryptohack

Description

Megalomaniac 2 — nc socket.cryptohack.org 13409

A client registers RSA-2048 crypto material and uploads an encrypted bundle. A separate "new login" flow performs an RSA-CRT decryption on attacker-supplied data. Recover the flag — and the hint suggests it can be done with a minimal number of queries.

English summary: The server's Client serializes its RSA-2048 private key (p, q, d, u) length-prefixed, AES-ECB-encrypts it under a master_key, and exposes the result as share_key_enc. The flag is encrypted with AES-ECB(SHA256(p_bytes || q_bytes)), so recovering the actual primes p and q is mandatory. A second flow, Client_new_login, takes attacker-controlled SID_enc, share_key_enc, and master_key_enc, performs an RSA-CRT decryption of SID_enc with the parsed key, and returns the plaintext with the last 16 bytes stripped. Maximum 4 logins.

Analysis

Registration material (revealed on connect)

auth_key_hashed = SHA256(auth_key)
master_key_enc  = AES-ECB(enc_key).encrypt(master_key)         # master_key = 16 random bytes
share_key_pub   = (n, e)
share_key_enc   = AES-ECB(master_key).encrypt(format_rsa_privkey())

enc_key is PBKDF2(PASS, SALT) with a 20-char random password and 8-byte random salt — unknown and uncrackable. We never learn enc_key or master_key.

Private-key serialization layout

format_rsa_privkey() concatenates, for each of p, q, d, u (with u = p⁻¹ mod q): a 2-byte big-endian length prefix followed by the big-endian bytes of the number, then PKCS#7-pads to 16 bytes. For RSA-2048 this is 656 bytes = 41 AES-ECB blocks. Approximate byte layout:

Field	Byte range	Block range
len+p	0..130	0..8
len+q	132..260	~8..16
len+d	262..518	~16..32
len+u	520..648	~32..40

The critical property: share_key_enc is AES-ECB, so each 16-byte ciphertext block decrypts independently. Corrupting one ciphertext block corrupts only the plaintext bytes of that block — and nothing else.

The login oracle (Client_new_login.login_step2)

self.master_key = self.cipher_enc.decrypt(master_key_enc)   # we control master_key_enc
self.cipher_master = AES.new(self.master_key, AES.MODE_ECB)
share_key = unpad(self.cipher_master.decrypt(share_key_enc), 16)  # we control share_key_enc
p, q, d, u = self.parse_rsa_privkey(share_key)
SID = self.RSA_CRT_decrypt(SID_enc, p, q, d, u)             # we control SID_enc
SID = SID[:-16]                                              # <-- last 16 bytes stripped
return SID

RSA_CRT_decrypt is textbook CRT recombination:

dp = d % (p - 1); dq = d % (q - 1)
mp = pow(ct, dp, p); mq = pow(ct, dq, q)
t = (mq - mp) % q; h = (t * u) % q
m = h * p + mp

Vulnerability

1. Replay → real-key oracle. We don't need enc_key or master_key. If we simply replay the original master_key_enc and share_key_enc, the server reconstructs the original master_key, decrypts the original serialized key, and parses the real (p, q, d, u). We now have a full RSA-CRT decryption oracle for the genuine private key.

2. ECB block shuffle → Bellcore CRT fault. Because share_key_enc is ECB, we can duplicate/shuffle a single ciphertext block in the q region (block index 9 worked). This corrupts the bytes of q (and therefore dq = d mod (q-1), the mod-q CRT branch) while the mod-p branch (p, dp, mp) stays correct. The recombined output then satisfies the classic Bellcore condition:

   m' ≡ m (mod p),   m' ≢ m (mod q)   ⇒   gcd(m' - m, n) = p
   

3. Obstacle: truncation. The oracle returns SID[:-16], throwing away the low 128 bits of every decryption. We can't directly compute m' or m.

4. Defeat truncation by choosing the plaintext. Pick a message M whose low 128 bits are zero (M -= M % 2**128) and query c = M^e mod n. The correct decryption is exactly M, fully reconstructable from the truncated output: m_correct = bytes_to_long(SID) << 128 == M. For the faulty query only the high bytes H_f are known, with an unknown low part x_f < 2^128:

   m' = (H_f << 128) + x_f
   

5. Recover x_f via linear Coppersmith, then factor. Since p | (m' - M):

   m' - M = ((H_f << 128) - M) + x_f = a + x_f   (a known, x_f < 2^128)
   

   So p divides a + x_f where x_f is small and p ≈ √n. This is a univariate linear Coppersmith / Howgrave-Graham small-root problem: find the root of f(x) = x + a modulo an unknown factor p ≈ N^0.5. The bound X < N^0.25 is trivially satisfied (X ≈ 2^128 ≪ N^0.25 ≈ 2^512), so a tiny lattice (m = 1..2) reduced with fpylll LLL plus a sympy polynomial-GCD extraction recovers x_f instantly. Then p = gcd(a + x_f, n), q = n / p.

6. Recover the flag. secret = SHA256(long_to_bytes(p) || long_to_bytes(q)), AES-ECB-decrypt the flag ciphertext (try both (p,q) orderings). The (p, q) order yielded the flag.

Total: 1 correct + 1 faulty decryption — comfortably under the 4-login cap, matching the "minimal number of queries" hint.

Solution

Step 1 — choose a plaintext with zero low 128 bits and get both oracle answers

# choose M with low 128 bits zero
M = bytes_to_long(get_random_bytes(255)) % n
M -= M % (1 << 128)
ct = pow(M, e, n)
cb = long_to_bytes(ct)

# ---- query 1: correct decryption (reconstruct M from the truncated high bytes) ----
c.send({"action": "wait_login"}); c.recv_json()
c.send({"action": "send_challenge",
        "SID_enc": cb.hex(),
        "share_key_enc": share_key_enc.hex(),      # original, replayed
        "master_key_enc": master_key_enc.hex()})    # original, replayed
sid_c = bytes.fromhex(c.recv_json()["SID"])
m_correct = bytes_to_long(sid_c) << 128
assert m_correct == M                               # truncation fully recovered

Step 2 — inject the Bellcore CRT fault by shuffling one ECB block of the q region

blocks = [share_key_enc[i:i+16] for i in range(0, len(share_key_enc), 16)]
for bi in [9, 10, 11, 12, 13, 14, 15, 33, 34, 35]:
    nb = blocks[:]
    nb[bi] = blocks[(bi + 1) % len(blocks)]          # duplicate next block over q region
    ske2 = b"".join(nb)
    c.send({"action": "wait_login"}); c.recv_json()
    c.send({"action": "send_challenge",
            "SID_enc": cb.hex(),
            "share_key_enc": ske2.hex(),             # faulty q -> faulty dq -> Bellcore
            "master_key_enc": master_key_enc.hex()})
    resp = c.recv_json()
    if "SID" not in resp:
        continue
    sid_f = bytes.fromhex(resp["SID"])
    H_f = bytes_to_long(sid_f)
    a = (H_f << 128) - M                              # p | (a + x_f), x_f < 2^128
    x0, p = linear_cop(a, n, 1 << 130, m=2)
    if p and n % p == 0:
        q = n // p
        break

Step 3 — linear Coppersmith small-root (attack_lib.py)

from fpylll import LLL, IntegerMatrix
from math import gcd
import sympy

_xs = sympy.symbols('x')

def linear_cop(a, N, X, m=2):
    """Find x0 with 0<=x0<X s.t. gcd(a+x0, N) is a nontrivial factor (~sqrt N)."""
    t = m
    f = [a, 1]

    def polymul(p, q):
        r = [0] * (len(p) + len(q) - 1)
        for i, pi in enumerate(p):
            for j, qj in enumerate(q):
                r[i + j] += pi * qj
        return r

    polys = []
    for i in range(m + 1):
        fi = [1]
        for _ in range(i):
            fi = polymul(fi, f)
        Np = N ** (m - i)
        polys.append([c * Np for c in fi])
    for kk in range(1, t + 1):
        fm = [1]
        for _ in range(m):
            fm = polymul(fm, f)
        polys.append([0] * kk + fm)
    ncols = m + t + 1
    B = IntegerMatrix(len(polys), ncols)
    for r, pp in enumerate(polys):
        for c in range(ncols):
            B[r, c] = (pp[c] if c < len(pp) else 0) * (X ** c)
    LLL.reduction(B)
    rows = []
    for ridx in range(min(len(polys), 3)):
        row = [B[ridx, c] // (X ** c) for c in range(ncols)]
        if any(row):
            rows.append(row)
    P = [sympy.Poly(sum(int(cf) * _xs ** i for i, cf in enumerate(rw)), _xs) for rw in rows]
    # recover the integer root via pairwise polynomial GCD
    cand_roots = set()
    for i in range(len(P)):
        for j in range(i + 1, len(P)):
            g = sympy.Poly(sympy.gcd(P[i], P[j]), _xs)
            if g.degree() == 1:
                c1, c0 = g.all_coeffs()
                if int(c1) != 0 and (-int(c0)) % int(c1) == 0:
                    cand_roots.add(-int(c0) // int(c1))
    try:
        for r in sympy.real_roots(P[0]):
            if r.is_real:
                cand_roots.add(int(round(float(r))))
    except Exception:
        pass
    for x0 in cand_roots:
        for cand in range(x0 - 2, x0 + 3):
            if cand < 0:
                continue
            gg = gcd(a + cand, N)
            if 1 < gg < N:
                return cand, gg
    return None, None

Step 4 — derive the flag key and decrypt

for (a_, b_) in [(p, q), (q, p)]:
    secret = hashlib.sha256(long_to_bytes(a_) + long_to_bytes(b_)).digest()
    pt = AES.new(secret, AES.MODE_ECB).decrypt(enc_flag)
    if b"crypto{" in pt:
        print("FLAG:", pt)
        break