Does stretching a hash increase a denial-of-service (DoS) risk and does brute-force protection mitigates that?

Question

Disclaimer: I noticed several questions on this site but none really answer this two questions directly. Therefor I do not consider this duplicate.

Personally I really like the article called Some words on Password use, salting and stretching from Michael Anders explaining why stretching is important.

For the legitimate user it doesn't make a difference whether the program needs a microsecond to verify the password or a tenth of a second. He will not notice the difference. For the attacker it may be the difference between 1 day for an exhaustive search or the 100 thousand fold time of 300 years.

I wonder if extensive stretching increases the risk of a denial-of-service (DoS) caused by resource exhaustion. It's likely easier to use more server resources when doing multiple login-attempts (not for the purpose of logging in, brute-forcing but for the purpose of causing a DoS).

Secondly, would a simple brute-force protection that prevents the password from reaching the password check function (including hashing and stretching) after an X amount of failed login attempts, possibly prevent this kind of DoS (by resource exhaustion)?

Answer 1

1) In a sense, yes, since checking the password against a stretched hash will take more CPU time. But you should have some rate-limiting in any case to prevent brute-force guessing passwords, and while doing that, you can take into account the DoS potential. Also, login attempts will not be the only way to (try and) DoS something, you might get excessive load from other requests too, or just receive excessive amounts of network traffic, preventing legitimate requests from reaching you.

I think making it harder to crack the passwords in case of a leaked password database is worth the cost, but of course it is a trade-off. You have to take into account the expected amount of (valid) logins, and that the system can handle them. With millions of users, the stretching might start to take its toll.

2) Yes, if you rate-limit connection attempts and start denying them outright at some point, it would be useless work to run the hash fully for a login that is going to be denied. Though, returning a failure immediately will reveal via timing the fact that the password wasn't even checked.