Countermeasure to timing attack against SQL SELECT of hash token

Question

We want to create a web API, where users receive hash tokens (196-bit) via email as part of their purchase of our software license and can then use this token to activate their trial software version to the "full" software. The web API is responsible to receive the hash token and confirm or reject the user from upgrading to full.

Leaving out lots of details about this, it seems that receiving a hash token in such a way and then just checking with SQL SELECT if this token is in the database exposes a timing attack. The attacker can attempt to guess individual bytes from the tokens in the database by measuring the response time.

How to guard against this? In general and specifically in Ruby on Rails.

Ideas so far:

• Achieve constant time for the look-ups (how?)
• Add random noise (how much?)
• Split token in key part (32-bit) and remainder. Perform look-up only on key and a secure compare on the rest

Answer 1

My working solution using a second indexed token_key field, which is the leading 8 bytes of the token_hash:

def valid_token(given_token_hash)

  # don't look for hash, because of SQL timing attacks
  token_key = given_token_hash[0,8]
  token = ActivationToken.find_by_token_key(token_key)

  # Even if not found in database, we should pretend to take some time
  token_hash = token.nil? ? "123e4567-e89b-12d3-a456-426655440000" : token.token_hash

  if (!secure_compare(token_hash, given_token_hash))
    return nil
  end

  return token
end

Answer 2

One solution that came out when devise removed token_authentication for this reason was to perform the look up based on a public criteria, such as email, and then use a constant time comparison on the hash token found by the query and the one sent in the params. Check the gist on the "safe" version.

https://gist.github.com/josevalim/fb706b1e933ef01e4fb6#file-2_safe_token_authentication-rb

I believe adding random noise would be futile from a statistical viewpoint, with enough data the randomness should flatten out. Would love love to hear more detail on the internal comparison mechanism of SQL comprisons.