Score:4

Crypto

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

Puruporo

12/28/23, 12:32 AM

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?

481

2 + 2

key-derivation

password-based-encryption

pbkdf-2

sha-512

password-hashing

fgrieu

12/28/23, 4:58 PM

`PBKDF2` has an output width parameter. At what values is it set?

Puruporo

12/29/23, 10:49 PM

256bits with SHA-512

Score:6

Crypto

forest

12/28/23, 2:33 AM

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.

+ 0

Score:0

Crypto

Ángel

12/28/23, 3:51 PM

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.

+ 5

Puruporo

12/28/23, 3:59 PM

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)?

Ángel

12/28/23, 4:29 PM

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.

fgrieu

12/28/23, 5:04 PM

@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?

Puruporo

12/28/23, 5:41 PM

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

Ángel

1/3/24, 11:07 PM

@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_

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.