What is the difference between Key Derivation Function and (salted) Hash?

Question

I see in this post that the main difference is that KDF outputs have "certain randomness properties", and I don't understand what does it mean. Suposing that that "certain randomness properties" are for protect from rainbow tables and that precomputed stuff.

But using hash with proper salting we can also protect from those attacks. So in that sense I believe that there's no difference between this two tools, differing only in the implementation.

I also know that other aim of the KDF is to be enough slow in order to slow down hypothetical attacks, without spoiling user experience in terms of speed. Well, in the strict sense, this could be also achieved in hashing adding some useless operations (e.g. for(i = 0; i < 1000000; i++); ), even if it wouldn't be very clean.

So, what's the difference? Is one better than other? When would we have to use one, and when the other?

Answer 1

There are actually two kinds of KDFs. One kind is designed to derive a key from high-entropy input (like another key); this can be done with a fast keyed hash like HMAC. The other kind takes a password as input. Passwords are low-entropy; they're not inherently very hard to brute-force. A good password hash thus has to be slow.

In your question, you said that adding for (i=0; i<bignum; i++); would slow the hash. This is actually completely useless. The attacker does not have to play by your rules. Hashes need to protect passwords when the attackers have a copy of the hashes. If the attacker can compute hashes quickly, it doesn't matter how slowly you compute them. Hashes need to be inherently slow; there should be no shortcuts to evaluate them faster than the legitimate server.

The "randomness properties" are because a KDF needs to produce a key. They have nothing to do with precomputation, including rainbow tables. Cryptographic algorithms typically make certain assumptions about the key; among other things, they normally assume it was selected totally at random from the set of possible keys. Keys are also expected to be a certain length; their derivation functions need arbitrary-length output. In contrast, it's OK if a password hash has lots of structure to the output. Maybe there's a 70% chance that adjacent bits have the same value. Maybe it spreads 128 bits of entropy into 4096 bits of output. As long as it's hard to reverse, that's a fine hash, but it's unsuitable as a key.

A secure password-based key derivation function is a secure password hash (PBKDF2 is in fact one of the big 3 hashes). The reverse is not necessarily true. Which one to use is simple: use a password-based key derivation function to derive a key from a password, and a hash to store passwords.

Answer 2

Just addressing the other answer (cpast's), with regards to when to use one or the other for managing passwords:

This is actually completely useless. The attacker does not have to play by your rules. Hashes need to protect passwords when the attackers have a copy of the hashes. If the attacker can compute hashes quickly, it doesn't matter how slowly you compute them. Hashes need to be inherently slow; there should be no shortcuts to evaluate them faster than the legitimate server.

sha256sum(sha256sum(sha256sum.....(salt + master password)))...

Applying the hash numerous times DOES increase the difficulty for an attacker trying to retrieve a password from the hash, and it DOES make the password derivation function inherently slow. The attacker would need to go through every single SHA256 function for every attempt.

This would make it as slow as the other key derivation algorithms (or even slower/harder).

Cryptographic algorithms typically make certain assumptions about the key; among other things, they normally assume it was selected totally at random from the set of possible keys. Keys are also expected to be a certain length; their derivation functions need arbitrary-length output. In contrast, it's OK if a password hash has lots of structure to the output. Maybe there's a 70% chance that adjacent bits have the same value. Maybe it spreads 128 bits of entropy into 4096 bits of output. As long as it's hard to reverse, that's a fine hash, but it's unsuitable as a key.

Running just one pass of SHA256 will produce output that is seemingly randomly selected from the set of integers up to 2²⁵⁶. 2²⁵⁶ is an astronomically large number, and truncating it allows the user to sample arbitrary length output without losing security (as long as they sample enough entropy of course).

There is negligible chance that there could be "lots of structure to the output" of a SHA256 function to the detriment of the generated password. And even then, an attacker has no better strategy than guessing random numbers if they want to crack the hashed output (it would be futile to even try).