Why is the SlowEquals function important to compare hashed passwords?

Question

I recently read an article on password hashing and salting wherein it was explained (under "How does the SlowEquals code work?") that a SlowEquals function must be used to compare the hash of the password entered to the hash of the password in the database.

As I understand it the SlowEquals function is used because it uses XOR instead of == and as a result will check every character in the both strings rather than failing on the first non-matching characters.

There are two things I don't understand:

1. Why will the XOR continue to check the string after a fail condition is reached.
2. If the main idea is to not give the attacker any useful information while trying to crack a password, wouldn't a sleep() function with a randomly generated time do the trick just fine?

Answer 1

The fact that the algorithm compares all bytes of the two hashes is simply a result of the implementation, and is not related to the use of XOR (i.e. one could write an algorithm that compares all bytes without breaking at the first mismatch even using ==). The use of XOR is intended to avoid introducing branching instructions in the loop body, which might reveal details as to the number of matching bytes as a result of the CPU's branch-prediction (though whether that is an issue would depend somewhat on the particular implementation, and the instructions it's compiled to).

The use of a random sleep() to mask timing of a hash check that returns at the first mismatch doesn't really work as it may still be possible to distinguish match from mismatch at a given point by taking more samples. For the sake of argument if we assume we sleep for a random number of milliseconds uniformly distributed in the range [0..100], and a match at a certain position takes 2ms and a mismatch at that position takes just 1ms (as the algorithm exits early). With sufficient sampling we could distinguish the match and mismatch cases as we would observe responses ranging from [1..101]ms in the mismatch case, but [2..102]ms in the match case (assuming we can time responses perfectly). Of course real-world observations would suffer jitter and other sources of randomness, but a bias would still potentially be observed.

Then of course there is simply the practical consideration - why introduce sleeps, randoms etc. when relatively minor modifications should result in it running in constant time, and eliminating timing attacks?

Answer 2

TL;DR - It is not important to use SlowEquals when comparing password hashes.

If you were trying to verify a non-hashed secret, then using "SlowEquals" would be valuable in thwarting a timing attack.

However, if you're using a proper password hash that is sufficiently computationally intensive (PBKDF2, 50k+ iterations) it just plain does not matter. Why? Because password hashing "assumes breach". Even if the attacker steals/knows the hash AND the salt, it is too time consuming to find a plaintext password that hashes to that value and thus the password is still protected. That is the whole point of cryptographic hashes, they're unusable even if stolen. Sure, someone could use a timing attack to figure out the hash, but it doesn't matter, because they still won't be able to figure out the password.

Coupled with locking functionality, where the account becomes locked after X invalid attempts (3-10, take your pick), timing attacks on hashed passwords goes from worthless to undoubtedly worthless.