KDF followed by a Hash?

Question

It is my understanding that a KDF adds entropy, whereas a hash loses information.

I've read that KDF should be used to store passwords. I don't understand why we don't use a KDF and then a hash, so that – if the database of password is leaked – it would also be impossible to figure out the plain passwords.

So storing passwords in a database would be like this:

1. Use KDF to increase entropy (especially good if users are using short passwords),
2. Use a hash to lose information,
3. Store the hash.

Shouldn't this be the advised way to store passwords?

Answer 1

It is my understanding that a KDF adds entropy, whereas a hash loses information.

No deterministic process can add entropy. If the same input always produces the same output then the entropy associated with the output cannot be more than the entropy of the input.

The confusion probably comes from the practice of using password stretching to compensate for low entropy passwords.

The idea is that cracking a password with 40-bit strength hashed using an algorithm that requires 1 second to compute takes roughly as much time to crack as a password with 60-bit strength hashed using an algorithm that takes only 1 microsecond.

$$ 2^{40} \text{ guesses} \times \frac{1 \text{ second}}{\text{guess}} \approx 1.10 \times 10^{12} \text{ seconds}\\ 2^{60} \text{ guesses} \times \frac{10^{-6} \text{ seconds}}{\text{guess}} \approx 1.15 \times 10^{12} \text{ seconds}\\ $$

It is my understanding that a KDF adds entropy, whereas a hash loses information.

For any injective function, entropy out equals entropy in. For a non-injective function you end up mapping multuple inputs to the same output.

Some outputs become more probable and other outputs become impossible. The new probability distribution will have less entropy than the distribution associated with the input.

Both hash functions and KDFs are typically non-injective. However entropy loss is not a concern for passwords, assuming a few things. (Informal explanation shown below.)

---

---

Using some hash function with 256-bit output ideally means you won't see any collisions before trying around $2^{128}$ inputs. (The birthday bound of such a function.) If you test much, much fewer than $2^{128}$ inputs (passwords) then it will be extremely improbable that you see any collision.^*

Cryptographic hash functions are not truly injective, but if we know that for a given set of preimages (passwords) there are no collisions, then we can treat the (sub)mapping as if it were injective.

That is enough to informally conclude that no entropy is lost if a typical password is processed using a secure hash function. Weak passwords are then the weakest link in the chain, not the hash algorithm.

The number of unique passwords all of humanity has used is certainly insignificant compared to $2^{128}$. It is so small that the number of unique outputs (using some large ideal hash function) is practically certain to be the same as the number of unique inputs.

If you had more than 256-bit entropy input, then you would definitely lose some of that. The output of a 256-bit hash can, at most, have only 256 bits of entropy.

Between 128 bits and 256 bits you will lose entropy, but I think input entropy and output entropy would still be pretty close.

^{_{*Note: Be careful not to confuse things here. It's a common misconception that a password hash needs to be collision resistant. The hash function must be preimage resistant, but collision resistance is unnecessary if there is no harm in allowing users to have multiple valid passwords. For the purpose of validating passwords, it might be okay to use a non-collision-resistant hash as long as collisions are unlikely in a non-adversarial scenario.}}

^{_{Pre-image-resistance is necessary. Otherwise it would allow someone that knows an account's password hash to forge a password that would allow them to log in as that user. It's not possible for the authentication server to distinguish the original password from a second pre-image using only the hash, so it doesn't matter if the two passwords are different.}}

---

Use Argon2 !

Answer 2

It is my understanding that a KDF adds entropy, whereas a hash loses information.

Password Based KDFs can be seen as hash functions (or families of hash functions, depending on your definition), just ones with a lot of complexity. It is sometimes said that they "add entropy" but that usually means either

1. they combine entropy from a salt into the password hash (which you can do with any hash function), or
2. they make the password more computationally difficult to crack as if it had more entropy (also called computational entropy).

PBKDFs and hashes are irreversible; meaning that it is impossible to find a password without performing a brute force or dictionary attack. PBKDF's make it computationally harder to perform a brute force search and the salt makes it impossible to find matching passwords within a database.

Both PBKDFs and hashes "lose information" in the sense that their image (output) is smaller than their input domain. That does not make them stronger, however, since if two passwords give the same output hash, either can be used as authentication.

So using a hash after a KDF is at best redundant and can lead to less security through e.g. increased collisions.