7

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.

O. Jones
  • 103,626
  • 17
  • 118
  • 172
John Weisz
  • 30,137
  • 13
  • 89
  • 132
  • Depends on the attacker, but not likely. You're much more vulnerable to [SQL Injection!](http://stackoverflow.com/questions/60174/how-can-i-prevent-sql-injection-in-php). You should use parameterised queries. – Jay Blanchard Nov 19 '14 at 22:32
  • The query that is currently in development is more complex than this, of course; I just gave a short and brief example to illustrate this question. – John Weisz Nov 19 '14 at 22:33

3 Answers3

11

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.

Ilmari Karonen
  • 49,047
  • 9
  • 93
  • 153
  • As of 2014.11.20, both submitted answers are high quality and offer well described solutions. I'm picking this as the accepted one because in my opinion, it provides more details for future reference and highlights some of the additional possible dangers of timing attacks - even though the other post is a more direct answer to the question. – John Weisz Nov 20 '14 at 12:10
1

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.

O. Jones
  • 103,626
  • 17
  • 118
  • 172
  • 5
    This is actually not a secure way to handle timing attacks. It makes it more inconvenient to perform a timing attack but it doesn't actually solve the issue. http://security.stackexchange.com/questions/96489/can-i-prevent-timing-attacks-with-random-delays http://stackoverflow.com/questions/28395665/could-a-random-sleep-prevent-timing-attacks/28406531#28406531 – d0nut Feb 16 '16 at 01:03
0

one solution to prevent timing attacks in PHP in general would be

/**
 * execute callback function in constant-time,
 * or throw an exception if callback was too slow
 *
 * @param callable $cb
 * @param float $target_time_seconds
 * @throws \LogicException if the callback was too slow
 * @return whatever $cb returns.
 */
function execute_in_constant_time(callable $cb, float $target_time_seconds = 0.01)
{
    $start_time = microtime(true);
    $ret = ($cb)();
    $success = time_sleep_until($start_time + $target_time_seconds);
    if ($success) {
        return $ret;
    }
    // dammit!
    $time_used = microtime(true) - $start_time;
    throw new \LogicException("callback function was too slow! time expired! target_time_seconds: {$target_time_seconds} actual time used: {$time_used}");
}

with that you can do

$rows = execute_in_constant_time(function () use ($db, $password_hash, $username) {
    return $db->query("SELECT * FROM `users` WHERE `password`='$password_hash' AND `username`='$username';")->fetchAll();
}, 0.01);
  • from there you can tune 0.01 for 10 milliseconds, or 0.1 for 100 milliseconds, and so on, and the function will use exactly that long, no matter how many bytes were correct or incorrect... unless you chose a too small time to execute, in which case you get a LogicException...
hanshenrik
  • 19,904
  • 4
  • 43
  • 89