4

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.

8
  • 1
    This thing that you posted has far worse issues than timing attaks: ist a straight away injection vulnerability. Read about prepared statements
    – marstato
    Jun 18, 2017 at 17:21
  • mysqli_real_escape_string or php prepared statements does not fully protect against sql injections. I can find 5 ways to bypass prepared statements online. The best protection against sql injections is a firewall, and I use mod_security and Comodo Firewall.
    – desbest
    Jun 18, 2017 at 17:27
  • Five, you say? Go earn a lot of money then because all the infosec people i know, know only one loophole that is unlikely to ever occur (obscure encoding for php and db server).
    – marstato
    Jun 18, 2017 at 17:31
  • Anyways: php has its flaws but sure is more secure than that plain concatenation you are doing. Where do you host this?
    – marstato
    Jun 18, 2017 at 17:32
  • 2
    "The best protection against sql injections is a firewall, and I use mod_security and Comodo Firewall." A firewall will do nothing to protect your from SQL-injection. Don't stick your head in the sand, use prepared statements.
    – Jacco
    Jun 18, 2017 at 18:15

4 Answers 4

5

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.

3
  • In the initial query, WHERE token = ?, wouldn't this depend on the specific indexing rule? The best case for an attacker is a BTREE index in a sparse DB. The worst case for an attacker is HASH index - because this theoretically is like testing hash(input) == hash(stored). But I'm quite unsure about the specific hash used -- eg a cryptographically secure index might be good, but it's not the kind of performant hash that a DBMS wants. But even if it's a performant hash... maybe that's enough to frustrate timing attacks?
    – Tim Otten
    Mar 4, 2021 at 22:04
  • @TimOtten Without knowing of hash indexes in databases specifically, I'm pretty sure that this hash won't be a cryptographically secure one. You can likely find collisions similar to what people did for HashDoS, or even if not, it's not an hmac so you can hash the values client-side as well and know what the database looked up, thereby narrowing the search range (e.g. you can learn that the hash is somewhere between c76.. and c7a..). From there you can start to do offline brute-force, at least in case of passwords (secure session tokens could be different iff a cryptographic hash() is used).
    – Luc
    Mar 5, 2021 at 10:49
  • They're good questions though, I (or someone) should look into this properly if I have time at some point!
    – Luc
    Mar 5, 2021 at 10:50
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
10
  • I have brute force protection on my authentication/website so there can only be 50 failed logins for an account per day, if it gets to 50, the user can't login for the rest of the day. I store passwords with bcrypt so the password is by default salted and bcrypt cannot be broken. To authenticate a user to a website, something on the user's computer has to match what's on the server, so ALL cookies are attacker controlled as anyone can steal cookies from someone's computer to login as someone else. I don't store plaintext passwords, yet the bcrypt password is in my database.
    – desbest
    Jun 18, 2017 at 17:36
  • If I store the permlogin token in the database and as a cookie, what if someone steals the permlogin cookie? It doesn't make a difference if I store a permlogin token or a password. Also someone can do a timing attack on the permlogin cookie, which is what my question is asking about.
    – desbest
    Jun 18, 2017 at 17:37
  • Also, should I have a random millisecond delay when validating the cookies? I think it's a good idea, but Stack Overflow said it was a bad idea.
    – desbest
    Jun 18, 2017 at 17:43
  • 1
    @desbest, Only 50 failed logins per account per day you say? Well, that sounds like a perfect denial of service attack vector. Also, most attackers try a set of the most common passwords, against a wide set of usernames. So, limiting your failed logins per account, won't add that much protection, while opening up another attack vector.
    – Jacco
    Jun 18, 2017 at 18:18
  • 1
    @desbest: One last thing; if you still want to discuss, lets move to chat then. The time it takes to brute-force any hash depends on the entropy of the plaintext. If a users uses a low entropy password (such as p4ssw0rd) your bcrypt hash wont stand a chance against a determined attack (see dictionary attacks). A truly random 256bit permlogin token has an entropy of 256 bits. Thats hard to reach with a password, even with generated ones.
    – marstato
    Jun 18, 2017 at 19:33
2

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.

2
  • The key is that a bcrypt operation is constant-time. The first-half of the token is open to a timing-attack, but that's OK because the information is useless without the second half.
    – phayes
    Aug 4, 2019 at 16:43
  • I've updated the comment to better explain that how the first-half (open to a timing attack) and the second half (not open to a timing attack) work together to make the entire system secure. I'm finding the downvotes baffling since this is the correct answer.
    – phayes
    Aug 4, 2019 at 16:58
0

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

5
  • Sorry but I can't cycle through all my users in order to authenticate a user, as it will make my code slow. It isn't designed for growth. If I have 40,000 users, cycling through all the users on every webpage load will slow down the website.
    – desbest
    Jun 18, 2017 at 20:33
  • If you use a token you only need to do it on logon. Generally speaking verifying the hash is a lot slower and to properly avoid a timing attack on logon you should ensure that you spend the same amount of time checking the hash whether or not the user exists
    – ste-fu
    Jun 18, 2017 at 22:54
  • How do I only need to do it on login? When the user navigates to a members only page, I need to verify the hash to see if they have permission to view the page. I need to verify the hash on every page.
    – desbest
    Jun 19, 2017 at 9:04
  • If you use a token ie if you store a single token eg a uuid generated in logon.This can be stored in a table. Existence of the token does not leak an actual user id, and the table can be cleared at suitable intervals without requiring a password change.
    – ste-fu
    Jun 19, 2017 at 9:56
  • The only way to securely use a single token to identify a user is if the token is HMAC'd before sending it to the user, and the HMAC is verified before allowing a query against the database. This prevents a timing attack by only allowing the user to query using an identifier than is provably correct (the attacker cant get perform queries to extract timing information). Letting a user authenticate with a single-token where that token hasn't been verified before doing the query opens up the system to a timing attack and is insecure.
    – phayes
    Aug 4, 2019 at 17:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .