Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Is it correct that increasing the iteration possibly decreases the cipher strength but increases the amount of time it would take to find the original hash values if using brute-force on a given hash? (i.e. from a compromised database)?

In other words, if someone accessed user password hashes would be better to protect against weaknesses in the cipher implementation or weaknesses in the amount of time it takes to calculate hashes?

public function hash_password(password, usersalt)
{
    var result = hash('sha256', usersalt . SITE_SALT . password);

    for (i = 0; i < 100; i++)
    {
        result = hash('sha256', usersalt . SITE_SALT . result);
    }

    return result;
}

Note: SITE_SALT is a value stored in a configuration file outside the document root. usersalt is a unique salt generated for each user and stored with the password hash in a database.

share|improve this question
    
Some more discussion is here: Webapp password storage: Salting a hash vs multiple hashes? –  Paŭlo Ebermann Oct 12 '11 at 18:14
add comment

2 Answers 2

up vote 7 down vote accepted

Yes. Iterating the hash like you do slightly increases the chance of collisions (as a hash function is not a random permutation, but an approximation of a random function): It is enough if two different passwords produce the same hash at any of the 100 steps, to produce the same final hash. (But as Thomas noted in a comment, the probability of collisions remains neglibly small.)

It is normally considered better to input the original password in the following iterations, too, this works against this effect: even if two different passwords give the same hash at step 39, at step 40 their hashes will be different again.

result = hash('sha256', result . usersalt . SITE_SALT . password);

On the other hand, iterating takes more time, and thus more computation power (both from you and a bruteforce attacker), which is good.

The bad news is that a fast hash like SHA256 is easily parallelizable, which means that the attacker can try hundreds of different passwords at a time on cheap hardware (like GPUs). Repeating the hash 100 times does not much here.

Instead, use a slow hash function which has some work factor parameter build in. One example is PBKDF-2 (which essentially does what you are doing, just with quite higher repeat counts), another example would be bcrypt (which builds on the key schedule algorithm of blowfish and needs about 4 KB of memory which will be constantly changed, thereby making implementation on standard GPUs ... inefficient), or the newer scrypt, where the needed memory is also depending on the work parameter (which means that you can only parallelize it if you have lots of memory available (and fastly accessible, too)).

Set the work factor so that the needed time is just acceptable for your users.

share|improve this answer
3  
It is worth adding to this that the risk of collisions is increased but remains negligible. For a 256-bit hash function, multiple iteration end up (after, on average, $2^{128}$ operations...) into a big "cycle" of average length $2^{128}$, which is large enough to make collision quite improbable. –  Thomas Pornin Oct 12 '11 at 18:44
add comment

In the question's code, the parameter $n=100$ controlling the number of iterations controls (nearly linearly) the cost of evaluating the hash_password function. As a first order approximation, in the attack model where the result and salts are known, the time it takes for an adversary to find the right password in a list by brute force grows (nearly linearly) with $n$.

There's a catch: increasing $n$ also slightly increases the odds that a random password gives the same result as the right password due to hash collisions, and is thus a false but accepted password; however that remain very unlikely, in the order of $n·2^{-256}$ for practical values of $n$, and can be entirely ignored in practice.

Thus, for all practical purposes, increasing $n$ does not weaken anything (and certainly not a cipher, since there is no cipher involved, except internally in SHA-256); and it greatly increases the resistance to dictionary attacks. The only drawback to increasing $n$ is that it has some cost (CPU usage, energy, delay) for the legitimate parties.

Good practice is to pay attention to the optimization of hash_password and hash; then increase $n$ as much as tolerable in the situation(s) at hand.

Best practice would be to use a PBKDF refined to improve the ratio of cost between attacker and legitimate parties, such as scrypt; and revise parameters such as $n$ every few years to account for technological progress.

share|improve this answer
    
@Paŭlo Ebermann: kudos for the improvements! –  fgrieu Oct 13 '11 at 19:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.