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's 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
}

Observer

Answer 1

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.

Organogenesis

See, if they tested rounds (at this point -2^31) using rounds != 0 instead of rounds > 0, then it would still have worked correctly! :-P – Irrefutable

@Chris: Lesson learned, always write your for loops with != in case of overflow! :P This is exactly why it's so dangerous for people to roll their own crypto functions; even the experts get it wrong! I guess this bug just never got reported because nobody has ever actually tried 31 log-rounds before... – Organogenesis

@David: Yep, that will do it. – Organogenesis

I've posted a related question here: #2223606 – Observer

Does the fix result in the same hash being generated when using rounds < 31? I'd like to implement the fix, but don't want to have to make all users change their passwords. Given the nature of the bug, I suspect the answer is "yes". – Catnip

@KeithS: What fix? If you use a uint instead then no, you'd get different results for rounds = 30 and rounds = 31. – Organogenesis

No, I mean if you change this line to use uints, will any arbitrary number of rounds < 31 produce the same hash for a given input/salt as it did before the fix? – Catnip

@KeithS: Why wouldn't it? A value in a uint variable is the same as a value in an int variable, the only difference is the range. Better yet, just test it on your machine, it should take 30 seconds. – Organogenesis

Answer 2

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. :-(

Irrefutable

this seems like a very likely explanation to me... I'll +1 even though I don't know for sure :) – Bethsaida

makes sense: if you double every time and it fails at 31, there's probably a 32bit integer involved (minus one bit for sign ) somewhere that should be using a long or decimal instead. – Editor