13

Why would you choose to slow down the calculation of a password hash?

Renee Pachan
  • 155
  • 1
  • 3

5 Answers5

27

The calculation is intentionally slowed down to make it harder for an attacker to brute-force the user passwords in case the password database gets stolen for example.

Because a hash function only works "one way", to get the password for a hash you have to hash random passwords until you find one with a matching hash. (Rainbow tables provide a tradeoff though).

Using GPUs it is possible to brute-force billions of e.g. MD5 hashes per second.

That's why hash functions like bcrypt or scrypt were developed to mitigate this problem by running slowly and in case of scrypt requiring lots of memory so it's unfeasible to compute the hash using GPUs.

For your "normal" application this will most likely still be fast enough, because you're computing a single hash only, so the performance impact will be negligible.

Stefan
  • 431
  • 3
  • 7
  • 14
    I think it's worth pointing out that a single password hash is still so fast that you wouldn't notice, so there's no effect on user experience. It only affects malicious actors attempting to hash millions and billions of passwords a second in a brute force attempt. – puhlen Feb 07 '17 at 18:32
  • 1
    @puhlen, yep, I've added that to the answer. – Stefan Feb 07 '17 at 19:33
  • @Stefan: Is there any advantage to trying to use an algorithm that a GPU can't help with, rather than using one that could exploit a GPU to increase the practical complexity of individual password hashes? An FPGA-based password cracker can offer more computational work per dollar than general-purpose computing hardware, but an off-the-shelf GPU can offer more computational work per dollar than either. – supercat Feb 07 '17 at 21:22
  • @supercat Even for hash functions that are designed to be hard like `bcrypt` or `scrypt` a GPU will still be several times faster than a CPU. But fortunately, the slowdown in comparasion to a cryptographic hash function is more than enough to stop brute-force attacks even with GPUs. You can raise the **bcrypt work factor** to make it even harder. Just don't use MD5/SHA1/SHA256. Stick with `bcrypt` or `scrypt` or `PBKDF2` (if you must) and you'll probably be fine. – Stefan Feb 07 '17 at 21:55
  • 3
    Rainbow tables provide a trade-off, but their value is nullified by good salting practices. Side-note: [neglectable --> negligible](http://english.stackexchange.com/q/202832/97308). – jpmc26 Feb 07 '17 at 22:04
  • @Stefan: For functions that are designed not to be very efficient on a GPU, an FPGA-based board may offer better performance than a GPU to someone wanting to attack lots of passwords in parallel. But if a function was designed around common GPU operations, people performing hash computations for the purpose of processing legitimate logins could achieve better performance from a cheap GPU than attackers would be able to get with an FPGA-based board. – supercat Feb 07 '17 at 22:11
  • 1
    @supercat I'm not aware of any library used for building applications that offers computing the hashes with the GPU (probably because most servers don't even have one and the performance benefit is neglectable for legitimate uses). Do you know of any such implementation? – Stefan Feb 07 '17 at 22:53
16

Possibly what is puzzling you is that it isn't clearer that... the calculation is not slowed down at all!

That is: there is no "faster" way that is purposefully ignored (not that we know of); there is no artificial "wait" shoehorned in the algorithm.

Rather, the calculation is designed to be slow. Or memory intensive. Or better yet, both. There is no road except the long and winding one to get the result.

This way, one calculation (that of the right password) is still very very fast. To honest users, nothing perceptibly changes. One tenth of a second or one billionth of a second don't seem to differ too much.

But one billion calculations (those to find which is the right password among a billion candidates - and in reality there are many, many more) will be agonizingly slow, guaranteeing that a "brute force" check of all possible passwords is doomed to failure.

So if we have a hashing algorithm that's too fast, we require not its first iteration, but its (say) millionth. If safe. Hopefully there is no way (that we know of) to jump straight to the millionth result; you have to calculate them all. And if this can't be done - if the iterations can be "short-circuited" to arrive at the answer faster - then we say the algorithm isn't secure (enough).

LSerni
  • 22,670
  • 4
  • 51
  • 60
4

Password hashes are meant to be a computationally slow calculation because in the event that the password hashes are ever leaked it can significantly slow down an attacker trying to find the plaintext password.

Timothy Faraci
  • 81
  • 1
1

If a password hash is slow to calculate, it makes brute-forcing a password much, much slower, which is going to add up over a large dataset or number of guesses. If it takes much longer, you gain that much extra time to deal with the breach.

Philip Rowlands
  • 1,789
  • 1
  • 13
  • 27
0

With it, you can add a linear hardness to the dictionary attacks. I.e. appling a complex salting algorithm, you can make the computation need of the dictionary attacks n-times larger. For example, you can make it 1000 times larger.

In algorithmical sense, it is not very useful, because as we can see, the computing power grows mainly exponentially with the time. But it is still an additional layer of security.

peterh
  • 2,958
  • 6
  • 26
  • 32