An (over)simplified explanation of timing attacks and how to protect yourself
As a developer with an interest in security; every once in a while I learn of a new vulnerability that is so insidious and so clever it makes my hair stand on end. Today it’s timing attacks.
This post oversimplifies many concepts. If security is an issue for your app (and if you handle client information, then it should be!), please educate yourself on the implications of different security vulnerabilities and attack vectors.
You can learn more about timing attacks in the following links:
https://codahale.com/a-lesson-in-timing-attacks/
https://thisdata.com/blog/timing-attacks-against-string-comparison/
Say you have an API that clients can use to get information. To make sure the information only goes to the intended parties you require your clients to authenticate themselves using an API key, which is a random string they send along with each request. When a request comes in, you compare the API key they sent with the key you have on file, if the keys match, you know the client is who they say they are.
Timing attacks are a clever workaround for hackers with patience to get this private info without a key. How do they do it? Using math and statistics, and some exact measurements.
You see, at the heart of the function that compares the API key that was sent with the API key on file is the algorithm used to compare the 2 strings. That algorithm usually looks something like this (in pseudo-code):
Go through the string being sent in and check the first character, if it matches the first character of the string on file check the next character, if that one matches go on to the next one, etc. until you get to the last character. If the last character matches return ‘true’, if any of the characters checked don’t match return ‘false’.
The vulnerability is in the last line. Let’s say the API keys are 15 characters long, the attacker will send a few hundred requests using a few hundred strings that look like a00000000000000, b00000000000000, c00000000000000, etc. sending a few hundred of each. They will then very carefully analyze how long it takes the server to reject their request. Using statistics, they will find that one of the versions of their string takes on average just a few milliseconds longer to reject. The reason for the slight delay is simple; most of the strings were rejected as soon as the first character was compared while one string (let’s say it was g00000000000000) passed the first letter and was only rejected when it got to the second letter. The hackers now know that the first letter of the API key is the letter g.
The hackers will now repeat the process using the strings ga0000000000000, gb0000000000000, gc0000000000000, etc. until they find the next letter in the key. They will keep repeating this process until they figure out all 15 characters of the API key and the attacker can now impersonate a legitimate client and gain access to any information available to that client.
The way around this attack is relatively simple; replace the algorithm that checks if the strings are equal with one that takes the same amount of time no matter which characters don’t match.
One implementation (in pseudo-code) is as follows:
let indicator = 0
for (each char in the string) {
if (char is not equal to the corresponding char in the string on file) {
change the value of indicator by one
}
}
return true if the value of indicator is 0 //i.e. it was never changed due to a mismatched character
otherwise return false
As you can see, the function above goes through the entire string every time and only returns true or false at the end. It will, therefore, take the same amount of time no matter what string is passed in.
For those of you using Rails, ActiveRecord actually has a built-in method for this:
ActiveSupport::SecurityUtils.secure_compare(string1, string2)
This method incorporates the functionality above to compare both strings in constant time.
This article has been cross-posted from my blog Coding Hassid.
You can read more about my coding journey there, or by following me on Twitter @yechielk
Latest comments (6)
This is a good explanation,
But never ever authenticate a client based directly on a string send in plaintext... If I want to impersonate the app like that, I don't need such an attack. Just sniff the traffic of the app. Even easier if there is a web client.
So if that attack poses a threat for your system, please fix the authentication protocol, not only the string compare.
What about DB queries ? is this working as well for methods which queries a DB for username and password ?
I tried to find how MySQL does string comparison but I couldn't find an exact answer...
I don't know the technical answer with 100% certainty, but I learned about timing attacks while working on a Rails app that uses ActiveRecord to talk to MySQL database so I assume it applies to DB queries as well.
This made me laugh.
It's like hacking is 1:1 lock picking in digital.
On the one side you have all the math and crypto pros and on the other some people with very practical down to earth solutions.
Someone mentioned the lock-picking analogy to me on Twitter! That's exactly it! :)
thanks,