Is comparing strings in MySQL vulnerable to timing attacks?

Question

I'm deploying a classic hashing protection for user passwords. The submitted password on login is salted, hashed, and then compared to the already stored hash in the database.

But instead of using a PHP function call to compare the now hashed user input and the stored hash, the comparison is done in database - more precisely, using a WHERE clause (NOTE: the salt is already known for various reasons at the time this comparison begins, but the password is not).

Since usernames are unique, the following query effectively tells if the username + password pair is a match or not:

SELECT * FROM `users` WHERE `password`='$password_hash' AND `username`='$username';

Is this approach vulnerable to timing attacks?

---

EDIT: SQL injection is not a concern, it is taken care of.

Answer 1

Yes, the string comparison (and/or index lookup) may, in principle, leak how many identical leading bytes the password hash stored in the database and the one computed from the entered password share.

In principle, an attacker could use this to iteratively learn a prefix of the password hash, byte by byte: first they find a hash that shares its first byte with the hash in the database, then one that shares its first two bytes, and so on.

No, this will almost certainly not matter.

Why? Well, for a number of reasons:

1. A timing attack may allow the attacker to learn a part of the user's password hash. A well-designed password hashing scheme (using a salt and key stretching), however, should remain secure (assuming, of course, that the passwords themselves are not easily guessable) even if the attacker knows the entire password hash. Thus, even if the timing attack succeeds, the passwords themselves will be safe.

2. To carry out the attack, the attacker must submit passwords whose hash value they know. The hash value depends on the salt. Thus, unless the attacker somehow already knows the salt, this attack is not possible.

   (It is true that, in most security analyses of password hashing schemes, the salt is assumed to be public information. However, this is only because such analyses assume the worst-case scenario mentioned above, where the attacker has already obtained a copy of the entire user database, salts and hashes and all. If the attacker doesn't yet know the hash, there's no reason to assume they would know the salt.)

3. Even if the attacker knows the salt, in order to carry out the iterative attack described above, they'll need to generate passwords that hash to a value with a desired prefix. For any secure hash function, the only practical way to do this is by trial an error, which means that the time needed to do so scales exponentially with the length of the prefix.

   What this means in practice is that, in order to extract sufficiently many bits of the hash to be able to carry out an offline brute force attack against it (which need not be all of them; just more than the effective amount of entropy in the password), the attacker needs to carry out about as much computation as required to crack the password itself. For a well designed password hashing scheme, and a securely chosen password, this is not feasible.

4. What the iterative attack can give the attacker, in principle, is the ability to do most of the brute force computation locally at their end, while only submitting a fairly small number of passwords to your system. However, even this only holds if they receive detailed and reliable timing information back from each password submitted. In practice, real timing attacks are extremely inefficient, and require many (often thousands or millions) queries to yield any useful information at all. This will very likely cancel out any potential performance advantage that the timing attack could provide for the attacker.

   This point is amplified you use a proper key-stretching password hashing scheme, since such schemes are deliberately designed to be slow. Thus, the string comparison in the database will likely take a negligible amount of time compared to hashing the password in the first place, and any timing variations caused by it will thus be lost in the noise.

Answer 2

If you put a compound index on (username, password) in your users table and change the query from SELECT * to SELECT COUNT(*) AS matching_user_count, you will go a long way towards making queries which match and queries which don't take roughly the same amount of time. If your hashes are all the same length that will help too.

If all these queries take the same amount of time it will make timing attacks much harder. Obviously you can do more to defeat timing attacks by sleeping a pseudorandom amount of time on each query. Try this:

SELECT COUNT(*) AS matching_user_count, SLEEP(RAND()*0.20) AS junk
  FROM `users` 
 WHERE `password`='$password_hash'
   AND `username`='$username'

It'll add a random time between 0 and 0.2 secs to each query. That randomness will dominate the near-constant time to carry out the indexed WHERE clause.