Faster string comparison in Ruby

Question

I am trying to compare the authentication token provided by the user with the authentication token stored on my server.

The most obvious way to do this is to simply use == , but this potentially creates a temporary attack.

To mitigate this, I wrote this safe 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 it is very slow: it adds 180 ms to the 60-80 ms page load.

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

EDIT: I use the following script to compare different solutions, fwiw - https://gist.github.com/daxtens/a3a59f163f08f9b447bb - it shows how == can help out early, information leakage and how secure_compare is several orders of magnitude slower than == .

EDIT 2: To be completely clear, I am trying to achieve the secure_compare(secret, untrusted_input) function, where the time taken to complete it depends entirely on untrusted_input , not 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 time dependency, but it is too slow.

Answer 1

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

The source is on GitHub ( https://github.com/daxtens/fast_secure_compare ), but its essence is the following very simple C.

 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 make him talk to Ruby.

This is much faster than the original pure Ruby, and somewhat faster (and much easier) than hashing. I edited the rehearsals for short. This is on a 2008 MacBook. You can replicate this using 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

Something like this might work (this is constant time versus pass )

 def check(x, pass) ((x.length > pass.length ? x : pass) .take(x.length) .zip(x) .reduce(true) { |r, (y, z)| r & (y == z) }) & (pass.length == x.length) end 

On my computer, it takes 0.5 ms for a long password 1000 characters long.

Answer 3

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

Obviously, “comparing constant time strings” is theoretically impossible when the input size is unlimited. You were almost aware of this when you used 'The sly fox' * 1000 as test input, rather than 'abc' .

I wrote this safe comparison function

I smell bad here; why don't you just use existing authentication algorithms / implementations that have stood the test of time?

EDIT: I use the following script to compare different solutions

FYI: since module initialization, etc. may affect the result, it’s nice to use Benchmark.bmbm .

Anyway, 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 

In fact, computing the hash on the fly potentially consolates time information to the attacker. You must save a pair of the original, eh, auth token and its hash value. The addition of salt grains 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.

Performance update

On my Atom D510 (1.6 GHz) machine, hashing 1 MB of 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"