SHA-512 w/ per User Salts is Not Enough

Why everybody wants to invent their own crappy password hashing scheme? Just pick one of already widely used ones, eg.: PBKDF, bcrypt, scrypt, any non-DES-based algorithm offered by crypt(3)... And when you want to really design your own scheme, at least look at how all previously mentioned schemes are designed and try to understand why.

And as for why this scheme is bad: your application has access to this "protected file" with secret shared key and so does attacker.

His entire argument hinges on this one sentence: "Once the salt is known, it would be pretty trivial to dictionary a bunch of hashes in little or no time and get a pretty significant hit rate."

The author does not understand that salts primarily protect against rainbow tables (pre-computation attacks). He assumes the purpose is to increase brute force search complexity or somehow add additional secrecy, and is correct that it fails at both.

If you are already using user specific salts and a strong SHA hash, the next place you should be looking to add security is increasing the number of rounds (i.e. sha(sha(sha(hash+pass)))) or switching to bcrypt (which takes advantage of an expensive key setup phase in blowfish to make brute force searches very painful).

Just as a random question: Why are people using hash functions designed to be fast for large file digests/etc (ie. SHA) for password hashing?

Isn't this what scrypt/bcrypt/etc. are designed for?

This seems more complicated than it has to be.

hash(salt + nonce + password)

gets the same job done. If you don't trust your hash algorithm... pick a new one.

EDIT: It occurs to me that this whole notional improvement (the one from the article and my alternative) isn't as great as it might first seem: if an attacker gets the table of salt+password, and if the attacker knows the password to one account on the system, he can figure out what the nonce is by doing trial hashes using hash(nonce+salt_k+password_k), where salt_k and password_k are the known salts and passwords. In this way, he can figure out the nonce. Since you will very likely run into collisions when attempting to guess the nonce, you will have to have more than one known password, and you probably want to know something more about the nonce, e.g., its length, but fundamentally you're only increasing the difficulty of the attack by a small amount.

EDIT 2: thinking about it more, the right way around this is just to use a gigantic nonce. If your nonce is 1k, good luck brute forcing it. In this case, I'm fairly certain that my proposed alternative is just as sufficient as the original.

Do many platforms have a login-specific crypto call? That is, one tied to the user's system password? (Like Windows CryptProtectData.) That has the added benefit that if anyone steals the disk or resets the user's system password to login to their account, all such secrets are lost.