Does combining multiple PBKDF2 keys result higher iteration count when using same password but different salts?

Question

I did some experimenting with web subtle crypto.

I derived a key using PBKDF2 with SHA-512 and 100 000 iterations and timed it. Doing same with 200 000 rounds doubled the time as expected.

Then I did PBKDF2 twice in parallel, both with same password, same iteration count (100k) but different salts. This took about same time than doing one time 100 000 iterations. I took the results and hashed those to create one key final result key. So the operation was: SHA-512(PBKDF2(password, salt1, 100000), PBKDF2(password, salt2, 100000))

So the question is, is that last combined key (100k + 100k) as strong as traditionally created key with 200k iterations? Can I use this to save time when doubling the iterations? And if so, should I use HKDF to combine the keys?

Answer 1

By performing two PBKDF2 computations in parallel and combining the results, you're increasing the effort it would take an attacker to break the keys without increasing the amount of time it takes you to compute it. You can increase the number of parallel PBKDF2 computations you are performing until you're no longer seeing any performance benefit (probably up to the number of cores you have).

Every time you double the number of parallel computations, you effectively add a single bit to the final hash (compared to a single hash with no slow KDF). A password with $n$ bits of entropy run through 100,000 PBKDF2 iterations adds $\log_2(100000) \approx 16.6$ bits of entropy. If you do that two times in parallel, you add another bit. If you do it four times in parallel, you add one more bit. Eight times adds one more bit still. Thus, even if you have eight cores and you use all of them, you only add 3 bits of entropy to your single-threaded 100,000 iteration PBKDF2. However, if you have eight cores, there's no downside to utilizing them all, even if you are only gaining a few more bits.

Combining the keys can be done in any number of ways. You could hash them together, XOR them together, or run them through HKDF. I would, however, recommend you use a different KDF. Argon2 will utilize as much parallelism as it can, while also being memory-hard, a feature PBKDF2 lacks.

Related: Multithreading PBKDF2 or javascript alternative

Answer 2

Can I use this to save time when doubling the iterations?

Yes, per your own tests. Note that you actually need to parallelize it, if you were using a language/compiler that calculated the first pbkdf2, and after it finishes the second pbkdf2, you would not get that timing improvement.

So the question is, is that last combined key (100k + 100k) as strong as traditionally created key with 200k iterations?

This is an interesting question.

First of all, the two components of the final password hash depend on the same password, so an attacker could not reuse half an output for another iteration (this is generally not possible since the goal of the iterations is precisely that the computation is not parallelizable), so we are fine on this front.

Then, we shall take into account you half the time you need for computing one global password hash, but so does the attacker. However, the attacker already has a parallelizable problem (trying many passwords). So, if an attacker needs half the time, but also computes half the passwords (because when they are now using two cores per password instead of one), you would end up even.

Things get more complicated, though, as an attacker would be unlikely to be using CPU cores for password bruteforcing (with the above result) but GPU cracking. In that case, computing two PBKDF2 for the same password (albeit different salts) may be a simpler calculation than two PBKDF2 for different passwords. Since the salt is only used on the first round of the multiple per-block iterations, that does seem to be the case (but I'm no GPU programmer, plus there may be differences between implementations).

So, I would conclude that computing two 100k PBKDF2 is not stronger than one 200k PBKDF2, and probably somewhat weaker.

On the other hand, the attacker would probably already have code for in-parallel bruteforcing PBKDF2 (likely written by others), whereas needing to adapt it for your custom setup, and the final combining of the two pieces would require some costly human effort (that is only to be paid once, though), which might offset the previous advantage.

should I use HKDF to combine the keys?

I don't think it wil matter much which kind of (cryptographic) function you use for that final combination, but HKDF seems a reasonable option.