You all really need to read this paper, because it is hilarious. It's honestly hard to believe Mega could have come up with this bizarre jungle gym of a cryptanalyst puzzle.

You're the client, and you have a bucket of keys: keys for files, keys for chat, more keys for chat, &c. You encrypt them all with AES-ECB† under a "master key" which is in turn encrypted under a key derived from PBKDF2, so you can upload them to a server without revealing them to the server.

So the server has all these keys that you encrypted. You've got your password. Now you want to log in.

So what you do is you send an identifier (PKBDF2-derived from your password) to the server†. They look you up and they send you back one of those keys you uploaded before, the encrypted RSA key, along with a session ID encrypted under that RSA key. The idea is, you have the password and so you can decrypt the RSA key (by deriving the master key), and then decrypt the session ID and post it back to them so they know you're you.

The problem is these encrypted key blobs aren't authenticated; they're just the ECB ciphertext of the keys. And they do, like, no checking at all on them. So when they send you this RSA key blob (ostensibly the blob you sent them before, but of course, the server is malicious and so they tamper with it), they're just sending ECB(mk, [p, q, d, qInv, pad]) --- with that 4-tuple being length-delimited. The client just ECB-decrypts the blob and then makes sure it got 4 values.

So the first half of this paper is just 3 cryptographers doing stunt cryptography by randomizing qInv, the RSA CRT coefficient. The client obliviously uses whatever ECB decrypts here, and better yet, it uses it to perform an RSA operation on another ciphertext the server gets to choose, and better still, it then posts back the partial result of that encryption, so the server can see what happened and guess what to do next. And better yet, that RSA decryption is done with no meaningful padding: they just stick the session ID into a blob of zeroes; they don't even verify the padding, they just assume the session ID is the 43 bytes starting at offset 2 of the RSA plaintext, and ignore everything else.

They start by recovering the RSA key itself. They do this by recovering q, the first factor of the key. They can do this because by corrupting qInv and strategicially choosing RSA-encrypted session IDs, they can get back a session ID that is 0 if their current guess if below q, and nonzero if it's above q. A 1023-step binary search gets you q; you can get it down to 512 guesses using a lattice search that, as someone pointed out, is definitely going to be in a CTF level next year, now that scenarios like this can't be dunked on as entirely, ridiculously contrived. (From q you can quickly recover the rest of the key).

But this isn't even the craziest part. The craziest part is that all these other keys, a key per file or directory, are also encrypted under the same master key as that RSA key is. So when the server sends you the encrypted RSA key and blob encrypted under that RSA key, you can ECB-swap in blocks of other keys with carefully chosen session IDs to set up oracles to recover the other keys, based on how the client's RSA behaves with fucky qInv values. "We believe it to be an entirely novel kind of attack", they say. And to that I say, no shit it's novel, it's so novel Mega probably should have gotten an authorship credit on this paper: Backendal, Haller, Paterson, and Mega. They couldn't have done it --- or even thought of it --- without Mega.

Truly wonderful stuff.

† I know, I know, ECB, you can see penguins through it, but they're encrypting keys, which are fully random --- I mean, you assume they're fully random but just keep reading --- so it's not like completely unprecedented to see ECB here.

†† This is already terrible! All your security is that password, and they can attack it from this value!