Faster constant-time string comparison in Ruby

Question

I'm trying to compare an authentication token supplied by a user with an authentication token stored on my server.

The most obvious way to do this is just to use ==, but that potentially creates a timing attack.

To mitigate that I wrote this secure comparison function:

# string comparison that leaks no information about the strings.
# loosely based on https://github.com/rack/rack/blob/master/lib/rack/utils.rb
# and http://security.stackexchange.com/questions/49849/timing-safe-string-comparison-avoiding-length-leak
def secure_compare(a, b)
  l = a.unpack("C*")

  i = 0
  r |= a.length - b.length # fail if the lengths are different
  b.each_byte do |v|
    r |= v ^ l[i]
    i = (i + 1) % a.length # make sure we compare on all bytes of b, even if a is shorter.
  end
  r == 0
end

The only problem is that this is really slow: it adds 180ms to a 60-80ms page load.

Is there a faster way to do constant time string comparisons? Is there a more standardised way to do it?

EDIT: I'm using the following script to benchmark different solutions, fwiw - https://gist.github.com/daxtens/a3a59f163f08f9b447bb - it shows how == can bail out early, leaking information, and how secure_compare is several orders of magnitude slower than ==.

EDIT 2: Just to be perfectly clear, what I am trying to achieve is a function secure_compare(secret, untrusted_input), where the time taken to execute depends entirely on untrusted_input, and not on secret. I also want this function to be no more than a couple of orders of magnitude worse than ==. The provided function has the desired timing dependency, but it's way too slow.

Answer 1

To make things fast while keeping them simple, I've reimplemented the function in C, and made it available as a gem.

The source is on GitHub (https://github.com/daxtens/fast_secure_compare), but the crux of it is the following very simple C routine.

int secure_compare_bytes(const unsigned char * secret, unsigned int secret_len, 
                     const unsigned char * input, unsigned int input_len) {

    int input_pos;
    int secret_pos = 0;
    int result = secret_len - input_len;
    // make sure our time isn't dependent on secret_len, and only dependent
    // on input_len
    for (input_pos = 0; input_pos < input_len; input_pos++) {
        result |= input[input_pos] ^ secret[secret_pos];
        secret_pos = (secret_pos + 1) % secret_len;
    }

    return result;
}

```

There's also a bit of FFI glue to get it to talk to Ruby.

It's much faster than the original pure Ruby, and is somewhat faster (and much simpler) than hashing. I have edited out rehearsals for brevity. This is on a 2008 MacBook. You can replicate this with timing.rb in the demo directory.

==== Long text ====
                                         user     system      total        real
==, early fail                       0.000000   0.000000   0.000000 (  0.000028)
==, late fail                        0.000000   0.000000   0.000000 (  0.000710)
Pure Ruby secure_compare, 'early'    1.730000   0.040000   1.770000 (  1.777258)
Pure Ruby secure_compare, 'late'     1.730000   0.050000   1.780000 (  1.774144)
C-based FastSecureCompare, 'early'   0.040000   0.000000   0.040000 (  0.047612)
C-based FastSecureCompare, 'late'    0.040000   0.000000   0.040000 (  0.045767)
SHA512-then-==, 'early'              0.050000   0.000000   0.050000 (  0.048569)
SHA512-then-==, 'late'               0.050000   0.000000   0.050000 (  0.046100)

==== Short text ====
                                         user     system      total        real
==, early fail                       0.000000   0.000000   0.000000 (  0.000028)
==, late fail                        0.000000   0.000000   0.000000 (  0.000031)
Pure Ruby secure_compare, 'early'    0.010000   0.000000   0.010000 (  0.010552)
Pure Ruby secure_compare, 'late'     0.010000   0.000000   0.010000 (  0.010805)
C-based FastSecureCompare, 'early'   0.000000   0.000000   0.000000 (  0.000556)
C-based FastSecureCompare, 'late'    0.000000   0.000000   0.000000 (  0.000516)
SHA512-then-==, 'early'              0.000000   0.000000   0.000000 (  0.000780)
SHA512-then-==, 'late'               0.000000   0.000000   0.000000 (  0.000812)

Answer 2

secure_compare (constant time string comparison in Rails)

---

If you are using Rails (or a standalone ActiveSupport) you can consider using ActiveSupport::SecurityUtils.secure_compare for the constant time string comparison.

Here is an example:

ActiveSupport::SecurityUtils.secure_compare('foo', 'bar')

Also if you are interested in on how it works, please have a look at the source.

Answer 3

Is there a faster way to do constant time string comparisons?

It is obvious that "constant time string comparison" is theoretically impossible when the input size is unlimited. You were almost aware of that when you used 'The sly fox' * 1000 as your test input rather than 'abc'.

I wrote this secure comparison function

I feel bad smell here; why don't you just use existing authentication algorithms/implementations which endured the trial of time?

EDIT: I'm using the following script to benchmark different solutions

FYI: because module initialization etc might impact the result, it's nice to use Benchmark.bmbm.

Anyways how do you like this way?

require 'digest/sha2'

def secure_compare_kai(a, b)
    return Digest::SHA512.digest(a) == Digest::SHA512.digest(b) && a == b
end

Actually calculating the hash on the fly potentially leaks timing information to the attacker. You should store the pair of the original, eh, auth token and its hash value. Adding a grain of salt is also recommended:

• https://crackstation.net/hashing-security.htm

You might want to insert something like sleep(Random.rand(10e-3..30e-3)) for your peace of mind.

Update on performance

On my Atom D510 (1.6 GHz) machine, hashing a 1 MB input with Digest::SHA512 took only 10 ms.

irb(main):009:0> x = "A" * 10**3; y = "A" * 10**6; 0
=> 0                   

irb(main):011:0> Benchmark.bmbm{|b| b.report("1 KB"){ Digest::SHA512.digest(x) }; b.report("1 MB"){ Digest::SHA512.digest(y) } }
Rehearsal ----------------------------------------
1 KB   0.000000   0.000000   0.000000 (  0.000049)
1 MB   0.010000   0.000000   0.010000 (  0.009677)
------------------------------- total: 0.010000sec

           user     system      total        real
1 KB   0.000000   0.000000   0.000000 (  0.000079)
1 MB   0.010000   0.000000   0.010000 (  0.009731)

irb(main):012:0> RUBY_VERSION
=> "2.1.2"