Stretching a hash, many iterations versus longer input string

Question

I have been reading up on various password hashing schemes, for example the SHA-based Crypt proposed by Ulrich Drepper and used in some Linux versions.

A recurring theme here is to 'strengthen' or 'stretch' the hashing function, by using many iterations of the same hash. The runtime of the hashing function can also be increased by concatenating the salt and password together several thousand times, to form a much longer string, and then hash the string once. However, this method seems not to be favored.

Why is that -- why does it appear that concatenating the salt and password together many times isn't a viable way of stretching the hash function?

Answer 1

The main reason why concatenating the salt and password many times is not used is a combination of tradition and laziness. Namely, since password size is not fixed, the number of copies would have to be adjusted so that the "much longer string" size reaches a given goal. It seems that some initial implementers of such schemes found it cumbersome, possibly because it implies using a "streamed" hash function implementation (which accepts data by successive chunks) instead of a one-function-call implementation. Most ulterior designers simply copied the previous designs for no real good (neither bad) reason.

On a theoretical point of view, multiple concatenations of the salt and password are better, because multiple iterations reduce the space of possible hash values (a hash function is not a permutation). But the reduction does not go below a 2¹²⁸ space of a 256-bit hash function, so no worry here.

Answer 2

The reason for 'stretching' (iterating) the hash function for password storage purposes is not to make a stronger hash, but simply to slow the function down, the purpose being to slow down offline brute forcing and dictionary-based attacks.

Iteration is just a simple way to achieve that, because the results are easy to figure out (1000 iterations takes about 1000 times as long as one). Concatenation would have a similar effect, but it would be more difficult to figure out how long the input string needed to be to get a similar slowdown.