What's the difference between PBKDF and SHA and why use them together?

Question

I've been reading a little bit about hashing lately and according to AgileBits, they use "SHA512 within PBKDF2" in their new vault file.

I've looked in Wikipedia for both names and I know PBKDF2 is a key derivation function and SHA is a cryptographic hash function but I can't really understand the difference and why they are both used together with one inside the other.

Can anyone explain this for a person without experience in cryptography?

(You can assume I only know about math, if necessary).

Answer 1

SHA-512 is a cryptographically secure hash, PBKDF2 is what we call a Password Based Key Derivation Function. If the resulting secret isn't used as key but as hash value it's also called a password hash. Password hashes differ from secure hashes in the sense that they contain a salt and a work factor / iteration count.

Both cryptographic hashes and password hashes are one way functions designed to create a short, fixed sized output from a given input. In the case of the password hash the input would be the password and salt. The size of the salt and the iteration count are commonly considered configuration parameters; both do of course influence the output of the password hash.

Password hashes are generally build on top of Pseudo Random Functions or PRFs. A usual form of PRF is a HMAC or Hash based Message Authentication Code, which in turn uses a hash internally. When hash-based PRFs such as HMAC are used then the type / size of hash used is often configurable. PBKDF 1 and 2 are examples of these kind of constructions. Password hashes however do not need to be build using hashes. Any other PRF, such as ones based on symmetric ciphers, may do. bcrypt for instance is build on top of Blowfish, a block cipher.

Password hashes need a salt so that identical passwords won't map to the same hash. They therefore also prevent rainbow tables (that contain pre-calculated hashes which cover a wide range of related passwords) from being useful. Furthermore they contain a work factor / iteration count so that an attacker needs to perform more work to calculate the hash of each possible password. This is needed because most passwords are not random enough. Without the work factor the attacker would be able to test vast amounts of possible passwords using brute force or a dictionary attack.

Some password hashes also contain methods for deliberately increasing memory usage during the entire runtime of the password hash. This mainly makes it harder to implement the password hashing scheme in hardware, which can speedup password hashing significantly - similar to how mining hardware can speed up BitCoin mining. scrypt is an example of such a password hash.

Answer 2

To paraphrase my answer to an earlier question, PBKDF2 is a generic high-level algorithm that internally calls a pseudorandom function (PRF) to process its input. The PBKDF2 spec does not mandate any particular PRF, so implementors are free to choose any PRF they want (as long as it meets the definition of a secure PRF, and can accept the input PBKDF2 gives it).

As it happens, by far the most common choice of PRF for PBKDF2 is HMAC, which is another high-level construction that internally uses a cryptographic hash function. Again, the HMAC spec does not mandate any particular hash function,* so implementors are free to choose any hash they want. Probably the most common choice today is one of the SHA-2 family of hashes, which include SHA-256 and SHA-512.

So "SHA512 within PBKDF2" almost certainly means that they're using PBKDF2 with HMAC as the PRF, and with SHA-512 as the hash inside HMAC.**

What may be confusing is that, at a glance, this PBKDF2-with-HMAC-with-SHA512 may look like it's doing something very similar to just plain SHA-512: both take an arbitrary password as input and turn it into a pseudorandom bit string from which the original password cannot be easily reconstructed. However, there are actually several differences, the most important ones being that:

• SHA-512 is fast. Very fast. PBKDF2 is deliberately slow to compute, and its slowness can be controlled by adjusting the iteration count parameter.

• As a direct consequence of its speed, SHA-512 alone is vulnerable to brute force password guessing attacks using software like hashcat, which simply generate lots of passwords and hash them until they find one that produces a matching hash. A single modern CPU can easily hash millions of passwords per second, and GPUs are even faster.

In addition, there are a few other minor differences with noting:

• PBKDF2 takes a "salt" parameter, which can be used to ensure that the outputs are unique even if the input passwords are not. (Using a salt also thwarts precomputation-based attacks, since the attacker cannot usefully begin hashing guessed password before they know the salt.) SHA-512 by itself does not have the concept of a salt, although an equivalent effect can be achieved e.g. by prepending the salt to the password.

• SHA-512 always produces a 512-bit output (hence its name), although you can always truncate it to a shorter length if you don't need the full 512 bits. PBKDF2 can, in principle, produce output of any length, although in practice using it to generate more than one internal hash output's worth of bits is not recommended.

---

^{*) The original HMAC definition and security proofs effectively assume that the hash function used is of a particular type known as a Merkle–Damgård hash function. As it happens, all the most popular cryptographic hash functions for the past several decades, including the SHA-2 family, have been of this type, so this limitation has not been much of an issue in practice. This may be gradually changing with the standardization of SHA-3 (a.k.a. Keccak), which is not a Merkle–Damgård hash, but conveniently, comes with its own security claim for HMAC-SHA3.}

^{**) This is a fine and traditional choice, as far as it goes. It's not as resistant to GPU-based and other parallel attacks as more modern KDFs like scrypt or Argon2 would be, but it's still a lot better than plain old un-iterated hashing. That said, to properly evaluate its security, we would also need to know the iteration count used for PBKDF2. Unfortunately, many PBKDF2 implementations tend to use the old "recommended minimum" of 1000 iterations, which is little more than a speed bump nowadays. Personally, on a modern CPU, I'd prefer something closer to 1,000,000 or 1,000,000,000 iterations.}