The devil's in the details.
General a way to compare the passwords (chunks of memory) would be memcmp or strcmp. The default versions of these functions break out of the checking loop on the first inequal byte.
Unless they're using a cryptographically safe memcmp (which should XOR the memory to 0 or similar), the speed of the computation will vary based on how many leading characters match between hash(supplied password) and hash(saved password).
If the hash function is known, the attacker could use a chosen set of plaintext that they know give a different leading value once hashed. One of these inputs will take slightly longer than the rest. The attacker now knows the first byte of the hash. They repeat the previous step as many times as computationally possible (it will get harder to find inputs such that hash(input) starts with a chosen substring as that substring increases in length).
Then finally, using the known start of the hash value, use a dictionary attack to reduce the number of searches to a minimal set (by dropping all entries from the dictionary that don't start with the precomputed hash substring)
And then you think so what? There's no way an attacker can use that because all requests are transmitted over the internet where latencies are way, way bigger than a few clock cycles, right?
Wrong. Using statistical analysis over a vast amount of requests you can find out which ones execute a few clock cycles faster than others, and then you're home free.
Lesson learned: I'm not smart enough for security. :-)
>... even though the Internet induces significant timing jitter, we can reliably distinguish remote timing differences as low as 20µs.
Say I give you these results:
*
* *
*
* *
*
No real pattern, yea? So sample some more: *
* * *
* * * *
* * * *
*
Maybe nothing. So try more: * *
* * *
* ** *** *
* * ** * * *
* *
And more: * * * * *
* * * *
* * *********
********** * *
* * ** * *
Zomg. You have a discernable behavior. Adding more randomness would just give you the same easily-visible results after adding, say, 2x as many points, at which point you have this (expanded a little): * * * * * * *
** * ** * * * *
* * *** * **********
*************** * *
* * ** ** * * *Avoid the pain and burn the CPU cycles for all code paths. If you find that bcrypt takes up proportionally too much CPU, reduce the work factor by 1 until it's acceptable. Keep in mind that the vast majority of logins will be legitimate. For the small number that aren't and persist with failed attempts, let their IP get banned then you don't need to spend any CPU cycles dealing with them -- in this case, it would be fine to sleep an arbitrary amount of time and then display the banned notification.
It would be a bit of a hack compared to just using bcrypt every time, but it would save processing power, which may be useful in some contexts, like very energy-efficient devices, etc.
You seem to only be considering the case where the only logins you need to deal with are invalid logins. A busy and successful service will see the vast majority of logins being for legitimate, known users where the bcrypt check must consume CPU time. You have to design the system to be able to handle the workload from both good and bad logins without revealing information about a bad login to an attacker. Anything other than going through the same motions every time will leak information in ways you don't expect.
Also, there is no reason to implement an extensive backlog in the first place. It's far better for a system at 105% load to drop one in ten attempts than to have an infinitely growing queue.
If the user record does not exist, you should still perform a check against a precomputed bcrypt hash that uses the same work factor as a real one, but throw away the results. This will incur the same performance penalty as a real check but won't leak information. This assumes that your login doesn't leak info already from saying "Sorry, that user does not exist" but instead says "Invalid username and/or password".
With regards to attempts to brute force a password, it's going to be slow with bcrypt and a sufficiently high work factor. However, you can improve this by implementing IP address banning. More than X failed attempts within Y minutes gets you a Z minute timeout period which you can easily implement in your database.
To prevent distributed attacks on a single account, if an account has more than M failed attempts within N minutes suspend the account and send the account owner an email with a reactivation link. The reactivation link must be designed to be immune to the above attacks as well. When clicked, the system should temporarily ignore the account suspension status from their IP address only, subject to normal failed attempt banning.
Password reset links should similarly not reveal whether or not an account exists, but send an email to the requested address anyways. For example, the email could read "A password reset was requested for your email address [[email protected]] but an account with that email address does not exist in our system". IP-based banning should apply to the password reset email as well to prevent someone flooding everyone on the internet with emails from your system. If someone has to try more than 10 email addresses to find their own account, their IP address should get banned and they should be prompted to call or email customer service for assistance.
Corrections and/or other login tips appreciated!