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
endIt 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
endIt'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
Written by Luca Mearelli
Related protips
7 Responses
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.
It's in O(n), where n is the hash length. So it's in linear time, isn't it?
@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 :)
@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
@luca OK then :).
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@khalsah oops, I stand corrected, you are perfectly right. I've updated my protip to reflect your suggestion, thanks!
