How is PBKDF2 so much better than normal Hashing or even using HMAC

Question

I do not know how the Key Length extension attack works. So if we leave that aside for once, and say just about usual brute-force attack on the hash, I don't really know how is PBKDF2 so much better than usual hashing.

Mathematically I know that PBKDF2 is so better against rainbow table attacks and also slow to recreate, but as computing power is moving up in the world, how it's still keeping its integrity?

For an HMAC we use a salt, also we can do the same for an usual hash.

So, SHA256('Hello'), is easily rainbow tabled. So if I prepend a salt, it's a little bit better, like SHA256(salt+msg), but Salts are usually kept in DB as clear text, so if some hacker is able to crack that salt, he can manually append the salt and perform the same operation.

Now in HMAC, -> H(key(opad) + h(salt + key(ipad))) is mathematically secure, but one can easily brute-force all possible password by running it through an HMAC operation (if he knows the salt), and he gets the key. A bit slower, but possible, and in pbkdf2, this whole process is looped maybe a million times even, with that much mathematical complexity, yet, if one gets the salt. He could simply run a big list of passwords with through another pbkdf2 function, and maybe very slow, but still possible, right?

• So what's the use of this much complex algorithms by hashing and hashing with previous results of HMAC and so on, if it's still very much prone to a slower bruteforce?

Answer 1

• The salt of a password hash mitigates multi-target attacks like rainbow tables (and variants like the parallel rainbow table search machine), if you use a distinct salt for each user. Effectively, a distinct salt for each user means each user is using a slightly different hash function, so the advantage of any batch attack on many instances of the same hash function goes away. This applies equally to HKDF, to PBKDF2, to scrypt, and to argon2id, and even to $\operatorname{MD5}(\mathit{salt} \mathbin\| \mathit{password})$.

• The cost parameters of a password hash—iterations, memory, and parallelism—raise the cost of testing a guess for the password. The legitimate user who knows the password only pays that cost once (or twice or three times if they're fat-fingered). The adversary who doesn't know the password has to pay the cost for every guess.

  But you and the adversary are a little different. You, the legitimate user, want authentication or key derivation to happen before you get bored, when you're hashing a single password—you care about latency. The adversary doesn't care whether it takes 1 sec or 1 hr to test a single password guess, exactly; a serial password-guessing machine that tries 3600 passwords in sequence second by second over the course of an hour, vs. a parallel password-guessing machine that tries 3600 passwords simultaneously over the course of an hour and gets an answer to all of them in the end, still gives a password-guessing rate of 3600/hr—the adversary cares about throughput, or about price/performance ratio to determine how much throughput they can get by throwing more money at the task.

  The dedicated adversary will use all tools available to them—not just run a password cracker on their laptop, but maybe run it on a GPU, or an FPGA, or even fabricate application-specific integrated circuits on a silicon die. The adversary will use the smallest password-guessing circuit they can on the die, corresponding to the least energy consumption and heat dissipation, and fit as many of them in parallel as they can.

  Different cost parameters have different impacts on an adversary's actual costs. So what do the cost parameters do?

  • Memory. If you use $m$ times the memory with a memory-hard hash function in the same time, you present the adversary with a choice: make the password-guessing circuit $\Omega(m)$ times larger to store the memory, or make each password guess take (say) $\Omega(m^2)$ as long to recompute what isn't stored. The adversary would rather use (say) double the space to fit twice as many password-guessing circuits on the die; by doubling the memory requirements they can't take advantage of that parallelism.

  • Parallelism. If you use $p$ times the CPUs in parallel to compute a password hash in the same time, you present the adversary with a choice: make the password-guessing circuit $\Omega(p)$ times larger like you have $p$ CPUs in parallel, or make each password guess take $\Omega(p)$ as long. The adversary would rather use (say) double the space to double the password-guessing throughput; by doubling the parallelism requirements they have to use the parallelism for a single password guess and not two password guesses in parallelism.

  • Iterations or time. If you use $t$ times the iterations to compute a password hash with the same memory and parallelism, the adversary also has to compute the same number of iterations sequentially on any password-guessing circuit. So on any particular password-guessing machine the adversary has, however much parallelism or whatever fabrication process they use, their throughput is divided by $t$.

  Modern password hashes support using all of these resources available to the legitimate user—memory, parallelism, and time—in order to drive up the adversary's costs. Plain SHA-256 and HMAC (and HKDF) do not have cost parameters; rather they, or BLAKE2 or SHA-3, are often used as components in password hashes. PBKDF2 only takes advantage of the user's time, on a sequential CPU with fixed memory—it does not take advantage of any additional CPUs available to the user or any spare memory in the user's computer.

  There are better designs than PBKDF2: bcrypt uses a little more memory than (say) PBKDF2-SHA256 but the memory is not scalable; scrypt can scale in memory and time, but not in parallelism; and newer designs like Argon2 and Balloon hash can scale memory, parallelism, and time.

Answer 2

The point is not to make the attack infeasible time-wise. Computational resources (usually, area*time, which is roughly a measure of the monetary cost) needed for the attack is the only thing you can hope to increase here.

As you observed, it is always possible to parallelize brute-force search of passwords, so the best you can do is increase the computational effort it takes to check a single password. Sure, even if checking one password required 10 seconds, the attacker could always put millions of ASICs in parallel and bruteforce everything in 10 seconds. To put it differently: the adversary can always get the password using little time, but this requires a lot of area (i.e., number of parallel computing units used simultaneously). Essentially, the adversary is forced to always invest a large quantity of area $\times$ time.

The point is that doing so will cost a lot of money to the adversary: it is usually considered that area $\times$ time is a decent (rough) approximation of monetary cost of the attack. So the hope is to make this attack less interesting money-wise.

A further note: the quantity area $\times$ time does in fact not perfectly measure monetary cost, as experiments with modern ASICs have shown. However, a lot of research has been devoted to find much better measures that map more closely to monetary cost (e.g. 1, 2). There are a bunch of satisfying candidates, and several constructions of hash functions which provably maximize this measure for the adversary. PBKDF2 does not seem to be the best one out there - but it is an old, well-established alternative which, experimentally, does not perform too bad with respect to the monetary cost it incurs to the adversary.

Answer 3

The "normal" hashing like MD5, SHA-1, SHA-3 have their primarily goal on checking the integrity of data / files. Even when used for big files, they need to be efficient. That's why all of them were designed to be as efficient as possible (fast and use little memory).

When you apply these algorithms to passwords (that are normally pretty short, mainly below 20 bytes), these advantages show their drawbacks, they make brute forcing and parallel computation easy.

The password derivation or password stretching hash functions have an opposite goal. They were designed to be as resource hungry as possible (use much CPU and much memory). Many of such algorithms, like Argon2, have configurable parameters that affect CPU usage and memory usage.

"A bit slower ... looped maybe a million times" - this is a wrong statement. When you calculate it for a single user one time, user may be will not even notice any difference. Bug if you are brute forcing 10^15 passwords, the difference will be huge. If you can brute force password with a normal hash withing 1 year, then adding 1 000 000 iterations means you will need 1 000 000 years, or you will need 1 000 000 computers to do it within 1 year. Means, you would need 1 000 000 more money to pay for these computers. To use CPU efficiently, brute forcing uses often multiple threads on the same CPU. Argon2 and similar algorithms prevent it. If you set hashing to use 10MB or 100MB RAM per hash, then the number of threads will be limited by the RAM on a particular PC and the attacker will need more RAM (which is expensive) and more PCs (because the number of threads will be limited).

To your wording: "How is PBKDF2 so much better than normal Hashing". Better for what? For password derivation / stretching they are better, but for file integrity checks the normal hashes like SHA-3 are better, obiously.

Answer 4

So what's the use of this much complex algorithms by hashing and hashing with previous results of HMAC and so on, if it's still very much prone to a slower bruteforce?

We often use KDFs to hardening the process to generate encryption keys (and authentication digests too) from somehow possible simple and guessable customer's / client's passwords. When we use random / noise bits possibly derived from some key agreement protocol or issued as an HTTPS API Key, HMAC suffices here. Note that both PBKDF2 and HMAC take a salt for private integrity verification as well.

So, this problem is regarded as how much noise we have from the input message to compute a hash image. A human readable password is easy to break with brute force due the use of simple/plain characters. KDFs let us tune execution parameters for this digest algorithm, making infeasible to find second preimages from known digests with fast dedicated hardwares such as FPGAs and ASICs by embedding a huge memory & some time consumption on the algorithm (or at least, KDFs try to race against ever more powerful hardwares produced).

Such security concerns are important if you or your clients have too much skin in the game to lose. Think in a core banking service or a healthcare startup, here you want to encrypt all data with KDFs on encryption keys to be a good mitigation in the case of data breaches. The attacker can always regard your API as an external/online Oracle and spoof IPs to bypass rate-limits, all the time costs here will be latency, bandwidth and endpoint processing during login brute force, so KDFs also help to reduce the vector attack here.