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 (126.96.36.199): 56 data bytes 64 bytes from 188.8.131.52: icmp_seq=0 ttl=53 time=275.568 ms 64 bytes from 184.108.40.206: icmp_seq=2 ttl=53 time=177.634 ms 64 bytes from 220.127.116.11: icmp_seq=3 ttl=53 time=270.396 ms 64 bytes from 18.104.22.168: icmp_seq=4 ttl=53 time=343.046 ms 64 bytes from 22.214.171.124: icmp_seq=5 ttl=53 time=206.094 ms 64 bytes from 126.96.36.199: icmp_seq=6 ttl=53 time=275.967 ms 64 bytes from 188.8.131.52: icmp_seq=7 ttl=53 time=348.216 ms 64 bytes from 184.108.40.206: icmp_seq=8 ttl=53 time=226.734 ms 64 bytes from 220.127.116.11: icmp_seq=9 ttl=53 time=288.783 ms 64 bytes from 18.104.22.168: 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.