2
$\begingroup$

Is nesting/re-hashing a viable way of slowing down a fast cryptographic hash function (such as SHA-256) to slow down brute-forcing attacks on shorter passwords? The use of longer passwords would of course be ideal, since it would lead to an exponential growth in brute-force difficulty, but is the use of multiple rounds an acceptable way of achieving linear growth in computational cost?

suppose an example: SHA256(SHA256(password)) would be twice as computationally expensive as SHA256(password), and so, a function with a difficulty parameter could be defined as:

function hash(String password, int difficulty)
{
String result = password;
while(difficulty >0)
{
result = SHA256(result);
difficulty--;
}
return result;
}

Are there any security risks/weaknesses with this approach? thanks.

$\endgroup$
4
$\begingroup$

Iterating a hash function such as SHA-256 does raise the cost of brute-force preimage attacks to recover passwords from password hashes, and in fact this technique appears in most password hash functions, usually with some variation in the input to the hash function in each iteration. See, for example, PBKDF2 for a widely used password hash function that does only this.

However, it does not exponentially increase the cost of a brute force preimage attack. It only linearly increases the cost, because if you iterate SHA-256 2x instead of 1x, the attacker must do 2x as many SHA-256 evaluations.

The cost here is measured in the area*time product of an attack, not how long an attack takes in wall clock time: an attacker with $2n$ CPU cores can compute an attack on 2x-iterated SHA-256 in the same time an attacker with $n$ CPU cores can compute an attack on 1x-iterated SHA-256. To attack your iterated SHA-256, a smart attacker will buy computers with many CPU cores on a die to attack hashes in parallel, e.g. with GPUs or custom ASICs. This is essentially what Bitcoin miners do.

The cost factor you can impose on the attacker by this method is bounded by the time you're willing to wait for your CPU to compute the password hash function once. But there's another way you can impose cost on the attacker, which is by making the password hash require a lot of memory as well as time. Area on the die dedicated to memory can't be used to attack multiple passwords in parallel like area on the die dedicated to extra CPU cores can.

Sequential memory-hard password hashes were introduced in scrypt to force attackers to spend either a linear amount of memory or (say) a quadratic amount of time to compute the same function you compute. Since on your laptop or phone you typically have gigabytes of memory available, you can easily spend a lot of it to evaluate a single password hash in a tolerably short time. This is how modern password hashes such as scrypt and argon2 work to raise the cost for an attacker without hurting legitimate users.

$\endgroup$
1
$\begingroup$

First of all, this isn't multiple rounds (as SHA-2 itself has rounds, count could be modified in some implementations). This is nested SHA-2 calls (or so I would call it, "rounds" makes it confusing).

There are minor problems with such approach. It increases chance of collision (adding counter and original value to each SHA-2 call would fix this), but this isn't issue for most uses and especially not here.

But why we don't use such schemes is that this allows for good ASIC/GPU implementations, which allow for quick breaking. We tend to use bigger amounts of ram rather than ALU speed, because CPUs shine in ram and cache, and GPUs and ASICs do mostly in ALU. That is why I recommend Argon2 or scrypt in this case - it works good on CPU, but not that great on GPU and ASIC, which makes it even harder (and more costly) to break.

And remember: Don't roll your own, we have plenty of good KDFs! Of course unless this is for learning purposes. Then I recommend looking at vague scheme of argon2.

$\endgroup$
  • $\begingroup$ Thanks. I know of course that solutions exist specifically for increasing computational complexity, so this is only for curiosity, and not for any kind of production case :) $\endgroup$ – Daniel Valland Jul 21 '17 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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