Why is the SlowEquals function important to compar

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

If there is no slowEquals.

Let’s consider the compute compares two chararters using 2 seconds(more faster in true compute, but a large amount of testing could work), and we use 1234554321 as the password. The attacker uses 0000000000 to attempt. Because we don’t use slowEquals function, the comparison takes only 2 seconds because of 0!=1, so when attacker knows the “2 seconds”, he will change the ‘0’ to another one until using “1000000000” then the server takes 4 seconds.

Answer 2

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 3

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.