4
$\begingroup$

I am interested in Mega.nz cloud storage. It is using end-to-end encryption.

It says that it uses AES-128 to encrypt files

And there are more details in their white paper

But I saw that quantum computers could be dangerous for AES-128:

Grover's algorithm allows brute-forcing an n-bit key in $\mathcal{O}(2^{n/2})$ time instead of the $\mathcal{O}(2^n)$ time required by classical computers. Therefore, an 128-bit AES key could be brute-forced in $O(2^{64})$ time by a sufficiently powerful quantum computer that can do Grover's algorithm with 128+ qubits for $2^{64}$ time.

So, my question is: could the encrypted files be decrypted by quantum computers?

$\endgroup$
4
  • 2
    $\begingroup$ The answers to this question focus mostly on the capability of quantum computers, and arent specific to any cloud service. Would you edit your question to make it more generic? $\endgroup$ – DannyNiu Dec 12 '20 at 2:43
  • 2
    $\begingroup$ @DannyNiu For what it’s worth, the general guidance from the Stack Exchange network as a whole is that specific questions are usually better. If specific factors don’t really matter, answers are free to ignore them (and readers can see that they don’t matter/that the answer also applies to their similar situation), but in case they do matter, the details are available. Plus, artificially genericizing questions is kind of a fraught process: often you wind up with a rather hypothetical question that is difficult to supply real details for. $\endgroup$ – KRyan Dec 12 '20 at 16:50
  • 1
    $\begingroup$ Obligatory: xkcd.com/538 $\endgroup$ – David Tonhofer Dec 12 '20 at 18:37
  • $\begingroup$ @DannyNiu I've skimmed the White Paper, which requires a lot of time to review. The AES-128 is the obvious mistake, see the updated answer. $\endgroup$ – kelalaka Dec 12 '20 at 20:03
12
$\begingroup$

Grover's algorithm on AES-128

If all of the problems of Grover's algorithm are solved then yes, otherwise no!

  • Grover's algorithm provides quadratic speed up so AES-128 has 64-bit security in the terms of searching complexity of Grover's method.

  • Grover's attack for AES-128 requires approximately $2^{64}$ successive AES evaluations. That is one has to set up the machine $2^{64}$ times, run successfully, and extract the result. This is not like a for loop on the classical machines.

  • The attack time is still quadratic and the required gates are not practical and it can be around $2^{86}$ for AES-128.

  • Graver algorithm can run in parallel, however, running $k$ machines will provide $\sqrt{k}$ speed up, and the above problem will still exist in each copy.

They are a company, if you are going to be their customer ask them to include the easiest mitigation AES-256 if you fear the future. The performance difference between AES-128 and AES-256 is just 40%, that is AES-256 is 40% slower. This is not a big deal in security. It is strange that they don't offer that since the industry sees the AES-256 as the gold standard.


A more realistic attack on AES-128

In MEGA file encryption, each node (file or folder) has its own encryption key. Although AES-128 is secure, with AES-128 the more users the MEGA has and the more file uploaded by the users will create an realistic attack on AES-128, the multi-target attack with parallel versions of Oechslin's rainbow tables.

Finding a key from $t$ targets's expected cost is $2^{128}/t$. Now assume that you have a billion targets. Then, you will be able to find the first encryption key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This can be achievable with supercomputers.

Therefore the MEGA must give the option to use AES-256 for their clients. In the end, the encryption is performed on the client-side, that is no cost for the MEGA servers at all.


A Review of Mega from their White Paper

Mega is simply

MEGA is a secure cloud storage and communication platform with user-controlled end-to-end encryption (E2EE). End-to-end encryption means that no intermediary - not even MEGA - has access to the user’s encryption keys and therefore the stored data. However, users have the option to share data (individual files or entire folders), plus the associated encryption keys, with others.

It enables browser-based access to end-to-end-encrypted cloud storage.

End-to-end encryption

The files are encrypted on the client-side before uploading. If the user wants to share a file, then they share the encryption key of the file with the recipient’s public key. The recipient key can be verified in another channel as the Signal does, and any change will be notified.

Source code transparency

All security-related code work on the user side and Mega releases the source code so that third parties can verify the source code. This is a very important aspect

Privacy

They promise to only keep the user's e-mail and IP address for operational purposes. They promise to not keeping processing activities and the data, though they can see the activity. The files are still encrypted and not accessible to Mega.

Vulnerability management

They want to ensure security on an ongoing basis and they offer a prize for a previously unknown security-relevant bug or design flaw. This is an important aspect since it will attract more people to look at their designs and codes.

They also provide Data Redundancy and compliance with regulatory requirements. The compliance is an interesting part since, at least now, Australia banned end-to-end encryption. Although the MEGA's service is governed by New Zealand law, it is unclear to me in the case of LAW change.

$\endgroup$
2
  • $\begingroup$ The update from the first section, the white paper has a total of 42 pages. $\endgroup$ – kelalaka Dec 12 '20 at 17:02
  • 1
    $\begingroup$ wow, thanks, for such a complete and insightful answer. I will send them a link to your answer to see what they think about it. And I will ask whether they could use aes-256 instead of aes-128. $\endgroup$ – le menhir Dec 13 '20 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.