What differentiates a password hash from a cryptographic hash besides speed?

Question

I understand that password hashes like bcrypt have the principal property of taking a long time to run, but I'm wondering what if anything about password hashes make them superior to merely running a fast cryptographic has a bunch of times.

In particular, why does bcrypt exist when I can just run SHA-256 100000 times? Furthermore, it seems relatively extensible to adapt to increases in computing power. When computers get 100000 times as fast as they are today, I can just reapply the hash to my password hashes 100000 times and at verification time run SHA-256 100000*100000 times to validate a password attempt. Are there flaws in this naive approach. Are there other properties of password hashes that make them particularly suited to hashing passwords? Lack of parallelizability, space complexity, something else?

My question comes about when analyzing a prominent response to the June 2012 incident in which 6 million password hashes were stolen from LinkedIn. In the article, the author emphasizes the value of using a password hash instead of a fast cryptographic hash in validating user passwords. I understood the basic argument for having a hash that's slow but failed to glean from it particular advantages of "password" hashes that made them distinct.

Answer 1

To the best of my knowledge there is no formal distinction, since "password hashes" aren't formally defined.

That said, if you look at this presentation from the author of scrypt you'll see that he wanted:

1. Password hashing to be CPU hard (i.e. to require significant amounts of CPU processing, in a manner that cannot be optimized away).

2. Password hashing to be memory hard, i.e. to require large amounts of RAM capacity and RAM I/O bandwidth.

Being CPU hard helps delay offline brute force password breaking, as you note. Being memory hard helps guard against getting dramatic speedups from using a different type of hardware.

Simple SHA hashes require minimal internal state, and can as such be massively accelerated by running hashing in parallel on the 256+ cores of a modern graphics card. An even larger speedup could be had by creating a bunch of FPGA / ASIC chips dedicated to running SHA operations in parallel.

Being memory-hard gives a measure of protection against this, because currently there is no cheap technology to scale memory-I/O. FPGA's are comparatively 'cheap' to make; but large amounts of low-latency memory isn't.

---

To your questions:

I can just run SHA-256 100000 times?

If you loop through the same hash function many times, then there might be a small loss of entropy each time, if the hash function isn't ideal. See "Why does PBKDF2 xor the iterations ..". If you improve your own suggestion, for example by mixing in the salt at each iteration, then you get close to the design of PBKDF2. In that case you should use PBKDF2 instead, because PBKDF2 is a mature and peer reviewed design.

Furthermore, it seems relatively extensible to adapt to increases in computing power. [...] I can just reapply the hash to my password hashes 100000 times and at verification time run SHA-256 100000*100000

That works. At verification time the end user gives you his password in plain text. So you could also verify the password against the old hash using the old hashing function, and create a new hash from the plaintext, using the new hashing function.

---

For more, see the scrypt presentation as well as the hash + password tag on Crypto, as well as the past discussions here.

Please note: It's great that you learn about this for your own interest and understanding. When it comes to building production software, you should not create your own password hashing implementation -- you should use an appropriate higher-level library, one that has seen extensive security scrutiny.

Answer 2

Usually "password hashes" like bcrypt use cryptographic hashes like SHA, so it is like "running a fast cryptographic hash a bunch of times"

Cryptographic hashes are designed to be fast and collision resistant.

Key derivation functions like bcrypt are designed to do what their name suggests. This has some advantages:

• If the derived key is stolen it is hard to guess the master key.
• You can implement a protection against weak keys.
• scrypt allows you to also choose how much memory should be consumed (an important factor for bruteforce on GPUs)

Read more ar http://en.wikipedia.org/wiki/Key_derivation_function, http://en.wikipedia.org/wiki/PBKDF2, http://en.wikipedia.org/wiki/Bcrypt

But this perfectly sums it up: http://en.wikipedia.org/wiki/PBKDF2#Alternatives_to_PBKDF2

One weakness of PBKDF2 is that while its c parameter can be adjusted to make it take an arbitrarily large amount of computing time, it can be implemented with a small circuit and very little RAM, which makes brute-force attacks using ASICs or GPUs relatively cheap[15]. The bcrypt key derivation function requires a larger (but still fixed) amount of RAM and is slightly stronger against such attacks, while the more modern scrypt[15] key derivation function can use arbitrarily large amounts of memory and is much stronger.

Answer 3

The problem with just repeating a hash function like SHA256 over and over is that SHA256 pipelines very, very efficiently. An attacker may be able to perform hashes thousands of times faster than you just because he uses hardware specifically designed to do the hash quickly. Then he also gets the unavoidable benefits of more hardware, more money, and so on.

Say you use 100,000 SHA256 operations. An attacker could design a custom ASIC that does 5,000 SHA256 operations in an assembly line. Then he'll connect 20 of them. Then he'll start feeding passwords into the first one, one per clock cycle. Then, a split second later, he'll starting getting outputs from the last one, one per clock cycle. So now, rather than 20 chips getting him 20 times faster than you (if he had to use CPUs), he's two million times faster than you (because he can now do 100,000 SHA256 operations per clock cycle)!

Cryptographic hashes are very heavy on binary logic operations such as shifts and XORs. They generally have no feedback dependencies, don't require any decisions to be made, and so on. This makes them easy to implement on GPUs, FPGAs, and ASICs in ways that outperform general purpose CPUs by orders of magnitude.

In contrast, password hashes are very heavy on memory use and decision making. They require feedback dependencies that break pipelining. An attacker likely won't be able to do much better than using a large number of general purpose CPUs.

So, an attacker with \$2,000,000 to spend on SHA256 can spend \$300,000 designing an ASIC that can do SHA256 operations 1,000 times faster than a CPU. Then he can spend \$1.7 million on copies of the ASIC at \$60 each. That gets him to be 30 million times faster than you. An attacker with \$2,000,000 to spend on a password hash just buys lots of general purpose CPUs. So he can spend \$2 million on CPUs at \$40 each. That gets him 50,000 times faster than you. This difference is a factor of 600.

So, using a password hash that takes as much CPU time as a cryptographic hash disadvantages an attacker by a factor of 600. That's as good as adding 9 more bits of entropy to the password.