Megalomaniac 3 — cryptohack

Description

Megalomaniac 3 - Now it is about time to recover the actual data uploaded by a user!

nc socket.cryptohack.org 13410

This is the final part of CryptoHack's "Megalomaniac" series, reproducing the real-world MEGA "Malleable Encryption Goes Awry" (mega-awry.io) Plaintext Recovery attack. The goal is to recover a file that a user encrypted under a per-file node_key, where node_key itself is AES-ECB-encrypted under the user's master key.

Analysis

Key hierarchy (per connection)

The server derives enc_key/auth_key from a password via PBKDF2(SHA512, 1000 iters) and builds the following encrypted material, sent in the banner:

• master_key = random 16 bytes; master_key_enc = AES-ECB(enc_key, master_key)
• RSA-2048 share key. The private key is serialized into a blob: format = len(p)|p | len(q)|q | len(d)|d | len(u)|u | pad16, each len is 2 bytes big-endian and u = p^{-1} mod q. share_key_enc = AES-ECB(master_key, privkey_blob)
• node_key = random 16 bytes; node_key_enc = AES-ECB(master_key, node_key); file_enc = AES-ECB(node_key, pad(FILE))
• Leak: the banner discloses the prime p of the share key (recovered_shared_key = (n, e, p)), so the full RSA private key is recoverable: q = n//p, d = e^{-1} mod (p-1)(q-1), u = inverse(p, q).

The login oracle (Client_new_login.login_step2)

Attacker-controlled inputs: SID_enc, share_key_enc, master_key_enc. It:

1. master_key = AES-ECB-dec(enc_key, master_key_enc)
2. priv = unpad(AES-ECB-dec(master_key, share_key_enc)); parse (p, q, d, u)
3. SID = RSA_CRT_decrypt(SID_enc, p, q, d, u); return SID[:-16] (drops the low 128 bits)

RSA-CRT internals: dp=d%(p-1); dq=d%(q-1); mp=c^dp%p; mq=c^dq%q; t=(mq-mp)%q; h=u*t%q; m=h*p+mp.

The vulnerability — AES-ECB has no integrity

AES-ECB is malleable: any 16-byte ciphertext block can be cut and pasted into another ciphertext, and on decryption it deterministically yields that block's plaintext under the same key. Both share_key_enc (the privkey blob) and node_key_enc are AES-ECB under the same master key. So we can splice the node_key_enc block into the u-region of share_key_enc: when the client decrypts the blob it gets AES-ECB-dec(master_key, node_key_enc) = node_key planted inside the parsed u' field.

Solution

Step 1 — chosen SID makes the oracle leak u'

Choose the RSA-encrypted SID so the plaintext is SID = u * p. In RSA-CRT:

• mp = (u*p) mod p = 0
• mq = (u*p) mod q = 1 (because u = p^{-1} mod q)
• t = (1 - 0) mod q = 1, h = u' * 1 mod q = u', so m' = h*p + mp = u' * p

where u' is whatever the parsed u field is — i.e. the spliced block. Keep the real master_key_enc unchanged so the genuine master key decrypts the blob; only share_key_enc is tampered.

Step 2 — splice and read back

The oracle returns long_to_bytes(m')[:-16]. Undo the truncation with m' ≈ received << 128, then u' = m' // p. Render u' to the full 128-byte u-field width and extract the injected 16-byte block.

Offsets for 2048-bit RSA: privkey blob = 648 bytes (+8 pad = 656). u value starts at byte offset off_u = 520. The first 16-byte block boundary inside u is byte 528 (block index 33), so inject_pos = 528 - 520 = 8 and node_key = u_prime_bytes[8:24]. The lost low 128 bits don't matter because the injected block sits in the high bytes of u'.

Step 3 — decrypt the file

FILE = AES-ECB-dec(node_key, file_enc) → Congratulations! ... The flag is : crypto{...}.

Protocol flow (single connection — all state is per-connection)

1. Read banner; parse JSON lines for master_key_enc, (n,e), share_key_enc, node_key_enc, file_enc, leaked p.
2. Send {"action":"wait_login"} (sets LOGIN state, returns auth_key_hashed). Note the Login attempt from Alice: text precedes the JSON line.
3. Send {"action":"send_challenge","SID_enc":hex,"share_key_enc":hex(modified),"master_key_enc":hex}.
4. Receive {"SID": hex}, recover node_key, decrypt the file.

#!/usr/bin/env python3
import socket, json, re
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from Crypto.Cipher import AES

HOST, PORT = "socket.cryptohack.org", 13410

def fmt(num):                       # len(2B big-endian) | bytes
    nb = long_to_bytes(num)
    return long_to_bytes(len(nb), 2) + nb

s = socket.socket(); s.connect((HOST, PORT)); s.settimeout(8)

# --- read banner (3 JSON lines among prose) ---
buf = b""
while b'"share_key"' not in buf:
    try: buf += s.recv(4096)
    except socket.timeout: break
lines = [l for l in buf.decode(errors="replace").splitlines() if l.strip().startswith("{")]
material, file_upload, recovered = map(json.loads, lines[:3])

master_key_enc = bytes.fromhex(material["master_key_enc"])
share_key_enc  = bytes.fromhex(material["share_key_enc"])
n, e           = material["share_key_pub"]
node_key_enc   = bytes.fromhex(file_upload["node_key_enc"])
file_enc       = bytes.fromhex(file_upload["file_enc"])
_, _, p        = recovered["share_key"]

# --- recover full RSA private key from leaked prime ---
q = n // p; assert p * q == n
d = inverse(e, (p - 1) * (q - 1))
u = inverse(p, q)                   # u*p == 1 (mod q)

# --- locate the u-region and the first block boundary inside it ---
off_u  = len(fmt(p)) + len(fmt(q)) + len(fmt(d)) + 2     # = 520 for 2048-bit
u_len  = len(long_to_bytes(u))                           # = 128
block_start = ((off_u + 15) // 16) * 16                  # = 528
inject_pos  = block_start - off_u                        # = 8
assert block_start + 16 <= off_u + u_len

# --- splice node_key_enc into the u block of share_key_enc ---
ske = bytearray(share_key_enc)
ske[block_start:block_start + 16] = node_key_enc
share_key_enc_mod = bytes(ske)

# --- chosen SID = u*p so decrypted m' = u'*p ---
SID_enc = long_to_bytes(pow(u * p, e, n))

def sendjson(o): s.sendall((json.dumps(o) + "\n").encode())
def wait_for(key, t=20):
    s.settimeout(t); b = b""
    while True:
        try: c = s.recv(4096)
        except socket.timeout: break
        if not c: break
        b += c
        for ln in b.decode(errors="replace").splitlines():
            ln = ln.strip()
            if ln.startswith("{") and key in ln:
                try: return json.loads(ln)
                except Exception: pass
    raise RuntimeError("no json with %r" % key)

sendjson({"action": "wait_login"}); wait_for("auth_key_hashed")
sendjson({"action": "send_challenge",
          "SID_enc": SID_enc.hex(),
          "share_key_enc": share_key_enc_mod.hex(),
          "master_key_enc": master_key_enc.hex()})
out = wait_for("SID")

# --- undo [:-16] truncation, recover u', read node_key ---
m_prime = bytes_to_long(bytes.fromhex(out["SID"])) << 128
u_prime_bytes = (m_prime // p).to_bytes(u_len, "big")
node_key = u_prime_bytes[inject_pos:inject_pos + 16]

file_dec = AES.new(node_key, AES.MODE_ECB).decrypt(file_enc)
print(re.search(rb"crypto\{[^}]*\}", file_dec).group().decode())
s.close()