Why does BCrypt.net GenerateSalt(31) return straight away?

Question

I stumbled across BCrypt.net after reading Jeff Atwood's post about storing passwords which led me to Thomas Ptacek recommendation to use BCrypt to store passwords. Which finally led me to this C# implementation of BCrypt

In the comments on the last link above someone asked "Why do GenerateSalt(30) take for ever, but GenerateSalt(31) seems to take no time at all?"

I ran BCrypt.HashPassword(password, BCrypt.GenerateSalt(31)) and got my result in 0 milliseconds.

I've been running BCrypt.HashPassword("password", BCrypt.GenerateSalt(30)) for over 5 minutes now and still do not have a result.

I realize we'll probably not need a randomly generated 30 character salt to create our password hashes (or irreversible encryption in BCrypt's case) for years. EDIT I should have read the code a bit, logRounds doesn't have anything to do with the salt length. Thanks Aaronaught.

So, why does GenerateSalt(31) return a value almost instantly (when it should take about twice as long as GenerateSalt(30)?

UPDATE

here is the fix:

private byte[] CryptRaw(byte[] password, byte[] salt, int logRounds) {
    // ... snip ...
    uint rounds = 1U << logRounds;
    // ... snip
}

Answer 1

If hashing with GenerateSalt(31) returns almost instantly, that's a bug. You should report that upstream (I have, for jBCrypt). :-)

By default, the log-rounds is 10. This means that (if I remember correctly), 1024 rounds is used. Each time you increment the log-rounds, the number of rounds is doubled.

At 30 log-rounds, you're doing 1073741824 rounds. That rightfully takes a long time. At 31 log-rounds, 2147483648 rounds should be being done, but I suspect that the particular implementation you're using overflows instead. :-(

Answer 2

I suspect that the bug is here:

private byte[] CryptRaw(byte[] password, byte[] salt, int logRounds) {
    // ... snip ...
    int rounds = 1 << logRounds;
    // ... snip
}

When you specify 31 for the logRounds, it computes that as 2^32, which can't fit in an int and overflows, so the hash is actually done in... er, zero passes. The author should have used uint instead. Easy to fix!

---

Also wanted to comment on this:

I realize we'll probably not need a randomly generated 30 characters salt to create our password hashes...

Note that the logRounds parameter does not refer to the number of characters/bytes in the salt, which is always 16. It refers to the logarithmic base of the number of passes that the hash will take to compute; in other words it's a way to make bcrypt scale with Moore's Law, making the function several orders of magnitude more expensive to compute if computers ever get fast enough to crack existing hashes.