Many hash iterations: append salt every time?

Question

I have used unsalted md5/sha1 for long time, but as this method isn't really secure (and is getting even less secure as time goes by) I decided to switch to a salted sha512. Furthermore I want to slow the generation of the hash down by using many iterations (e.g. 100).

My question is whether I should append the salt on every iteration or only once at the beginning. Here are the two possible codes:

Append every time:

// some nice big salt $salt = hash($algorithm, $salt);  // apply $algorithm $runs times for slowdown while ($runs--) {     $string = hash($algorithm, $string . $salt, $raw); }  return $string; 

Append once:

// add some nice big salt $string .= hash($algorithm, $salt);  // apply $algorithm $runs times for slowdown while ($runs--) {     $string = hash($algorithm, $string, $raw); }  return $string; 

I first wanted to use the second version (append once) but then found some scripts appending the salt every time.

So, I wonder whether adding it every time adds some strength to the hash. For example, would it be possible that an attacker found some clever way to create a 100timesSha512 function which were way faster than simply executing sha512 100 times?

Answer 1

In short: Yes. Go with the first example... The hash function can lose entropy if feed back to itself without adding the original data (I can't seem to find a reference now, I'll keep looking).

And for the record, I am in support of hashing multiple times.

A hash that takes 500 ms to generate is not too slow for your server (considering that generating hashes are typically not done the vast majority of requests). However a hash that takes that long will significantly increase the time it will take to generate a rainbow table...

Yes, it does expose a DOS vulnerability, but it also prevents brute force attacks (or at least makes them prohibitively slow). There is absolutely a tradeoff, but to some the benefits exceed the risks...

A reference (more like an overview) to the entire process: Key Strengthening

As for the degenerating collisions, the only source I could find so far is this discussion...

And some more discussion on the topic:

1. HEKS Proposal
2. SecurityFocus blog on hashing
3. A paper on Oracle's Password Hashing Algorithms

And a few more links:

1. PBKDF2 on WikiPedia
2. PBKDF2 Standard
3. A email thread that's applicable
4. Just Hashing Is Far From Enough Blog Post

There are tons of results. If you want more, Google hash stretching... There's tons of good information out there...

Answer 2

In addition to re-hashing it multiple times, I would use a different salt for each password/user. Though I think 5000 iterations is a bit too much, try a lower number. There's a trade-off here; you'll have to tweak it according to your needs and hardware.

With different salts for each password, an attacker would be forced to bruteforce each password individually instead of constructing a rainbow table, which increases the workload considerably.

As always, here's a recommended read for this: Just hashing is far from enough

EDIT: Iterative hashing is a perfectly valid tactic. There are trade-offs, but everything has them. If you are worried about computation time, why not just store the plaintext password?