ludhva
Last Updated: February 25, 2016
·
2.809K
· luca

Constant time hash comparison

Comparing two hashes (e.g. for password verification or when handling an HMAC or session id) may leak informations on the source data being hashed.

Using a trivial string comparison to check the hash leaves
one vulnerable to timing attacks. See also this post.

This little function is something I've used to (try to) verify in a constant time that two hashes are the same

def still_bad_time_constant_compare(string_A, string_B)
  result = true; 
  string_A.split("").each_with_index do |c,idx|
    result &&= (string_B[idx].upcase==c.upcase)
  end
  result
end

It simply compares all the characters in the two strings without short circuiting the operation on the first difference.

As explained by @khalsah in the comments below the &&= operator still short circuits the comparison so this is still vulnerable.

This is a correct way to do it:

def time_constant_compare(string_A, string_B)
  a = string_A.upcase 
  b = string_B.upcase
  check = a.bytesize ^ b.bytesize
  a.bytes.zip(b.bytes) { |x, y| check |= x ^ y.to_i }
  check == 0
end

It's basically the solution by @khalsah belowwith the added upcasing of the strings (which I needed)

N.B. constant time here is not meant in the big-O sense (the algorithm is O(n) on the size of the strings beng compared), but it means that the algorithm will take the same time to compare any two strings of a given length

7 Responses
Add your response

4444

Correct me if I'm wrong, but since you're comparing hashes it only gives you a timing attack to find the hash. However if you are using a salt (which you should be) you don't know either of the values being compared, making it very hard to get any information back out at all. Unless I'm missing something this seems to be more trouble than it's worth.

over 1 year ago ·
4489

It's in O(n), where n is the hash length. So it's in linear time, isn't it?

over 1 year ago ·
4490

@khalsah I think you are correct when strictly speaking of passwords hashed with salt but there are cases where this can be useful e.g. when dealing with cookies / sessions ids. The page I linked contained a link to this post: http://codahale.com/a-lesson-in-timing-attacks/ which explains better than I might do the problem :)

over 1 year ago ·
4491

@nubbel I should have clarified this: in this context what's constant is it's the time required to do the comparison between any two of all the possible strings. The computational complexity is O(n) as you wrote

over 1 year ago ·
4493

@luca OK then :).

over 1 year ago ·
4509

Bad news, testing this I found that your code actually makes the situation worse! I believe the problem is that the &&= operator still short circuits the comparison, so you're still vulnerable to timing attacks. Additionally since the ruby code is much slower than the native comparison the timing difference is far more pronounced.

The solution given by: http://stackednotion.com/blog/2009/09/09/timing-attacks-in-ruby/ avoids all but one comparison operation at the end by using bitwise operations.

My code (tested in ruby 2, doesn't do upcase)

def safe_compare a, b
  check = a.bytesize ^ b.bytesize
  a.bytes.zip(b.bytes) { |x, y| check |= x ^ y.to_i }
  check == 0
end
over 1 year ago ·
4521

@khalsah oops, I stand corrected, you are perfectly right. I've updated my protip to reflect your suggestion, thanks!

over 1 year ago ·