Cracking MEGA … in Six Queries

Cracking MEGA … in Six Queries

While the methods that we use in cryptography are often highly secure in their operation, it is often the implementation that lets them down. A recent paper identified problems with the MEGA cloud platform [paper][Web][1]:

In this paper, researchers were able to crack the RSA private key in just 512 attempted logins.

MEGA Part 1

The analysis relates to MEGA, and which is a massive cloud infrastructure which uses User-Controlled end-to-end Encryption (UCE), with over 250 million registered users and 1000 PB of stored data. Overall, the paper does not have just one attack, but five:

• RSA Key Recovery: This recovers a user’s secret key using 512 attempted logins.
• Plaintext Recovery: This recovers all the related encryption key material, and which can be used to decrypt all of the communications and files related to a user.
• Framing: This can create files within a user’s storage area, and which cannot be differentiated from the ones that have been uploaded in a genuine way.
• Integrity: This is similar in scope to the framing attack, but less sophisticated.
• GaP-Bleichenbacher: This crack RSA encryption using a modified Bleichenbacher method.

The key generation method is outlined in Figure 1. It involves an initial password, and which derives an authentication key (used to authenticate the user) and an encryption key (which is used to encrypt a master key, and which is used to encrypt all the other related user content). The keys are an RSA key pair (for data sharing), Curve25519 key pair (for messages), and an Ed25519 key pair (for signing keys). Every file or folder is then encrypted with a node key, and where all of the keys are encrypted with AES ECB with a master key and stored on MEGA’s servers. A password can then be used to regenerate all of the keys.

RSA key are used for data sharing node keys — the keys which encrypt files — with other users, along with sharing session IDs. If Alice wants to share a file with Bob, she will encrypt the file with Bob’s public key (B_pk), and for Bob to decrypt it with his private key (B_sk). But, Bob’s private key is stored on MEGA’s servers, and where the researchers were able to recover the private key by discovering one of the prime number (p) factors used in the RSA modulus (N). It was found that it need 512 requests to discover the prime number used. Once this is discovered it is fairly easy to discover the other prime number involved and then from this to discover the decryption key. With N (which is public) and the discovered prime number (p), we can discover the other prime number (q) with:

Next, we can derive PHI with:

And then the decryption exponent with:

And finally, decrypt the ciphertext © with:

MEGA Part 2

Now, researchers have published work which achieves the discovery of the secret key within just six queries [here][2]:

It combines several techniques, including with the extended hidden number problem and in the structure of RSA keys. It does this in just six queries and can crack the key in 4.5 hours on an 88-core computer. With the MEGA login, the server sends the RSA private key to the client, and that is encrypted with AES using ECB mode. The client then decrypts this to discover the private key. It then decrypts a session ID that it is sent by the server, and sends it back to the server. The original attack modified the ECB cipher, in order to obtain one bit of the private key for each login. In the Ryan and Heninger attack, blocks of the ECB ciphered RSA key are swapped, and which reveals even more information about the RSA private key. There are a number of phases, including for the Extended Hidden Number Problem and brute force analysis.

Conclusions

The papers are a feast of cryptographic discovery.

References

[1] Backendal, M., Haller, M., & Paterson, K. G. MEGA: Malleable Encryption Goes Awry.

[2] Ryan K and Heninger N, Cryptanalyzing MEGA in Six Queries, Cryptology ePrint Archive, Paper 2022/914.