Does bcrypt compare the hashes in "length-constant" time?

Question

I saw this function slowEquals() while reading Salted Password Hashing - Doing it Right, which uses a byte-level xor comparison to avoid timing attacks. I was wondering whether this is what Bcrypt also does to avoid timing attacks. I use Openwall PHPass which has its own CheckPassword() method which doesn’t seem to xor. How does it avoid timing attack?

Answer 1

The cool thing about hashing is that even a one-bit change to the input will completely change the output. Keep this in your mind! How does that relate to your question? Well, bear with me a little.

In the vast majority of cases, access to the salt implies access to the password hash. This is especially true in the case of Bcrypt since almost all implementations store the salt, the hash, and the iteration count in the same string with delimiters. Also keep this in your mind!

Since the comparison is happening on the password's hash, and any change to the input password will completely change resulting hash (remember?), the yield of the timing attack will be information about the hash itself at best. However, that's only true if the attacker has access to the salt. Remember what we said? An access to the salt implies access to the hash. This means that the timing attack in this case is irrelevant.

If the attacker doesn't have access to the salt, then the timing attack will give (practically speaking) zero information. Thus it will give the attacker zero advantage.

Bottom line: For hashing schemes such as Bcrypt, Scrypt, etc., timing attacks are irrelevant. Using comparisons such as == and === isn't a problem. Having that said, using constant time comparison is a good practice as part of a defence-in-depth policy. In fact, many Bcrypt implementations already used timing-safe comparison just in case (timingsafe_bcmp.c in py-bcrypt, for example).

Update:

There is indeed a way to extract some information about the hash without knowledge of any of its components (salt, iterations, or plaintext value). It's described in a comment by Oasiscircle

This can still leak parts of the hash using the early-exit byte comparison. Example: Attacker computes tons of hashes and stores them looking for a hash that starts with 0x00. Upon finding a plaintext with that value, send that plaintext, listen for timing on response. Do this for 255 more values until one value takes slightly longer. That's the first byte value of the hash created from the plaintext.

Having that said, I still hold the same opinion expressed in the original answer about the irrelevance of the timing attack when using a hashing scheme such as Bcrypt. While there's indeed a possibility of such attack, it's extremely infeasible. The computation and storage requirements for such attack are enormous, and they keep grown exponentially with every bit discovered from the hash.

Answer 2

bcrypt doesn't compare hashes at all, bcrypt just hashes. If you compare the result with a naïve $storedHash === $hash, then you're (theoretically) susceptible to timing attacks. This has been raised in a Github ticket for PHPass, with the response being:

I've looked into this previously, and all my research indicates that this is unnecessary when dealing with proper password hashing techniques. Even the article you link states, "Using one-way hashing should defeat this because it’s very hard to work backwards from timing leaks when the attacker derived input keeps changing (hashes to a different digest each time a byte changes in the original plaintext input)."

I'll be happy to look into this again, but these issues are related more to accidental data disclosure than brute-force password cracking when hashes are in use.

So PHPass does not explicitly try to prevent such timing attacks, and the author does not deem the issue to be a problem.

The "official" bcrypt implementation for password hashing in PHP is password_hash and password_verify, the latter of which does implement a constant-time xor comparison. There's a userland implementation for PHP versions below 5.5.