2
$\begingroup$

What is the likelihood of 2 bcrypt hashes colliding if they use the same work-factor and input?

Are bcrypt's salts large enough to prevent this from happening?

$\endgroup$

1 Answer 1

1
$\begingroup$

What is the likelihood of 2 bcrypt hashes colliding if they use the same work-factor and input?

You're describing this: $\tau_1,\tau_2=\text{bcrypt}(pw,cost), \Pr[\tau_1=\tau_2]$. This means that the collision probability comes down to the length of the salt. bcrypt uses 128-bit salts. So you expect to find a collision after doing roughly $2^{64}$ hashings (assuming you're PRNG is good).

If you really want to find a collision, $2^{64}$ is feasible. Especially if you'd use FPGAs / ASICs. The practical relevance of this is low though as you rarely see password database (with the same password) beyond $2^{35}$ and even then collision resistance isn't an all that important property of password hashing (what can you do if the tags collide?).

$\endgroup$
1
  • $\begingroup$ Considering that on average, you have to explore half of the space of possible values, to find a match while brute forcing: Shouldn't it be $2^{127}$ hashes instead of $2^{64}$? $\endgroup$
    – das Keks
    Jan 31 at 5:44

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.