4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ PBKDF2 has an output width parameter. At what values is it set? $\endgroup$
    – fgrieu
    Dec 28, 2022 at 16:58
  • $\begingroup$ 256bits with SHA-512 $\endgroup$
    – Puruporo
    Dec 29, 2022 at 22:49

2 Answers 2

6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ So this setup may be useful if I want more security than 200k iterations (but can't run more than 200k iterations once) but not good if I use it to split the original iteration count (and expect same level of security)? $\endgroup$
    – Puruporo
    Dec 28, 2022 at 15:59
  • $\begingroup$ You could consider it like that. It's not clear to me if those two 100k PBKDF2 would provide a security level similar to 180k or more like 120k. $\endgroup$
    – Ángel
    Dec 28, 2022 at 16:29
  • 1
    $\begingroup$ @Angel: I do not see any attack nor definition of security that would make the proposed construct weaker than PBKDF2 with 200k iteration, when there are more than a few possible passwords. Do you? $\endgroup$
    – fgrieu
    Dec 28, 2022 at 17:04
  • $\begingroup$ If we assume that the attacker always wants to use all available cores (lets say 4), attacker needs to choose between trying 4 different passwords with 2xPBKDF2 runs per core or 2 different passwords with 1xPBKDF2 run per core. That would make the perceived penalty for the attacker higher than penalty for the legitimate user? I can not think cases where the attacker normally uses only half of the cores available (compared to legitimate users who normally use only 1 core for the key!). $\endgroup$
    – Puruporo
    Dec 28, 2022 at 17:41
  • $\begingroup$ @fgrieu the point is that with specialized hardware we are playing with different rules. But I'm unable to exactly quantify the value for that somewhat $\endgroup$
    – Ángel
    Jan 3, 2023 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.