1
$\begingroup$

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?

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Let's say the key derived with the function is also used as in password verification mechanism. $y$ equals $E_{K}(0^{b})$ and verification is performed by seeing if $D_{K}(y)=0^{b}$. What would the strength of that be? $\endgroup$ – Melab Apr 17 '16 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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