Megalomaniac 1 — cryptohack

Description

In June 2022, a team of researchers from the Applied Crypto Group at ETH Zurich discovered a few flaws in the E2E cryptographic architecture of MEGA. This series of challenges puts you in the shoes of a Mega cloud storage server, interacting with clients logging into their personal storage. The implementation is close to the real one but simplified. First, recover the user's ShareKey! Connect at socket.cryptohack.org 13408.

Resource: https://mega-awry.io/ (MEGA: Malleable Encryption Goes Awry, eprint 2022/959). The relevant academic attack is the Backendal-Haller-Paterson RSA Key Recovery Attack.

We play the role of a malicious MEGA cloud server. A client logs in and the server holds the client's RSA "ShareKey" private key — but only in an AES-ECB-encrypted, unauthenticated blob. The goal is to recover that RSA private key (and, as a bonus, the flag).

This is a reimplementation of the real-world MEGA Malleable Encryption Goes Awry attack (Backendal–Haller–Paterson, eprint 2022/959): a single garbled ECB block turns the login flow into a partial RSA decryption oracle that leaks the prime q one bit at a time.

Analysis

Material the server sends on connect

• auth_key_hashed
• master_key_enc = AES-ECB(enc_key, master_key)
• share_key_pub = (n, e) (RSA public key)
• share_key_enc = AES-ECB(master_key, format_rsa_privkey())

How the private key blob is serialized

format_rsa_privkey() concatenates length-prefixed big-endian integers:

[len(p)(2B) ‖ p] ‖ [len(q)(2B) ‖ q] ‖ [len(d)(2B) ‖ d] ‖ [len(u)(2B) ‖ u]

then PKCS7-pads to a 16-byte boundary. Here u = p^-1 mod q is the CRT coefficient (pycryptodome RSA.u).

For a 2048-bit key:

field	size	byte range
p	2 + 128	0..129
q	2 + 128	130..259
d	2 + 256	260..517
u	2 + 128	518..647

Total 648 bytes → padded to 656 bytes = 41 AES blocks. u lives in bytes 518..647 (blocks 32..40); block 40 holds the final 8 u bytes plus 8 PKCS7 padding bytes.

Login protocol (the oracle surface)

• wait_login → creates a fresh login object, returns auth_key_hashed.
• send_challenge → takes attacker-supplied SID_enc, share_key_enc, master_key_enc and does:
  1. master_key = AES-ECB-decrypt(enc_key, master_key_enc)
  2. share_key = unpad(AES-ECB-decrypt(master_key, share_key_enc))
  3. parse p, q, d, u (asserts exactly 4 elements)
  4. SID = RSA_CRT_decrypt(SID_enc, p,q,d,u); returns SID[:-16] (last 16 bytes stripped).

RSA_CRT_decrypt:

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

The core flaw — no integrity on the ECB key blob

share_key_enc is AES-ECB with no MAC. By the ECB property, flipping bytes of one ciphertext block corrupts exactly that 16-byte plaintext block and leaves all other blocks intact.

If we flip a block strictly inside the u field but not the final padding block, we garble u → u' while keeping p, q, d correct and keeping PKCS7 padding valid — so unpad succeeds and login does not error. We used block index 35 (bytes 560..575), safely in the interior of u.

Pitfall: corrupting block 40 (the last block) or anything past the end of u breaks unpad, and the server returns {"error": ...} instead of a SID. The corrupted block must be inside u's interior; keeping it well inside also protects against off-by-one prime byte-lengths (127 vs 128 bytes).

The resulting 1-bit comparison oracle

Pick a probe integer x and send SID_enc = x^e mod n. With a garbled u':

• If x < q: mq = x mod q = x and mp = x mod p = x, so t = (mq - mp) % q = 0, hence h = 0 and m = mp = x. Result is exactly x, independent of the wrong u'.
• If x >= q: t != 0, so h = (t * u') % q uses the wrong coefficient and m = h*p + mp is a huge (~2047-bit) garbled value, essentially never == x.

The server returns SID = long_to_bytes(m)[:-16]. Define expected(x) = bytes_to_long(long_to_bytes(x)[:-16]). Then:

• returned == expected(x) ⇒ m == x ⇒ x < q
• returned != expected(x) ⇒ x >= q

That's a clean 1-bit-per-query oracle for the value of the prime q.

Solution

Binary-search q over [2^1023, 2^1024 - 1]. Each query is one login round-trip (wait_login + send_challenge) reused over a single TCP connection. Convergence in 1023 queries; afterwards up == q exactly (verified by n % q == 0). Then p = n // q and d = e^-1 mod (p-1)(q-1) — the full ShareKey is recovered.

Condensed solver

from Crypto.Util.number import long_to_bytes, bytes_to_long
import socket, json, hashlib
from Crypto.Cipher import AES

# 1) connect, read banner JSON: share_key_pub=(n,e), master_key_enc, share_key_enc
n, e = share_key_pub
mke  = master_key_enc           # hex, sent back unchanged
ske  = bytearray(bytes.fromhex(share_key_enc))

# 2) garble u: flip an interior block of u (block 35 = bytes 560..575)
for i in range(560, 576):
    ske[i] ^= 0xff
ske_hex = ske.hex()

def oracle(x):
    sid_enc = long_to_bytes(pow(x, e, n)).hex()
    send({"action": "wait_login"})                  # fresh login object
    r = send({"action": "send_challenge",
              "SID_enc": sid_enc,
              "share_key_enc": ske_hex,
              "master_key_enc": mke})
    return bytes_to_long(bytes.fromhex(r["SID"]))    # may KeyError on {"error":...}

def expected(x):
    return bytes_to_long(long_to_bytes(x)[:-16])

# 3) binary search the prime q
low, up = 1 << 1023, (1 << 1024) - 1
while up - low > 1:
    mid = (low + up) // 2
    if oracle(mid) == expected(mid):   # mid < q
        low = mid
    else:                              # mid >= q
        up = mid

q = up
assert n % q == 0
p = n // q
d = pow(e, -1, (p - 1) * (q - 1))      # full RSA private key (ShareKey)

# 4) bonus: decrypt the flag (fetch enc_flag on the SAME connection)
#    secret = SHA256(long_to_bytes(p) + long_to_bytes(q)); try both orders.
secret = hashlib.sha256(long_to_bytes(q) + long_to_bytes(p)).digest()
flag = AES.new(secret, AES.MODE_ECB).decrypt(enc_flag)
print(flag)

Recovering the flag

get_encrypted_flag returns AES-ECB(secret, pad(FLAG)) with secret = SHA256(long_to_bytes(p) + long_to_bytes(q)). The encrypted flag must be fetched on the same connection whose key was attacked (each connection regenerates a fresh RSA key; the FLAG constant itself is static). In our solve the working hash order was (q, p) — try both.

Recovered values

n, e, p, q, d are saved in tasks/cryptohack/megalomaniac_1/recovered_key.txt (2048-bit; the giant integers are omitted here). Verification: n % q == 0, p == n // q, and (e * d) % ((p-1)*(q-1)) == 1.

Key Indicators / Lessons

Use this technique when:

• An RSA private key is stored AES-ECB-encrypted with no MAC/integrity and serialized as length-prefixed p, q, d, u (MEGA-style key blob).
• CRT decryption uses the CRT coefficient u = p^-1 mod q and the result is partially returned to the client (here SID[:-16]), giving a comparison oracle.
• You control one of the ECB ciphertexts — flip a single interior block to corrupt exactly one field (u) while keeping the rest (p, q, d) and padding intact. Corrupting the last/padding block instead just breaks unpad.
• The x < q vs x >= q behaviour (t = (mq - mp) % q = 0 when x < q) yields a 1-bit oracle; binary-search the 1024-bit prime in ~1023 queries.

Practical gotchas:

• Keep the corrupted block well inside u to be robust to off-by-one prime byte-lengths (127 vs 128 bytes) and to avoid touching the padding block.
• Each TCP connection regenerates a fresh RSA key — attack the key and fetch the encrypted flag on the same connection.
• On the local box pycryptodome's SHA256/SHA512 C library was broken under Python 3.14 (dlsym SHA256_init not found); use Python's stdlib hashlib for the final flag SHA256.

CWE: CWE-353 (missing integrity check) — malleable AES-ECB enabling the MEGA Backendal–Haller–Paterson RSA key-recovery attack.