PBKDF security if all but one keys are exposed

Question

I'm trying to understand the security of KDF but stuck with PBKDF case (case 3). Suppose, we have the following settings:

$KDF(SK,salt_1) \rightarrow k_1$

$KDF(SK,salt_2) \rightarrow k_2$

The adversary $A$ knows $salt_1$, $salt_2$, $k_2$ (and maybe even more derived keys $k_j$ for salts $salt_j$). His goal is to get $k_1$. Let even help him by makeing all salts closely related and haveing the same substring. Can $A$ learn $k_1$ from $salt_1$, $salt_2$, $k_2$?

1. In the best (and almost unrealistic) case $SK$ is random and uniformly distributed in key space $K$. In this case, we can use some PRF $F$ to derivate a key $k \leftarrow KDF(SK,salt,l):=F(SK,salt||0)||F(SK,salt||1)||...||F(SK,salt||l)$
   In such case $A$ can't learn $k_1$, otherwise $F$ is not secure PRF.

2. Slightly worse case: $SK$ is uniform in some subset of $K$. We need Extract-then-Expand KDF - so we use HKDF. At first we extract $k_{short} \leftarrow HMAC(salt, SK)$ and then expand $k_{short}$ to $k$ by using HMAC as PRF with key $k_{short}$. Again, $A$ can do nothing as long as underlying compression function in a hash is PRF and $SK$ has enough entropy.

3. Worst case: $SK$ is a password. Suppose it's PBKDF1 and $k \leftarrow PBKDF1(pwd,salt,c) = H^{(c)}(pwd||salt)$

On the one hand, $A$ still should learn nothing about $k_1$ if the hash is secure. On the other, I've got a feeling that he knows enough data to come up with something better than bruteforce. Am I wrong?

Answer 1

In case 3, one must consider that the knowledge of $salt_2$ and $k_2$ (or/and other ones) allows to test a guess of $pwd$ with about $c$ evaluations of $H$. The "brute force" attack becomes doing this with a dictionary of passwords with the most common first. Password crackers using GPUs or ASICs reach astonishingly high hash rates, and for $c$ in the thousands, if a password is memorable, it is best to consider that it is not safe form a well-funded attacker. That's why state of the art is memory-intensive password hashes, e.g. Scrypt, Argon2, Balloon, which make a large difference.

In a multi-target attack (where several $pwd$ each with their associated $salt_2$ and $k_2$ can be attacked, and finding any is a success for the attacker), the attacker should try the most likely $pwd$s on all available instances of the problem s/he's trying to attack before moving to less likely ones. Practical chances of success grow very fast with the number of different users having chosen $pwd$ !

I'm unaware of another weakness of PBKDF1 / $H^{(c)}(pwd\mathbin\|salt)$ that would be exploitable in the situation, and leak any info about $k_1$ without a successful guess of the full $pwd$ (if we leave a aside implementation issues like side-channels).

Note: in theory, the many iterated hashes of PBKDF1 reduce the possible values for the outcome as $c$ increases (see this). A wild guess of $k_1$ with a sizably better than random chance to match is plausible. However, for any hash at least as wide and remotely secure in the ROM as SHA-1, the probability of success remains so low that this is never a practical issue; and truncating the final result of PBKDF1 (which dramatically increases the probability of success of a wild guess) reduces to almost nothing the advantage that could be obtained by exploiting said effect of many iterations.

PBKDF1 successor's PBKDF2 fixes the above theoretical weakness, and allows producing large output, which can come handy. Neither comes with a security argument that it is a strong PRF (as HMAC does). However the main reason to discourage using PBKDF1 or PBKDF2 is that they are among what gives the least resistance to brute-force password crackers for a given level of effort by the legitimate user (number of iterations $c$).