Prevent denial of service attacks against slow hashing functions?

Question

I've been thinking about bcrypt recently, and what I wonder is if there's a way to deal with the inherent (D)DoS problems with slow hashing functions. Namely, if I set up bcrypt so my machine takes 100 ms to hash a password, then it only takes 10 password attempts per second to make my server unresponsive. I could reduce the difficulty, but the faster I make it for me, the faster I make it for an attacker. I could ban anyone who tries too many passwords, but botnets are everywhere these days.

Are there any common solutions to this problem?

I was thinking there's probably strategies where you make the client do something complicated but easily verifiable, and check the result before checking the password, but it has a couple problems:

• Is there a way to do it in plain HTML (without JavaScript).
• What would the "something complicated" be? RSA encryption gave me the idea of generating two primes, multiplying them together, and asking the client what the original primes were, but I suspect the "generating two primes" step wouldn't be particularly fast either.

Another thing I had considered was caching bcrypt results in memory, so attacks against one user don't cause problems, but what if I have too many users to reasonably do that?

I'm mainly thinking of using this in the context of a username/password login box on a website, but any method of dealing with this could likely be done in JavaScript if there's nothing better.

EDIT:

The idea of somehow rate limiting requests is useful, but it's not the kind of solution I had in mind. It makes DDoS attacks more expensive (because you need more IP addresses), but it doesn't solve the fundamental problem that the server is doing significantly more work than the attacker(s).

An example of what I'm thinking of is how using a salted password makes rainbow tables worse than a straightforward brute-force attack. So if you're using salt, you don't have to worry about rainbow tables at all, since there's better attacks. What I want is a way to make attacking my login page no better (or worse) than just hitting random URLs.

Answer 1

One possibility is to consider using client puzzles. The basic idea is to force the client to do a significant amount of work, and prove it has done so, before you will accept a username/password pair and try to validate it.

Here is an overview of the approach. The server generates a random puzzle, and sends the puzzle to the client. The server generates the puzzle in a way that it can predict reasonably well how much effort will be required to solve the puzzle (e.g., 100ms of computation). The client solves the puzzle, and then sends the solution along with the user's username and password.

In a web setting, this would probably be implemented with Javascript: the login page would contain the Javascript code to solve the puzzle and the puzzle description. A legitimate user's web browser would run the Javascript on the page, which would solve the puzzle and include the solution in the form along with the username and password.

This makes it harder for an attacker to DOS the server. For instance, if it takes the server 100ms of computation to check the validity of the user's password, and if the server chooses a puzzle that takes 100ms to solve, then an attacker will have to do at least as much work as the server. If you turn up the dial to select puzzles that will take 200ms to solve, then now the attacker has to do twice as much work as you, to DOS you. Thus, this does not prevent DOS, but it makes it harder and requires the attacker to invest more resources -- which may reduce the risk somewhat.

Here's a very simple example of how to construct a puzzle. The description of the puzzle is a random 128-bit number R (chosen by the server, and sent to the client). The goal is to find a number n such that SHA256(R, n) is zero in its low 20 bits. The client can loop over values of n (test whether n=0 is a solution, test whether n=1 is a solution, test whether n=2 is a solution, ...) until the client finds a solution. On average, you should expect this to take about 2²⁰ trials. If the client can perform about ten million hashes per second, then 2²⁰ trials should take about one-tenth of a second (100ms). Once the client finds a solution, the client can send n to the server. Note that the server can quickly verify that n is a valid solution to the puzzle (it takes only one hash, not a million hashes). This creates the required assymetry, where the server can very quickly generate new puzzles and verify claimed puzzle solutions, but where it takes longer to solve the puzzle, and where the server can control how long puzzle-solving takes with a fair degree of accuracy. This is just one example of a puzzle construction; there has been a great deal of research on this problem, and there are better constructions.

You might be especially interested in kaPoW, which implements this idea for the web context.

The main limitation is that this is not going to be secure against dedicated attack. A serious attacker can just acquire a botnet of a few hundred machines (this is not that expensive) and DOS you, and now you're completely hosed. Client puzzles can't stop that kind of attack: they can only stop a relatively low-grade attack. However, stopping DOS is in general very difficult.

A secondary limitation has to do with the broad variability of computational power of clients that might access your website. A puzzle that a high-end desktop can solve in 100ms might take a mobile device 1000ms to solve (I'm making up numbers here). If you choose parameters that make the puzzle relatively easy to solve on the lowest-power device that is ever likely to access your website, then you may find that security against high-end desktops is degraded. Also, it seems plausible that a C program (run by an attacker) might be able to solve the puzzle much faster than the Javascript (run by legitimate users), which would further exacerbate the gap between how fast an attacker can solve puzzles vs. how fast the slowest legitimate client can solve them. This gap degrades security.

A tertiary limitation is that client puzzles require the client to use Javascript, to log in. However this might be acceptable.

A variant of this idea is for the server to monitor itself and check whether it is under heavy load. Under normal conditions, skip the puzzle. However, if the server seems to be under DOS attack, then start requiring login attempts to come with a puzzle solution. This mitigates some of the disadvantages of the client puzzle approach, but still is far from perfect, and still cannot withstand a serious DOS attack.

I describe this potential solution, in case you interested, but I don't really recommend it for most sites. For most sites, the risk of DOS is relatively low, and if it does occur, you can deal with it at the time. For that reason, my guess is that it probably isn't worth your time or energy to implement these kinds of defenses. If you've got that much extra time and energy to spare, you might be better off spending it building new features or making your site better.

Answer 2

Reducing the number of guesses per minute is the way to go, but implementing it as a sleep in your code will still consume precious resources and lead to a denial-of-service.

Instead, you want the client to wait, not the server. So log the time the attempt was made, add X seconds to that time, and don't attempt further authentications from that user/IP until after that time has expired. (Edit, added:) That is, if an authentication attempt is received, reject it with an error message without even checking the password.

You'll want to put some corresponding javascript in the login page so that the user won't submit a new login attempt until that timeout has expired (plus a safety margin). That keeps users from seeing unnecessary error messages and getting confused.

Increasing the timeout with each attempt is also a good idea. This helps to keep from inconveniencing "normal" users, while making a brute-force attack practically impossible.

Answer 3

Another approach you could consider is to use CAPTCHAs to make this kind of DOS attack harder. The basic idea is to require the user to solve a CAPTCHA when they want to log in, and require them to present a correct solution to the CAPTCHA before you will validate their password.

This is unfriendly to users, so if you want to consider this, I would recommend a variant. Have your server monitor its own load, so it can detect when it is under attack. (For instance, measure how much of your CPU time you are spending on bcrypt-hashing passwords; or just measure the load on the server.) Under normal conditions, do nothing special: users just need to present a username and password, as usual, with no CAPTCHA anywhere.

When you detect you might be under attack, enter self-protection mode. In this mode, the server should send a CAPTCHA in the login page, asking users to enter in their username, enter their password, and enter the solution to the CAPTCHA. When the user clicks submit, the server should first validate the solution to the CAPTCHA before using bcrypt to verify the user's password. If the user didn't solve the CAPTCHA properly, don't even try to verify their password.

This raises the bar against DOS attacks, because now an attacker cannot simply send 10 invalid username/password pairs per second: the attacker will have to also solve 10 CAPTCHAs per second to DOS the server. As a result, the trivial DOS attack no longer succeeds. Also, this provides DOS resistance, while ensuring that in most situations users never need to see a CAPTCHA: users only need to solve CAPTCHAs when the server is under attack.

Of course, you can combine this scheme with rate-limiting by IP address and by username, if you wish.

That said, the security of this scheme is far from perfect. There are underground markets used by attackers that exist to automate the process of solving CAPTCHAs for you, at a fee. These services provide an API that their customers can use to submit a CAPTCHA and get back the solution. The going rate is something like a few dollars per thousand CAPTCHAs solved. Based upon this, we can compute what it would cost to mount a successful DOS attack against this scheme, by using these CAPTCHA-solving services. An attacker would need to solve 864,000 CAPTCHAs per day (10 per second) to take down your server, which would cost a few thousand dollars per day of downtime using existing markets. This is an upper bound on the cost of mounting a successful DOS attack. However, it almost certainly greatly over-estimates the cost of DOSing your server, as there will almost certainly be other, far more economical ways of mounting a DOS attack on your server.

Anyway, I share this potential solution based upon use of CAPTCHAs, but I don't really recommend it for most sites. For most sites, the risk of DOS is relatively low, and if it does occur, you can deal with it at the time. For that reason, my guess is that it probably isn't worth your time or energy to implement these kinds of defenses. If you've got that much extra time and energy to spare, you might be better off spending it building new features or making your site better.

Currently, DDOS is the simplest and cheapest way to take down your server. I have seen estimates for the cost of DDOS attack in the range of $100 per day, though it may cost significantly more to defeat a larger, better-resourced target.

Protecting your server against DOS attack is not easy; the economics of it are not working in your favor. Perhaps one of the best things you can do is arrange for your site to have a lot of excess capacity, and to make sure it can scale up as traffic grows (perhaps using a cloud service with VMs and network capacity on demand). The advantage of this approach is that it is beneficial even if you never come under DOS attack, because it will help you avoid getting overwhelmed by a flood of legitimate users -- e.g., if you get Slashdotted.

Answer 4

What you could do is to force the request to sleep for an exponential time on every failed login.

For the first login hold for one second; second failed 2 seconds; third failed 4 seconds, etc. Or longer or shorter depending on what your server can handle. It doesn't hurt normal users who mistype their password, but it makes anyone attempting a brute force wait a very long time after only a few failures.

Answer 5

Basically the first step to make a risk evaluation:

• what are the potential attack scenarios ?
• how much resources are available to the attacker ?
• is a DOS the worst case scenario ?
• what is the probability versus business cost of each scenario ?

Depending on the answers above the measures can vary - for example:

• a simple scheme implemented on the HTML level
  won't defend against anything but the most basic form of attack
• a simple "increase the time to next password validation with every failed attempt" and return always false in the meantime
  this slows down any attack considerably but won't hold up against a saturated network
• handle the password validation on some other machine(s) which can be easily scaled up on case-by-case-basis
  this help keep the site responsive by "outsourcing" the "heavy lifting"
• implement some defenses on the network level (usually done one or more hops before the request reaches your server)
  this can help in cases where the attacker has lots of bandwidth capable of satuarating your network...

One thing to be kept in mind:

Even the best defenses will not hold when confronted with an attacker with unilimited bandwidth and IPs...

Answer 6

My general view on DoS is: all existing systems are fundamentally vulnerable to DoS. It is just a question of degree. If you have a high-profile site that is at high risk for DoS, it may be worth worrying about these vectors. If you just run an ordinary everyday site, I wouldn't bother. In most sectors, DOS attacks are rare, so they're probably not worth spending time and energy to defend against. (There are of course exceptions, but I'm talking about most sites here.)

The great thing about DoS attacks is that, if they occur, they are readily detectable.

Edit (2/25): It sounds like you really want to do what you can against computational DOS attacks, despite the limitations I've articulated. Given that, please see my other answers for some ways to make computational DOS attacks harder. They're far from perfect, and personally I'm sticking with my bottom line recommendation (namely: implementing these defenses most likely isn't the best use of your time), but there they are, in case you feel differently.

Answer 7

My simple recommendation, and what I have done to mitigate DoS attacks on slow password hashing, is to use a password strength calculation score as primary validation method.

So for a user login example: I get the user record by email. Then first check if the strength score match against the plain text password (which is obviously fast, just a couple functions). And only start password hashing functions with a score match, else bail with a failed request.

And to avoid exposing the strength of the password in the database, you can find some sort of basic one way calculation algorithm to mask the real password strength score.