Timing Attacks in Ruby

A few days ago I read an article I saw on Twitter discussing how analysing the time it takes your application to do stuff can lead to the discovery of security flaws. The actual flaw seems rather obvious once explained, too obvious infact, so I decided to test it out in Ruby. My results are documented below.

So whats the flaw?

One of the important rules of security is to never let anyone know more than they need to about your system. The article focuses on the use of hashes which are used for authentication, called HMACs. These are typically generated in order to sign requests in order to verify their authenticity and integrity.

Hashes are a predefined length, SHA-1 for example returns hashes of 160 bits, or 20 bytes. The human-friendly hexadecimal notation is commonly used for hash representation. Each byte is converted into a hexadecimal nibble (two characters) which returns a string of 40 characters. Rather than converting hashes back into binary format, comparison methods typically compare them character by character.

def are_equal?(str1, str2)
    # not valid if lengths are different
    return false unless str1.length == str2.length
    
    # check each character
    str1.each_index |i|
     return false unless str1[i] == str2[i]
    end
    
    # yay
    true
  end

For a hash of, say, 20 bytes (SHA1), this will take less than 200μs on modern computers. The flaw is that the execution time varies depending on how many characters match. Let’s say the initial length check (line 3) takes 10μs, and then each comparison (line 7) takes 5μs. For matching hashes the function will take 110μs to execute, however for hashes where only the first 5 characters match it will take 35μs to execute. Now we have the information.

Meh, so what?

Information is power, or so they say. In this case it is a security breach. By generating a group of hashes where the first byte is 0 – 255, one of them will take slightly longer to execute. By taking a large number of samples, it is possible to reliably use this method to work out what the value of the byte is. This can then be done for the rest of the bytes in the hash. After this you are in.

In my experimentation with this in Ruby I found that taking 500 samples, and then taking the median execution time for each sample gave accurate results. According to the original article it is even possible to reliably do this over the internet, assuming the number of samples is high enough. I am not entirely convinced by this however, as the latency produced by the internet can vary wildly by hundreds of milliseconds for each request. I don’t see how it is possibly to tell a difference of a few microseconds in this case.

$ ping www.google.com
PING www.l.google.com (216.239.59.104): 56 data bytes
64 bytes from 216.239.59.104: icmp_seq=0 ttl=53 time=275.568 ms
64 bytes from 216.239.59.104: icmp_seq=2 ttl=53 time=177.634 ms
64 bytes from 216.239.59.104: icmp_seq=3 ttl=53 time=270.396 ms
64 bytes from 216.239.59.104: icmp_seq=4 ttl=53 time=343.046 ms
64 bytes from 216.239.59.104: icmp_seq=5 ttl=53 time=206.094 ms
64 bytes from 216.239.59.104: icmp_seq=6 ttl=53 time=275.967 ms
64 bytes from 216.239.59.104: icmp_seq=7 ttl=53 time=348.216 ms
64 bytes from 216.239.59.104: icmp_seq=8 ttl=53 time=226.734 ms
64 bytes from 216.239.59.104: icmp_seq=9 ttl=53 time=288.783 ms
64 bytes from 216.239.59.104: icmp_seq=10 ttl=53 time=342.466 ms
^C
--- www.l.google.com ping statistics ---
10 packets transmitted, 10 packets received, 0% packet loss
round-trip min/avg/max/stddev = 177.634/275.490/348.216/55.956 ms

Back to Ruby

Fortunately, Ruby does things differently. The string comparison method in Ruby is not time dependent. I decided to look in the source after I only got successful results when implementing the comparison method above. In Ruby the lexicographical string comparison method is called (str1 <==> str2, which returns an integer), and then this is checked to see whether it is 0, and the strings match. An example of this is shown below:

def are_equal?(str1, str2)
    # not valid if lengths are different
    return false unless str1.length == str2.length
    
    # check each character
    result = 0
    str1.each_index |i|
     result |= str1[i] ^ str2[i]
    end
    
    # check equal
    return result == 0
  end

This sets a flag in result whenever the characters don’t match, and at the end this is checked to ensure no flags have been set and the strings match.

So if you ever need to implement your own comparison function (why I don’t know), make sure that you aren’t revealing information that can lead to a security flaw. If you use a prebuilt on make sure it is up to scratch.

Bed time now I think as it is 3:41am. Drinking a can of Relentless isn’t a good idea before going to bed.