string_compare.md

String equality is something we check all the time when writing code. Are all_systems == "nominal"? Most of the time using your programming language's default equality operator is fine. However when performing equality checks in sensitive areas of your app, like authentication, you need to be extra careful.

What is a Timing Attack?

Timing attacks are a way of learning information about something by measuring the time it takes to respond to different queries. When a response is faster or slower based on what you send it, the algorithm is leaking information about what two values are being compared.

Don't do this!

if "password123" == "hunter2"
  # The user is logged in! :D
else
  # The user got the password wrong

Most equality algorithms are designed to return true or false as fast as possible. So you take two strings, start at the beginning, and go one by one looking at each character in that string. As soon as you find a mismatch, you return false.

Knowing this, an attacker can deduce how much they got right. If it returns super duper fast, then they got it all wrong. If it starts taking a little bit longer to return false, they've got the first character right, and the second character wrong. By doing enough queries enough times they can statistically deduce what the value is.

Here's an example of an equality algorithm which steps through each character one at a time, and returns as soon as it fails. This revealing the time it took to do its comparison.

"hunter2" == "password123" # False. 51μs
 F
"hunter2" == "obama"       # False. 50μs
 F
"hunter2" == "havana"      # False. 73μs
 TF
"hunter2" == "humana"      # False. 90μs
 TTF
...
"hunter2" == "hunter1"     # False. 170μs
 TTTTTTF
"hunter2" == "hunter2"     # True.  190μs
 TTTTTTT

It works across the fickle internet too - in Codahale's classic blog post on this issue he quotes research from 2009 which can "reliably distinguish remote timing differences as low as 20µs ... with only hundreds or possibly thousands of measurements".

Time-Constant String Comparison

The solution to this problem is to compare the two strings in such a way that, no matter what you compare, it takes the same (constant) amount of time to compare them.

To do this successfully you must:

1. Compare all of the characters before returning true or false. - returning early will leak information
2. Compare strings of equal length - if one string is longer or shorter, you'll return early and leak information about string length

An implementation for Ruby on Rails

If you use Ruby on Rails, you can get time-constant string comparison using ActiveSupport::SecurityUtils.secure_compare. Let's take a look at how it has been written.

Check out this StackOverflow answer for examples in PHP, Java, C/C++, and Python.

require 'digest'

module ActiveSupport
  module SecurityUtils

    # Constant time string comparison.
    #
    # The values compared should be of fixed length, such as strings
    # that have already been processed by HMAC. This should not be used
    # on variable length plaintext strings because it could leak length info
    # via timing attacks.
    def secure_compare(a, b)
      return false unless a.bytesize == b.bytesize

      l = a.unpack "C#{a.bytesize}"

      res = 0
      b.each_byte { |byte| res |= byte ^ l.shift }
      res == 0
    end

  end
end

Note that you need to hash the strings yourself first, to get equal length strings! Otherwise that first return statement will leak information by returning fast when you get the length wrong. (Rails wrote a method which does that for you called variable_size_secure_compare, but they haven't made it public 😭).

In secure_compare it will loop over an Array of bytes. Here's how it gets the arrays:

> a = "hunter2"
> l = a.unpack "C#{a.bytesize}"
 => [104, 117, 110, 116, 101, 114, 50]

> b = "punter3"
> b.each_byte.to_a
 => [112, 117, 110, 116, 101, 114, 51]

Using the XOR operator if two of those bytes mismatch, res (which starts as 0) will become non-zero:

> res = 0
> res |= 112 ^ 104
 => 24
> res |= 117 ^ 117
 => 24

After iterating through all of the values, we'll know whether res is still 0. And you've avoided leaking information about how much of the password was wrong! 👍

Using secure_compare in your Rails app

Let's say you have a ApiController which authenticates access in a really simple way. First we hash the two values, so that the strings have equal length. Then we compare them.

class ApiController < ApplicationController
  REAL_KEY = "secret"   # P.S. don't actually keep secrets in the code

  def authenticate
    password_correct = ActiveSupport::SecurityUtils.secure_compare(
      ::Digest::SHA256.hexdigest(REAL_KEY),
      ::Digest::SHA256.hexdigest(params[:api_key].to_s)
    )
    unless password_correct
      head :unauthorized
    end
  end

Where do I need to use time-constant string comparison in my web app?

Hopefully you have rate limiting in place, and use community-vetted libraries. But even so it'd be worth checking some common places you should have time-constant string comparison:

• When checking password equality (including Basic HTTP Auth!)
• When checking "forgot my password" email tokens
• If you use "security questions" for additional security
• API key validation, or HMAC validation
• OAuth state parameter checks (probably low risk if you're doing it right, but it can't hurt!)

Timing attacks are a tricky problem, and string comparison is only one place where they show up. Another common process susceptible to timing attacks is login forms and password reset forms. Attackers can figure out if someone uses your service by guessing their email address and submitting it. If your page takes 200ms to send a "reset your password" email when the account exists, and 50ms to respond when the account doesn't exist, you're leaking information!

Perhaps you've thought of some common places which are vulnerable to this attack. Let us know in the comments below!

Securing your apps and end users is hard, and it's something ThisData is striving to improve. I'd love for you to check us out!