Is sql where queries in authentication prone to timing attacks, if one or no database rows are returned?

Question

Say I have this code for authentication.

   $me = mysql_query("SELECT * from users WHERE id='$_COOKIE[userid]' && password ='$_COOKIE[pass]'") or die (mysql_error());
   $me = mysql_fetch_array($me);

To authenticate a user to a website, something on the user's computer has to match what's on the server (this question is not about preventing cookie stealing as all websites can have cookies stolen regardless), but is there a way to do use sql where to check if it matches in the database without it being prone to a timing attack?

What if someone modifies their cookies to a different userid and password to try to find out someone else's password using a timing attack? If $me produces 0 results instead of 1 result, does that change the average time it takes to run the query?

If yes, how should I change my code, because I can't figure it out? Should I add a random delay to the code above, and does it make a difference as I read it wouldn't.

Answer 1

One way to protect against timing attacks when querying an indexed database field, would be to hash the value server-side. It's similar to how an attacker can't login if they obtained hashes of a password because the server still applies the hash before checking the database.

The original code (from the question above) has a number of issues, as marstato's answer pointed out, so let's start with this code instead:

$token = $_COOKIE['token'];
$db->query("SELECT COUNT(*) FROM sessions WHERE token = ?", $token);

The attacker can indeed incrementally find a valid token. It is typically hard or impossible, but in theory, this works. The attacker would query "A" and the server would ask the database for "A". Then they try "B" and the server asks the database for "B". If "A" was faster, they now try "AA" and "AB". If that is slower, they might try "BA" and "BB", etc. There's a lot more to it, but to recap the general idea of a timing attack, that's how it works.

To fix the issue, you could do this:

$secret = 'qJHcsgkED0egeuljhsZr'; // randomly generated
$hashed_token = hash_hmac('sha256', $_COOKIE['token'], $secret);
$db->query("SELECT COUNT(*) FROM sessions WHERE hashed_token = ?", $hashed_token);

Let's try the attack again: the attacker tries "A" and the server queries the database for "a661024ef...". The attacker tries "B" and the server queries the database for "5407624cb...". The timings are equal (or at least random) because neither will exist and it will never lead the attacker to a valid token.

This is, of course, dependent on the $secret remaining secret. It would be best practice to change this regularly so that an old employee cannot know the secret and apply the attack, but this does mean that you have to also change all values in the database. If the database can do HMAC, you could work around that by doing something like this:

$secure_rnd = openssl_random_pseudo_bytes(16);
$randomized_token = hash_hmac('sha256', $_COOKIE['token'], $secure_rnd);
$db->query("SELECT COUNT(*) FROM sessions WHERE hmac(token, '$secure_rnd') = ?", $randomized_token);

Security-wise, this is the best approach for three reasons:

• While it is equivalent in speed to a non-indexed field, it prevents a future database admin from accidentally indexing the field. Typically, one would index a field when it is used for lookups. This leads to a timing attack, but how would you tell your future database administrator? Better have code in place such that it does not matter whether the field is indexed
• If the field were merely non-indexed, there may still be an attack: the database will go through each row and compare the values. Going through each row and comparing the first character is O(n), but if the database compares more characters (because more than zero characters match), it will take slightly longer, so an attacker could (again, theoretically) observe this slower response and learn that they guessed more than one character correct of any token. Using a $secret or $secure_rnd is not vulnerable to that.
• It does not depend on a static $secret that may be known to old sysadmins.

The downside is that it is an O(n) slow query.

A hybrid approach, to take advantage of an index while avoiding a static $secret, might be to use a $secret that is changed daily. During the transition period every night, the application server could first try today's secret and, as a fallback, yesterday's secret. Since your tokens as well as the hashing method should be secure (otherwise you have bigger problems), looking for two values should never lead to collisions with other tokens. Once every database record is updated, it can stop querying for the old $secret. The cron job that updates the database can write the secret(s) and upgrade status to a config file.

---

That said, I have never heard of anyone using a timing attack like this. Comparing passwords in a language like PHP, yes, but not with a database query. Most session token systems I know work in this theoretically-insecure way and yet they never seem to get hacked. That doesn't mean it's impossible, and especially if it seems 100% possible in theory, someone will probably make it work in practice sooner or later. While I'm not sure all this effort is necessary today for a small website, it would be good to protect high-security systems.

Answer 2

Dont worry about a timing attack. The difference between 0 und 1 row is miniscule.

However, there are a number of other issues with the Code you have posted:

• Dont allow an attacker to send enough requests so that they could exploit a timing difference here. Block out people after a small number auf failed authentication attempts
• $_COOKIE is entirely attacker Controlled. You are exposing a SQL injection vulnerability here that any semi-professional pentester will be able to exploit in a matter of minutes
• Do not EVER store the password in plaintext, anywhere. Dont do it in your DB and for sure dont store it in the Cookie where it can easily become visible to the public. Instead, store a permlogin token for each user that is entirely random (see CSPRNG) and large (256bit or more). Use that for cookie-based authentication
• Use a salt for your passwords. Select the user record by id and then compare the passwords. Doing so will also decrease the surface for a timing attack

Answer 3

The correct way to do this is to break the identifying information in half. The first half is what you query against, the second half is the secret that is encrypted with bcrypt (or pbkdf2, scrypt or equivalent).

The key thing to understand is that it's not possible to make a query constant-time in most databases, so you need to work around that fact.

For example, let's say you wanted to create a secure invite-code, where a user can use an invite code to sign-up and create an account, you might structure your invite database table like so:

CREATE TABLE invites (
  id SERIAL,
  token_first_half VARCHAR,
  token_second_half VARCHAR CHECK (pass like '$2$12$%'), -- Must be bcrypt version 2 with strength of 12
)

The user would be given a invite code like XY0F-CD37-HZ5J-KL6P, where XY0F-CD37 is token_first_half and HZ5J-KL6P is token_second_half. You would probably want to use human-readable base32 (https://www.crockford.com/base32.html) to encode these tokens.

When the user provides a token, you would break it in half, and use the first half to query against the database, then verify it by checking the second half with bcrypt (https://en.wikipedia.org/wiki/Bcrypt). Bcrypt will perform this operation in constant-time, which avoids timing attacks.

The important insight here is that the first-half is open to a timing attack, but that is irrelevant, since it's only used a selector to access the bcrypt string, which is what we are actually using.

For your particular example, the first-half would be the username, and the second half would be the password. Please note that the username remains open to a timing attack and this can be used for user enumeration.

If you can't break the token in half for some reason, or can't use bcrypt for performance reasons (for example for handling cookies / session), then you need to prevalidate the secret token using an HMAC. Most web-frameworks have a "secure-cookie" functionality that can be used to get and set HMAC-secured cookies for session management. Only after the HMAC has been validated do you do the database query. This prevents a timing attack by denying the attacker enough queries to obtain timing information.

Answer 4

If you wanted to be sure then you could do

`SELECT * FROM Users`

and then enumerate the entire list in code checking for the password against the entire list. That would be near enough constant time.

My PHP is a bit rusty but something like

$authUser = NULL;
$users = mysql_query("SELECT * from users");
$users = mysql_fetch_array($users);
foreach($users as $user){
    if ($user['id'] = $_COOKIE[userid]' && $user['password']='$_COOKIE[pass]'){
        $authUser = $user;
    }
}

if(is_null($authUser))
     // whatever

However I still think it is a mistake to store the actual password hash in a cookie. It means that it is impossible to revoke a session without changing the password. Any type of session identifier even with a 100 year expiration still allows clearing sessions or changing the expiration without password change