Let's assume CAPTCHA is enabled with account lock out control (after five continuous failed attempts, the account will be locked for 15 min) on a system.
Is brute force still a probable threat?
The protections you describe are good ones that you should consider, but there can still be weaknesses:
it depends on how you define "brute force".
A lockout after X incorrect attempts is great for protecting an account where an attacker is going after a single target.
There's another scenario where the attacker has picked a few common passwords "password, password123, etc." And rather than attacking a single user, they try their 4 common passwords on every account they know of in your system.
User: Jim PW: password, password123, letmein, secret User: Bob PW: password, password123, letmein, secret User: Alice PW: password, password123, letmein, secret
This is more common in scenarios where attackers are looking to harvest credentials for resale on the darknet, or make lateral moves to other services where passwords may have been reused.
I suggest you add something in place to count the rate of overall invalid logins, rather than just on a per account or IP level.
It is a threat in a different sense. If you lock accounts for 15 minutes after 5 unsuccessful attempts, then you've effectively built-in a DoS mechanism.
Assume I don't really want to break in, but I'm fine with just causing havoc, no problem. Just do a few thousand logins per second with random usernames. Hey, I'll not even bother doing the CAPTCHA, who cares. All I want is to fail and lock up.
A better strategy than a fixed amount of time after a fixed number of failures might be quadratic (or exponential) growth. Some AVM routers do that. First login failure, you have 15 second lockout, next failure you have 30, etc etc. This is much less hassle to legitimate users, and much more trouble to attackers.
In order to make DoS harder, you would need a kind of recipe involving the IP address as well as the account name, capping the maximum delay per account-IP pair to a tolerable value. Otherwise, a legitimate user could still be DoSed easily and indefinitively. The exponential growth deals better with the "infinite number of attempts" problem, though.
Actually finding a username-password pair online by brute force is, well, assuming people aren't stupid, practically hopeless. Unluckily, people are stupid, so you cannot assume they won't have one of the top-ten-most-stupid passwords, and you must assume it's doable. So, yes, there is a bit of a threat there, too. In particular because while it may be hard to target one user on one server, on a purely username-based control system, you can target a thousand users on that same server in parallel no problem (each scoring only a single fail!) and you can do that on a thousand servers in parallel. And, it doesn't really cost you anything to keep this script running for weeks (months, years...), retrying every 15-20 minutes.
So, while for the individual account your chances as attacker are very small, as numbers add up to, well, virtually infinity you are bound to hit someone, somewhere, eventually, it's unavoidable. Since otherwise it's trivial to try a thousand users in parallel, it should be clear that you also need to consider IP addresses in your calculation. Even so, it doesn't give 100% protection against a botnet with a few thousand bots, but it sure makes the attack somewhat less effective, requiring more work and management. More work is good.
You cannot win the race once you are a serious target, but the harder you make an attacker's work, the more likely it is the attacker chooses someone else (who's an easier target) to begin with.
It's very much the same thing as locking your front door instead of leaving it wide open. A burglar can easily break your window, and there's finally nothing you can do to prevent someone from entering. But given the choice of an open door at the neighbour's house and having to smash your window, he will likely choose the easier way. Fewer expenses, same profit.
Yes, it is still a threat, because:
Ideas for improving what you've proposed:
15 * 2^nminutes with a cap of 2 hours, where
nis the number of previous lockouts in the past 24 hours (first attempt is a 15 minute lockout, second is 30, third is 60, fourth and subsequent are 120).
There is such a thing as low speed brute force attacks, designed specifically to break into accounts with timeouts or lockouts.
If the attacker can figure out your thresholds (which he can by trial runs), he can write a bot to stay just under that threshold.
Of course, this limits the number of combinations he can try in a given time period, which is why these kinds of attacks often run for months or years and are unlikely to compromise accounts with reasonably long passwords.
So, in combination with a sane password policy (that's a different topic, here I'll just say that complexity != security and length > complexity) and a solid implementation of your described system, you can reduce the probability of a compromise considerably. In most cases, enough that the remaining risk is well within your risk acceptance limit.
Rate limit logins, account locking, etc are good to stop any economically feasible brute force attack against a login screen, but that is not necessarily how the attack is done.
Quite often accounts are compromised because the brute force attack isn't done against the login screen itself (which is limiting) but against a copy of the data. If an attacker can gain access to the data via a compromised server or some other means, the brute force attack is really about downloading the accounts and passwords, and then breaking the encryption on a much more powerful machine.
Brute force does not need to use much "force". Brute force could run for days and be a tiny, but persistent drop after drop after drop. I would consider captcha as a non issue for any determined attacker.
Even with your constrains you implied that these limits only apply to a single account. So if I know there are multiple accounts, I can still automate the process to keep trying.
I wont be able to brute force the whole possible keyspace with your constrains, but I will be able to force the top 1000 passwords per account within very slightly over 2 days.
Given that a list of top-1000 passwords would most likely cover a reasonable percentage of your users, you should be able to gain access to your system quite soon.
So can you defend against it?
Limit the trial per IP? -> Vector to avoid it: Botnets / VPN
So lets add "impossible travel" to the list? (User logs in from Germany and US within a minute)
So how about same IP tries various users?
One thing to consider is the value of the resource you try to protect, and which additional steps you want to take to secure it. Another quite safe addition to the strength of your system is a 2nd factor. But these can cause an additional cost for you, depending on what you use and on how many authentications you need to make. For example as a stand alone Service Azure will charge 1,4 $ per 10 authentications. Or you could use some kind of free service or a "Grid" system with unique data per user.
Is brute force still a probable threat?
"Probable" depends on how tasty a target you are. If you're a desirable target, then yes, they're a threat.
While a timeout with a rate limit and lockout will take care of brute force, since they would only get X tries in Y minutes, it's a huge problem since it allows outside attackers to lock out your users with almost no effort.
In this case you have a choice between threats. You're deciding that in exchange for protecting individual accounts, an attacker can lock out the users. It's a different attack than actually stealing/changing data, but it's still an attack.
A better solution would be to require strong passwords and Two-Factor Authentication and have no lockout.
If you do both of these, your accounts will be reasonably safe and your users won't be locked out.
The vulnerability here is reduced significantly since the attacker will need to steal and crack your password database and 2FA secrets to gain access, but by the time they're in deep enough to do that, they don't actually need the user accounts anymore.
This really all depends on what you're protecting. If it's a Wordpress blog and the users don't get to comment on your latest post, it's not a big deal. If your site contains financial or medical or security records, it's a huge deal.