MEGA is a leading cloud storage platform with more than 250 million users and 1000 Petabytes of stored data, which aims to achieve user-controlled end-to-end encryption.
We show that MEGA's system does not protect its users against a malicious server and present five distinct attacks, which together allow for a full compromise of the confidentiality of user files.
Additionally, the integrity of user data is damaged to the extent that an attacker can insert malicious files of their choice which pass all authenticity checks of the client.
We built proof-of-concept versions of all the attacks, showcasing their practicality and exploitability.
MEGA is a cloud storage and collaboration platform founded in 2013 offering secure storage and communication services.
With over 250 million registered users, 10 million daily active users and 1000 PB of stored data, MEGA is a significant player in the consumer domain.
What sets them apart from their competitors such as DropBox, Google Drive, iCloud and Microsoft OneDrive is the claimed security guarantees:
MEGA advertise themselves as the privacy company and promise User-Controlled end-to-end Encryption (UCE).
We challenge these security claims and show that an adversarial service provider, or anyone controlling MEGA’s core infrastructure, can break the confidentiality and integrity of user data.
Key Hierarchy
At the root of a MEGA client’s key hierarchy, illustrated in the figure below, is the password chosen by the user.
From this password, the MEGA client derives an authentication key and an encryption key.
The authentication key is used to identify users to MEGA.
The encryption key encrypts a randomly generated master key, which in turn encrypts other key material of the user.
For every account, this key material includes a set of asymmetric keys consisting of an RSA key pair (for sharing data with other users), a Curve25519 key pair (for exchanging chat keys for MEGA’s chat functionality), and a Ed25519 key pair (for signing the other keys).
Furthermore, for every file or folder uploaded by the user, a new symmetric encryption key called a node key is generated.
The private asymmetric keys and the node keys are encrypted by the client with the master key using AES-ECB and stored on MEGA’s servers to support access from multiple devices.
A user on a new device can enter their password, authenticate to MEGA, fetch the encrypted key material, and decrypt it with the encryption key derived from the password.
MEGA can decrypt RSA ciphertexts using an expensive padding oracle attack.
RSA Key Recovery Attack
MEGA uses RSA encryption for sharing node keys between users, to exchange a session ID with the user at login and in a legacy key transfer for the MEGA chat.
Each user has a public RSA key \(pk_{share}\) used by other users or MEGA to encrypt data for the owner, and a private key \(sk_{share}\) used by the user themselves to decrypt data shared with them.
The private RSA key is stored for the user in encrypted form on MEGA’s servers.
Key recovery means that an attacker successfully gets possession of the private key of a user, allowing them to decrypt ciphertexts intended for the user.
We discovered a practical attack to recover a user’s RSA private key by exploiting the lack of integrity protection of the encrypted keys stored for users on MEGA’s servers.
An entity controlling MEGA’s core infrastructure can tamper with the encrypted RSA private key and deceive the client into leaking information about one of the prime factors of the RSA modulus during the session ID exchange.
More specifically, the session ID that the client decrypts with the mauled private key and sends to the server will reveal whether the prime is smaller or greater than an adversarially chosen value.
This information enables a binary search for the prime factor, with one comparison per client login attempt, allowing the adversary to recover the private RSA key after 1023 client logins.
Using lattice cryptanalysis, the number of login attempts required for the attack can be reduced to 512.
Update:
In July 2022, Keegan Ryan and Nadia Heninger from UC San Diego drastically improved on the key recovery attack described above.
Their attack requires only six login attempts.
From the abstract of their paper “Cryptanalyzing MEGA in Six Queries”:
Our optimized attack combines several techniques, including a modification of the extended hidden number problem and the structure of RSA keys, to exploit additional information revealed by MEGA’s protocol vulnerabilities.
MEGA has emphasized that users who had logged in more than 512 times could have been exposed; these improved attacks show that this bound was conservative, and that unpatched clients should be considered vulnerable under a much more realistic attack scenario.
Proof of Concept Attack
Since the server code is not published, we cannot implement a Proof-of-Concept (PoC) in which the adversary actually controls MEGA.
Instead, we implemented a MitM attack by installing a bogus TLS root certificate on the victim.
This setup allows the attacker to impersonate MEGA towards the user while using the real servers to execute the server code (which is unknown to us).
Server responses can be patched on the fly since they do not rely on secrets stored by the server, allowing the attack to be performed in real time as the victim interacts with MEGA.
The following video shows how our attack recovers the first byte of the RSA private key.
Afterward, we abort the attack to avoid any adverse impact on MEGA’s production servers.
For each recovered bit, the attack consists of the following steps:
The victim logs in.
The adversary hijacks the login and replaces the correct session ID with their probe for the next secret bit.
Based on the client’s response, the adversary updates its interval for the binary search of the RSA prime factor.
The login fails for the victim. This is only a limitation of the MitM setup, since the correct SID is lost. An adversarial cloud storage provider can simply accept the returned SID.
Note that after aborting the attack, the search interval is [0xe03ff...f, 0xe07ff...f].
The secret prime factor \(q\) of the RSA modulus starts with 0xe06....
This value is within the search interval and the adversary already recovered the first byte 0xe0.
Using all of \(q\), the adversary can recover the RSA private key \((d, N)\) using the public key \((e, N)\) as \(p = N / q\) and \(d = e^{-1} \mod (p-1)(q-1)\).
Plaintext Recovery
As shown in the key hierarchy MEGA clients encrypt the private keys for sharing, chat key transfer, and signing with the master key using AES-ECB.
Furthermore, file and folder keys also use the same encryption.
A plaintext recovery attack lets the adversary compute the plaintext from a given ciphertext.
In this specific attack, MEGA can decrypt AES-ECB ciphertexts created with a user’s master key.
This gives the attacker access to the aforementioned and highly sensitive key material encrypted in this way.
With the sharing, chat, signing, and node keys of a user, the adversary can decrypt the victim’s data or impersonate them.
This attack exploits the lack of key separation for the master key and knowledge of the recovered RSA private key (e.g., from the RSA key recovery attack).
The decryption oracle again arises during authentication, when the encrypted RSA private key and the session ID (SID), encrypted with the RSA public key, is sent from MEGA’s servers to the user.
MEGA can overwrite part of the RSA private key ciphertext in the SID exchange with two target ciphertext blocks.
It then uses the SID returned by the client to recover the plaintext for the two target blocks.
Since all key material is protected with AES-ECB under the master key, an attacker exploiting this vulnerability can decrypt node keys, the victim’s Ed25519 signature key, its Curve25519 chat key, and, thus, also all exchanged chat keys.
Given that the private RSA key has been recovered, one client login suffices to recover 32 bytes of encrypted key material, corresponding, for instance, to one full node key.
Framing Attack
This attack allows MEGA to forge data in the name of the victim and place it in the target’s cloud storage.
While the previous attacks already allow an adversary to modify existing files using the compromised keys, this attack allows the adversary to preserve existing files or add more documents than the user currently stores.
For instance, a conceivable attack might frame someone as a whistle-blower and place an extensive collection of internal documents in the victim’s cloud storage.
Such an attack might gain credibility when it preserves the user’s original cloud content.
To create a new file key, the attacker makes use of the particular format that MEGA uses for node keys.
Before they are encrypted, node keys are encoded into a so called obfuscated key object, which consists of a reversible combination of the node key and information used for decryption of the file or folder.
(Specifically, a nonce and a truncated MAC tag.)
Since none of our attacks allow an attacker to encrypt values of their choosing with AES-ECB under the master key, the attacker works in the reverse direction to create a new valid obfuscated key object.
That is, it first obtains an obfuscated key by decrypting a randomly sampled key ciphertext using the plaintext recovery attack.
Note that this ciphertext can really be randomly sampled from the set of all bit strings of the length of one encrypted obfuscated key object.
Decryption will always succeed, since the AES-ECB encryption mode used to encrypt key material does not provide any means of checking the integrity of a ciphertext.
The resulting string is not under the control of the adversary and will be random-looking, but can regardless be used as a valid obfuscated key object since both file keys and the integrity information (nonces and MAC tags) can be arbitrary strings.
Hence, the adversary parses the decrypted string into a file key, a nonce and MAC tag.
It then modifies the target file which is to be inserted into the victim’s cloud such that it passes the integrity check when the file key and integrity information from the obfuscated key is used.
The attacker achieves this by inserting a single AES block in the file at a chosen location.
Finally, the adversary uses the known file key to encrypt the file and uploads the result to the victim’s cloud.
Many standard file formats such as PNG and PDF tolerate 128 injected bits (for instance, in the file’s metadata, as trailing data, or in unused structural components) without affecting the displayed content.
The image above shows the file our proof of concept inserts in the victim account.
Our attack added the highlighted bytes to satisfy the integrity check.
Due to the structure of PNG files, these bytes do not change the displayed pixels, i.e., it is visually identical to the unmodified image.
The victim logs into their account without any attack running. There are only three files in the cloud storage and none of them is called hacker-cat.png.
The victim logs out and the adversary runs the plaintext recovery attack once. This involves the following steps:
The adversary hijacks the victim’s login attempt and replaces the encrypted SID with the encrypted key that it picked for the file forgery.
The victim’s client responds with the decrypted SID, from which the adversary can recover the plaintext for the injected ciphertext blocks.
The log in attempt fails, which is only a limitation of the MitM setting. A malicious cloud provider can perform this attack without the user noticing.
The adversary uses the key recovered in the previous step to forge an encrypted file.
The victim logs in again.
The adversary injects the forged file into the loaded file tree.
The victim’s cloud now displays four files, including a new file called hacker-cat.png.
When the user views this file in the browser, it correctly decrypts and shows the image.
Integrity Attack
This attack exploits the peculiar structure of MEGA’s obfuscated key objects to manipulate an encrypted node key such that the decrypted key consists of all zero bytes.
Since the attacker now knows the key, this key manipulation can be used to forge a file in a manner similar to the framing attack.
Unlike for the framing attack (which requires the ability to decrypt arbitrary AES-ECB ciphertexts), for this attack the adversary only needs access to a single plaintext block and the corresponding ciphertext encrypted with AES-ECB under the master key.
For instance, the attacker can use MEGA’s protocol for public file sharing to obtain the pair: when a user shares a file or folder publicly, they create a link containing the obfuscated key in plaintext.
Hence, a malicious cloud provider who obtains such a link knows both the plaintext and the corresponding ciphertext for the node key, since the latter is uploaded to MEGA when the file was created (before being shared).
This can then be used as the starting point for the key manipulation and allows a forged file ciphertext to be uploaded into the victim’s cloud, just as for the framing attack.
However, this attack is less surreptitious than the framing attack because of the low probability of the all-zero key appearing in an honest execution, meaning that an observant user who inspects the file keys stored in their account could notice that the attack has been performed.
GaP-Bleichenbacher Attack
This attack is a novel variant of Bleichenbacher’s attack on PKCS#1 v1.5 padding.
We call it a Guess-and-Purge (GaP) Bleichenbacher attack.
MEGA can use this attack to decrypt RSA ciphertexts by exploiting a padding oracle in the fallback chat key exchange of MEGA’s chat functionality.
The vulnerable RSA encryption is used for sharing node keys between users, to exchange a session ID with the user at login and in a legacy key transfer for the MEGA chat.
As shown in the key hierarchy, each user has a public RSA key used by other users or MEGA to encrypt data for the owner, and a private key used by the user themselves to decrypt data shared with them.
With this attack, MEGA can decrypt these RSA ciphertexts, albeit requiring an impractical number of login attempts.
Attack idea:
The original Bleichenbacher attack maintains an interval for the possible plaintext value of a target ciphertext.
It exploits the malleability of RSA to test the decryption of multiples of the unknown target message.
Successful unpadding leaks the prefix of the decrypted message due to the structure of the PKCS#1 v1.5 padding.
This prefix allows an adversary to reduce intervals efficiently and recover the plaintext.
MEGA uses a custom padding scheme which is less rigid than PKCS#1 v1.5.
This makes it challenging to apply Bleichenbacher’s attack, because a successful unpadding no longer corresponds to a single solution interval.
Instead many disjoint intervals are possible, depending on the value of an unknown prefix in MEGA’s padding scheme.
Our attack devices a new Guess-and-Purge strategy that guesses the unknown prefix and quickly purges wrong guesses.
This enables us to perform a search for the decryption of a ciphertext in \(2^{16.9}\) client login attempts on average.
Although this attack is weaker than the RSA key recovery attack (in the sense that a key recovery implies plaintext recovery), it is complementary in the vulnerabilities that it exploits and requires different attacker capabilities.
It attacks the legacy chat key decryption of RSA encryption instead of the session ID exchange and can be performed by a slightly weaker adversary since no key-overwriting is necessary.
The details of the GaP-Bleichenbacher attack are intricate.
For a full description, see Appendix B of the paper.
Mitigation
Responsible Disclosure
We contacted MEGA to inform them of the vulnerabilities in their system and to suggest three different levels of mitigation (immediate, minimal, and recommended) on March 24, 2022.
MEGA acknowledged the attacks, confirmed that the system is vulnerable and needs patching, and awarded us a bug bounty.
We agreed to a 90-day disclosure window.
Our Proposed Countermeasures
The scale of MEGA poses many practical challenges for both MEGA and customers, such as the load and traffic implications of re-encrypting over 1000 petabytes of user data.
Furthermore, backwards compatibility is a significant issue as disruptive changes render some customer data inaccessible, while legacy code is a security risk.
Due to these significant practical challenges, we organize our proposed mitigations in three levels:
Immediate countermeasures: Backwards compatible and non-invasive mitigations which complicate the attacks sufficiently to temporarily protect users from the most severe security breaches.
Minimal countermeasures: More substantial changes that better address the attacks while avoiding the most expensive modifications (such as file re-encryption).
General recommendations: Long-term goals for redesigning the cryptographic architecture to address the root causes of the attacks and adhere to best practices.
A visual overview of how the proposed mitigation steps change the key hierarchy is here.
Immediate Countermeasures
Key separation for the master key: following the key separation principle, we propose to introduce a derivation key and derive different keys to protect the RSA Sharing, Chat, Sign, and Node Keys, instead of using a single master key to encrypt them all.
Ad hoc integrity protection: we propose to use HMAC on top of the existing ciphertexts to protect the integrity of key ciphertexts.
Fixing the RSA padding prefix: we propose to enforce stricter client-side checks of MEGA’s RSA padding scheme to increase the number of queries needed for the GaP-Bleichenbacher attack and further reduce the practicality of the attack.
These measures protect against our first four attacks.
However, they should only be considered as temporary measures that can be deployed quickly.
They do not address the root flaws in the cryptographic design.
Minimal Countermeasures
AES-GCM for key ciphertexts: instead of the ad hoc integrity protection proposed as part of the immediate countermeasures, we suggest replacing AES-ECB with an authenticated encryption scheme, namely AES-GCM.
RSA-OAEP for sharing: we recommend replacing MEGA’s padding scheme by a standardized padding mechanism for RSA encryption. Additionally, we suggest using different RSA key pairs for sharing node keys and for the legacy chat key transfer to improve key separation.
These measures address our attacks more adequately at the cost of losing backwards compatibility.
General Recommendations
File encryption: we propose a thorough redesign of MEGA’s system. This includes protecting node keys with AES-GCM and using separate keys for file encryption and for protecting their attributes. Furthermore, we propose to replace MEGA’s custom variant of AES-CCM for file encryption with the well-analyzed AES-GCM.
Augmented PAKE for authentication: we recommend the usage of OPAQUE (the version where the server does not learn the password in the registration phase) instead of the authentication key. Users authenticate by proving their knowledge of the password to the server. Meanwhile a MitM adversary capable of breaking TLS cannot gain any advantage in recovering user passwords. However, a malicious server can still mount targeted dictionary attacks by simulating the authentication locally.
The proposed measures in this section require users to re-encrypt their files because the key material is derived differently, and new primitives are used.
According to our estimates, this process would take more than half a year, even in the ideal setting where all customers are reachable and have the computational resources to re-encrypt up to hundreds of gigabytes of data.
While this needs to be planned carefully, the long-term goal should, in our opinion, be to replace insecure legacy code and temporary patches.
The immediate and minimal countermeasures are only temporary suggestions and are not unlikely vulnerable to more attacks themselves due to the extensive key reuse and non-standard combination of primitives.
MEGA’s Patch
MEGA decided to introduce additional client-side checks on the format of RSA private keys to protect against our first attack.
They are explained in more detail in MEGA’s blog post.
While these checks directly prevent the RSA key recovery attack, and hence by extension the attacks that depend on it, this fix significantly differs from our proposed countermeasures.
MEGA uses AES for End-to-End Encryption (E2EE), why isn't that enough?
Unfortunately, the use of secure primitives alone does not guarantee security.
The overall system design is crucial.
For instance, this includes key derivation and management, the support of advanced features (like file-sharing or a chat), and how the primitives are used and combined.
Our attacks exploit unintended interactions between ciphertexts resulting from key reuse.
Furthermore, MEGA uses the ECB mode of AES for some encryptions, which does not protect the integrity of ciphertexts.
Can your attacks be applied to other services?
The attacks rely on details of the architecture and implementation of MEGA.
Therefore, they cannot be directly applied to other services.
Nevertheless, some of our observations are generalizable.
For instance, the RSA key recovery attack shows that the missing integrity protection of ciphertexts does not only fail to provide IND-CCA security but can also lead to powerful attacks in practice.
Other services with malleable key ciphertexts might be vulnerable to similar attacks.
Moreover, the GaP-Bleichenbacher attack is a new variant of Bleichenbacher’s attack on PKCS#1 v1.5 that makes the attack applicable to other custom implementations of the RSA padding.
Does changing my password ensure I am safe?
Not entirely.
Changing the password will derive new authentication and encryption keys for your account.
However, your master key will not be updated, only re-encrypted with the new password.
Furthermore, existing asymmetric keys, including the RSA private key that could have been recovered using our first attack, as well as the symmetric file and folder keys are not changed.
We are not aware of any functionality to re-new these keys using MEGA’s standard clients.
Can I detect whether any of your attacks was exploited on my account?
No, almost all of our attacks do not leave persistent traces.
Only the integrity attack may result in files with an unusual structure.
However, this is not a guaranteed indicator of compromise and could be further hidden.
After researchers from UCSD published an improvement over our key recovery attack which requires only six client login attempts, this attack could have been performed by anyone controlling MEGA’s infrastructure without the users noticing.
This makes the plaintext recovery, framing, and integrity attacks feasible since their pre-requisite is only a compromised RSA private key.
Could there be further vulnerabilities?
Yes, with a system as large and complex as MEGA’s, there is always a possibility for vulnerabilities.
Furthermore, our analysis showed that MEGA uses non-standardized cryptographic primitives in unusual ways in several places in their system.
Some of these might be vulnerable to attacks, although we did not exploit them in the attacks presented here.
In the mitigation section we outline the changes to MEGA’s cryptographic architecture that we consider advisable.
Our recommendations include a transition to well-analyzed and standardized algorithms and would ensure that MEGA follows current best practices.
Implementing these changes would give confidence that no further vulnerabilities are possible that, e.g., exploit interactions between primitives due to key reuse.
However, some of the proposed changes would be very expensive to perform in practice.
Please refer to the section on MEGA’s patch for information on the changes implemented by them.
What is the impact of your attacks?
MEGA or any entity controlling the core infrastructure of MEGA can achieve the following with our attacks:
Decrypt all files and folders owned by or shared with the victim.
Decrypt all chat messages exchanged with the victim.
Forge files that are indistinguishable from genuinely uploaded ones and place them in the victim’s cloud storage.
Both the framing and integrity attack forge files — what's the difference between them?
They differ in the assumed attacker capabilities and the stealthiness of the created files.
Framing attack:
Capabilities: the adversary needs access to an AES decryption oracle, i.e., it needs to be able to decrypt arbitrary ciphertexts encrypted with AES-ECB under the master key. (The plaintext recovery attack, provides exactly this.)
Stealthiness: the resulting file encryption uses a uniformly random key just like genuinely uploaded files.
Integrity attack:
Capabilities: the adversary only needs to know a single ciphertext-plaintext pair for AES-ECB under the master key. This is easier to achieve than a decryption oracle.
Stealthiness: the encrypted file uses a key of all zero bytes, which is very unlikely to happen for genuinely uploaded files. However, the user needs some technical expertise to extract the decrypted file key from their MEGA client in order to detect the attack.
MEGA decided to address our attacks with different measures than those that we proposed.
Their patch is less invasive than our recommendations, but in turn maintains the non-standard use of cryptographic primitives.
It suffices to protect against the RSA key recovery and plaintext recovery attacks.
Hence, it also protects against the chain of attacks up to the framing attack that we present here.
(That is, it removes the access to the AES-ECB decryption oracle needed for the framing attack, which we instantiated with the plaintext recovery attack.)
However, their patch does not directly protect against the framing attack, nor the integrity attack.
If the prerequisites can be fulfilled in a different way (see e.g. the discussion on publicly shared files and folders in the integrity attack section), these attacks could still be mounted.
Furthermore, the patch introduced by MEGA does not protect against the GaP-Bleichenbacher attack, although the latter is arguably too inefficient to be practically exploitable.
We did not analyze whether MEGA’s patches can be bypassed or if they introduce new vulnerabilities.
Are there Proof-of-Concept implementations of your attacks?
The bottleneck of the attack is the required 512 user login attempts.
If users frequently log out of their account, the attack could recover their RSA private key within a few months.
However, users stay logged in by default on the MEGA clients that we examined.
Nevertheless, as the attacker in our threat model controls the core infrastructure of MEGA, they could make the attack much more practical with an inconspicuous code update.
Currently, MEGA clients cache the old session ID and user’s secret key material by default.
Therefore, a new SID is only exchanged when users manually terminate their session and re-enter their password.
An adversary could push an update to MEGA’s clients such that they transparently re-negotiate a new session ID (SID) on every new access.
Afterwards, the adversary can perform the 512 queries within hours or days without the user noticing.
The integrity attack can additionally be performed without the RSA key if the attacker knows a single AES-ECB plaintext-ciphertext pair under the master key.
Such a pair can for example be obtained by MEGA from a link to a publicly shared user file or folder.
Finally, the GaP-Bleichenbacher attack is of a more theoretical nature since \(2^{16.9}\) interactions with the client are very expensive.
However, attacks only improve over time, and this attack shows a fundamental flaw in the use of RSA encryption.
Update [July 2022]
In “Cryptanalyzing MEGA in Six Queries”, Keegan Ryan and Nadia Heninger from UC San Diego published an improved key recovery attack which reduces the number of required login attempts to six.
This improvement not only makes recovering the RSA key easy to perform for an adversary, but also makes our plaintext recovery, framing, and integrity attacks feasible.
Isn't this threat model assuming too strong an adversary?
We think the threat model is consistent with the security claims made by MEGA.
For instance, the following quote from their website showcases that MEGA advertise confidentiality of user data even against themselves:
MEGA does not have access to your password or your data. Using a strong and unique password will ensure that your data is protected from being hacked and gives you total confidence that your information will remain just that – yours.
Moreover, we must consider the possibility that even if MEGA is not adversarial, their systems may have been compromised by malicious third parties, for example nation state security agencies or hacking groups, who wish to gain access to users’ data and files.
Indeed, the sheer size of MEGA – and the likelihood of it attracting users who wish to protect highly sensitive data precisely because of the security the service claims to offer – surely make MEGA an attractive target.
Who is affected by these vulnerabilities?
We looked at the official MEGA Web Client v. 4.11.2 and the MEGA SDK v. 3.9.15.
However, the vulnerabilities are fundamental issues in the cryptographic design.
Clients have only limited implementation flexibility because they need to remain compatible with the server code of MEGA.
Thus, we expect them to be present in all current clients, as well as older versions.
