Encryption strength when using a PBKDF

Question

Suppose:

• $m$ is a positive integer.
• $n=2 \times m$.
• $H: \{0,1\}^{*} \rightarrow \{0,1\}^n$.
• $p$ is a password.
• $s$ is a salt.
• $K=\{0,1\}^n$ is the derived key.
• $PBKDF(p,s)$ derives a key from $p$ and $s$ using $H$ in some manner.
• $K=PBKDF(p,s)$.

Given the birthday paradox, is the key strength here $m$-bit or $n$-bit?

Answer 1

Actually, the strength of the derived key is likely to be limited by the strength of the password; for example, if the user selects the password "password", well, that's likely be to within the first couple that an attacker checks.

However, if we assume that the password is stronger than what most people select, then the next limiting factor is $n$. The birthday paradox doesn't help the attacker; he's not looking for two different passwords that derive the same key. Instead, he's trying to find a password that generates the derived key; a guess at the password has a probability $2^{-n}$ of mapping to the right value (remember, we assumed above that the probability of him happening to guess the original password is even smaller), and so that's the probability per guess of him being able to break the system.