Earlier quoted context omitted.
Great question. In the recommendations, we're suggesting using two salts. One for deriving the key, and one just for challenges. Both of them are stored plaintext on the server. The salt itself does not need to be kept secret -- it's purpose is just to mitigate pre-computation attacks on the password and the resulting derived key. Both salts are created by the client from random data at the time the account is create…
It does so far, and I see how this does no harm (as you say), but I also don't see how it improves security? Can you give an attack that would work against the unsalted system which wouldn't work against the salted system?
What we're trying to protect against is someone in possession of the data (such as Mega themselves, or anyone working for them, or hacking them, or seizing their assets, or just someone over the internet making an offline attempt against an account after discovering the auth hash) from making a brute force attempt to learn the plaintext content of the accounts.
So to help me crack accounts, I could make a database of outputs from the KDF, with every password combination pre-computed. "Start with "aaaaaa" as a password, and go all the way through "ZZZZZZ" out to some number of characters. The database would have 32 output bytes per entry. The first 32 bytes would be the output of "aaaaaa" through the kdf, then "aaaaab", and so on.
If my math is right, going out to 6 characters using letters numbers and punctuation, the database (probably just a file really) would be about 5 TB in length, and based on my single slow CPU's AES speed, would take about 99 CPU days to compute. Of course if you have 100 CPUs (or EC2, or a botnet) you could have it done in time for dinner tomorrow. Or just wait because someone will likely precompute one you can bittorrent in the next few days.
So, if I wanted to make a brute force attack against Mega's database of users, I would use this pre-computed database, reading it sequentially from disk, taking every 32 byte section and trying it as a key to decrypt the next layer of keys for a user. My CPU could likely check answers faster than the data would stream in from the disk.
So I would be able to brute force any combination out to 6 password characters in a few minutes using only the spare hardware sitting around my office and unoptimized code. Imagine what NSA could do.
So, finally getting back to answering your question. If the salt were used, then I couldn't pre-compute the KDF output. I would have to do it separately for each user. So then my attempts would (again on my weak CPU) proceed at only about 520 attempts per second. That's still about 500 times to fast. So, the design needs both a slower KDF, and salt. :)
Trivia: Want to time your own CPU and how many AES cycles it can do?
$ openssl speed -evp aes-128-ecb
Doing aes-128-ecb for 3s on 16 size blocks: 102358287 aes-128-ecb's in 3.00s
>>> 102358287 / 3 / 2**16
520