The common way to store passwords in web applications is this form:
$$hash(password||salt)$$

Does it make sense to store them in the following form instead:? $$hash_1(hash_2(...hash_n(password||salt)))$$ Where $n$ is the order of a $10^9$.

The main advantage of this method is the difficulty in decrypting passwords using brute-force techniques. (this will take about a million times longer compared to the usual method of calling a single hash function)

The disadvantage would be some delay when creating an account and logging on.

• The first option should absolutely not be used. As for the second, see PBKDF2 – hunter Sep 14 '14 at 16:00

Instead of rolling your own, you should use an established password hash, like PBKDF2, scrypt or maybe bcrypt, they try to be more expensive on GPUs and custom cracking hardware. (Argon2 is also an option, but not widely supported yet.)

(this will take about a million times longer compared to the usual method of calling a single hash function)

If you used $n=10^9$, brute force would take a billion times as long. However, that would be really slow to use in practice. My mid range Intel CPU can hash ~10 million SHA-256 / s on one core, meaning a couple of minutes for your $n$. A million is more reasonable.

Does it make sense to store them in the following form instead:?

Your iterated hash is pretty close to being PBKDF1. One important issue is the salt: PBKDF1 requires an eight octet salt. If you allowed arbitrary salts that can differ in length, it would be possible to have $p_1 || s_1 = p_2 || s_2$.

PBKDF1 is only recommended for legacy applications (due to the limited output size) and I would be more comfortable with PBKDF2:

• Each iteration increases the collision rate. If you use a large enough hash function with $\log_2n$ bits of collision resistance to spare, that will not matter in practice, but PBKDF2 avoids it.
• By using HMAC, PBKDF2 benefits from security proofs that show it is potentially secure with some weaker hash functions. Also a theoretical thing unless you use an obsolete/broken hash.
• Thanks, it seems that this function (PBKDF2) does what I need. $10^9$ was my typo (meant to be $10^6$). – pitoko Sep 14 '14 at 17:10
• 1) The second suggestion if PBKDF1. 2) I prefer PBKDF1 over PBKDF2 as long as the underlying hash is wide enough (256 bits is plenty). The only concern I have is the lack of domain separation, but that doesn't matter for fixed size salts. 3) PBKDF2 abuses the underlying hash so much, that proving its security will be harder than proving the security of PBKDF1. – CodesInChaos Nov 4 '15 at 7:44
• @CodesInChaos, personally I think it's the other way around. PBKDF1 also relies on nonstandard properties of the hash function, but PBKDF2 uses HMAC which at least has proofs. However, your point that it is approximately PBKDF1 is correct, and I should fix the answer. – otus Nov 4 '15 at 8:02
• As far as I can tell, PBKDF1 only relies on collision resistance (to a small degree) and first-pre-image resistance, which are standard properties. PBKDF2 uses the password as key, which is clearly not something HMAC has been designed for. It adds those weird xor-s, which can interfere with the feed-forward of the underlying hash (it does not for the common ones, because they use addition for the feed-forward), which means that you can't consider the hash as a black-box. On top of that PBKDF2 is hard to implement and most implementations are several times slower than they need to be. – CodesInChaos Nov 4 '15 at 8:05
• @CodesInChaos, AFAICT, it is sufficient for PBKDF2 that HMAC is PRF. That means e.g. that the XORs are independent. The implementation complexity is a valid point, but bcrypt et al. are much more complex. You usually need to trust the cryptographic library to get much more complex things right. – otus Nov 4 '15 at 8:15