4

I understand how Mega's encryption works. For a quick summary of all those in the future looking for an answer on this... here is how it works:

Upon first signing up for an account you make a username and password. It also generates a symmetric key which is used to encrypt your files and a RSA key pair to share secrets securely when files are sent to other peoples "inboxes". Once the client has both these, the symmetric key is encrypted with your password and uploaded to the server. This way only someone with your password can decrypt your symmetrical key and then decrypt your files. I'll leave it at this for now as thats all that is relevant to my question.

If my symmetric key is encrypted with my password, no matter how secure my key is would it not still be as weak as the hashing function they use to store my password on their server? This ties into my second question, do they even store a hash of my password? I'm thinking along the lines of no, as it would weaken the encryption hugely, but Mega still needs to be able to determine if your login details are correct. How can they do this without compromising their encryption?

This may be the wrong place for asking this, so please move it if appropriate.

jduncanator
  • 413
  • 1
  • 5
  • 10

3 Answers3

6

Here are some hints on how it's done on Mega:

The password provided is passed through a KDF to derive a key, that is used to en-/decrypt the master key (later provided by the server through an API call).

To bring it down to the crucial bits: The KDF applies $2^{16}$ rounds of AES-128 with it. The details can be found in the function prepare_key() of the web client in file crypto.js.

The user supplied password itself is never sent over the wire. And the master key is only decrypted client side using this password-derived 128 bit AES key.

To log in against the Mega servers, which gives one a valid session that allows one to access the (encrypted) master key, a token is computed. This token is computed using the derived key (see above) by running it through an additional series of $2^{14}$ rounds of AES-128 (see the stringhash function in crypto.js) after "joining" the user's email address with the above mentioned derived key.

D.W. is right, that the procedures in place are unfortunately not properly documented, yet. This is a severe shortcoming that needs to be rectified over time. Having said that, newer cryptographic work by Mega is paired with documentation in the form of a white paper as it is implemented to allow for peer review. These white papers are currently not openly published, yet, but interested parties have received these easily as needed or as requested, as they're still somewhat in flux.

If anybody is interested in further information, please feel free to email crypto@mega.co.nz for this to get first hand answers. However, that should still hold nobody back from discussing here or elsewhere, though it seems not easy to get explicit answers from the Mega developers here without letting them know of a question raised here.

Update:

There's an independent study that has been conducted by a researcher team in Spain: English PDF. They have dug into the available JavaScript code and reasoned on it. Except for minor flaws, the information is pretty much correct.

xemacs
  • 61
  • 1
  • 2
2

Here's a possible scenario:

1) Your password is put through a slow KDF such as Scrypt. The output of Scrypt can be configured to take a long time to calculate, and as such, can mitigate the risk of brute-forcing passwords. See here.

2) The output length of Scrypt is also configurable. So assume that half of the output becomes the encryption key for your symmetric key, and the other half is stored to identify you when you log-in.

SEJPM
  • 45,967
  • 7
  • 99
  • 205
hunter
  • 3,965
  • 6
  • 28
  • 42
  • 1
    I'm assuming that the symmetric key being encrypted is a string of 16 or 32 pseudo-random bytes, so there's no way for an attacker to verify that they've decrypted the key successfully without actually attempting to decrypt your data with it In my opinion is wrong. Lets say they use MD5 as a hasing algo (I know, its not secure but meh). All I would need to do is bruteforce that MD5 and I would have the password used to encrypt my symmetric key. – jduncanator Apr 04 '13 at 03:21
  • Also, what do you mean by the password-hash and the symmetric password hash? Are they not the same thing? – jduncanator Apr 04 '13 at 03:23
  • 1
    @jduncanator "All I would need to do is bruteforce that MD5 and I would have the password used to encrypt my symmetric key". But how would the attacker know when the brute-force attack has been successful if they don't know what they're looking for? Regardless, if they're using MD5 as their hash algorithm, then they're not taking security seriously. Assuming they use an industry standard like SHA512 and a proper salt, then brute-forcing isn't viable (most people think sha256 is sufficient, and sha512 is overkill). – hunter Apr 04 '13 at 03:39
  • 1
    Regarding "the password-hash and the symmetric password hash - Are they not the same thing?", assuming they are salted with unique values (as demonstrated above), then no, the resulting hash values are very different. – hunter Apr 04 '13 at 03:42
  • The attacker would know when they have generated a password that matches the hash. I get the hash, and the salt. Then I bruteforce every combination until I get the hash stored in the database. Now I have password, I can simply decrypt the key used to encrypt all my files. – jduncanator Apr 04 '13 at 03:47
  • Your logic assumes being able to brute-force the hash. Put simply, if Mega uses MD5 (doubtful), then the attack you describe is viable. If they use an industry standard (which they should) such as SHA512, then the attack you describe is not viable. Read the first answer here to learn why brute-forcing SHA512 isn't feasible. – hunter Apr 04 '13 at 04:06
  • Mega uses neither MD5 nor SHA*! They implemented a self-made hash-function that can be found in this file (https://eu.static.mega.co.nz/crypto_23.js) at line 97 (function prepare_key). The function encrypts a fixed string with the password as the key for fixed iterations. Unfortunately, I cannot say anything about the security of this construction... – Ekris Apr 04 '13 at 10:32
  • @Ekris - SHA and MD were just being used as illustrative examples. Besides, the code you point to is executed client-side, it doesn't give any indication of what's happening server-side. – hunter Apr 04 '13 at 13:59
  • 2
    Actually, bruteforcing an (even salted) SHA-256 hash of a password is quite possible. It takes a bit longer than MD5 (on the same hardware) proportionally to the hashing taking longer, but not exponentially longer – just hash each possible (probable) password once and compare the results. You need a slow hash to prevent this. – Paŭlo Ebermann Apr 04 '13 at 19:55
  • Well yes, regardless of the hash algorithm used (MD5, SHA512, Keccak, or whatever), if the password is only 8 characters long then brute-forcing it would be trivial. Using a slow-hash such as PBKDF2 or Scrypt was mentioned in my answer, but given all this talk about brute-forcing hashes, it's worth underscoring it. – hunter Apr 04 '13 at 20:06
  • My comment was mostly a reaction to your comment stating If they use an industry standard (which they should) such as SHA512, then the attack you describe is not viable. about a brute force password search. Also the answer you linked contains this same dangerous assertion, I added a comment there, too. – Paŭlo Ebermann Apr 04 '13 at 20:11
  • I was referring to using something like SHA256 or SHA512 as the underlying algorithm for a PBKDF, (as per my original answer), but re-reading, I can see that I should have made that clearer in my comments. – hunter Apr 04 '13 at 20:51
  • And by the way - you're right about that link - the answer assumes brute-forcing 256 or 512 bits of high entropy psuedo-random data, but in fact the question is in regard to brute-forcing a low-entropy password. – hunter Apr 04 '13 at 20:58
  • "even if a simple hash was used, [...] there's no way for an attacker to verify that they've decrypted the key successfully without actually attempting to decrypt your data with it, which would be too time-consuming" - This is incorrect. Doubly incorrect, actually. 1) There is a way to verify a guess at a password without decrypting all your data. To verify a guess at your password, hash it, compute the resulting decryption key, and then just decrypt some of your data and see if it looks correct. 2) This is not too time-consuming. It'd be a serious threat, if they used a fast hash/KDF. – D.W. Apr 05 '13 at 01:26
  • "Doubly incorrect", you mean, like a double-negative? "Too time-consuming" is subjective, it depends on the attacker's patience, and what is known about the encrypted data. Anyway, in the interest of putting an end to this insufferable thread, I've edited my answer. Downvote if you disagree. – hunter Apr 05 '13 at 02:23
  • Patience really isn't an issue. I was thinking this at a more, FBI wants information, goes downloads encrypted files of suspect user, requests from mega their encrypted key and a hash of their password, FBI uses super duper mega powerful computer to bruteforce hash. – jduncanator Apr 05 '13 at 04:37
2

I don't know what Mega is doing. They haven't published a design document that describes how their system addresses these threats. That's irresponsible on their part, and it doesn't invite trust. Cryptographers have already criticized Mega for sloppy engineering, and researchers have found a bunch of security problems, vulnerabilities, and design issues. Consequently, I wouldn't use Mega for anything super-sensitive at this point in time.

While I don't know for certain what they are doing, my guess/hope is that they are using a slow hash function or slow KDF to derive a key from your password. In other words, they might derive the key $K$ from your password $P$, via $K=H(P)$, where $H$ is some hash algorithm that is fairly slow -- it might take 1 millisecond to compute, for example. Then, Mega might encrypt your data using this derived key $K$. Or, they might encrypt a session key using $K$ and encrypt your data under the session key, and store the encrypted data and encrypted session key.

Assuming this is what they do, the result is: brute-force attacks on your password remain possible.

For example, if the slow hash takes 1 millisecond to hash your password, then brute-force attacks will need to spend about 1 millisecond per guess at your password. (Probably less, because the attacker may be using a faster computer or a better-optimized implementation of the hash.) Thus, use of a slow hash increases the cost of brute-force attacks but does not eliminate the threat entirely. If your password is long enough and strong enough, brute-force attacks might be impossible. But for many people who choose mediocre passwords or passwords, brute-force attacks will likely still be a serious threat.

For a bit more detail, see this advice: Try to avoid using passwords as encryption keys.

Community
  • 1
D.W.
  • 36,365
  • 13
  • 102
  • 187
  • 2
    Be reasonable. Nobody is asking anyone to reverse-engineer anything. If participants in this forum (especially new ones) can't ask questions such as: "How can they (mega) do this without compromising their encryption?" without being told to go away and ask someone else, then what is the point of the forum? – hunter Apr 05 '13 at 02:31
  • 1
    @hunter, OK, I revised my answer in response to your suggestion. Thanks for the helpful comments! Keep 'em coming! – D.W. Apr 05 '13 at 04:28
  • @D.W. Although I appreciate the work done to find all the links, the information posted is obsolete and actually wrong. MEGA has a public repository - https://github.com/meganz/sdk - feel free to check the code and report any issues you find (they also have a bounty for any security threats reported) – tagyro Apr 01 '15 at 09:20
  • 1
    @tagyro, thank you for the pointer. Unfortunately, a source code repository is not a substitute for a design document that describes how the architecture addresses these threats. (That said, from xemacs' answer, it sounds like they did exactly what I speculated in my answer.) I think the links to vulnerabilities in early versions of the system are relevant to understanding the history of the system. If there are public documents that respond to that analysis and explain why they're wrong or how they've been fixed, with technical details, I'd gladly update my answer with that information. – D.W. Apr 01 '15 at 16:59