9

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?

Community
  • 1
Julen
  • 311
  • 3
  • 6
  • 3
    Adding useless operations does not slow down the attacker, because the attacker does not have to execute those operations. Technically, there is no work factor provided by an empty loop. – cpast Jul 30 '15 at 23:34

2 Answers2

13

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.

cpast
  • 7,223
  • 1
  • 29
  • 35
  • 4
    This all seemed well and good until "use a hash to store passwords." Bcrypt/scrypt/PDKDF2 are the state of the art in encrypting passwords, which are obviously KDF's, and you just said use a hash to store passwords, not a kdf. So that last sentence isn't quite right there, is it? Or am I misunderstanding you somehow? – temporary_user_name Mar 13 '16 at 08:33
  • 1
    Bcrypt is a password hash, NOT a kdf. – Patrick Nov 12 '18 at 22:22
0

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 2256. 2256 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).

Glorfindel
  • 2,235
  • 6
  • 18
  • 30
dcadf dfbdf
  • 1
  • 1
    You pretty badly misread both the question and the answer you're responding to. The question proposed `for(i = 0; i < 1000000; i++);`, which is a "do nothing" loop; there's no hashing (or anything else!) going on in the loop body, all it's doing is counting to a million (which will take a modern CPU somewhere under a millisecond, even if for some reason the whole pointless step wasn't optimized out). Also, just iterating the hash with no changes is better than nothing but not *good*, look up how PBKDF2 works. – CBHacking Jul 12 '21 at 06:47
  • Ah, my bad. I didn't realize he meant just adding basically a sleep statement. I thought he's applying the hash in a loop. In termms of why it's not good, I looked up some information about PBKDF2, and it seems that the main purpose of it is to slow down brute force attacks. Applying sha256 in a loop does that too. So why is PBKDF2 better? Is it with regards to OS specific nuances e.g. memory leaks? Or ASIC attacks (PBKDF2 is vulnerable here as well as sha256)? Or quantum computer threats? What is it exactly? – dcadf dfbdf Jul 14 '21 at 19:33