19

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.

Brendan Long
  • 2,898
  • 1
  • 19
  • 27

7 Answers7

17

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 220 trials. If the client can perform about ten million hashes per second, then 220 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.

D.W.
  • 98,860
  • 33
  • 271
  • 588
  • 2
    very interesting topic generally. i bookmarked several related links to study about client puzzles/PoW. but seems to me that a C program can solve the puzzle much faster than javascript, and that seems another deficiency for web usage. – H M Apr 30 '13 at 17:57
  • 1
    @HM, good point. I've added this to my answer. Thank you! – D.W. Apr 30 '13 at 18:53
  • @D.W., doesn't "puzzle solving" all involves brute-force mechanisms regardless? If so, then it seems more than just plausible (it seems to be certain in fact) that a 500ms javascript puzzle would be totally eaten up by a single non-distributed attacker using a C program. – Pacerier Mar 15 '14 at 11:13
  • @Pacerier, yes. As I wrote in my answer: " 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." – D.W. Mar 15 '14 at 16:20
  • @D.W. I don't see how this merely just *degrades* security. If a 500ms javascript puzzle could be solved in C within 5 ms, is there even any security at all? – Pacerier Mar 17 '14 at 18:55
  • 2
    @Pacerier, yes. The purpose of a client puzzle is to increase the cost of a denial-of-service attack. So, it's not a black-and-white situation; it's a matter of *how much* we can increase the cost to an attacker. Here the cost to an attacker is based upon the amount of computation power the attacker must mount. If the attacker has to do 5ms of computation per request, that limits the attacker to at most 200 requests per second per bot, which might be a step forward compared to the situation if there is no client puzzle. Is it enough? That'll depend, but it might be better than nothing. – D.W. Mar 17 '14 at 21:18
  • Issues of balancing could be resolved, I would think, by having the the machine give out harder puzzles when it seems to be under attack by an entity that can solve them too quickly. That would force legitimate users's machines to do more work to log in, but users would at least still be able to log in, even if slowly. – supercat Aug 22 '14 at 21:50
8

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.

tylerl
  • 82,665
  • 26
  • 149
  • 230
  • Brute-force bots won't run javascript. I would probably send them 503 responses until they wait long enough. There may be a more appropriate response code. – Ladadadada Feb 24 '12 at 07:24
  • 1
    @Ladadadada This is a two-part solution. The javascript is only there to keep "normal" users from seeing the server-generated error message. The second paragraph above is where the actual security happens. – tylerl Feb 24 '12 at 07:30
  • @Ladadadada: brute-force bots probably won't back off if they get a 5xx either, though that's not a bad idea. If it ends up causing resource starvation, you can always trigger blocking via iptables. A little overkill for most instances, but I've worked with clients where that was necessary. – tylerl Feb 24 '12 at 07:36
  • 4
    Caution: I don't see this defense as likely to work. Rejecting by IP is easy to bypass with a botnet, so that each request comes from a different IP. Rejecting by user doesn't work; the attacker can just choose a different username each time. Javascript on the error page returned by the server does nothing; the attacker can simply ignore it (since the attacker controls the client and what it does with the response from the server). Bottom line: It will still be the case that a trickle of requests (say, 10 per second) can take down your server. Attack certainly isn't "practically impossible". – D.W. Feb 24 '12 at 20:32
  • This does push back the danger a little bit, since a small attack (less than 10 IP addresses) wouldn't work, it doesn't help the underlying problem, that the attacker only needs a small number of tiny requests to take down the site, they just need more IP addresses. – Brendan Long Feb 24 '12 at 22:09
7

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.

D.W.
  • 98,860
  • 33
  • 271
  • 588
  • Don't these guys get caught advertising their DDOS services so publicly? – Pacerier Mar 15 '14 at 11:20
  • @Pacerier, caught how? They're just someong posting on a forum, or something like that. How are you going to catch them? How are you going to identify them? And then when you discover they live in Bulgaria (or something), what are you going to do? It's no easier to catch them than to catch any other kind of online criminal. It's probably sometimes doable given enough law enforcement effort and cross-country competition, but they're small fry. – D.W. Mar 15 '14 at 16:18
  • Surely they can be tracked if they are using their own IPs... or does these guys all use Tor? – Pacerier Mar 19 '14 at 06:36
  • @Pacerier, 1) Usually they don't use their own IP addresses. They use an anonymizer, or a proxy, or route through a compromised machine, or use Tor, or some combination of the above. 2) The forums may be hosted overseas, so it's typically not entirely trivial for law enforcement to get the IP addresses of people posting to those forums. We're now getting quite far afield from the question. This is not a discussion forum, so I'm not going to continue any further discussion of this topic here. For more about why it is hard to prosecute criminals, try searching, or ask a separate question. – D.W. Mar 19 '14 at 06:38
3

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.

Steve
  • 15,215
  • 3
  • 38
  • 66
  • Bear in mind that apache, PHP-FPM, and many other PHP implementations block the worker process until the response is sent, so while sleeping uses less CPU than computation, you're still consuming limited resources and DOSing yourself. – tylerl Feb 24 '12 at 06:37
  • 2
    I don't understand why you think this is helpful. If the server sleeps after each failed login, with exponentially increasing sleep times, you've just created a self-inflicted DOS. The attacker just initiates 40 failed attempts, and now your server is sleeping until the heat-death of the universe, rendering your web service unavailable to all of your users. – D.W. Feb 24 '12 at 20:34
  • @D.W. - You can do asynchronous waits, which are close-enough-to-free. A NodeJS server would have no problem with servicing other requires while the wait is in progress. – Brendan Long Feb 24 '12 at 22:04
  • 1
    @Brendan, I don't understand what benefit an asynchronous wait would have. The attacker can send an invalid username/password pair, and then immediately ignore the response (e.g., close the connection; or fork off the process) and continue sending another invalid username/password pair immediately. Basically, my objection is this: having the server wait or sleep after a failed login does not constrain the attacker's behavior or ability to send more invalid username/password pairs immediately, so it doesn't seem to add any real security. – D.W. Feb 24 '12 at 23:52
  • 1
    Put another way, this approach is only effective against the least determined attacker: Somebody who has the ability to produce repeated requests from only one IP. – Steven Lu Jun 09 '13 at 03:14
  • @D.W. If the attacker aim at DOSing, then yes. But if they're online cracking, then such a delay could make sense, couldn't it? Together with blocking of the IP during the period. This won't help in case of IP spoofing, but then a simple Retry-After could make the attack much less efficient (as the response can be generated orders of magnitude faster and for a spoofed-request there'll be no retry). – maaartinus Jun 16 '17 at 19:33
2

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.

Community
  • 1
D.W.
  • 98,860
  • 33
  • 271
  • 588
  • 3
    The interesting DoS attacks are those that exhaust the server's resources while consuming minimal bandwidth, because these can be run with a small number of attacking clients. If the attacker has to saturate the network to DoS your server, you are already one step further, because now the attacker will have to spend considerable bandwidth. (And this kind of DoS is the kind you can hardly defend against, unless you can block the attack at the network level.) – tdammers Feb 24 '12 at 11:29
  • 1
    I'm not concerned about a standard DoS attack, I'm more worried about cases where a very small number of targeted requests could take down the entire site. – Brendan Long Feb 24 '12 at 20:25
  • @Brendan, I'm sympathetic to that viewpoint, though I gotta warn you: if you're really worried about that threat model, I don't think any of the defenses I've seen proposed so far will actually stop that kind of attack. – D.W. Feb 24 '12 at 20:29
2

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...

Yahia
  • 121
  • 2
  • 2
    These are all useful in a general case, but I'm more interested in the specific case where I have I resource that needs to be available, but requires significantly more server work than client work. Obviously I can't protect against a determined attacker with more resources than me, but I'd like to at least defend against a couple people running `wget`. – Brendan Long Feb 24 '12 at 22:02
  • @BrendanLong Indeed, these 200 ms per password verification are so terrible, that a single user could saturate one core using the login form alone. It has already happend, that legitimate users brought a site pretty down by trying to login at about the same time (as a reaction to an event published on the site). – maaartinus Jun 16 '17 at 19:43
0

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.

hexalys
  • 185
  • 1
  • 6
  • 3
    Since knowing the strength score lets you discard passwords without testing them, this solution weakens the password's protection. I'm not convinced that a "basic encoding to mask the real password strength score" would help here, since if the server can decode it, then presumably an attacker can too (which is why we use iterated hash functions in the first place). – Brendan Long Apr 12 '15 at 18:35
  • I revised my answer for precision. I didn't want to get into implementation details. But think of a one way calc like a crc32 from a derivated key that cannot be converted back into a score. Even if a dozen possible scores from a weak one way key are extracted. The possible combinations for identifying the password composition are fairly meaningless. Esp. if the password strength algorithm rely on many interchangeable factors. Average length of people's passwords is already predictable. And such minor weakening can also be adjusted for by increasing the hashing cost factor for weak passwords. – hexalys Apr 13 '15 at 03:36
  • Someone stealing your database could repeat your computation an find what you store for weak passwords. Then they could concentrate on weak passwords they identified this way. – maaartinus Jun 16 '17 at 19:51
  • @maaartinus As I said, the crc I generate is independent from the score. It says nothing useful about the weakness of the password. You can't revert that to a score. – hexalys Jun 16 '17 at 20:04