Feasibility of time-based database brute-force attacks on websites

Question

I recently learned that there is an attack that utilizes the fact that when brute-forcing a compared string (e.g. hash from a password or token) in a database the query fails a few nanoseconds earlier if the beginning of the string is different than if the end is different and the previous characters are correct. If the attacker manages to get exact isolated access to the query time, the tries necessary to find the correct string significantly decreases in comparison to standard brute-forcing.

Is it even possible to isolate the query time on a remote webserver given there are constant visits of other people and running background processes?

If this is in fact a threat, what are best-practice solutions to secure webservers? Things I thought of:

• Hash the input strings in order to obfuscate the character sequence.
• Add some kind of minimum response time to related queries. Probably bad idea because it may open up DOS attack-vectors and might not be feasible with typical PHP/MySQL-scenarios due to poor multithreading support.

Answer 1

How feasible the attack is depends on how much noise you have to remove to get to the signal you want to have. If you can do a lot of tests against the website you should be able to increase the level of signal which might be enough to filter out enough noise to make this kind of attack feasible. But details depend a lot on the actual setup of the system you want to abuse.

To fight this kind of attack you use operations which are deliberately constructed so that their behavior does not depend on the input. Such algorithms are an important part of practical cryptography, not only for simple string comparison but also for hashing and encryption. And timing is not the only side channel but you have also need to look at power consumption and even weirder side channels like radiation.

And you probably not only need to have a look at timing attacks against string comparison. Your web application might leak other data which makes brute force easier, like behaving differently if the username exists or not. Please also note that simply hashing before comparison might not help if the hash function you use is not resistant against timing attacks itself.

I think the best approach if to have some serious rate limiting for the number of login attempts. This not only makes brute force much harder but also will probably make timing attacks infeasible because their is too much noise around and the signal can not be amplified due to the rate limiting.

Answer 2

While this is certainly a very interesting idea, in practise I think it's pretty much impossible to exploit. We're on a fiber connection here, and even the response time direct to our ISP is all over the place:

If the difference you're looking for is a few nanoseconds, you'd literally have to already have access to the local machine to even begin to hope to actually detect a reliable pattern. And if the attacker has access to your local networking environment, you've got much bigger problems to worry about.

Answer 3

It's very hard or impossible to exploit this vulnerability over the network as Nic Barker already stated.

I want to mention that it's best practice to define a lockout threshold for authentication mechanisms. For example: If a client authentication fails for the 7th time, further authentication for this client is blocked for at least 5 minutes. If a lockout is not feasible, a CAPTCHA (for human interfaces) or a crypto challenge could be added to the authentication process.