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:

...